35 citations · 98 across the 9 of their papers we have counts for
9 papers · 1 filter
Tight bounds for hybrid quantum-classical query algorithms
Andris Ambainis, András Gilyén, Martins Kokainis
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most oracle queries; between subroutines, all qubi…
Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
Andris Ambainis, Jānis Iraids, Martins Kokainis
We study how large the certificate complexity of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean fu…
Improved Algorithm and Lower Bound for Variable Time Quantum Search
Andris Ambainis, Martins Kokainis, Jevgēnijs Vihrovs
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable tim…
Strong dispersion property for the quantum walk on the hypercube
Martins Kokainis, Krišjānis Prūsis, Jevgēnijs Vihrovs +2
We show that the discrete time quantum walk on the Boolean hypercube of dimension has a strong dispersion property: if the walk is started in one vertex, then the probability o…
A random-walk benchmark for single-electron circuits
David Reifert, Martins Kokainis, Andris Ambainis +2
Mesoscopic integrated circuits achieving high-fidelity control of elementary quantum systems require new methodology for benchmarking. We offer circuit-level statistical descriptio…
Quadratic speedup for finding marked vertices by quantum walks
Andris Ambainis, András Gilyén, Stacey Jeffery +1
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quan…
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
Andris Ambainis, Kaspars Balodis, Jānis Iraids +3
In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path i…
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
Andris Ambainis, Martins Kokainis
We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and a…
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Scott Aaronson, Andris Ambainis, Jānis Iraids +2
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function is computable by a 1-query quantum alg…