Short answer: In 1997 Brassard, Hoyer and Tapp gave a quantum algorithm that finds collisions in a function using about the cube root of N/r evaluations, where classical methods need the square root. A 2002 paper showed this is the best possible for quantum algorithms in the black-box model. Collisions in hash functions matter in cryptography, so this result shapes how hash output sizes are assessed, but it is a result about black-box functions.
The collision problem
The 1997 note describes an r-to-one function, where every element in the image has exactly r preimages, given as a black box so that the only way to learn about it is by evaluating it. For a two-to-one function, the most efficient classical algorithm needs an expected order of the square root of N evaluations, where N is the domain size. The note says the problem is of interest in cryptology because hash functions appear in many protocols whose security depends on the presumed difficulty of finding collisions.
The quantum algorithm
The authors give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O((N/r)^(1/3)) expected function evaluations. For a black box, they state this is more efficient than the best possible classical algorithm, even allowing probabilism. The approach uses Grover's search algorithm in a novel way. The same technique gives an algorithm for finding claws in pairs of functions, which they say has consequences for classical signature and bit commitment schemes, and they exhibit a space-time tradeoff.
A matching lower bound
A 2002 paper notes that classical algorithms need and suffice with order of the square root of n/r evaluations. Before that, Aaronson had shown a lower bound of order (n/r)^(1/5) for quantum algorithms. The 2002 paper improves this to a tight bound: any error-bounded quantum algorithm distinguishing a one-to-one function from an r-to-one function must evaluate it order (n/r)^(1/3) times, so finding a collision requires that many evaluations. The paper also describes the related element distinctness problem, where a different use of Grover's algorithm makes order n^(3/4) log n comparisons.
Why the cube root matters for hash functions
Classically, finding a collision in a two-to-one black-box function takes on the order of the square root of N evaluations, a figure that already drives how long hash outputs need to be. The 1997 note shows that Grover search, applied in a new way, lowers the exponent from one half to one third in the black-box model. The 2002 paper's tight bound then tells readers that no further black-box improvement of this kind is possible, so any gain beyond it would have to exploit the internal structure of a particular function. The 1997 authors also point to claw finding, the task of locating pairs from two functions that agree, and say it affects classical signature and bit commitment schemes that rely on claw-freeness.
What this does not tell you
These results assume a black-box function and count evaluations only. They do not account for the memory the algorithm needs, which the 1997 note addresses only through a space-time tradeoff, and they say nothing about a specific hash function or a built quantum computer.
FAQ
What is a collision?
Two different inputs that produce the same output of a function.
How much faster is the quantum algorithm?
About the cube root of N/r evaluations, against the square root classically, in the 1997 black-box analysis.
Can it be improved?
Not in the black-box model. The 2002 paper proves a matching lower bound.
Which algorithm does it build on?
Grover's search algorithm, used in a new way.
Does this break hash functions?
These papers do not claim that. They concern black-box evaluation counts.
All field notes