= Solution
List the known distinct strings in $A$ as $a_0,\ldots,a_{N-1}$, where $N=2^m$, and use an $m$-<qubit> index <quantum ancilla>. Apply <Hadamard gates> to that register to prepare
$$
|0^n\rangle\otimes\frac1{\sqrt N}\sum_{j=0}^{N-1}|j\rangle.
$$
First, for each $j$ with $a_j\ne0^n$, apply the available <unitary operator> that transposes $|0^n,j\rangle$ and $|a_j,j\rangle$. The pairs are disjoint because they have distinct index labels. Skip a transposition when the two vectors coincide. This produces
$$
\frac1{\sqrt N}\sum_j|a_j,j\rangle.
$$
Second, for each $j\ne0$, transpose $|a_j,j\rangle$ and $|a_j,0^m\rangle$. These pairs are disjoint because the data strings $a_j$ are distinct. No pair contains the term with $j=0$, and no later transposition moves an earlier output. The final state is exactly
$$
\boxed{\frac1{\sqrt N}\sum_j|a_j\rangle\otimes|0^m\rangle=|\psi_A\rangle\otimes|0^m\rangle.}
$$
This <clean subset superposition preparation> uses at most $N+(N-1)=2N-1$ of the given transpositions and $m$ <Hadamard gates>. Since $m=O(\log_2 n)$, $N$ is polynomial in $n$; multiplying this count by the assumed polynomial size of each transposition gives a polynomial-size <quantum circuit>. The index <quantum ancilla> returns to zero, so the data register is a pure <uniform superposition state>, rather than a mixture obtained by discarding its index. The construction uses an available enumeration of the known subset; a membership oracle alone would not justify that enumeration.
Back to article page
