Quantum Lower Bound for the Collision Problem

2001/11/20 by Scott Aaronson, Aaronson, Scott · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0111102

10 pages plus 4 page appendix, no figures. Submitted to STOC'2002

arxiv created 2001/11/20 · arxiv updated 2009/11/30

Abstract

The collision problem is to decide whether a function X:1,..,n->1,..,n is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Theta(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 Theta(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 Theta(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.

Cited by

• Lecture Notes on Quantum Algorithms

Related

• Adversary Lower Bounds for the Collision and the Set Equality Problems
• A quantum lower bound for the collision problem
• A Polynomial-Time Quantum Algorithm for Collision Problem
• A Note on the Quantum Collision and Set Equality Problems
• On Finding Quantum Multi-collisions