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.
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.
Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Z_2^n provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. In this paper, 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) in G^n from an oracle f with the property that f(x) = f(xy) iff y equals m or the identity. 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. Here we give quantum algorithms with time complexity 2^O(sqrt(n log n)) that recover hidden involutions m = (m_1, ..., m_n) in G^n where, as in Simon's problem, each m_i is either the identity or the conjugate of a known element k, and there is a character X of G for which X(k) = -X(1)$. 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 hidden subgroup algorithms for group families that require highly entangled multiregister Fourier sampling.
Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively.
In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form G=A⋊φZpk, with A finite Abelian, p prime, k∈N and the action of Zpk is generated by the scalar automorphism a↦μa, for some μ∈ZExp(A)×, where Exp(A) is the exponent of A. Our algorithm is efficient when A has bounded generator rank and Exp(A)/p=polylog(∣G∣). This includes the case A=ZN for N∈N and k=1, studied by Bacon, Childs and van Dam (FOCS 2005), and A=Zqr with q prime and r∈N studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).
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.
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).
The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems.
We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element.
We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries.
For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements.
We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements.
For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.
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 Omega(n log n) 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 towards representations whose probabilities differ depending on, for example, whether the hidden subgroup is trivial or nontrivial. In this paper we give strong evidence that no such approach can succeed for Graph Isomorphism. Specifically, we consider the natural reduction of Graph Isomorphism to the HSP over the the wreath product S_n \wr Z_2. We show, modulo a group-theoretic conjecture regarding the asymptotic characters of the symmetric group, that no matter what rule we use to adaptively combine quantum states, there is a constant b > 0 such that no algorithm in this family can solve Graph Isomorphism in e^{b sqrt{n}} time. In particular, such algorithms are essentially no better than the best known classical algorithms, whose running time is e^{O(sqrt{n \log n})}.