Given a subset of of the hypercube and an affine transform of it, find the affine map This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some full rank $M\in\mathbb{F}_2^{d\times d}$ and $s\in\mathbb{F}_2^d$.

Given $A$ and $B$ what are the randomized and quantum complexities of finding an $M$ and an $s$ so that $MA + s = B$ (let us assume SETH for the purposes of this post)?

Does this connect to any problems studied in tcs?
From D.W.'s comment, we see that your problem is equivalent to the same problem with $s=0$ (and with $d$ only increased by 1). The resulting problem is precisely the Linear Code Equivalence Problem over $\mathbb{F}_2$, just phrased slightly differently. (Usually CodeEq is phrased as "you have two $d \times n$ generator matrices of linear codes, is there a permutation of the $n$ columns which makes the two generator matrices have the same row-span?" In your case, the action by $GL(d,2)$ is the action which preserves the row-span, and the fact that you are only interested in a set of vectors means you essentially have an action of $S_n$ on the columns.)

Here's what's known about its complexity:


This problem is at least as hard as Graph Isomorphism (essentially goes back to Luks '93 "Permutation groups and polynomial-time computation", see Miyazaki, though it is often cited to Petrank-Roth '97)
As with GI, it is in $\mathsf{NP} \cap \mathsf{coAM} \cap \mathsf{SZK}$, by essentially the same proof as for GI.
It's no harder than Tensor Isomorphism [GQ19]
The best known worst-case upper bound is $2^{O(n)}$ (due to Babai, cf. [BCGQ11])
There is an algorithm by Sendrier 2000 that may work well in practice, depending on what kinds of codes you are looking at.