On the impossibility of a quantum sieve algorithm for graph isomorphism

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 S_n ࣀ Z₂. Using a recently proved bound on the irreducible characters of S_n, 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 e^{O(√(n log n))}.

REFERENCES

• 1: Dorit Aharonov , Vaughan Jones , Zeph Landau, A polynomial quantum algorithm for approximating the Jones polynomial, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132579]
• 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 , Eugene M. Luks, Canonical labeling of graphs, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.171-183, December 1983 [doi>10.1145/800061.808746]
• 6: 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]
• 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 , 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]
• 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 , Umesh Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.68-74, July 2001, Hersonissos, Greece [doi>10.1145/380752.380769]
• 12: Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510001]
• 13: Sean Hallgren, Fast quantum algorithms for computing the unit group and class group of a number field, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060660]
• 14: 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]
• 15: 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]
• 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 Problem, SIAM Journal on Computing, v.35 n.1, p.170-188, 2005 [doi>10.1137/S0097539703436345]
• 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 , 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
• 23: 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]
• 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, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.520-529, November 16-19, 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, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.576-584, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238006]
• 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.

INDEX TERMS

General Terms:
Algorithms, Performance

Keywords:
graph isomorphism problem, quantum computation