Hybrid Quantum-classical Algorithm For Near-optimal Planning In Pomdps

Abstract

Reinforcement learning (RL) provides a principled framework for decision-making in partially observable environments, which can be modeled as Markov decision processes and compactly represented through dynamic decision Bayesian networks. Recent advances demonstrate that inference on sparse Bayesian networks can be accelerated using quantum rejection sampling combined with amplitude amplification, leading to a computational speedup in estimating acceptance probabilities.\\ Building on this result, we introduce Quantum Bayesian Reinforcement Learning (QBRL), a hybrid quantum-classical look-ahead algorithm for model-based RL in partially observable environments. We present a rigorous, oracle-free time complexity analysis under fault-tolerant assumptions for the quantum device. Unlike standard treatments that assume a black-box oracle, we explicitly specify the inference process, allowing our bounds to more accurately reflect the true computational cost. We show that, for environments whos

Stats

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

Related papers

• Quantum Framework For Reinforcement Learning: Integrating Markov Decision Process, Quantum Arithmetic, And Trajectory Search (2024)0.00
• A Bit Of Freedom Goes A Long Way: Classical And Quantum Algorithms For Reinforcement Learning Under A Generative Model (2025)0.00
• Accelerating Quantum Reinforcement Learning With A Quantum Natural Policy Gradient Based Approach (2025)0.00
• From Classical Data To Quantum Advantage -- Quantum Policy Evaluation On Quantum Hardware (2025)0.00
• Quantum Policy Iteration Via Amplitude Estimation And Grover Search -- Towards Quantum Advantage For Reinforcement Learning (2022)0.00
• Quantum Reinforcement Learning By Adaptive Non-local Observables (2025)2.26
• Quantum Algorithms For Reinforcement Learning With A Generative Model (2021)0.00
• MADQRL: Distributed Quantum Reinforcement Learning Framework For Multi-agent Environments (2026)0.00