Learning-graph-based Quantum Algorithm for k-distnictness
Author:
Preprint
Abstract
In this paper, 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=\alpha(G)$ is the independence number of the graph.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Span programs for functions with constant-sized 1-certificates2012
- Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection2012
- Quantum Algorithms for the Triangle ProblemSIAM Journal on Computing, 2007
- Quantum Walk Algorithm for Element DistinctnessSIAM Journal on Computing, 2007
- Quantum lower bounds for the collision and the element distinctness problemsJournal of the ACM, 2004
- Quantum Lower Bounds by Quantum ArgumentsJournal of Computer and System Sciences, 2002