02226nas a2200133 4500008004100000245006800041210006600109490000600175520174200181100001901923700002201942700002301964856010501987 2010 eng d00aQuantum Algorithms for Simon’s Problem over Nonabelian Groups0 aQuantum Algorithms for Simon s Problem over Nonabelian Groups0 v63 a
Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z2n 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 = (m1,…,mn) ∈ Gn 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 Gn, 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 Gn have a simple product structure, they share important representation--theoretic properties with the symmetric groups Sn, 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 2O(√n) that recover hidden involutions m = (m1,…mn) ∈ Gn where, as in Simon's problem, each mi 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.
1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://quics.umd.edu/publications/quantum-algorithms-simon%E2%80%99s-problem-over-nonabelian-groups02185nas a2200145 4500008004100000245006500041210006300106260001400169300001600183520173300199100001901932700002201951700002301973856004301996 2007 eng d00aQuantum Algorithms for Simon’s Problem over General Groups0 aQuantum Algorithms for Simon s Problem over General Groups c1/25/2007 a1217–12243 aDaniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Zn2 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 = (m1,...,mn) ε Gn from an oracle f with the property that f(x) = f(x · y) ⇔ y ε {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, 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 Gn have a simple product structure, they share important representation-theoretic properties with the symmetric groups Sn, 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 2O(√n log n) that recover hidden involutions m = (m1,..., mn) ε Gn where, as in Simon's problem, each mi is either the identity or the conjugate of a known element m and there is a character X of G for which X(m) = - 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.
1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/060325101168nas a2200133 4500008004100000245004200041210004200083260001400125520078800139100001900927700002200946700002300968856004300991 2005 eng d00aStrong Fourier Sampling Fails over Gn0 aStrong Fourier Sampling Fails over Gn c11/7/20053 aWe present a negative result regarding the hidden subgroup problem on the powers Gn of a fixed group G. Under a condition on the base group G, we prove that strong Fourier sampling cannot distinguish some subgroups of Gn. Since strong sampling is in fact the optimal measurement on a coset state, this shows that we have no hope of efficiently solving the hidden subgroup problem over these groups with separable measurements on coset states (that is, using any polynomial number of single-register coset state experiments). Base groups satisfying our condition include all nonabelian simple groups. We apply our results to show that there exist uniform families of nilpotent groups whose normal series factors have constant size and yet are immune to strong Fourier sampling.
1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/0511054