194 citations · 1.9k across the 115 of their papers we have counts for
4 papers · 2 filters
On the Role of Problem Structure in Single-Layer QAOA
Guilherme Adamatti Bridi, Franklin de Lima Marquezino, Andris Ambainis
Problem structure is regarded as a key factor influencing the performance of the Quantum Approximate Optimization Algorithm (QAOA), yet it remains an informal notion without a prec…
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…