Exponential Improvements For Quantum-accessible Reinforcement Learning

Abstract

Quantum computers can offer dramatic improvements over classical devices for data analysis tasks such as prediction and classification. However, less is known about the advantages that quantum computers may bring in the setting of reinforcement learning, where learning is achieved via interaction with a task environment. Here, we consider a special case of reinforcement learning, where the task environment allows quantum access. In addition, we impose certain "naturalness" conditions on the task environment, which rule out the kinds of oracle problems that are studied in quantum query complexity (and for which quantum speedups are well-known). Within this framework of quantum-accessible reinforcement learning environments, we demonstrate that quantum agents can achieve exponential improvements in learning efficiency, surpassing previous results that showed only quadratic improvements. A key step in the proof is to construct task environments that encode well-known oracle problems, such

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keydunjko2017exponential

Related papers

• Quantum-enhanced Machine Learning (2016)19.33
• Quantum Algorithms For Reinforcement Learning With A Generative Model (2021)0.00
• Quantum Policy Iteration Via Amplitude Estimation And Grover Search -- Towards Quantum Advantage For Reinforcement Learning (2022)0.00
• On The Convergence Of Projective-simulation-based Reinforcement Learning In Markov Decision Processes (2019)8.35
• From Classical Data To Quantum Advantage -- Quantum Policy Evaluation On Quantum Hardware (2025)0.00
• Efficient Quantum Recurrent Reinforcement Learning Via Quantum Reservoir Computing (2023)0.00
• Benchmarking Quantum Reinforcement Learning (2025)0.00
• A Survey On Quantum Reinforcement Learning (2022)0.00