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 March 26, 2008 | public
Journal Article Open

The Symmetric Group Defies Strong Fourier Sampling


The dramatic exponential speedups of quantum algorithms over their best existing classical counterparts were ushered in by the technique of Fourier sampling, introduced by Bernstein and Vazirani and developed by Simon and Shor into an approach to the hidden subgroup problem. This approach has proved successful for abelian groups, leading to efficient algorithms for factoring, extracting discrete logarithms, and other number-theoretic problems. We show, however, that this method cannot resolve the hidden subgroup problem in the symmetric groups, even in the weakest, information-theoretic sense. In particular, we show that the Graph Isomorphism problem cannot be solved by this approach. Our work implies that any quantum approach based upon the measurement of coset states must depart from the original framework by using entangled measurements on multiple coset states.

Additional Information

©2008 Society for Industrial and Applied Mathematics. Received by the editors November 11, 2005; accepted for publication (in revised form) November 12, 2007; published electronically March 26, 2008. This work was supported by NSF grants CCR-0093065, PHY-0200909, PHY-0456720, EIA-0218443, EIA-0218563, CCR-0220070, CCR-0220264, CCF-0524828, and CCF-0524613, and ARO grants W911NF-04-R-0009 and W911NF-05-1-0294. We are grateful to Denis Thérien, 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 Moore for providing a larger perspective. Finally, we thank Gorjan Alagic for his comments on the structured involutions material.


Files (277.7 kB)
Name Size Download all
277.7 kB Preview Download

Additional details

August 22, 2023
October 16, 2023