= Clean subset superposition preparation
{title2=$|0^n0^m\rangle\longmapsto |\psi_A\rangle|0^m\rangle$}
Suppose a known list of $2^m$ distinct $n$-bit strings $a_j$ is available and <computational basis> transpositions on $n+m$ <qubits> have polynomial-size implementations. Start with the <uniform superposition state> of index labels $j$, leaving the data zero. First swap $|0^n,j\rangle$ with $|a_j,j\rangle$ for each nonzero $a_j$. Next, for each $j\ne0$, swap $|a_j,j\rangle$ with $|a_j,0^m\rangle$. Distinct index labels separate the first-stage pairs, and distinct data strings separate the second-stage pairs. Thus no later transposition disturbs an earlier term. At most $2^{m+1}-1$ transpositions prepare the uniform data state and return the <quantum ancilla> to zero. For $m=O(\log n)$ the <quantum circuit> has polynomial size. This assumes the list is available; a membership predicate alone does not supply it.
Back to article page
