CaltechAUTHORS
  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 http://resolver.caltech.edu/CaltechAUTHORS:20110822-081948476

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

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
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/SFCS.2005.73 DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1530740PublisherUNSPECIFIED
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:
Funding AgencyGrant Number
NSFCCR-0093065
NSFPHY-0200909
NSFEIA-0218443
NSFEIA-0218563
NSFCCR-0220070
NSFCCR-0220264
NSFCCR-0049092
Institute for Quantum InformationUNSPECIFIED
ARDAW911NF-04-R-0009
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number8803116
Record Number:CaltechAUTHORS:20110822-081948476
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20110822-081948476
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