Quantum lower bounds for the collision and the element distinctness problems
Top Cited Papers
- 1 July 2004
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 51 (4), 595-605
- https://doi.org/10.1145/1008731.1008735
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 Ω( n 2/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.Keywords
This publication has 8 references indexed in Scilit:
- Quantum Complexities of Ordered Searching, Sorting, and Element DistinctnessAlgorithmica, 2002
- Quantum cryptanalysis of hash and claw-free functionsLecture Notes in Computer Science, 1998
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Constructive ApproximationPublished by Springer Science and Business Media LLC ,1993
- Lower bounds for algebraic decision treesJournal of Algorithms, 1982
- A lower bound of 12n2 on linear search programs for the Knapsack problemJournal of Computer and System Sciences, 1978