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

Limitations of quantum coset states for graph isomorphism

Published: 21 May 2006 Publication History

Abstract

It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore, Russell, and Schulman [30] that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Ω(n log n) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because highly entangled measurements seem hard to implement in general. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL(n,Fpm) and Gn where G is finite and satisfies a suitable property.

References

[1]
D. Aharonov and A. Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the 35th Annual ACM Symposium on Theory of computing, pages 20--29, 2003. Also: ArXiv preprint quant--ph/0301023.]]
[2]
G. Alagic, C. Moore, and A. Russell. Strong Fourier sampling fails over Gn. ArXiv preprint quant-ph/0511054, 2005.]]
[3]
D. Bacon, A. Childs, and W. v. Dam. From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005. Also: ArXiv preprint quant--ph/0504083.]]
[4]
R. Beals. Quantum computation of Fourier transforms over the symmetric groups. In Proceedings of the Symposium on Theory of Computing (STOC'97), pages 48--53, El Paso, Texas, 1997.]]
[5]
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510--1523, 1997.]]
[6]
Y. G. Berkovich and E. M. Zhmud. Characters of finite groups, part 2, volume 181 of Translations of Mathematical Monographs. American Mathematical Society, 1999.]]
[7]
G. Brassard and P. Hoyer. An exact polynomial--time algorithm for Simon's problem. In Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems, pages 12--33. ISTCS, IEEE Computer Society Press, 1997. Also: ArXiv preprint quant--ph/9704027.]]
[8]
A. Childs and P. Wocjan. On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems. ArXiv preprint quant--ph/0510185, 2005.]]
[9]
M. Ettinger and P. Hoyer. On quantum algorithms for noncommutative hidden subgroups. Advances in Applied Mathematics, 25(3):239--251, 2000.]]
[10]
M. Ettinger, P. Hoyer, and E. Knill. A quantum observable for the graph isomorphism problem. ArXiv preprint quant--ph/9901029, 1999.]]
[11]
M. Ettinger, P. Hoyer, and E. Knill. Hidden subgroup states are almost orthogonal. ArXiv preprint quant--ph/9901034, 1999.]]
[12]
K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen. Hidden translation and orbit coset in quantum computing. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 1--9, 2003. Also: ArXiv preprint quant--ph/0211091.]]
[13]
W. Fulton and J. Harris. Representation theory: A first course, volume 129 of Graduate Texts in Mathematics. Springer, 1991.]]
[14]
P. X. Gallagher. Character values at involutions. Proceeedings of the American Mathematical Society, 120(3):657--659, 1994.]]
[15]
M. Grigni, L. Schulman, M. Vazirani, and U. Vazirani. Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Combinatorica, pages 137--154, 2004.]]
[16]
L. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 212--219, 1996. Also: ArXiv preprint quant--ph/9605043.]]
[17]
S. Hallgren. Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. In Proceedings of the 34th Annual ACM Symposium on Theory of computing, pages 653--658, 2002.]]
[18]
S. Hallgren. Fast quantum algorithms for computing the unit group and class group of a number field. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 468--474, 2005.]]
[19]
S. Hallgren, M. Rötteler, and P. Sen. Limitations of quantum coset states for graph isomorphism. arXiv preprint quant-ph/0511148.]]
[20]
S. Hallgren, A. Russell, and A. Ta-Shma. The hidden subgroup problem and quantum computation using group representations. SIAM Journal on Computing, 32(4):916--934, 2003.]]
[21]
I. M. Isaacs. Character theory of finite groups. Academic Press, 1976.]]
[22]
G. Ivanyos, F. Magniez, and M. Santha. Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. International Journal of Foundations of Computer Science, pages 723--740, 2003. Also: ArXiv preprint quant--ph/0102014.]]
[23]
G. James and A. Kerber. The representation theory of the symmetric group. Addison-Wesley, Reading, 1981.]]
[24]
A. Y. Kitaev. Quantum measurements and the abelian stabilizer problem. ArXiv preprint quant--ph/9511026, 1995.]]
[25]
J. Köbler, U. Schöning, and J. Torán. The graph isomorphism problem. Birkhäuser, 1993.]]
[26]
G. Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. ArXiv preprint quant--ph/0302112, 2003.]]
[27]
J. D. Lafferty and D. Rockmore. Fast Fourier analysis for rm SL2 over a finite field and related numerical experiments. Experimental Mathematics, 1(2):115--139, 1992.]]
[28]
C. Moore, D. Rockmore, A. Russell, and L. Schulman. The power of basis selection in fourier sampling: Hidden subgroup problems in affine groups. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1113--1122, 2004. Journal version in preparation. Also: ArXiv preprint quant--ph/0503095.]]
[29]
C. Moore and A. Russell. The symmetric group defies strong Fourier sampling: Part II. ArXiv preprint quant--ph/0501066, 2005.]]
[30]
C. Moore, A. Russell, and L. Schulman. The symmetric group defies strong Fourier sampling. In Proceedings of the 46th Annual IEEE Symposium on the Foundations of Computer Science, pages 479--488, 2005. Also: ArXiv preprint quant--ph/0501056.]]
[31]
M. Mosca and A. Ekert. The hidden subgroup problem and eigenvalue estimation on a quantum computer. In Quantum Computing and Quantum Communications, volume 1509 of Lecture Notes in Computer Science, pages 174--188. Springer-Verlag, 1998.]]
[32]
M. Nielsen and I. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.]]
[33]
J. Radhakrishnan, M. Rötteler, and P. Sen. On the power of random bases in Fourier sampling: Hidden subgroup problem in the Heisenberg group. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 3580, pages 1399--1411. Springer-Verlag, 2005. Also: ArXiv preprint quant--ph/0503114.]]
[34]
Y. Roichman. Upper bound on the characters of the symmetric groups. Inventiones Mathematicae, 125:451--485, 1996.]]
[35]
A. Schmidt and U. Vollmer. Polynomial time quantum algorithm for the computation of the unit group of a number field. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 475--480, 2005.]]
[36]
P. Sen. Random measurement bases, quantum state distinction and applications to the hidden subgroup problem. In Proceedings of the 21st IEEE Conference on Computational Complexity, 2006. To appear. Also: ArXiv preprint quant--ph/0512085.]]
[37]
J. P. Serre. Linear representations of finite groups. Springer, 1977.]]
[38]
P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484--1509, 1997.]]
[39]
D. R. Simon. On the power of quantum computation. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 116--123, Los Alamitos, CA, 1994. Institute of Electrical and Electronic Engineers Computer Society Press.]]

Cited By

View all

Index Terms

  1. Limitations of quantum coset states for graph isomorphism

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
      May 2006
      786 pages
      ISBN:1595931341
      DOI:10.1145/1132516
      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: 21 May 2006

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. graph isomorphism
      2. hidden subgroup problem
      3. quantum algorithms

      Qualifiers

      • Article

      Conference

      STOC06
      Sponsor:
      STOC06: Symposium on Theory of Computing
      May 21 - 23, 2006
      WA, Seattle, 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)2
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 13 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all

      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