Learning-Graph-Based Quantum Algorithm for k-distinctness

Abstract

We present a quantum algorithm solving the $k$-distinctness problem in $O(n^{1-2^{k-2}/(2^k-1)})$ queries with a bounded error. This improves the previous $O(n^{k/(k+1)})$-query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an $O(\sqrt{n}{\alpha }^{1/6})$ algorithm for the graph collision problem where $\alpha$ is the independence number of the graph.

19 pages, 2 figures, major changes

References in corpus (9)

• Search via Quantum Walk
• Negative weights make adversaries stronger
• Quantum query complexity of state conversion
• Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
• Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
• Quantum lower bounds by quantum arguments
• Quantum algorithms for subset finding
• The Quantum Query Complexity of Algebraic Properties
• Adversary Lower Bound for the k-sum Problem

Cited by in corpus (15)

• Nested Quantum Walks with Quantum Data Structures
• Quantum Walks and Electric Networks
• Variations on Quantum Adversary
• Applications of the Adversary Method in Quantum Query Algorithms
• A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
• Parameterized Quantum Query Complexity of Graph Collision
• Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks
• Adversary Lower Bound for the Orthogonal Array Problem
• Quantum Algorithms for Connectivity and Related Problems
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• Span-program-based quantum algorithm for tree detection
• Quantum Algorithm for Monotonicity Testing on the Hypercube
• On the Power of Non-Adaptive Learning Graphs
• On Finding Quantum Multi-collisions
• Three-state quantum walk on the Cayley Graph of the Dihedral Group