31 citations · 49 across the 3 of their papers we have counts for
4 papers · 1 filter
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…
Quantum Algorithm for Monotonicity Testing on the Hypercube
Aleksandrs Belovs, Eric Blais
In this note, we develop a bounded-error quantum algorithm that makes queries to a Boolean function , accepts a monotone function, and reje…
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…