31 citations · 199 across the 33 of their papers we have counts for
42 papers
Tight Quantum Lower Bound for k-Distinctness
Aleksandrs Belovs
In this paper, we introduce a new quantum query lower bound framework. It is inspired by Zhandry's compressed oracle technique, but it also subsumes the polynomial method as a spec…
Space-Efficient Quantum Error Reduction without log Factors
Aleksandrs Belovs, Stacey Jeffery
Given an algorithm that outputs the correct answer with bounded error, say , it is sometimes desirable to reduce this error to some arbitrarily small -- e.g., if…
Quantum algorithms for Hopcroft's problem
Vladimirs Andrejevs, Aleksandrs Belovs, Jevgēnijs Vihrovs
In this work we study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. Given points and lines in the plane, the task is t…
Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem
Aleksandrs Belovs
Up to now, relatively few exponential quantum speed-ups have been achieved. Out of them, the welded tree problem (Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman'2003) is one o…
On the quantum time complexity of divide and conquer
Jonathan Allcock, Jinge Bao, Aleksandrs Belovs +2
We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimi…
Taming Quantum Time Complexity
Aleksandrs Belovs, Stacey Jeffery, Duyal Yolcu
Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors throug…