A Caltech Library Service

The Symmetric Group Defies Strong Fourier Sampling

Moore, Christopher and Russell, Alexander and Schulman, Leonard J. (2008) The Symmetric Group Defies Strong Fourier Sampling. SIAM Journal on Computing, 37 (6). pp. 1842-1864. ISSN 0097-5397. doi:10.1137/050644896.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
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.
Subject Keywords:quantum computing; hidden subgroup problem; graph isomorphism; Fourier sampling
Issue or Number:6
Record Number:CaltechAUTHORS:MOOsiamjc08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10100
Deposited By: Archive Administrator
Deposited On:13 Apr 2008
Last Modified:08 Nov 2021 21:05

Repository Staff Only: item control page