Quantum Algorithms for Element Distinctness
arXiv:quant-ph/0007016 · doi:10.1137/S0097539702402780
Abstract
We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hoyer, and Tapp, and imply an O(N^{3/4} log N) quantum upper bound for the element distinctness problem in the comparison complexity model (contrasting with Theta(N log N) classical complexity). We also prove a lower bound of Omega(N^{1/2}) comparisons for this problem and derive bounds for a number of related problems.
arXiv comment15 pages. Supersedes quant-ph/007016v1 and quant-ph/0006136
References in corpus (1)
Cited by in corpus (18)
- Search via Quantum Walk
- Efficient Distributed Quantum Computing
- Hitting time for quantum walks on the hypercube
- Quantum walks with infinite hitting times
- Quantum walks on quotient graphs
- Claw Finding Algorithms Using Quantum Walk
- Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
- Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates
- Deterministic quantum search with adjustable parameters: implementations and applications
- Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
- Quantum property testing for bounded-degree graphs
- Element Distinctness Revisited
- Quantum Algorithm for Triangle Finding in Sparse Graphs
- Optimal exact quantum algorithm for the promised element distinctness problem
- Lower bounds for adiabatic quantum algorithms by quantum speed limits
- Quantum divide and conquer
- Derandomization of quantum algorithm for triangle finding
- Quantum Algorithms for Finding Constant-sized Sub-hypergraphs