Hidden translation and orbit coset in quantum computing

ABSTRACT

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z pⁿ, whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N, for any solvable normal subgroup N of G.

REFERENCES

• 1: D. Aharonov. Quantum computation -- A review. In Annual Review of Computational Physics, volume VI. World Scientific, 1998.
• 2: 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]
• 3: 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
• 4: H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87(16), 2001. Article 167902.
• 5: 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]
• 6: L. Babai and E. Szemerédi. On the complexity of matrix group problems I. In Proc. 25th FOCS, pages 229--240, 1984.
• 7: K. Cheung and M. Mosca. Decomposing finite abelian groups. J. Quantum Inf. Comp., 1(3), 2001.
• 8: Wim van Dam , Sean Hallgren , Lawrence Ip, Quantum algorithms for some hidden shift problems, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 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: D. Gottesman and I. Chuang. Quantum digital signatures. Technical report, Quantum Physics e-Print archive, 2001. http://xxx.lanl.gov/abs/quant-ph/ 0105032.
• 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 , 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]
• 13: Gábor Ivanyos , Frédéric Magniez , Miklos Santha, Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.263-270, July 2001, Crete Island, Greece [doi>10.1145/378580.378679]
• 14: A. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. Technical report, Quantum Physics e-Print archive, 1995. http://xxx.lanl.gov/ abs/quant-ph/9511026.
• 15: A. Yu. Kitaev , A. H. Shen , M. N. Vyalyi, Classical and Quantum Computation, American Mathematical Society, Boston, MA, 2002
• 16: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 17: Markus Püschel , Martin Rötteler , Thomas Beth, Fast Quantum Fourier Transforms for a Class of Non-Abelian Groups, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.148-159, November 15-19, 1999
• 18: J. Preskill. Quantum information and computation. http://www.theory.caltech.edu/people/preskill/ ph229, 1998.
• 19: M. Rötteler and T. Beth. Polynomial-time solution to the Hidden Subgroup Problem for a class of non-abelian groups. Technical report, Quantum Physics e-Print archive, 1998. http://xxx.lanl.gov/ abs/quant-ph/9812070.
• 20: 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]
• 21: 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]
• 22: M. Sudan. Notes on algebra. Lecture 2.5 of the course Algorithmic Introduction to Coding Theory. Course notes at http://theory.lcs.mit.edu/~madhu/FT01.
• 23: 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms