Quantum algorithms for some hidden shift problems

ABSTRACT

Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structure of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation.In this paper, we present three examples of "unknown shift" problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.

REFERENCES

• 1: M. Abadi , J. Feigenbaum, Secure circuit evaluation, Journal of Cryptology, v.2 n.1, p.1-12, 1990 [doi>10.1007/BF02252866]
• 2: Eric Bach , Jeffrey Shallit, Algorithmic number theory, MIT Press, Cambridge, MA, 1996
• 3: 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]
• 4: J. Niel de Beaudrap, Richard Cleve, and John Watrous. Sharp quantum vs. classical query complexity separations. quant-ph archive no. 0011065, 2001. Journal version to appear in Algorithmica.
• 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: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 7: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 8: 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
• 9: Dan Boneh , Richard J. Lipton, Algorithms for Black-Box Fields and their Application to Cryptography (Extended Abstract), Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.283-297, August 18-22, 1996
• 10: Richard Cleve, The Query Complexity of Order-Finding, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, p.54, July 04-07, 2000
• 11: R. Cleve , J. Watrous, Fast parallel circuits for the quantum Fourier transform, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.526, November 12-14, 2000
• 12: Wim van Dam. Quantum algorithms for weighing matrices and quadratic residues. quant-ph archive no. 0008059, 2000. Journal version to appear in Algorithmica.
• 13: Wim van Dam and Sean Hallgren. Efficient Quantum Algorithms for Shifted Quadratic Character Problems. quant-ph archive no. 0011067, 2000.
• 14: Wim van Dam and Gadiel Seroussi. Efficient Quantum Algorithms for Estimating Gauss Sums. quant-ph archive no. 0207131, 2002.
• 15: Ivan Damgård, On the Randomness of Legendre and Jacobi Sequences, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.163-172, August 21-25, 1988
• 16: Mark Ettinger and Peter Høyer. On Quantum Algorithms for Noncommutative Hidden Subgroups. quant-ph archive no. 9807029, 1998.
• 17: Mark Ettinger, Peter Høyer and Emanuel Knill. Hidden subgroup states are almost orthogonal. quant-ph archive no. 9901034, 1999.
• 18: Katalin Friedl, Frédéric Magniez, Miklos Santha and Pranab Sen. Quantum testers for hidden group properties quant-ph archive no. 0208184, 2002.
• 19: 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]
• 20: Lisa Ruth Hales , Umesh V. Vazirani, The quantum fourier transform and extensions of the abelian hidden subgroup problem, 2002
• 21: L. Hales , S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.515, November 12-14, 2000
• 22: 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]
• 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: Lawrence Ip. Solving Shift Problems and the Hidden Coset Problem Using the Fourier Transform. quant-ph archive no. 0205034, 2002.
• 25: 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]
• 26: Alexei Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. quant-ph archive no. 9511026, 1995.
• 27: Alexei Yu. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191--1249, 1997.
• 28: Rudolf Lidl and Harald Niederreiter. Finite Fields, volume 20 of Encyclopedia of Mathematics and Its Applications. Cambridge, second edition, 1997.
• 29: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 30: 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
• 31: 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]
• 32: 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]
• 33: Richard Tolimieri, Myoung An, and Chao Lu. Algorithms for Discrete Fourier Transform and Convolution. Springer-Verlag, 1989.
• 34: 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.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Algorithms, Theory