35 citations · 98 across the 9 of their papers we have counts for
13 papers
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…
Two electrons interacting at a mesoscopic beam splitter
Niels Ubbelohde, Lars Freise, Elina Pavlovska +8
The non-linear response of a beam splitter to the coincident arrival of interacting particles enables numerous applications in quantum engineering and metrology yet poses considera…
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…
All Classical Adversary Methods are Equivalent for Total Functions
Andris Ambainis, Martins Kokainis, Krišjānis Prūsis +2
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{…
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…
Nearly optimal separations between communication (or query) complexity and partitions
Robin Kothari
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a r…
Almost quadratic gap between partition complexity and query/communication complexity
Andris Ambainis, Martins Kokainis
We show nearly quadratic separations between two pairs of complexity measures: 1. We show that there is a Boolean function with where is t…
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…