3 papers
cs.CC2026
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…
quant-ph2026
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…
cs.LG2025
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…