### Volume 2014

#### 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.
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)