Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem

ABSTRACT

In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

REFERENCES

• 1: László Babai , Gene Cooperman , Larry Finkelstein , Eugene Luks , Ákos Seress, Fast Monte Carlo algorithms for permutation groups, Journal of Computer and System Sciences, v.50 n.2, p.296-308, April 1995
• 2: L. Babai and E. Szemeredi, On the complexity of matrix group problems I., Proc. 25th IEEE Foundations of Computer Science, 1984, 229-240.
• 3: L. Babai and R. Beals, A polynomial-time theory of black-box groups I., Groups St. Andrews 1997 in Bath, I, London Math. Soc. Lecture Notes Ser., vol. 260, Cambridge Univ. Press, 1999, 30-64.
• 4: R. Beals, Towards polynomial time algorithms for matrix groups, Groups and Computation Proc. 1991 DIMACS Workshop, L. Finkelstein, W. M. Kantor (eds.), DIMACS Ser. in Discr. Math. and Theor. Comp. Sci. Vol. 11, AMS, 1993, 31-54.
• 5: R. Beals and L. Babai, Las Vegas algorithms for matrix groups, Proc. 34th IEEE Foundations of Computer Science, 1993, 427-436.
• 6: Dan Boneh , Richard J. Lipton, Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract), Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.424-437, August 27-31, 1995
• 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: K. Cheung and M. Mosca, preprint available at http://xxx.lanl.gov/abs/quant-ph/0101004.
• 9: M. Ettinger and P. Hfiyer, On quantum algorithms for noncommutative hidden subgroups, Proc. 16th Symposium on Theoretical Aspects of Computer Science, LNCSvol 1563, 1999, 478-487.
• 10: M. Ettinger, P. Hfiyer, and E. Knill, Hidden subgroup states are almost orthogonal, preprint available at http://xxx.lanl.gov/abs/quant-ph/9901034.
• 11: W. Feit and J. Tits, Projective representations of minimum degree of of group extensions, Canadian J. Math., vol. 30, 1978, 1092-1102.
• 12: 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]
• 13: J. Gruska, Quantum Computing, McGraw Hill, 1999.
• 14: 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]
• 15: R. Jozsa, Quantum algorithms and the Fourier transform, preprint available at http://xxx.lanl.gov/abs/quant-ph/9707033.
• 16: R. Jozsa, Quantum factoring, discrete logarithms and the hidden subgroup problem, preprint available at http://xxx.lanl.gov/abs/quant-ph/0012084.
• 17: A. Kitaev, Quantum measurements and the Abelian Stabilizer Problem, preprint available at http://xxx.lanl.gov/abs/quant-ph/9511026.
• 18: V. Landazuri and G. M. Seitz, On the minimal degrees of projective representations of the finite Chevalley groups, J. Algebra vol. 32, 1974, 418-443.
• 19: E. M. Luks, Computing in solvable matrix groups, Proc. 33th IEEE Foundations of Computer Science, 1992, 111-120.
• 20: W. M. Kantor and A. Seress, Black box classical groups, Manuscript.
• 21: M. Mosca, Quantum Computer Algorithms, PhD thesis, University of Oxford, 1999.
• 22: 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
• 23: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 24: J. Rotman, An Introduction to the Theory of Groups, Springer-Verlag, Series: Graduate Texts in Mathematics, vol. 148, 4th ed. 1995 (corr. 2nd printing 1999).
• 25: M. R.otteler and T. Beth, Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups, preprint available at http://xxx.lanl.gov/abs/quant-ph/9812070.
• 26: 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]
• 27: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
• 28: John Watrous, Quantum algorithms for solvable groups, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.60-67, July 2001, Hersonissos, Greece [doi>10.1145/380752.380759]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Performance, Theory, Verification