Adversary Lower Bound for Element Distinctness with Small Range

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.

22 pages. v2: one figure added, updated references, and minor typos fixed. v3: minor typos fixed

References in corpus (3)

• Optimal parallel quantum query algorithms
• Adversary Lower Bound for the Orthogonal Array Problem
• Symmetry-assisted adversaries for quantum state generation

Cited by in corpus (2)

• Quantum attacks against iterated block ciphers
• A note about claw function with a small range