skip to main content
10.1145/1250790.1250868acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

On the impossibility of a quantum sieve algorithm for graph isomorphism

Published: 11 June 2007 Publication History

Abstract

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.
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 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(√(n log n)).

References

[1]
Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Proc. 38th Symposium on Theory of Computing, 427--436, 2006.
[2]
Gorjan Alagić, Cristopher Moore, and Alexander Russell. Quantum algorithms for Simon's problem over general groups. Proc. 18th Symposium on Discrete Algorithms (2007).
[3]
David Aldous and Persi Diaconis. Hammersley's interacting particle process and longest increasing subsequences. Probab. Theory Relat. Fields 103 (1995), 199--213.
[4]
László Babai. On the complexity of canonical labeling of strongly regular graphs. SIAM J. Computing, 9(1):212--216, 1980.
[5]
László Babai and Eugene M. Luks. Canonical labeling of graphs. Proc. 15th Symposium on Theory of Computing, 171--183.
[6]
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, 469--478, 2005.
[7]
David Bacon, Andrew Childs, and Wim van Dam. Optimal measurements for the dihedral hidden subgroup problem. Chicago Journal of Theoretical Computer Science, 2006.
[8]
Philippe Biane. Representations of symmetric groups and free probability. Advances in Mathematics, 138(1):126--181, 1998.
[9]
Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, and Pranab Sen. Hidden translation and orbit coset in quantum computing. Proc. 35th Symposium on Theory of Computing, 1--9, 2003.
[10]
William Fulton. Young Tableaux: with Applications to Representation Theory and Geometry, volume 35 of Student Texts. London Mathematical Society, 1997.
[11]
Michelangelo Grigni, Leonard Schulman, Monica Vazirani, and Umesh Vazirani. Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Proc. 33rd Symposium on Theory of Computing, 68--74, 2001.
[12]
Sean Hallgren. Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. Proc. 34th Symposium on Theory of Computing, 653--658.
[13]
Sean Hallgren. Fast quantum algorithms for computing the unit group and class group of a number field. Proc. 37th Symposium on Theory of Computing, 468--474, 2005.
[14]
Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, and Pranab Sen. Limitations of quantum coset states for graph isomorphism. Proc. 38th Symposium on Theory of Computing, 604--617, 2006.
[15]
Sean Hallgren, Alexander Russell, and Amnon Ta-Shma. Normal subgroup reconstruction and quantum computation using group representations. Proc. 32nd Symposium on Theory of Computing, 627--635, 2000.
[16]
Gordon James and Adalbert Kerber. The representation theory of the symmetric group, volume 16 of Encyclopedia of mathematics and its applications. Addison-Wesley, 1981.
[17]
S. V. Kerov. Asymptotic representation theory of the symmetric group and its applications in analysis, volume 219 of Translations of Mathematical Monographs. American Mathematical Society, 2003. Translated by N. V. Tsilevich.
[18]
Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup. SIAM J. Computing 35(1): 170--188, 2005.
[19]
Cristopher Moore and Alexander Russell. On the impossibility of a quantum sieve algorithm for Graph Isomorphism. Preprint, quant-ph/0609138 (2006).
[20]
Cristopher Moore and Alexander Russell. Explicit multiregister measurements for hidden subgroup problems; or, Fourier sampling strikes back. Preprint, quant-ph/0504067 (2005).
[21]
Cristopher Moore and Alexander Russell. The symmetric group defies strong Fourier sampling: part II. Preprint, quant-ph/0501066 (2005).
[22]
Cristopher Moore, Alexander Russell, and Leonard Schulman. The power of basis selection in fourier sampling: hidden subgroup problems in affine groups. Proc. 15th Symposium on Discrete Algorithms, 1113--1122, 2004.
[23]
Cristopher Moore, Alexander Russell, and Leonard Schulman. The symmetric group defies Fourier sampling. Proc. 46th Symposium on Foundations of Computer Science, 479--488, 2005.
[24]
Amarpreet Rattan and Piotr Sniady. Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula. Preprint, math.RT/0610540 (2006).
[25]
Oded Regev. Quantum computation and lattice problems. Proc. 43rd Symposium on Foundations of Computer Science, 520--529, 2002.
[26]
Jean-Pierre Serre. Linear Representations of Finite Groups. Number 42 in Graduate Texts in Mathematics. Springer-Verlag, 1977.
[27]
Peter W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. Proc. 35th Symposium on Foundations of Computer Science, 124--134, 1994.
[28]
D. R. Simon. On the power of quantum computation. Proc. 35th Symposium on Foundations of Computer Science, 116--123, 1994.
[29]
Daniel A. Spielman. Faster isomorphism testing of strongly regular graphs. Proc. 28th Symposium on Theory of Computing, 576--584, 1996.
[30]
A. M. Vershik and S. V. Kerov. Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group. Funk. Anal. i Prolizhen, 19(1):25--36, 1985. English translation, Funct. Anal. Appl. 19(1):21--31, 1989.

Cited By

View all
  • (2024)Applications of Finite Non-Abelian Simple Groups to Cryptography in the Quantum EraLa Matematica10.1007/s44007-024-00096-z3:2(588-603)Online publication date: 2-Apr-2024
  • (2020)ϵKTELOACM Transactions on Database Systems10.1145/336203245:1(1-44)Online publication date: 8-Feb-2020
  • (2020)Computing Optimal Repairs for Functional DependenciesACM Transactions on Database Systems10.1145/336090445:1(1-46)Online publication date: 17-Feb-2020
  • Show More Cited By
  1. On the impossibility of a quantum sieve algorithm for graph isomorphism

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
    June 2007
    734 pages
    ISBN:9781595936318
    DOI:10.1145/1250790
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 11 June 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. graph isomorphism problem
    2. quantum computation

    Qualifiers

    • Article

    Conference

    STOC07
    Sponsor:
    STOC07: Symposium on Theory of Computing
    June 11 - 13, 2007
    California, San Diego, USA

    Acceptance Rates

    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Applications of Finite Non-Abelian Simple Groups to Cryptography in the Quantum EraLa Matematica10.1007/s44007-024-00096-z3:2(588-603)Online publication date: 2-Apr-2024
    • (2020)ϵKTELOACM Transactions on Database Systems10.1145/336203245:1(1-44)Online publication date: 8-Feb-2020
    • (2020)Computing Optimal Repairs for Functional DependenciesACM Transactions on Database Systems10.1145/336090445:1(1-46)Online publication date: 17-Feb-2020
    • (2018)Devirtualizing Memory in Heterogeneous SystemsACM SIGPLAN Notices10.1145/3296957.317319453:2(637-650)Online publication date: 19-Mar-2018
    • (2018)Exploiting Dynamic Thermal Energy Harvesting for Reusing in Smartphone with Mobile ApplicationsACM SIGPLAN Notices10.1145/3296957.317318853:2(243-256)Online publication date: 19-Mar-2018
    • (2018)Unconventional Parallelization of Nondeterministic ApplicationsACM SIGPLAN Notices10.1145/3296957.317318153:2(432-447)Online publication date: 19-Mar-2018
    • (2018)SMT-Based Observer Design for Cyber-Physical Systems under Sensor AttacksACM Transactions on Cyber-Physical Systems10.1145/30786212:1(1-27)Online publication date: 3-Jan-2018
    • (2017)Quantum-Secure Symmetric-Key Cryptography Based on Hidden ShiftsAdvances in Cryptology – EUROCRYPT 201710.1007/978-3-319-56617-7_3(65-93)Online publication date: 1-Apr-2017
    • (2015)Quantum Fourier Transform over Symmetric GroupsACM Communications in Computer Algebra10.1145/2733693.273370848:3/4(127-129)Online publication date: 5-Feb-2015
    • (2013)Quantum fourier transform over symmetric groupsProceedings of the 38th International Symposium on Symbolic and Algebraic Computation10.1145/2465506.2465940(227-234)Online publication date: 26-Jun-2013
    • Show More Cited By

    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