Quantum lower bound for the collision problem

ABSTRACT

(MATH) The collision problem is to decide whether a function X: { 1,&ldots;,n} → { 1, &ldots;,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Ω(n^1/5) on the number of queries needed by a quantum computer to solve this problem with bounded error probability. The best known upper bound is O(n^1/3), but obtaining any lower bound better than Ω(1) was an open problem since 1997. Our proof uses the polynomial method augmented by some new ideas. We also give a lower bound of Ω(n^1/7) for the problem of deciding whether two sets are equal or disjoint on a constant fraction of elements. Finally we give implications of these results for quantum complexity theory.

REFERENCES

• 1: Andris Ambainis, Quantum lower bounds by quantum arguments, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.636-643, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335394]
• 2: S. Bakhtiari, R. Safavi-Naini, and J. Pieprzyk. Cryptographic hash functions: a survey. Technical Report 95-09, Department of Computer Science, University of Wollongong, July 1995. Available at ftp://ftp.cs.uow.edu.au/pub/papers/1995/tr-95-09.ps.Z.
• 3: Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum Lower Bounds by Polynomials, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.352, November 08-11, 1998
• 4: 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]
• 5: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 6: Gilles Brassard , Peter Høyer , Alain Tapp, Quantum cryptanalysis of hash and claw-free functions, ACM SIGACT News, v.28 n.2, p.14-19, June 1997 [doi>10.1145/261342.261346]
• 7: Harry Buhrman , Ronald de Wolf , Christoph Dürr , Mark Heiligman , Peter Hyer , Frédéric Magniez , Miklos Santha, Quantum Algorithms for Element Distinctness, Proceedings of the 16th Annual Conference on Computational Complexity, p.131, June 18-21, 2001
• 8: Harry Buhrman , Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, v.288 n.1, p.21-43, 9 October 2002 [doi>10.1016/S0304-3975(01)00144-X]
• 9: E. W. Cheney. Introduction to approximation theory, McGraw-Hill, 1966.
• 10: I. B. Damgård. Collision free hash functions and public key signature schemes. Proceedings of Eurocrypt'87, Volume 304 of Lecture Notes in Computer Science (Springer-Verlag), 1988.
• 11: H. Ehlich and K. Zeller. Schwankung von Polynomen zwischen Gitterpunkten. (MATH)ematische Zeitschrift, 86:41--44, 1964.
• 12: 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]
• 13: 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]
• 14: 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]
• 15: E. Kashefi, A. Kent, V. Vedral, and K. Banaszek. On the power of quantum oracles, 2001. quant-ph/0109104.
• 16: A. Kitaev. Quantum measurements and the abelian stabilizer problem. Electronic Colloquium on Computational Complexity (ECCC) 3(3), 1996. quant-ph/9511026.
• 17: M. Minsky and S. Papert. Perceptrons, MIT Press, 1988. First appeared in 1968.
• 18: National Science Foundation. Quantum Information Science, Report of the NSF Workshop, Arlington, VA, October 28--29, 1999. Available at www.nsf.gov/pubs/2000/nsf00101/nsf00101.htm.
• 19: Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing, v.20 n.6, p.999-1007, Dec. 1991 [doi>10.1137/0220062]
• 20: Noam Nisan , Mario Szegedy, On the degree of Boolean functions as real polynomials, Computational Complexity, v.4 n.4, p.301-313, Oct. 1994 [doi>10.1007/BF01263419]
• 21: E. Rains. Talk given at AT&T, Murray Hill, New Jersey, on March 12, 1997.
• 22: T. J. Rivlin and E. W. Cheney. A comparison of Uniform Approximations on an interval and a finite subset thereof. SIAM Journal on Numerical Analysis, 3(2):311--320, 1966.
• 23: Amit Sahai , Salil Vadhan, A Complete Promise Problem for Statistical Zero-Knowledge, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.448, October 19-22, 1997
• 24: Y. Shi. Quantum lower bounds for the collision and the element distinctness problems. Manuscript, 2001. quant-ph/0112086.
• 25: 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]
• 26: D. Simon. On the power of quantum computation. Proceedings of FOCS'94, pages 116--123, 1994.
• 27: 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.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Boundary value problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Experimentation, Performance, Theory