skip to main content
10.5555/1283383.1283514acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Quantum algorithms for Simon's problem over general groups

Published: 07 January 2007 Publication History

Abstract

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

References

[1]
Gorjan Alagic, Cristopher Moore, Alexander Russell. Strong Fourier Sampling Fails over Gn . Preprint, quant-ph/0511054 (2005).
[2]
David Bacon, Andrew Childs, and Wim van Dam. From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. Proc. 46th Symposium on Foundations of Computer Science, 2005.
[3]
Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, and Pranab Sen. Hidden translation and orbit coset in quantum computing. Proc. 35th ACM Symposium on Theory of Computing, 2003.
[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, and Pranab Sen. Limitations of quantum coset states for graph isomorphism. Proc. 38th ACM Symposium on Theory of Computing, 2006.
[6]
Sean Hallgren, Alexander Russell, and Amnon Ta-Shma. Normal subgroup reconstruction and quantum computation using group representations. Proc. 32nd ACM Symposium on Theory of Computing, pages 627--635, 2000.
[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. Graduate Studies in Mathematics, Vol. 47, AMS (2002).
[10]
Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing, 35(1):170--188, 2005.
[11]
Cristopher Moore, Daniel Rockmore, Alexander Russell. Generic Quantum Fourier Transforms. Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 778--787, 2004.
[12]
Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard Schulman. The value of basis selection in Fourier sampling: hidden subgroup problems for affine groups. Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1113--1122, 2004.
[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 Schulman. The symmetric group defies strong Fourier sampling. Proc. 46th IEEE Symposium on Foundations of Computer Science, pages 479--488, 2005.
[15]
Oded Regev. Quantum computation and lattice problems. Proc. 43rd Symposium on Foundations of Computer Science, pages 520--530, 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 Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484--1509.
[18]
Daniel Simon. On the Power of Quantum Computation. SIAM Journal on Computing, 26(5).

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
January 2007
1322 pages
ISBN:9780898716245
  • Conference Chair:
  • Harold Gabow

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

  • Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Efficient classical simulation of the Deutsch---Jozsa and Simon's algorithmsQuantum Information Processing10.1007/s11128-017-1679-716:9(1-14)Online publication date: 1-Sep-2017
  • (2011)Multi-query Quantum SumsRevised Selected Papers of the 6th Conference on Theory of Quantum Computation, Communication, and Cryptography - Volume 674510.1007/978-3-642-54429-3_10(153-163)Online publication date: 24-May-2011
  • (2010)Limitations of quantum coset states for graph isomorphismJournal of the ACM10.1145/1857914.185791857:6(1-33)Online publication date: 5-Nov-2010
  • (2007)On the impossibility of a quantum sieve algorithm for graph isomorphismProceedings of the thirty-ninth annual ACM symposium on Theory of computing10.1145/1250790.1250868(536-545)Online publication date: 11-Jun-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media