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

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.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.

arXiv:quant-ph/0504067Apr 8, 20054 citations

The Symmetric Group Defies Strong Fourier Sampling: Part II

Cristopher Moore, Alexander C. Russell

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.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.

arXiv:quant-ph/0501066Jan 13, 200523 citations

Optimal measurements for the dihedral hidden subgroup problem

Dave Bacon, Andrew M. Childs, Wim van Dam

We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states.We show that the optimal measurement for solving this problem is the so-called pretty good measurement.We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density ν = k/ log 2 N , where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group.In particular, for ν < 1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N , while for ν > 1 the optimal measurement identifies the hidden subgroup with a probability of order unity.Thus the dihedral group provides an example of a group G for which Ω(log |G|) hidden subgroup states are necessary to solve the hidden subgroup problem.We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold.Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems.In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states.We show that the optimal measurement for solving this problem is the so-called pretty good measurement.We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density ν = k/ log 2 N , where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group.In particular, for ν < 1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N , while for ν > 1 the optimal measurement identifies the hidden subgroup with a probability of order unity.Thus the dihedral group provides an example of a group G for which Ω(log |G|) hidden subgroup states are necessary to solve the hidden subgroup problem.We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold.Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems.In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.

arXiv:quant-ph/0501044Chicago Journal of Theoretical Computer ScienceJan 1, 200655 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.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/0511149Nov 15, 20053 citations

The Hidden Subgroup Problem

Frédéric Wang

We give an overview of the Hidden Subgroup Problem (HSP) as of July 2010, including new results discovered since the survey of arXiv:quant-ph/0411037v1. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.We give an overview of the Hidden Subgroup Problem (HSP) as of July 2010, including new results discovered since the survey of arXiv:quant-ph/0411037v1. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.

arXiv:1008.0010Jul 30, 201010 citations

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.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 ScienceNov 15, 200559 citations

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.