Aleksandrs Belovs

most citedLearning-Graph-Based Quantum Algorithm for k-distinctness

31 citations · 49 across the 3 of their papers we have counts for

collaborators

3 papers

quant-ph2015★ 11 cited

Variations on Quantum Adversary

Aleksandrs Belovs

The (negative-weighted) quantum adversary bound is a tight characterisation of the quantum query complexity for any partial function. We analyse the extent to which this bound can…

quant-ph2012★ 7 cited

Adversary Lower Bound for the k-sum Problem

Aleksandrs Belovs, Robert Spalek

We prove a tight quantum query lower bound $Ω (n^{k / (k + 1)})$ for the problem of deciding whether there exist $k$ numbers among $n$ that sum up to a prescribed number, provided that…

quant-ph2012★ 31 cited

Learning-Graph-Based Quantum Algorithm for k-distinctness

Aleksandrs Belovs

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 al…