Quantum algorithms for Simon's problem over general groups

ABSTRACT

Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Zⁿ2 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) ε Gⁿ 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 Gⁿ, 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ⁿ 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 2^O(√n log n) that recover hidden involutions m = (m1,..., mn) ε Gⁿ 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.

REFERENCES

• 1: Gorjan Alagic, Cristopher Moore, Alexander Russell. Strong Fourier Sampling Fails over Gⁿ. Preprint, quant-ph/0511054 (2005).
• 2: Dave Bacon , Andrew M. Childs , Wim van Dam, From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.469-478, October 23-25, 2005 [doi>10.1109/SFCS.2005.38]
• 3: Katalin Friedl , Gábor Ivanyos , Frédéric Magniez , Miklos Santha , Pranab Sen, Hidden translation and orbit coset in quantum computing, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780544]
• 4: William Fulton and Joe Harris. Representation Theory: A First Course. Number 129 in Graduate Texts in Mathematics. Springer-Verlag, 1991.
• 5: Sean Hallgren , Cristopher Moore , Martin Rötteler , Alexander Russell , Pranab Sen, Limitations of quantum coset states for graph isomorphism, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132603]
• 6: Sean Hallgren , Alexander Russell , Amnon Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.627-635, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335392]
• 7: Yoshifumi Inui and François Le Gall. An efficient algorithm for the hidden subgroup problem over a class of semi-direct product groups. Proc. EQIS 2004.
• 8: Gábor Ivanyos, Frédéric Magniez, and Miklos Santha. Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. Int. J. Found. Comput. Sci. 14(5): 723--740, 2003.
• 9: A. Yu. Kitaev , A. H. Shen , M. N. Vyalyi, Classical and Quantum Computation, American Mathematical Society, Boston, MA, 2002
• 10: Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, SIAM Journal on Computing, v.35 n.1, p.170-188, 2005 [doi>10.1137/S0097539703436345]
• 11: Cristopher Moore , Daniel Rockmore , Alexander Russell, Generic quantum Fourier transforms, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 12: Cristopher Moore , Daniel Rockmore , Alexander Russell , Leonard J. Schulman, The power of basis selection in fourier sampling: hidden subgroup problems in affine groups, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 13: Cristopher Moore and Alexander Russell. Explicit Multiregister Measurements for Hidden Subgroup Problems; or, Fourier Sampling Strikes Back. Preprint, quant-ph/0504067 (2005).
• 14: Cristopher Moore , Alexander Russell , Leonard J. Schulman, The Symmetric Group Defies Strong Fourier Sampling, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.479-490, October 23-25, 2005 [doi>10.1109/SFCS.2005.73]
• 15: Oded Regev, Quantum Computation and Lattice Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.520-529, November 16-19, 2002
• 16: Martin Rötteler and Thomas Beth. Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups. Preprint, quant-ph/9812070 (1998).
• 17: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 18: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]