31 citations · 199 across the 33 of their papers we have counts for
5 papers · 2 filters
On the Power of Non-Adaptive Learning Graphs
Aleksandrs Belovs, Ansis Rosmanis
We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only requir…
Adversary Lower Bound for the k-sum Problem
Aleksandrs Belovs, Robert Spalek
We prove a tight quantum query lower bound for the problem of deciding whether there exist numbers among that sum up to a prescribed number, provided that…
Learning-Graph-Based Quantum Algorithm for k-distinctness
Aleksandrs Belovs
We present a quantum algorithm solving the -distinctness problem in queries with a bounded error. This improves the previous -query al…
Adversary Lower Bound for Element Distinctness
Aleksandrs Belovs
In this note we construct an explicit optimal (negative-weight) adversary matrix for the element distinctness problem, given that the size of the alphabet is sufficiently large.
Span programs and quantum algorithms for st-connectivity and claw detection
Aleksandrs Belovs, Ben W. Reichardt
We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for…