A new quantum lower bound framework proves a tight bound for k-Distinctness.
Quantum walk algorithm for element distinctness
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N^{2/3}) query quantum algorithm. This improves the previous O(N^{3/4}) query quantum algorithm of Buhrman et.al. (quant-ph/0007016) and matches the lower bound by Shi (quant-ph/0112086). The algorithm also solves the generalization of element distinctness in which we have to find k equal items among N items. For this problem, we get an O(N^{k/(k+1)}) query quantum algorithm.
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 3roles
background 1polarities
background 1representative citing papers
A matrix-discrepancy argument proves tight one-way quantum lower bounds for collision finding (Ω(N^{1/4})) and for streaming triangle finding (Ω(√Δ_V)) where Boolean-Hidden-Matching reductions fail.
A pseudo-unitary quasiperiodic quantum walk model exhibits a novel mobility edge sharply dividing metallic and insulating phases plus a second transition unique to discrete time, with PT-symmetry breaking quantified by spectral winding number.
citing papers explorer
-
Tight Quantum Lower Bound for k-Distinctness
A new quantum lower bound framework proves a tight bound for k-Distinctness.
-
Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
A matrix-discrepancy argument proves tight one-way quantum lower bounds for collision finding (Ω(N^{1/4})) and for streaming triangle finding (Ω(√Δ_V)) where Boolean-Hidden-Matching reductions fail.
-
Mobility edges in pseudo-unitary quasiperiodic quantum walks
A pseudo-unitary quasiperiodic quantum walk model exhibits a novel mobility edge sharply dividing metallic and insulating phases plus a second transition unique to discrete time, with PT-symmetry breaking quantified by spectral winding number.