7 papers
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…
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…
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 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…
Quantum Advantages in (n,d)->1 Random Access Codes
Andris Ambainis, Dmitry Kravchenko, Sk Sazim +2
A random access code (RAC), corresponding to a communication primitive with various applications in quantum information theory, is an instance of a preparation-and-measurement scen…