It is known that any quantum algorithm for Graph Isomorphism thatworks within the framework of the hidden subgroup problem (HSP) must performhighly entangled measurements across Ω(n log n) coset states. One ofthe only known models for how such a measurement could be carried outefficiently is Kuperberg's algorithm for the HSP in the dihedral group, in whichquantum states are adaptively combined and measured according to thedecomposition of tensor products into irreducible representations. This "quantum sieve" starts with coset states, and works its way down towardsrepresentations whose probabilities differ depending on, for example, whetherthe hidden subgroup is trivial or nontrivial.
It is known that any quantum algorithm for Graph Isomorphism thatworks within the framework of the hidden subgroup problem (HSP) must performhighly entangled measurements across Ω(n log n) coset states. One ofthe only known models for how such a measurement could be carried outefficiently is Kuperberg's algorithm for the HSP in the dihedral group, in whichquantum states are adaptively combined and measured according to thedecomposition of tensor products into irreducible representations. This "quantum sieve" starts with coset states, and works its way down towardsrepresentations whose probabilities differ depending on, for example, whetherthe hidden subgroup is trivial or nontrivial.
It is known that any quantum algorithm for graph isomorphism that works within the framework of the hidden subgroup problem (HSP) must perform highly entangled measurements across Ω(nlogn) coset states. One of the only known models for how such a measurement could be carried out efficiently is Kuperberg's algorithm for the HSP in the dihedral group, in which quantum states are adaptively combined and measured according to the decomposition of tensor products into irreducible representations. This “quantum sieve” starts with coset states and works its way down toward representations whose probabilities differ depending on, for example, whether the hidden subgroup is trivial or nontrivial. In this paper we show that no such approach can produce a polynomial-time quantum algorithm for graph isomorphism. Specifically, we consider the natural reduction of graph isomorphism to the HSP over the wreath product Sn≀Z2. Using a recently proved bound on the irreducible characters of Sn, we show that no algorithm in this family can solve graph isomorphism in less than eΩ(n) time, no matter what adaptive rule it uses to select and combine quantum states. In particular, algorithms of this type can offer essentially no improvement over the best known classical algorithms, which run in time eO(nlogn).
It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore, Russell, and Schulman [30] that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Ω(n log n) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because highly entangled measurements seem hard to implement in general. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL(n,Fpm) and Gn where G is finite and satisfies a suitable property.
It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore et al. [2005] that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Ω( n log n ) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because in general it seems hard to implement a given highly entangled measurement. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL( n ,F p m ) and G n where G is finite and satisfies a suitable property.
Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z 2 n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G , this is the problem of recovering an involution m = ( m 1 ,…, m n ) ∈ G n from an oracle f with the property that f ( x ⋅ y ) = f ( x ) ⇔ y ∈ {1, m }. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G n , where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form G n have a simple product structure, they share important representation--theoretic properties with the symmetric groups S n , where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called “standard method” requires highly entangled measurements on the tensor product of many coset states. In this article, we provide quantum algorithms with time complexity 2 O (√ n ) that recover hidden involutions m = ( m 1 ,… m n ) ∈ G n where, as in Simon's problem, each m i is either the identity or the conjugate of a known element m which satisfies κ( m ) = −κ(1) for some κ ∈ Ĝ . Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the “missing harmonic” approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.
We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups.
We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture.
For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem.
In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.
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.