Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2005 | public
Book Section - Chapter

The symmetric group defies strong Fourier sampling


We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem in general groups. Specifically, we show that the hidden subgroup problem in the symmetric group cannot be efficiently solved by strong Fourier sampling. Indeed we prove the stronger statement that no measurement of a single coset state can reveal more than an exponentially small amount of information about the identity of the hidden subgroup, in the special case relevant to the Graph Isomorphism problem.

Additional Information

© 2005 IEEE. Issue Date: 23-25 Oct. 2005. Date of Current Version: 14 November 2005. This work was supported by NSF through grants CCR- 0093065, PHY-0200909, EIA-0218443, EIA-0218563, CCR-0220070, CCR-0220264, CCR-0049092, the Institute for Quantum Information, and ARDA under ARO contract W911NF-04-R-0009. We are grateful to Denis Th´erien, McGill University, and Bellairs Research Institute for organizing a workshop at which this work began; to Dorit Aharonov, Daniel Rockmore, and Umesh Vazirani for helpful conversations; to Chris Lomont for pointing out several typos; and to Tracy Conrad and Sally Milius for their support and tolerance. C.M. also thanks Rosemary for her timely arrival, and for providing a larger perspective.

Additional details

August 19, 2023
January 13, 2024