Symmetric functions of qubits in an unknown basis
Ashley Montanaro · Physical Review A · 2009
Consider an $n$-qubit computational basis state corresponding to a bit-string $x$, which has had an unknown local unitary applied to each qubit, and whose qubits have been reordered by an unknown permutation. We show that, given such a state with Hamming weight $|x|\ensuremath{\le}\ensuremath{\lfloor}n/2\ensuremath{\rfloor}$, it is possible to reconstruct $|x|$ with success-probability $1\ensuremath{-}|x|/(n\ensuremath{-}|x|+1)$, and thus to compute any symmetric function of $x$. We give explicit algorithms for computing whether or not $|x|\ensuremath{\ge}t$ for some $t$, and for computing the parity of $x$, and show that these are essentially optimal. These results can be seen as generalizations of the swap test for comparing quantum states.