Volume 2014
Article 4
Published by the Department of Computer Science, The University of Chicago.
Quantum Adversary Lower Bound for Element Distinctness with Small Range
Ansis Rosmanis
David R. Cherlton School of Computer Science, and
Institute of Quantum Computing
University of Waterloo
Waterloo, Ont.
Canada
ansis DOT rosmanis AT gmail DOT com
July 10, 2014
Abstract
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 $\Theta(N^{2/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 $\Omega(N^2)$.
We construct a tight $\Omega(N^{2/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)
Submitted March 5, 2014, revised May 12, 2014, published July 10, 2014.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 3
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 5
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2014
Published articles
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif)
Licensed under a Creative Commons Attribution License