Quantum Algorithm for the Collision Problem

Details Quantum Algorithm for the Collision Problem Quantum Algorithm for the Collision Problem

1997-05-01

arxiv.org/abs/quant-ph/9705002v1

Physics

Quantum Physics

8 pages, LaTeX2e

Scientific paper

In this note, we give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O((N/r)^(1/3)) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.

Affiliated with

Also associated with

No associations

Rating

Quantum Algorithm for the Collision Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Algorithm for the Collision Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithm for the Collision Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-140445