194 citations · 1.9k across the 115 of their papers we have counts for
99 papers · 1 filter
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…
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…
Quantum computing and artificial intelligence: status and perspectives
Giovanni Acampora, Andris Ambainis, Natalia Ares +36
This white paper discusses and explores the various points of intersection between quantum computing and artificial intelligence (AI). It describes how quantum computing could supp…
Quantum Search on Bipartite Multigraphs
Gustavo Alves Bezerra, Andris Ambainis, Renato Portugal
Quantum walks provide a powerful framework for achieving algorithmic speedup in quantum computing. This paper presents a quantum search algorithm for 2-tessellable graphs, a genera…
Challenges and Opportunities in Quantum Optimization
Amira Abbas, Andris Ambainis, Brandon Augustino +43
Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. As such, a widespread interest in quantum a…
A hybrid quantum-classical approach for inference on restricted Boltzmann machines
Mārtiņš Kālis, Andris Locāns, Rolands Šikovs +2
Boltzmann machine is a powerful machine learning model with many real-world applications, for example by constructing deep belief networks. Statistical inference on a Boltzmann mac…
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…
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
Andris Ambainis, Aleksandrs Belovs
While it is known that there is at most a polynomial separation between quantum query complexity and the polynomial degree for total functions, the precise relationship between the…
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…
Quantum speedup for track reconstruction in particle accelerators
Duarte Magano, Akshat Kumar, Mārtiņš Kālis +10
To investigate the fundamental nature of matter and its interactions, particles are accelerated to very high energies and collided inside detectors, producing a multitude of other…
A note about claw function with a small range
Andris Ambainis, Kaspars Balodis, Jānis Iraids
In the claw detection problem we are given two functions and (, ), and we have to determine if there is exist such th…
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…
Quantum Lower Bounds for 2D-Grid and Dyck Language
Andris Ambainis, Kaspars Balodis, Jānis Iraids +2
We show quantum lower bounds for two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of…
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…
Understanding Quantum Algorithms via Query Complexity
Andris Ambainis
Query complexity is a model of computation in which we have to compute a function of variables which can be accessed via queries. The complexity of an a…
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…
Strong supremacy of quantum systems as communication resource
Maria Quadeer, Manik Banik, Andris Ambainis +1
We investigate the task of -level random access codes (-RACs) and consider the possibility of encoding classical strings of -level symbols (dits) into a quantum system of…
Optimal one-shot quantum algorithm for EQUALITY and AND
Andris Ambainis, Janis Iraids
We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function on an input $x\in\{0,…
Exact quantum query complexity of
Andris Ambainis, Jānis Iraids, Daniel Nagaj
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly or of the inp…
Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities
Andris Ambainis, Manik Banik, Anubhav Chaturvedi +2
One of the fundamental results in quantum foundations is the Kochen-Specker no-go theorem. For the quantum theory, the no-go theorem excludes the possibility of a class of hidden v…