Quantum Algorithm for the Collision Problem

Abstract

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.

8 pages, LaTeX2e

References in corpus (2)

• Quantum Mechanics helps in searching for a needle in a haystack
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem

Cited by in corpus (32)

• Random Oracles in a Quantum World
• The Impact of Quantum Computing on Present Cryptography
• Quantum algorithms for algebraic problems
• The Evolution of Quantum Secure Direct Communication: On the Road to the Qinternet
• Circuit-Based Quantum Random Access Memory for Classical Data
• Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm
• Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis
• Claw Finding Algorithms Using Quantum Walk
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Applying Grover's Algorithm to Hash Functions: A Software Perspective
• Quantum attacks against iterated block ciphers
• Quantum walk algorithm for element distinctness
• Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
• Introducing Structure to Expedite Quantum Search
• Identifying Research Challenges in Post Quantum Cryptography Migration and Cryptographic Agility
• Optimizing Gate Decomposition for High-Level Quantum Programming
• Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
• Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
• Applications of the Adversary Method in Quantum Query Algorithms
• New Developments in Quantum Algorithms
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Element Distinctness Revisited
• Using Quantum Switches to Mitigate Noise in Grover's Search Algorithm
• Thermodynamic Analysis of Classical and Quantum Search Algorithms
• Adversary Lower Bound for Element Distinctness with Small Range
• Efficient unstructured search implementation on current ion-trap quantum processors
• Online-Extractability in the Quantum Random-Oracle Model
• Proof-of-forgery for hash-based signatures
• Quantum-access security of the Winternitz one-time signature scheme
• Revisiting thermodynamics in computation and information theory
• Quantum Money from Quaternion Algebras
• On Finding Quantum Multi-collisions