Adversary Lower Bound for Element Distinctness with Small Range

2014/01/16 by Ansis Rosmanis, Rosmanis, Ansis
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #quant-ph

paper · pdf · doi:10.48550/arxiv.1401.3826

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

openalex publication_date 2014/01/16 · arxiv created 2014/08/01 · arxiv updated 2014/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Θ(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 Ω(N²). We construct a tight Ω(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.

Citations

• Adversary Lower Bound for the Orthogonal Array Problem
• On the Power of Quantum Computation

Related

• Adversary Lower Bound for Element Distinctness
• Adversary Lower Bounds for the Collision and the Set Equality Problems
• Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
• Adversary Lower Bound for the Orthogonal Array Problem
• The General Adversary Bound: A Survey