Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0501066

The Symmetric Group Defies Strong Fourier Sampling: Part II

Cristopher Moore, Alexander C. Russell

Published Jan 13, 2005• 23 citations
arXivHTMLPDF

Abstract

Part I of this paper showed that the hidden subgroup problem over the symmetric group--including the special case relevant to Graph Isomorphism--cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. In this paper, we extend these results to entangled measurements. Specifically, we show that the hidden subgroup problem on the symmetric group cannot be solved by any POVM applied to pairs of coset states. In particular, these hidden subgroups cannot be determined by any polynomial number of one- or two-register experiments on coset states.

DOI
10.48550/arxiv.quant-ph/0501066

Related papers

The Symmetric Group Defies Strong Fourier Sampling: Part I

Cristopher Moore, Alexander C. Russell, Leonard J. Schulman

We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem. Specifically, we show that the hidden subgroup problem over the symmetric group cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. Our results apply to the special case relevant to the Graph Isomorphism problem.

arXiv:quant-ph/0501056•Jan 12, 2005•1 citation

The Symmetric Group Defies Strong Fourier Sampling

Cristopher Moore, Alexander C. Russell, Leonard J. Schulman

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.

Annual Symposium on Foundations of Computer Science•Nov 15, 2005•59 citations

The Symmetric Group Defies Strong Fourier Sampling

Cristopher Moore, Alexander C. Russell, Leonard J. Schulman

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.

SIAM Journal on Computing•Jan 1, 2008•29 citations

Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement

Cristopher Moore, Alexander C. Russell

We establish a general method for proving bounds on the information that can be extracted via arbitrary entangled measurements on tensor products of hidden subgroup coset states. When applied to the symmetric group, the method yields an Omega(n log n) lower bound on the number of coset states over which we must perform an entangled measurement in order to obtain non-negligible information about a hidden involution. These results are tight to within a multiplicative constant and apply, in particular, to the case relevant for the Graph Isomorphism problem. Part of our proof was obtained after learning from Hallgren, Roetteler, and Sen that they had obtained similar results.

arXiv:quant-ph/0511149•Nov 15, 2005•3 citations

Explicit Multiregister Measurements for Hidden Subgroup Problems; or, Fourier Sampling Strikes Back

Cristopher Moore, Alexander C. Russell

We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses k = log 2 |G | registers, and each of the 2 k subsets of the registers contributes some information. While this does not, in general, yield an efficient algorithm, it generalizes the relationship between Subset Sum and the HSP in the dihedral group, and sheds some light on how quantum algorithms for Graph Isomorphism might work. 1

•Apr 8, 2005•11 citations

The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling

Cristopher Moore, Daniel N. Rockmore, Alexander C. Russell +1 more

Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined from a quantum state y uniformly supported on a left coset of H. These hidden subgroup problems are then solved by Fourier sampling: the quantum Fourier transform of y is computed and measured. When the underlying group is non-Abelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of Z_p by Z_q, where q divides (p-1) and q = p / polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the ``forgetful'' Abelian method are insufficient for these groups. We extend this to an information-theoretic solution for the hidden subgroup problem over semidirect products of Z_p by \Z_q where q divides (p-1) and, in particular, the Affine groups A_p. Finally, we prove a closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.

arXiv:quant-ph/0211124•Nov 20, 2002•17 citations
Part I of this paper showed that the hidden subgroup problem over the symmetric group--including the special case relevant to Graph Isomorphism--cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. In this paper, we extend these results to entangled measurements. Specifically, we show that the hidden subgroup problem on the symmetric group cannot be solved by any POVM applied to pairs of coset states. In particular, these hidden subgroups cannot be determined by any polynomial number of one- or two-register experiments on coset states.
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.
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.
We establish a general method for proving bounds on the information that can be extracted via arbitrary entangled measurements on tensor products of hidden subgroup coset states. When applied to the symmetric group, the method yields an Omega(n log n) lower bound on the number of coset states over which we must perform an entangled measurement in order to obtain non-negligible information about a hidden involution. These results are tight to within a multiplicative constant and apply, in particular, to the case relevant for the Graph Isomorphism problem. Part of our proof was obtained after learning from Hallgren, Roetteler, and Sen that they had obtained similar results.
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses k = log 2 |G | registers, and each of the 2 k subsets of the registers contributes some information. While this does not, in general, yield an efficient algorithm, it generalizes the relationship between Subset Sum and the HSP in the dihedral group, and sheds some light on how quantum algorithms for Graph Isomorphism might work. 1
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined from a quantum state y uniformly supported on a left coset of H. These hidden subgroup problems are then solved by Fourier sampling: the quantum Fourier transform of y is computed and measured. When the underlying group is non-Abelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of Z_p by Z_q, where q divides (p-1) and q = p / polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the ``forgetful'' Abelian method are insufficient for these groups. We extend this to an information-theoretic solution for the hidden subgroup problem over semidirect products of Z_p by \Z_q where q divides (p-1) and, in particular, the Affine groups A_p. Finally, we prove a closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.