Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement
arXiv:quant-ph/0511149
Abstract
We establish a general method for proving bounds on the information that can be extracted via arbitrary entangled measurements on tensor products of hidden subgroup coset states. When applied to the symmetric group, the method yields an Omega(n log n) lower bound on the number of coset states over which we must perform an entangled measurement in order to obtain non-negligible information about a hidden involution. These results are tight to within a multiplicative constant and apply, in particular, to the case relevant for the Graph Isomorphism problem. Part of our proof was obtained after learning from Hallgren, Roetteler, and Sen that they had obtained similar results.
supersedes earlier posting quant-ph/0510233, which was withdrawn
References in corpus (5)
- The quantum query complexity of the hidden subgroup problem is polynomial
- From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
- The Symmetric Group Defies Strong Fourier Sampling: Part II
- Optimal measurements for the dihedral hidden subgroup problem
- For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets