A Caltech Library Service

The symmetric group defies strong Fourier sampling

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 .

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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
Related URLs:
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.
Funding AgencyGrant Number
Institute for Quantum InformationUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number8803116
Record Number:CaltechAUTHORS:20110822-081948476
Persistent URL:
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24964
Deposited By: Tony Diaz
Deposited On:22 Aug 2011 22:53
Last Modified:23 Aug 2016 10:04

Repository Staff Only: item control page