Quantum Algorithm for k-distinctness with Prior Knowledge on the Input

2011/08/15 by Aleksandrs Belovs, Belovs, Aleksandrs, Troy Lee +1 · 4 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.1108.3022

21 pages

arxiv created 2011/08/15 · openalex publication_date 2011/08/15 · arxiv updated 2011/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

It is known that the dual of the general adversary bound can be used to build quantum query algorithms with optimal complexity. Despite this result, not many quantum algorithms have been designed this way. This paper shows another example of such algorithm. We use the learning graph technique from arXiv:1105.4024 to give a quantum algorithm for k-distinctness problem that runs in o(n^3/4) queries, for a fixed k, given some prior knowledge on the structure of the input. The best known quantum algorithm for the unconditional problem uses O(n^k/(k+1)) queries.

Citations

• Span Programs for Functions with Constant-Sized 1-certificates

Cited by

• Adversary Lower Bound for the Orthogonal Array Problem
• A quantum query algorithm for the graph collision problem
• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Applications of the Adversary Method in Quantum Query Algorithms

Related

• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Applications of the Adversary Method in Quantum Query Algorithms
• Exact quantum query complexity of EXACT and THRESHOLD
• Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester
• Quantum algorithms through graph composition