Scott Aaronson
Abstract
Given a function f as an oracle, the collision problem is to find two distinct indexes i and j such that f(i) = f(j), under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower bounds provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. We prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function Ω((n/r)1/3) times, where n is the size of the domain and r|n. This matches an upper bound of Brassard, Høyer, and Tapp. No lower bound better than constant was previously known. Our result also implies a quantum lower bound of Ω(n2/3) queries for the element distinctness problem, which is to determine whether n integers are all distinct. The best previous lower bound was Ω(√n) queries.
- Aaronson, S. 2002. Quantum lower bound for the collision problem. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC-02). ACM, New York, 635--642. Google Scholar
- Ambainis, A. 2000. Quantum lower bounds by quantum arguments. In Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing (Portland, Ore.), ACM, New York, 636--643. Google Scholar
- Ambainis, A. 2003a. Quantum lower bounds for collision and element distinctness with small range. Pre-print: quant-ph/0305179.Google Scholar
- Ambainis, A. 2003b. Quantum walk algorithm for element distinctness. Pre-print: quant-ph/0311001.Google Scholar
- Beals, R., Buhrman, H., Cleve, R., Mosca, M., and de Wolf, R. 1998. Quantum lower bounds by polynomials. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 352--361. Google Scholar
- Ben-Or, M. 1983. Lower bounds for algebraic computation trees. In Proceedings of the 15th Annual ACM Symposium on the Theory of Computing (Boston, Mass.), ACM, New York, 80--86. Google Scholar
- Bennett, C. H., Bernstein, E., Brassard, G., and Vazirani, U. 1997. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (Oct.), 1510--1523. Google Scholar
- Brassard, G., Høyer, P., and Tapp, A. 1998. Quantum cryptanalysis of hash and claw-free functions. In Lecture Notes in Computer Science, vol. 1380. Springer-Verlag, New York, 163--169. Google Scholar
- Buhrman, H., Dürr, C., Heiligman, M., Høyer, P., Magniez, F., Santha, M., and de Wolf, R. 2001. Quantum algorithms for element distinctness. In Proceedings of 16th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., Google Scholar
- DeVore, R. A., and Lorentz, G. G. 1993. Constructive approximation. Springer-Verlag, Berlin, Germany.Google Scholar
- Dobkin, D., and Lipton, R. 1978. A lower bound of 1/2n2 on linear search programs for the knapsack problem. J. Comput. Syst. Sci. 16, 413--417.Google Scholar
- Grigni, M., Schulman, L., Vazirani, M., and Vazirani, U. 2001. Quantum mechanical algorithms for the non-Abelian hidden subgroup problem. In Proceedings of 33rd Annual ACM Symposium on Theory of Computing. ACM, New York. Google Scholar
- Grigoriev, D., Karpinski, M., Meyer auf der Heide, F., and Smolensky, R. 1996. A lower bound for randomized algebraic decision trees. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (Philadelphia, pa.), ACM, New York, 612--619. Google Scholar
- Grover, L. K. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM, Symposium on the Theory of Computing (Philadelphia, pa.), ACM, New York, 212--219. Google Scholar
- Høyer, P., Neerbek, J., and Shi, Y. 2002. Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica 34, 4, 429--448.Google Scholar
- Klauck, H. 2003. Quantum time-space tradeoffs for sorting. In Proceedings of the 35th ACM Symposium on Theory of Computing. ACM, New York, 69--76. Google Scholar
- Kutin, S. 2003. A quantum lower bound for the collision problem. Pre-print: quant-ph/0304162.Google Scholar
- Minsky, M., and Papert, S. 1969. Perceptrons. MIT Press, Cambridge, Mass.Google Scholar
- Nisan, N., and Szegedy, M. 1992. On the degree of Boolean functions as real polynomials. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (Victoria, British Columbia, Canada). ACM, New York, 462--467. Google Scholar
- Paturi, R. 1992. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (Victoria, British Columbia, Canada). ACM, New York, 468--474. Google Scholar
- Shi, Y. 2002. Quantum lower bounds on the collision and the element distinctness problems. In Proceedings of the 43st Symposium on Foundations of Computer Science (FOCS) (Vancouver, B.C., Canada). IEEE Computer Society Press, Los Alamitos, Calif., 513--519. Google Scholar
- Shi, Y. 2004. Approximating linear restrictions of Boolean functions. Manuscript.Google Scholar
- Shor, P. W. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (Oct.), 1484--1509. Google Scholar
- Simon, D. R. 1997. On the power of quantum computation. SIAM J. Comput. 26, 5 (Oct.), 1474--1483. Google Scholar
- Steele, J. M., and Yao, A. C. 1982. Lower bounds for algebraic decision trees. J. Algorithms 3, 1, 1--8.Google Scholar
- Watrous, J. 2000. Succinct quantum proofs for properties of finite groups. In Proceedings of the 41st Symposium on Foundations of Computer Science (FOCS) (Redondo Beach, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 537--546. Google Scholar
Index Terms
- Quantum lower bounds for the collision and the element distinctness problems
Recommendations
Quantum lower bounds by polynomials
We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1}N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a ...
Quantum lower bounds by quantum arguments
Special issue on STOC 2000We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with on input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of ...
Quantum Walk Algorithm for Element Distinctness
We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among $N$ given items), we get an $O(N^{2/3})$ query quantum algorithm. This ...
Comments