Quantum algorithms for solvable groups

ABSTRACT

In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. Our algorithm works in the setting of black-box groups, wherein none of these problems have polynomial-time classical algorithms. As an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.

REFERENCES

• 1: V. Arvind , N. V. Vinodchandran, Solvable black-box group problems are low for PP, Theoretical Computer Science, v.180 n.1-2, p.17-45, June 10, 1997 [doi>10.1016/S0304-3975(96)00100-4]
• 2: László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.164-174, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103440]
• 3: László Babai, Bounded round interactive proofs in finite groups, SIAM Journal on Discrete Mathematics, v.5 n.1, p.88-111, Feb. 1992 [doi>10.1137/0405008]
• 4: L. Babai. Randomization in group algorithms: conceptual questions. In Groups and Computation, II, volume 28 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 1-17. American Mathematical Society, 1997.
• 5: L. Babai and R. Beals. A polynomial-time theory of black box groups I. In Groups St. Andrews 1997 in Bath, volume 260 of London Math. Soc. Lecture Note Ser. Cambridge University Press, 1999.
• 6: 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
• 7: L. Babai and E. Szemeredi. On the complexity of matrix group problems I. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pages 229-240, 1984.
• 8: 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]
• 9: R. Beals and L. Babai. Las Vegas algorithms for matrix groups. In Proceedings of the 34th Annual IEEE Conference onFoundations of Computer Science, pages 427-436, 1993.
• 10: C. H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17:525--532, 1973.
• 11: 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
• 12: 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
• 13: K. Cheung and M. Mosca. Decomposing finite Abelian groups. Los Alamos Preprint Archive, quant-ph/0101004, 2001.
• 14: R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society, London, A454:339-354, 1998.
• 15: Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 16: D. Deutsch. Quantum theory, theChurch-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London, A400:97-117, 1985.
• 17: M. Ettinger and P. Hyer. On quantum algorithms for noncommutative hidden subgroups. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, volume 1563 of Lecture Notesin Computer Science, pages 478-487, 1999.
• 18: M. Ettinger, P. Hyer, and E. Knill. Hidden subgroup states are almost orthogonal. Los Alamos Preprint Archive, quant-ph/9901034, 1999.
• 19: Lance Fortnow , John Rogers, Complexity limitations on Quantum computation, Journal of Computer and System Sciences, v.59 n.2, p.240-252, Oct. 1999 [doi>10.1006/jcss.1999.1651]
• 20: 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]
• 21: D. Grigoriev, Testing shift-equivalence of polynomials using quantum machines, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.49-54, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236897]
• 22: James L. Hafner , Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM Journal on Computing, v.20 n.6, p.1068-1083, Dec. 1991 [doi>10.1137/0220067]
• 23: 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]
• 24: P. Hyer. Quantum Algorithms. PhD thesis, Odense University, Denmark, 2000.
• 25: I. M. Isaacs. Algebra: a Graduate Course. Brooks/Cole, 1994.
• 26: G. Ivanyos, F. Magniez, and M. Santha. Efficient algorithms for some instances of the non-Abelian hidden subgroup problem. Los Alamos Preprint Archive, quant-ph/0102014, 2001.
• 27: R. Jozsa. Quantum algorithms and the Fourier transform. Proceedings of the Royal Society of London A, pages 323-337, 1998.
• 28: R. Kannan and A. Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM Journal on Computing, 8(4):499-507, 1979.
• 29: A. Kitaev. Quantum measurements and the Abelian stabilizer problem. Los Alamos Preprint Archive, quant-ph/9511026, 1995.
• 30: A. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191-1249, 1997.
• 31: E. Luks. Computing in solvable matrix groups. In Proceedings of the 33rd Symposium on the Foundations of Computer Science, pages 111-120, 1992.
• 32: M. Mosca. Quantum Computer Algorithms. PhD thesis, University of Oxford, 1999.
• 33: 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
• 34: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 35: M. R.otteler and T. Beth. Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups. Los Alamos Preprint Archive, quant-ph/9812070, 1999.
• 36: 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]
• 37: 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]
• 38: J. Watrous, Succinct quantum proofs for properties of finite groups, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.537, November 12-14, 2000

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  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