Symmetric functions of qubits in an unknown basis
arXiv:0903.5466 · doi:10.1103/PhysRevA.79.062316
Abstract
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| at most n/2, it is possible to reconstruct |x| with success probability 1 - |x|/(n-|x|+1), and thus to compute any symmetric function of x. We give explicit algorithms for computing whether or not |x| is at least t for some t, and for computing the parity of x, and show that these are essentially optimal. These results can be seen as generalisations of the swap test for comparing quantum states.
6 pages, 3 figures; v2: improved results, essentially published version
References in corpus (10)
- Quantum fingerprinting
- Classical and quantum communication without a shared reference frame
- Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
- The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography
- Applications of coherent classical communication and the Schur transform to quantum information theory
- Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
- Comparing the states of many quantum systems
- The Quantum Schur Transform: I. Efficient Qudit Circuits
- The Efficiency of Quantum Identity Testing of Multiple States
- Universal quantum computation in a hidden basis