Limitations of quantum coset states for graph isomorphism

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,F_p^m) and Gⁿ where G is finite and satisfies a suitable property.

REFERENCES

• 1: Dorit Aharonov , Amnon Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780546]
• 2: G. Alagic, C. Moore, and A. Russell. Strong Fourier sampling fails over Gn. ArXiv preprint quant-ph/0511054, 2005.
• 3: 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]
• 4: Robert Beals, Quantum computation of Fourier transforms over symmetric groups, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.48-53, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258548]
• 5: Charles H. Bennett , Ethan Bernstein , Gilles Brassard , Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing, v.26 n.5, p.1510-1523, Oct. 1997 [doi>10.1137/S0097539796300933]
• 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: Gilles Brassard , Peter Hoyer, An Exact Quantum Polynomial-Time Algorithm for Simon's Problem, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.12, June 17-19, 1997
• 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: Mark Ettinger , Peter Høyer, On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics, v.25 n.3, p.239-251, Oct. 2000 [doi>10.1006/aama.2000.0699]
• 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: 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]
• 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: Michelangelo Grigni , J. Schulman , Monica Vazirani , Umesh Vazirani, Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem, Combinatorica, v.24 n.1, p.137-154, January 2004 [doi>10.1007/s00493-004-0009-8]
• 16: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 17: 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]
• 18: 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]
• 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: 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
• 29: C. Moore and A. Russell. The symmetric group defies strong Fourier sampling: Part II. ArXiv preprint quant--ph/0501066, 2005.
• 30: 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]
• 31: Michele Mosca , Artur Ekert, The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.174-188, February 17-20, 1998
• 32: Quantum computation and quantum information, Cambridge University Press, New York, NY, 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: Arthur Schmidt , Ulrich Vollmer, Polynomial time quantum algorithm for the computation of the unit 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.1060661]
• 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: 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]
• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

General Terms:
Algorithms, Theory

Keywords:
graph isomorphism, hidden subgroup problem, quantum algorithms