194 citations · 1.9k across the 115 of their papers we have counts for
126 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…
Optimal bounds on the classical value of the repeated CHSH game
Andris Ambainis
We show that the maximum winning probability in the repeated CHSH game for classical strategies is at most . Together with a matching lower bou…
A Hierarchy for Constant Communication Complexity
Andris Ambainis, Hartmut Klauck, Debbie Lim
Similarly to the Chomsky hierarchy, we offer a classification of communication complexity measures such that these measures are organized into equivalence classes. Different from p…
A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
Andris Ambainis, Joao F. Doriguello, Debbie Lim
We propose novel classical and quantum online algorithms for learning finite- and infinite-horizon Markov Decision Processes (MDPs). Our algorithms are based on a hybrid online-off…
Quantum Algorithm for Apprenticeship Learning
Andris Ambainis, Debbie Lim
Apprenticeship learning is a method commonly used to train artificial intelligence systems to perform tasks that are challenging to specify directly using traditional methods. Base…