Published October 2005
| Version public
Book Section - Chapter
The symmetric group defies strong Fourier sampling
-
1.
California Institute of Technology
Abstract
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
Identifiers
- Eprint ID
- 24964
- Resolver ID
- CaltechAUTHORS:20110822-081948476
Funding
- NSF
- CCR-0093065
- NSF
- PHY-0200909
- NSF
- EIA-0218443
- NSF
- EIA-0218563
- NSF
- CCR-0220070
- NSF
- CCR-0220264
- NSF
- CCR-0049092
- Institute for Quantum Information
- ARDA
- W911NF-04-R-0009
Dates
- Created
-
2011-08-22Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
Caltech Custom Metadata
- Series Name
- Annual IEEE Symposium on Foundations of Computer Science
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 8803116