Quantum Adversary Lower Bound for Element Distinctness with Small Range
The Element Distinctness problem is to decide
whether each character of an input string is unique. The quantum query
complexity of Element Distinctness is known to be Θ(N2/3); the polynomial
method gives a tight lower bound for any input alphabet, while a tight
adversary construction was only known for alphabets of size Ω(N2).
We construct a tight Ω(N2/3) adversary lower
bound for Element Distinctness with minimal non-trivial alphabet size, which
equals the length of the input. This result may help to improve lower bounds
for other related query problems.
The article: PDF (340 KB)
Source material: ZIP (110 KB)
BibTeX entry for this article (285 bytes)
No comments:
Post a Comment