Chicago Journal of Theoretical Computer Science

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.
ansis DOT rosmanis AT gmail DOT com

July 10, 2014


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.

Submitted March 5, 2014, revised May 12, 2014, published July 10, 2014.

DOI: 10.4086/cjtcs.2014.004

[] Article 3 [] Article 5
[back] Volume 2014 [back] Published articles
[CJCTS home]