Moore, Cristopher and Russell, Alexander and Schulman, Leonard J. (2005) The symmetric group defies strong Fourier sampling. In: 46th Annual IEEE Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science . IEEE , Los Alamitos, CA, pp. 479-488. ISBN 0-7695-2468-0 http://resolver.caltech.edu/CaltechAUTHORS:20110822-081948476
Full text not available from this repository.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110822-081948476
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.
| Item Type: | Book Section | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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. | ||||||||||||||||||||
| Funders: |
| ||||||||||||||||||||
| Other Numbering System: |
| ||||||||||||||||||||
| Record Number: | CaltechAUTHORS:20110822-081948476 | ||||||||||||||||||||
| Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20110822-081948476 | ||||||||||||||||||||
| Related URLs: | |||||||||||||||||||||
| Official Citation: | Moore, C.; Russell, A.; Schulman, L.J.; , "The symmetric group defies strong Fourier sampling," Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on , vol., no., pp. 479- 488, 23-25 Oct. 2005 doi: 10.1109/SFCS.2005.73 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1530740&isnumber=32664 | ||||||||||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||||
| ID Code: | 24964 | ||||||||||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||||||||||
| Deposited By: | Tony Diaz | ||||||||||||||||||||
| Deposited On: | 22 Aug 2011 22:53 | ||||||||||||||||||||
| Last Modified: | 22 Aug 2011 22:53 |
Repository Staff Only: item control page
