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

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.

21 pages

References in corpus (2)

• Quantum query complexity of state conversion
• Span-program-based quantum algorithm for the rank problem

Cited by in corpus (10)

• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Nested Quantum Walks with Quantum Data Structures
• Quantum Walks and Electric Networks
• A learning graph based quantum query algorithm for finding constant-size subgraphs
• Applications of the Adversary Method in Quantum Query Algorithms
• A quantum query algorithm for the graph collision problem
• Optimal parallel quantum query algorithms
• Adversary Lower Bound for the Orthogonal Array Problem
• Span-program-based quantum algorithm for tree detection
• On the Power of Non-Adaptive Learning Graphs