Research map / Reinforcement learning / MDPs and planning
Quantum Algorithms for Finite-horizon Markov Decision Processes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Designs quantum value iteration algorithms (QVI-1 to QVI-4) for time-dependent finite-horizon MDPs in exact-dynamics and generative-model settings, with query/sample complexity speedups in A, S, H, and epsilon plus matching quantum lower bounds up to logs.
Problem
Solving time-dependent, finite-horizon MDPs more efficiently than classical value iteration and generative-model methods, where prior quantum work did not give guarantees for finite-horizon settings.
Approach
Combine quantum maximum searching over actions with quantum mean estimation (QME1/QME2) and a new binary-oracle mean estimation subroutine (QMEBO), adapting classical value iteration, monotonicity, variance reduction and total-variance techniques to obtain quantum query complexities improved in A, S, H, and epsilon.
Key results
- QVI-1 achieves O~(S^2 sqrt(A) H) quantum query complexity for optimal policy and V-value in the exact dynamics setting, versus classical Theta(S^2 A H).
- QVI-2 achieves O~(S^1.5 sqrt(A) H^3 / epsilon) queries for epsilon-optimal policies and values in the exact dynamics setting.
- QVI-3 achieves O~(S sqrt(A) H^3 / epsilon) quantum generative-model sample complexity, and QVI-4 achieves O~(SA H^2.5 / epsilon), versus classical O~(SAH^4/epsilon^2) and O~(SAH^3/epsilon^2) for Q-values in the sample-complexity analysis.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use quantum maximum searching over actions in value iteration | QVI-1 · Exact dynamics; optimal π∗, V∗₀ | query complexity: S2AH -> S2√AH | Helped |
| use quantum mean estimation with binary oracles for transition-value expectations | QVI-2 · Exact dynamics; ϵ-accurate π∗ and {V∗ₕ} | query complexity: S2AH -> S1.5√AH3/ϵ | Helped |
| use quantum mean estimation and quantum maximum searching | QVI-3 · Generative model; π∗, {V∗ₕ} | sample complexity: SAH4/ϵ2 -> S√AH3/ϵ | Helped |
| use variance reduction and total variance techniques with quantum mean estimation | QVI-4 · Generative model; {Q∗ₕ} | sample complexity: SAH4/ϵ2 -> SAH2.5/ϵ | Helped |
Limitations
- Purely theoretical; no numerical experiments or quantum simulations reported.
- Assumes quantum oracle/generative model access and QRAM for encoding transition probabilities, with unit-cost oracle calls.
- QVI-4 gives no speedup in A and lower bounds match only up to H or H^1.5 factors and logs, and only for constant horizon.
Experimental setup
Metrics: quantum query complexity quantum sample complexity asymptotic optimality up to log factors
Baselines: classical value iteration RandomizedFiniteHorizonVI (Sidford et al., 2023) Li et al. 2020 classical sample complexity Wiedemann et al. 2022 quantum Monte Carlo
Builds on: value iteration Durr-Hoyer quantum maximum searching Montanaro quantum mean estimation Sidford et al. variance reduction for finite-horizon MDPs Li et al. 2020 generative model sample complexity
Closest papers by meaning
- Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes (ICML 2025 · similarity 0.89)
- Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret (ICML 2024 · similarity 0.88)
- Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach (ICML 2025 · similarity 0.87)
- Multi-agent Markov Entanglement (NeurIPS 2025 · similarity 0.87)
- One More Time: Revisiting Neural Quantum States from a Reinforcement Learning Perspective (NeurIPS 2026 · similarity 0.86)
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.