Learning-Graph-Based Quantum Algorithm for k-Distinctness
Author:
- Aleksandrs BelovsABAleksandrs Belovs
- 1 October 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 207-216
Abstract
We present a quantum algorithm solving the k-distinctness problem in a less number of queries than the previous algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Span programs for functions with constant-sized 1-certificates2012
- Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection2012
- Reflections for quantum query algorithms2011
- Search via quantum walk2007
- 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
- Complexity measures and decision tree complexity: a surveyTheoretical Computer Science, 2002
- Quantum Lower Bounds by Quantum ArgumentsJournal of Computer and System Sciences, 2002
- Tight Bounds on Quantum SearchingFortschritte der Physik, 1998