Paper deep dive
Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model
Joao F. Doriguello
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/5/2026, 4:33:17 AM
Summary
This paper proposes improved quantum algorithms for computing approximate optimal policies in finite-horizon and infinite-horizon discounted Markov Decision Processes (MDPs) under a generative model. By combining standard value iteration with quantum mean estimation and quantum maximum finding, and enhancing these with classical techniques like monotonicity and total-variance reduction, the authors achieve query complexities that approach established quantum lower bounds.
Entities (11)
Relation Signals (7)
Joao F. Doriguello → affiliatedwith → HUN-REN Alfréd Rényi Institute of Mathematics
confidence 99% · Joao F. Doriguello doriguello@renyi.hu HUN-REN Alfréd Rényi Institute of Mathematics
Quantum Algorithms → appliedto → Markov Decision Processes
confidence 95% · propose new quantum algorithms for computing approximate optimal policies... study two types of MDPs
Infinite-horizon discounted MDPs → istypeof → Markov Decision Processes
confidence 95% · infinite-horizon discounted MDPs... are thus described by tuples
Finite-horizon MDPs → istypeof → Markov Decision Processes
confidence 95% · Central to this work are finite-horizon MDPs
Quantum Algorithms → usessubroutine → Quantum Maximum Finding
confidence 90% · Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding
Quantum Algorithms → usessubroutine → Quantum Mean Estimation
confidence 90% · Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation
Quantum Algorithms → improvesupon → Classical Algorithms
confidence 85% · Our resulting query complexities improve upon previous works
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy --- a function that tells the agent which action to take. In this work, we study two types of MDPs --- finite-horizon and infinite-horizon discounted --- and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.
Tags
Links
- Source: https://arxiv.org/abs/2608.02826v1
- Canonical: https://arxiv.org/abs/2608.02826v1
Trouble viewing inline? Open PDF directly →
Full Text
107,120 characters extracted from source content.
Expand or collapse full text
Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model Joao F. Doriguello doriguello@renyi.hu HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary Abstract Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy — a function that tells the agent which action to take. In this work, we study two types of MDPs — finite-horizon and infinite-horizon discounted — and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds. 1 Introduction The paradigm of reinforcement learning (RL) sutton1998reinforcement has received much attention recently due to its success in modeling an agent interaction with a dynamical environment aastrom1965optimal ; hu2007markov ; sato2010markov ; bauerle2011markov ; feinberg2012handbook ; bennett2013artificial ; chen2014distributed ; steimle2017markov ; natarajan2022planning and due to its applicability to a wide range of problems sutton1998reinforcement ; Szepesvari2010algorithms ; bertsekas2012dynamic ; bertsekas2022abstract . Such interaction is usually studied using Markov Decision Processes (MDPs) puterman2014markov , a simple yet powerful mathematical abstraction wherein an agent chooses actions given the environment’s state in order to maximise some kind of reward. Despite their versatility, MDPs suffer a “curse of dimensionality” when the number of possible actions or states are sufficiently large, rendering a solution computationally impossible powell2007approximate . Parallel to RL developments, quantum computation nielsen2010quantum has emerged as a new field promised to deliver substantial speedups to traditional problems like factoring shor1994algorithms , unstructured search grover1996fast , and optimisation harrow2009quantum by exploiting quantum mechanics. Quantum machine learning Schuld2015introduction ; Biamonte2017quantum ; Alchieri2021introduction , a subfield of quantum computation, has been consolidated as an area of study that can provide quantum speedups to several traditional machine learning problems lloyd2013quantum ; rebentrost2014quantum ; wiebe2015quantum ; kerenidis2017quantum ; kerenidis2019qmeans ; doriguello2023you , including RL dong2008quantum ; crawford2018reinforcement ; ambainis2025bit . At the same time, new advances in quantum hardware Arute2019quantum ; Saggio2021experimental ; Acharya2025quantum point to a future when quantum computers can become a reality. In this work, we propose novel quantum algorithms to tackle a central problem related to MDPs, obtaining approximately optimal policies, thus alleviating the curse of dimensionality. 1.1 Problem Setup and Previous Works In its most general form, a discrete-time MDP is described by a finite set S of states that the environment can assume and a finite set A of actions that the agent can take, a reward function r:×→[0,1]r:S×A→[0,1] that describes the agent’s reward when choosing action a∈a under the environment’s state s∈s , and stochastic kernels p(⋅|s,a)p(·|s,a) that denote the probability of transitioning to a new state after the reward is obtained. Beyond this general formalisation, there are different subtypes of MDPs depending on the reward criteria the agent must maximise. Central to this work are finite-horizon MDPs, where the agent interacts with the environment for a pre-determined number of steps H called horizon, and infinite-horizon discounted MDPs, where the agent-environment interaction lasts an infinite amount of time but at every time step the received reward is decreased by a discount factor γ∈[0,1)γ∈[0,1). The parameter Γ:=(1−γ)−1 :=(1-γ)^-1 is usually called effective horizon. Finite- and infinite-horizon discounted MDPs are thus described by tuples ⟨,,p,r,H⟩ ,A,p,r,H and ⟨,,p,r,γ⟩ ,A,p,r,γ , respectively. The main agent’s objective when interacting with the environment is to maximise some reward criteria by choosing an appropriate policy π=(πt)tπ=( _t)_t, which is a sequence of probability distributions over A given S called decision rules, i.e., πt:→Δ() _t:S→ (A). The reward criteria for finite-horizon MDPs is the expected sum of rewards under policy π=(πh)h∈[H]π=( _h)_h∈[H] and initial state s∈s , called value function: V0π,H(s)=[∑h=0H−1r(sh,ah)|s0=s,ai∼πi(si),si+1∼p(⋅|si,ai)]. V_0^π,H(s)=E [ _h=0^H-1r(s_h,a_h)~ |~s_0=s,a_i _i(s_i),s_i+1 p(·|s_i,a_i) ]. A policy πεπ is ε -optimal if V0πε,H(s)≥V0π,H(s)−εV_0^π ,H(s)≥ V_0^π,H(s)- for all π and s∈s , and the optimal value function is V0∗,H(s)=supπV0π,H(s)V_0 ,H(s)= _πV_0^π,H(s). A function V:→[0,H]V:S→[0,H] is ε -optimal if ‖V−V0∗,H‖∞≤ε\|V-V_0 ,H\|_∞≤ . On the other hand, the reward criteria for infinite-horizon MDPs is the discounted sum of rewards under policy π=(πt)t∈ℕπ=( _t)_t and initial state s∈s , also called value function: V∞π,γ(s)=[∑t=0∞γtr(st,at)|s0=s,ai∼πi(si),si+1∼p(⋅|si,ai)]. V_∞^π,γ(s)=E [ _t=0^∞γ^tr(s_t,a_t)~ |~s_0=s,a_i _i(s_i),s_i+1 p(·|s_i,a_i) ]. A policy πεπ is ε -optimal if V∞πε,γ(s)≥V∞π,γ(s)−εV_∞^π ,γ(s)≥ V_∞^π,γ(s)- for all π and s∈s , and the optimal value function is V∞∗,γ(s)=supπV∞π,γ(s)V_∞ ,γ(s)= _πV_∞^π,γ(s). A function V:→[0,Γ]V:S→[0, ] is ε -optimal if ‖V−V∞∗,γ‖∞≤ε\|V-V_∞ ,γ\|_∞≤ . One of the fundamental theoretical problems related to MDPs is that of learning an ε -optimal policy and value function. Among the several studied input models, arguably the most important — and the one considered in this work — is the so-called generative model kearns1998finite ; Kearns2002sparse ; kakade2003sample where one has full knowledge of state and action spaces and of the reward function, but the transition probabilities p(⋅|s,a)p(·|s,a) can only be accessed through an oracle. 1.1.1 Classical Setting In the classical setting, i.e., using standard classical computers, generative access to the stochastic kernel p:×→Δ()p:S×A→ (S) is given via an oracle or simulator pC_p that, on input (s,a)∈×(s,a) ×A, returns s′∈s with probability p(s′|s,a)p(s |s,a). One is thus interested in computing an ε -optimal policy with the least amount of queries to oracle pC_p. Classically computing ε -optimal policies under the generative model has been mostly solved for finite- and infinite-horizon discounted MDPs. A long list of works slowly improved the query complexity Kearns1999finite ; Kearns2002sparse ; GheshlaghiAzar2013 ; wang2017randomized ; Sidford2018variance until Sidford et al. sidford2018near and Li et al. li2020breaking obtained sample-optimal algorithms for finite- and infinite-horizon discounted MDPs with query complexity O~(H3SAε2) O ( H^3SA ^2 ) and O~(Γ3SAε2) O ( ^3SA ^2 ), respectively, thus matching the lower bounds from GheshlaghiAzar2013 ; sidford2018near . It is well known puterman2014markov that a solution to the equations below provides optimal value functions: VH(s) V_H(s) =0andVh(s)=maxa∈r(s,a)+∑s′∈p(s′|s,a)Vh+1(s′)∀h∈[H](finite-horizon), =0 V_h(s)= _a \r(s,a)+ _s p(s |s,a)V_h+1(s ) \ ∀ h∈[H] (finite-horizon), V0(s) V_0(s) =0andVt+1(s)=maxa∈r(s,a)+γ∑s′∈p(s′|s,a)Vt(s′)∀t∈ℕ(infinite-horizon). =0 V_t+1(s)= _a \r(s,a)+γ _s p(s |s,a)V_t(s ) \ ∀ t (infinite-horizon). More precisely, V0(s)=V0∗,H(s)V_0(s)=V_0 ,H(s) for finite-horizon MDPs and limt→∞Vt(s)=V∞∗,γ(s) _t→∞V_t(s)=V_∞ ,γ(s) for infinite-horizon discounted MDPs. Moreover, one can show that the sequence of maximums in the above equations form an optimal policy, i.e., πt+1(s)∈argmaxa∈r(s,a)+γ∑s′∈p(s′|s,a)Vt(s′) _t+1(s)∈ *arg\,max_a \r(s,a)+γ _s p(s |s,a)V_t(s )\ and similarly for finite-horizon MDPs. Given sampling access to p, the standard value iteration algorithm puterman2014markov obtains an ε -optimal policy for finite-horizon MDPs by approximating ∑s′∈p(s′|s,a)Vh+1(s′) _s p(s |s,a)V_h+1(s ) up to additive error εH H, to a total query complexity of O(H5SAε2)O ( H^5SA ^2 ). Similarly, in the infinite-horizon discounted setting one approximates ∑s′∈p(s′|s,a)Vt(s′) _s p(s |s,a)V_t(s ) up to additive error εΓ2 ^2 and stops after O(ΓlogΓε)O ( ) iterations, to a total query complexity of O~(Γ7SAε2) O ( ^7SA ^2 ). The algorithms of Sidford et al. sidford2018near are a modern and improved version of the aforementioned standard value iteration algorithm and work111We review the infinite-horizon discounted setting. The finite-horizon case is similar, the main difference being that one starts (and finishes) with H functions. by starting with a function V0V_0 such that 0≤V∞∗,γ(s)−V0(s)≤2ϵ0≤ V ,γ_∞(s)-V_0(s)≤ 2ε and then producing function VTV_T such that 0≤V∞∗,γ(s)−VT(s)≤ϵ0≤ V_∞ ,γ(s)-V_T(s)≤ε, thus halving the initial error. The initial choice V0(s)=0V_0(s)=0 yields a Γ -approximation and by repeating their halving procedure O(ΓlogΓε)O ( ) times, an ε -optimal policy can be obtained. In order to achieve the optimal query complexities O~(H3SAε2) O ( H^3SA ^2 ) and O~(Γ3SAε2) O ( ^3SA ^2 ), Sidford et al. sidford2018near employs three crucial techniques: monotonicity, variance reduction, and total-variance techniques. The monotonicity technique means choosing an approximate value VtV_t and decision rule πt _t such that the monotonicity condition222Here we abuse notation and consider deterministic decision rules πt:→ _t:S . Vt(s)≤r(s,πt(s))+γ∑s′∈p(s′|s,πt(s))Vt(s′) V_t(s)≤ r(s, _t(s))+γ _s p(s |s, _t(s))V_t(s ) (1) is maintained throughout all time steps t of the algorithm.333The finite-horizon setting does not require the monotonicity condition since the interaction lasts for a finite number of steps. The monotonicity condition is vital to guarantee that Vt(s)≤V∞πt,γ(s)V_t(s)≤ V_∞ _t,γ(s) and to obtain an ε -optimal policy from an ε -optimal function. Otherwise, an ε -optimal function only yields an Γε -optimal greedy policy in the worst case bertsekas2022abstract . The second technique, variance reduction, rewrites the standard value iteration as Vt+1(s) V_t+1(s) ←maxa∈r(s,a)+∑s′∈p(s′|s,a)V0(s′)+∑s′∈p(s′|s,a)(Vt(s′)−V0(s′)). ← _a \r(s,a)+ _s p(s |s,a)V_0(s )+ _s p(s |s,a)(V_t(s )-V_0(s )) \. The main idea is that the quantity ∑s′∈p(s′|s,a)V0(s′) _s p(s |s,a)V_0(s ) can be computed only once at the beginning of the algorithm using O~(Γ4ϵ2) O ( ^4ε^2 ) samples, which saves a factor of Γ . Regarding the quantity ∑s′∈p(s′|s,a)(Vt(s′)−V0(s′)) _s p(s |s,a)(V_t(s )-V_0(s )), since ‖Vt−V0‖∞≤2ϵ\|V_t-V_0\|_∞≤ 2ε by the monotonicity condition, it can be approximated up to error ϵ2Γ ε2 using O~(Γ2) O( ^2) samples, leading to O~(Γ3) O( ^3) samples after T=O~(Γ)T= O( ) time steps. The third and final technique, total-variance, is based on the fact that the true error accumulates as Γ3/m ^3/m given m samples, much less than the naive sum of estimation errors at each time step. This means that one does not require an update error of ϵ2Γ ε2 at each time step and m=O(Γ3ϵ2)m=O ( ^3ε^2 ) samples suffices for a total error ϵε, thus shaving off the last factor of Γ . 1.1.2 Quantum Setting The quantum equivalent of generative access to p is done through an oracle pQ_p (and its inverse) called quantum accessible-environment wang2021quantum ; wiedemann2022quantum ; jerbi2022quantum ; zhong2023provably which is the unitary operator p:|s⟩|a⟩|0¯⟩→∑s′∈p(s′|s,a)|s⟩|a⟩|s′⟩∀(s,a)∈×. _p:|s |a | 0 → _s p(s |s,a)|s |a |s ∀(s,a) ×A. If the classical oracle pC_p is itself a computer program and we have access to its source code, then it is straightforward to transform pC_p into its quantum version pQ_p above: one first produces a Boolean circuit (of roughly the same size as the program’s time complexity) that produces the samples s′∼p(⋅|s,a)s p(·|s,a) and then replaces all classical gates with their quantum counterparts as described, for example, in (nielsen2010quantum, , Section 1.4.1). The same fundamental problem of learning an ε -optimal policy can thus be proposed in a quantum setting where one has access to the oracle pQ_p and its inverse. The first work to tackle this problem in the infinite-horizon discounted setting was due to Wang et al. wang2021quantum , who obtained the query upper bound O~(minΓ1.5SAε,Γ3SAε) O ( \ ^1.5SA , ^3S A \ ) and the query lower bound Ω~(Γ1.5SAε) ( ^1.5S A ). The finite-horizon setting, on the other hand, has been more recently addressed by Luo et al. luo2025quantum and Ambainis et al. ambainis2025bit , both works proposing query upper bounds of O~(minH2.5SAε,H3SAε) O ( \ H^2.5SA , H^3S A \ ). Luo et al. luo2025quantum further proved a query lower bound of Ω~(H1.5SAε) ( H^1.5S A ). The quantum algorithms of wang2021quantum ; luo2025quantum ; ambainis2025bit are the combination of two different algorithms. The first one is a quantised version of the aforementioned standard value iteration puterman2014markov . The quantum advantage comes from estimating ∑s′∈p(s′|s,a)Vt(s′) _s p(s |s,a)V_t(s ) up to additive error εΓ using a quantum mean estimation subroutine montanaro2015quant ; hamoudi2019quantum ; hamoudi2021quantum2 ; hamoudi2021quantum ; Kothari2023mean with O(Γ2ε)O ( ^2 ) queries to p,p†Q_p,Q_p and nesting it into the quantum maximum finding subroutine of Dür and Høyer durr1996quantum in order to find Vt+1(s)V_t+1(s), which uses O(Γ2Aε)O ( ^2 A ) queries to p,p†Q_p,Q_p in total. Summing over all s∈s and O(ΓlogΓε)O ( ) time steps leads to the final complexity O~(Γ3SAε) O ( ^3S A ). Wang et al. wang2021quantum maintain the monotonicity condition from (1) throughout in order to obtain an ε -optimal policy from an ε -optimal function. The corresponding algorithm for finite-horizon MDPs luo2025quantum ; ambainis2025bit is quite similar, with H replacing Γ (and without the need for monotonicity). The second algorithms of wang2021quantum ; luo2025quantum ; ambainis2025bit are a quantised version of the modern value iteration algorithm of Sidford et al. sidford2018near explained in the previous section. In the infinite-horizon discounted setting, assuming an initial function V0V_0 such that 0≤V∞∗,γ(s)−V0(s)≤2ϵ0≤ V_∞ ,γ(s)-V_0(s)≤ 2ε, the quantities ∑s′∈p(s′|s,a)(Vt(s′)−V0(s′)) _s p(s |s,a)(V_t(s )-V_0(s )) are estimated using quantum mean estimation up to error ϵ2Γ ε2 using O~(Γ) O( ) queries to p,p†Q_p,Q_p , for a total of O~(Γ2SA) O( ^2SA) queries across all (s,a)∈×(s,a) ×A and O~(Γ) O( ) time steps. On the other hand, the quantities ∑s′∈p(s′|s,a)V0(s′) _s p(s |s,a)V_0(s ) are estimated, using a variance-dependent quantum mean estimation subroutine montanaro2015quant ; hamoudi2019quantum ; hamoudi2021quantum2 ; hamoudi2021quantum ; Kothari2023mean , up to additive error O(ϵσ0(s,a)Γ1.5)O ( ε [b] _0(s,a) ^1.5 ) using O~(Γ1.5ϵ) O ( ^1.5ε ) queries to p,p†Q_p,Q_p , where σ0(s,a)=∑s′∈p(s′|s,a)V0(s′)2−(∑s′∈p(s′|s,a)V0(s′))2 _0(s,a)= _s p(s |s,a)V_0(s )^2- ( _s p(s |s,a)V_0(s ) )^2 is the variance of V0V_0. The final query complexity is thus O~(Γ1.5SAϵ) O ( ^1.5SAε ) across all (s,a)∈×(s,a) ×A and since ∑s′∈p(s′|s,a)V0(s′) _s p(s |s,a)V_0(s ) needs to be estimated only once at the start and can be reused at all time steps. By starting with the trivial function V0(s)=0V_0(s)=0 and repeating the error-halving step O(logΓε)O ( ) times, one obtains an ε -optimal policy with O~(Γ1.5SAε) O ( ^1.5SA ) as previously mentioned. For finite-horizon MDPs, one starts with H different functions V0(0),…,VH−1(0)V_0^(0),…,V_H-1^(0) that approximate 0≤Vh∗,H(s)−Vh(0)(s)≤2ϵ0≤ V_h ,H(s)-V_h^(0)(s)≤ 2ε, therefore each quantity ∑s′∈p(s′|s,a)Vh+1(0)(s′) _s p(s |s,a)V_h+1^(0)(s ) must be estimated to sufficient precision involving its variance, which incurs an extra factor of O(H)O(H) and leads to the final query complexity of O~(H2.5SAε) O ( H^2.5SA ). Interestingly enough, the need for recycling ∑s′∈p(s′|s,a)V0(s′) _s p(s |s,a)V_0(s ) across all O~(Γ) O( ) time steps hinders the use of quantum maximum finding. The situation is even worse in the finite-horizon setting, since unlike the classical case where the same batch of samples can be reused to approximate all quantities ∑s′∈p(s′|s,a)Vh+1(0)(s′) _s p(s |s,a)V_h+1^(0)(s ) simultaneously, in the quantum setting we must start each calculation anew, which incurs an extra factor O(H)O(H) in the query complexity and hinders a full quadratic advantage in H. 1.2 Our Results In this work, we propose new quantum algorithms that improve upon the query upper bounds of wang2021quantum ; luo2025quantum ; ambainis2025bit both for finite- and infinite-horizon discounted MDPs. Result 1. Let ⟨,,p,r,H⟩ ,A,p,r,H be a finite-horizon MDP. There is a quantum algorithm that outputs an ε -optimal policy with high probability and query complexity O~(H2.5SAε) O ( H^2.5S A ). Result 2. Let ⟨,,p,r,γ⟩ ,A,p,r,γ be an infinite-horizon discounted MDP. There is a quantum algorithm that outputs an ε -optimal policy with high probability and query complexity O~(Γ2.5SAε) O ( ^2.5S A ). Table 1: Classical and quantum query bounds for computing an ε -optimal policy and value function for finite- and infinite-horizon discounted MDPs in the generative model setting. Here S and A are the size of the state and action spaces, respectively, while Γ=(1−γ)−1 =(1-γ)^-1. All bounds are up to polylogpoly factors and assume a constant failure probability δ. Setting Classical query complexity Quantum query complexity Upper bound Lower bound Upper bound Lower bound Finite-horizon H3SAε2 H^3SA ^2 sidford2018near ; li2020breaking H3SAε2 H^3SA ^2 sidford2018near minH2.5SAε,H3SAε \! \\! H^2.5SA , H^3S A \ ambainis2025bit ; luo2025quantum H2.5SAε H^2.5S A Result 1 H1.5SAε H^1.5S A luo2025quantum Infinite-horizon Γ3SAε2 ^3SA ^2 sidford2018near ; li2020breaking Γ3SAε2 ^3SA ^2 GheshlaghiAzar2013 minΓ1.5SAε,Γ3SAε \! \\! ^1.5SA , ^3S A \ wang2021quantum Γ2.5SAε ^2.5S A Result 2 Γ1.5SAε ^1.5S A wang2021quantum Our new algorithms are a quantised version of the standard value iteration but further improved with the monotonicity and total-variance techniques from sidford2018near . This includes using quantum mean estimation with variance Kothari2023mean to approximate the mean μt(s,a)=∑s′∈p(s′|s,a)Vt(s′) _t(s,a)= _s p(s |s,a)V_t(s ) together with its variance σt(s,a) _t(s,a) in a superposition fashion in the form of an oracle smean:|a⟩|0¯⟩↦|a⟩(1−δa|μ^t(s,a)⟩|μ~t(s,a)⟩|σ~t(s,a)⟩|garbage(a)⟩+δa|⟂a⟩), mean_s:|a | 0 |a ( 1- _a| μ_t(s,a) | μ_t(s,a) | σ_t(s,a) |garbage(a) + _a| _a ), which will serve as the base unitary for quantum maximum finding. Here δa∈[0,1) _a∈[0,1) is the failure probability of quantum mean estimation within the branch of the wave function described by |a⟩|a , μ~t(s,a) μ_t(s,a) and σ~t(s,a) σ_t(s,a) are good enough approximations of μt(s,a) _t(s,a) and σt(s,a) _t(s,a), |garbage(a)⟩|garbage(a) are “garbage” unit vectors, and |⟂a⟩| _a is a unit vector orthogonal to |μ~t(s,a)⟩|σ~t(s,a)⟩|garbage(a)⟩| μ_t(s,a) | σ_t(s,a) |garbage(a) . The quantity μ^t(s,a) μ_t(s,a) is a one-sided-error version of μ~t(s,a) μ_t(s,a) necessary to guarantee the approximate optimality of the derived greedy policies and the reason why we need an estimate of the variance σt(s,a) _t(s,a). The output of quantum maximum finding is then an one-side approximation of Vt(s)V_t(s) with additive error O(εσt(s,πt+1(s))Γ1.5)O ( [b] _t(s, _t+1(s)) ^1.5 ). Using the total-variance technique, after T=O(ΓlogΓε)T=O ( ) time steps the function VTV_T is ε -close to V∞∗,γV_∞ ,γ. By the monotonicity condition, its associated greedy policy is ε -optimal. The argument for finite-horizon MDPs is similar, with H replacing Γ . In contrast to wang2021quantum ; luo2025quantum ; ambainis2025bit that either (i) use quantum maximum finding but does not include any variance in the error propagation or (i) take variance into account but not quantum maximum finding, here we perform both, which ultimately yields a combined dependence on A A and a better dependence than Γ3 ^3 or H3H^3. Our finite-horizon complexity subsumes the ones of luo2025quantum ; ambainis2025bit , while our infinite-horizon complexity improves the part O~(Γ3SAε) O ( ^3S A ) from wang2021quantum , leading to a new overall complexity of O~(minΓ1.5SAε,Γ2.5SAε) O ( \ ^1.5SA , ^2.5S A \ ). Our results are thus a measurable improvement on past works and a new step towards the lower bounds Ω~(H1.5SAε) ( H^1.5S A ) and Ω~(Γ1.5SAε) ( ^1.5S A ). Acknowledgments. JFD is supported by the Lendület “Momentum” program of the Hungarian Academy of Sciences under grant agreement no. LP2025-8/2025. Artificial intelligence research statement. ChatGPT has been used to check for typos and mistakes. Ideas, proofs, and writing are the product of the author alone. 2 Preliminaries For n∈ℕ:=0,1,2,…n :=\0,1,2,…\, let [n]:=0,…,n−1[n]:=\0,…,n-1\. Given a finite set S, let ℬ() B(S) be the space of all bounded Borel measurable real-valued functions on S, which can be interpreted as ℝSR^S for S=||S=|S|, and let Δ() (S) denote the probability simplex over S. Given u∈ℬ()u∈ B(S), its ℓ∞ _∞-norm is ‖u‖∞:=maxs∈|u(s)|\|u\|_∞:= _s |u(s)|. We use ∈ℬ()1∈ B(S) to denote the all-ones function, (s)=11(s)=1. Given u,v∈ℬ()u,v∈ B(S), let uv∈ℬ()uv∈ B(S) be the function defined as (uv)(s)=u(s)v(s)(uv)(s)=u(s)v(s) ∀s∈∀ s , and u≤v⇔u(s)≤v(s)u≤ v u(s)≤ v(s) ∀s∈∀ s . 2.1 Quantum Computation Little background on quantum computation is needed for this paper and we refer the reader to nielsen2010quantum for more information. The quantum state of a quantum system is described by a unit vector from a Hilbert space denoted by the ket notation |⋅⟩|· . An n-qubit system is described by a unit vector in ℂ2nC^2^n. The evolution of a quantum state |ψ⟩∈ℂ2n|ψ ^2^n is described by a unitary operator U∈ℂ2n×2nU ^2^n× 2^n, UU†=IUU =I where U†U is the Hermitian conjugate of U. In order to extract classical information from a quantum system, a quantum measurement is usually performed, which is a set Emm\E_m\_m of positive operators Em≻0E_m 0 that sum to identity, ∑mEm=I _mE_m=I. The probability of measuring EmE_m on |ψ⟩|ψ is ⟨ψ|Em|ψ⟩ ψ|E_m|ψ . We use |0¯⟩ 0 to denote the state |0⟩⊗⋯⊗|0⟩ 0 ·s 0 where the number of qubits is clear from context. In this paper, we employ quantum oracles for functions and probability distributions. We say we have quantum access to u∈ℬ()u∈ B(S) if we have access to the unitary u:|s⟩|0¯⟩↦|s⟩|u(s)⟩O_u:|s | 0 |s |u(s) and its inverse, and we say we have quantum sampling access to p∈Δ()p∈ (S) if we have access to the unitary p:|0¯⟩↦∑s∈p(s)|s⟩O_p:| 0 _s p(s)|s and its inverse. Quantum access to a function is usually referred to as a quantum random access memory (QRAM) giovannetti2008architectures ; giovannetti2008quantum ; jaques2023qram ; allcock2023constant . It is possible to build quantum access to u∈ℬ()u∈ B(S) in O~(S) O(S) time. We shall require the following quantum subroutines. Fact 1 (Quantum maximum finding durr1996quantum ). Given quantum access to u∈ℬ()u∈ B(S) via oracle uO_u, there is a quantum algorithm that finds maxs∈u(s) _s u(s) and argmaxs∈u(s) *arg\,max_s u(s) with probability 1−δ1-δ using O(Slog1δ)O( S 1δ) queries to u,u†O_u,O_u . Fact 2 (Quantum mean estimation with variance (Kothari2023mean, , Theorem 1.1)). Let ϵ>0ε>0 and δ∈(0,1)δ∈(0,1). Assume quantum access to function u:→ℝu:S via oracle uO_u and quantum sampling access to probability distribution p∈Δ()p∈ (S) via oracle pO_p. Let σ:=∑s∈p(s)u(s)2−(∑s∈p(s)u(s))2σ:= _s p(s)u(s)^2- ( _s p(s)u(s) )^2. There is a quantum algorithm that computes μ~∈ℝ μ such that |μ~−∑s∈p(s)u(s)|≤σϵ| μ- _s p(s)u(s)|≤ σε with success probability 1−δ1-δ using O(1ϵlog1δ)O ( 1ε 1δ ) queries to u,pO_u,O_p, and their inverses. 2.2 Background on Markov Decision Processes In this work, we are concerned with two main types of discrete-time MDPs: finite-horizon and infinite-horizon discounted MDPs. A finite-horizon MDP is described by a tuple ⟨,,p,r,H⟩ ,A,p,r,H , while an infinite-horizon discounted MDP is described by a tuple ⟨,,p,r,γ⟩ ,A,p,r,γ . The Borel spaces S and A are called state and action spaces, respectively, assumed here to be finite with sizes ||=S|S|=S and ||=A|A|=A. The measurable bounded function r:×→[0,1]r:S×A→[0,1] is called reward function, while p:×→Δ()p:S×A→ (S) are stochastic kernels. Finally, the parameter H∈ℕH is called horizon, while γ∈[0,1)γ∈[0,1) is called discount factor. Define also Γ:=(1−γ)−1 :=(1-γ)^-1 as the effective horizon for infinite-horizon discounted MDPs. A discrete-time MDP models the interaction between an agent and an environment. At each time step t∈ℕt , the agent chooses an action at∈a_t given the environment’s state st∈s_t , after which a reward r(st,at)r(s_t,a_t) is received and the environment transitions to a new state st+1∼p(⋅|st,at)s_t+1 p(·|s_t,a_t). Such interaction is performed H times for finite-horizon MDPs, while for infinite-horizon discounted MDPs, it can last indefinitely, however, the received reward is progressively discounted by a factor γtγ^t at time step t. The agent chooses action at∈a_t according to a randomised Markovian decision rule πt:→Δ() _t:S→ (A), so that at∼πt(⋅|st)a_t _t(·|s_t). A decision rule πt _t is deterministic if for all s∈s , πt(a|s)=1 _t(a|s)=1 for some a∈a ; one can equivalently define a deterministic decision rule as a function πt:→ _t:S . A randomised Markovian policy π=(πt)tπ=( _t)_t is a sequence of randomized decision rules πt:→Δ() _t:S→ (A), and similarly for a deterministic policy. A policy π=(πt)tπ=( _t)_t is stationary if πt=πt′ _t= _t for all t,t′t,t . The set of all randomised and deterministic decision rules are denoted by RD R and DD D, and the set of all randomised and deterministic policies are denoted by ΠR R and ΠD D, respectively. Given a decision rule d∈Rd R, we employ the notation d∞d^∞ for the stationary policy (d,d,…)(d,d,…) in infinite-horizon discounted MDPs. Given d∈Rd R, define rd∈ℬ()r_d∈ B(S) and pd:→Δ()p_d:S→ (S) as rd(s):=a∼d(⋅|s)[r(s,a)]andpd(s′|s):=a∼d(⋅|s)[p(s′|s,a)]. r_d(s):= *E_a d(·|s)[r(s,a)] p_d(s |s):= *E_a d(·|s)[p(s |s,a)]. Given stochastic kernel p:×→Δ()p:S×A→ (S), decision rule d∈Rd R, and action a∈a , let the operators d,a:ℬ()→ℬ()P_d,P_a: B(S)→ B(S) be defined as (du)(s)=∑s′∈pd(s′|s)u(s′)(P_du)(s)= _s p_d(s |s)u(s ) and (au)(s)=∑s′∈p(s′|s,a)u(s′)(P_au)(s)= _s p(s |s,a)u(s ) for all u∈ℬ()u∈ B(S) and s∈s . Finite-horizon MDPs. Given policy π=(πh)h∈[H]π=( _h)_h∈[H] and h∈[H]h∈[H], let the value function Vhπ,H:→[0,H]V_h^π,H:S→[0,H] be defined as Vhπ,H(s)=[∑h′=hH−1r(sh′,ah′)|sh=s,ah′∼πh′(sh′),sh′+1∼p(⋅|sh′,ah′)]∀s∈. V_h^π,H(s)=E [ _h =h^H-1r(s_h ,a_h )~ |~s_h=s,a_h _h (s_h ),s_h +1 p(·|s_h ,a_h ) ] ∀ s . Note that not all decision rules that make up π are necessarily employed in Vhπ,HV_h^π,H. A policy πε∈ΠRπ ∈ R is ε -optimal for ε≥0 ≥ 0 if V0πε,H≥V0π,H−εV^π ,H_0≥ V^π,H_0- 1 for all π∈ΠRπ∈ R, and a policy π∗π is optimal if V0π∗,H≥V0π,HV^π ,H_0≥ V^π,H_0 for all π∈ΠRπ∈ R. The optimal value function is Vh∗,H:=supπ∈ΠRVhπ,HV ,H_h:=sup_π∈ RV_h^π,H. It is well known that V0∗,H=supπ∈ΠRV0π,H=supπ∈ΠDV0π,HV_0 ,H=sup_π∈ RV_0^π,H=sup_π∈ DV_0^π,H, i.e., the optimal policy is deterministic. Let the Bellman operator ℒd:ℬ()→ℬ()L_d: B(S)→ B(S) associated with d∈Rd R be defined as ℒdu=rd+du,or less compactly,(ℒdu)(s)=rd(s)+∑s′∈pd(s′|s)u(s′), _du=r_d+P_du, less compactly, (L_du)(s)=r_d(s)+ _s p_d(s |s)u(s ), and the optimal Bellman operator ℒ:ℬ()→ℬ()L: B(S)→ B(S) be defined as ℒu=supd∈Rℒdu,or less compactly,(ℒu)(s)=maxa∈r(s,a)+∑s′∈p(s′|s,a)u(s′). = _d RL_du, less compactly, (Lu)(s)= _a \r(s,a)+ _s p(s |s,a)u(s ) \. The Bellman operators ℒL and ℒdL_d are monotonic, i.e., u≤v⟹ℒu≤ℒvu≤ v , and non-expansive, i.e., ‖ℒu−ℒv‖∞≤‖u−v‖∞\|Lu-Lv\|_∞≤\|u-v\|_∞ for all u,v∈ℬ()u,v∈ B(S) (similarly for ℒdL_d). Finally, the value functions Vhπ,HV_h^π,H satisfy the recursive equation Vhπ,H=ℒπhVh+1π,H=rπh+πhVh+1π,HV_h^π,H=L_ _hV_h+1^π,H=r_ _h+P_ _hV_h+1^π,H. Infinite-horizon discounted MDPs. Given policy π=(πt)t∈ℕπ=( _t)_t and t∈ℕt , let the value function Vtπ,γ:→[0,Γ]V_t^π,γ:S→[0, ] be defined as Vtπ,γ(s)=[∑t′=0tγt′r(st′,at′)|s0=s,at′∼πt−t′(st′),st′+1∼p(⋅|st′,at′)]∀s∈. V_t^π,γ(s)=E [ _t =0^tγ^t r(s_t ,a_t )~ |~s_0=s,a_t _t-t (s_t ),s_t +1 p(·|s_t ,a_t ) ] ∀ s . Note that not all decision rules that make up π are necessarily employed in Vtπ,γV_t^π,γ. We observe the unusual ordering of the decision rules πt−t′ _t-t employed in choosing the t′t -th action at′a_t instead of the more natural choice at′∼πt′(st′)a_t _t (s_t ). Define also the value function V∞π,γ(s)=[∑t=0∞γtr(st,at)|s0=s,at∼πt(st),st+1∼p(⋅|st,at)]∀s∈. V_∞^π,γ(s)=E [ _t=0^∞γ^tr(s_t,a_t)~ |~s_0=s,a_t _t(s_t),s_t+1 p(·|s_t,a_t) ] ∀ s . Here the decision rule ordering is the conventional one, so at∼πt(st)a_t _t(s_t). Similarly to the finite-horizon setting, a policy πε∈ΠRπ ∈ R is ε -optimal for ε≥0 ≥ 0 if V∞πε,γ≥V∞π,γ−εV^π ,γ_∞≥ V^π,γ_∞- 1 for all π∈ΠRπ∈ R, and a policy π∗∈ΠRπ ∈ R is optimal if V∞π∗,γ≥V∞π,γV^π ,γ_∞≥ V^π,γ_∞ for all π∈ΠRπ∈ R. The optimal value function is V∞∗,γ:=supΠRV∞π,γV_∞ ,γ:=sup_ RV_∞^π,γ. It is well known that V∞∗,γ=supπ∈ΠRV∞π,γ=supd∈DV∞d∞,γV_∞ ,γ= _π∈ RV_∞^π,γ= _d DV_∞^d^∞,γ, i.e., the optimal policy is deterministic and stationary. Let the Bellman operator ℒd:ℬ()→ℬ()L_d: B(S)→ B(S) associated with d∈Rd R and optimal Bellman operator ℒ:ℬ()→ℬ()L: B(S)→ B(S) be defined as ℒdu=rd+γduandℒu=supd∈Rℒdu. _du=r_d+ _du = _d RL_du. The Bellman operators ℒL and ℒdL_d are monotonic i.e., u≤v⟹ℒu≤ℒvu≤ v , and contractive, i.e., ‖ℒu−ℒv‖∞≤γ‖u−v‖∞\|Lu-Lv\|_∞≤γ\|u-v\|_∞ for all u,v∈ℬ()u,v∈ B(S) (similarly for ℒdL_d). Given our deliberate choice for ordering the decision rules πt−t′ _t-t in the definition of Vtπ,γV_t^π,γ, the value functions Vtπ,γV_t^π,γ satisfy the recursive equation Vt+1π,γ=ℒπt+1Vtπ,γ=rπt+1+γπt+1Vtπ,γV_t+1^π,γ=L_ _t+1V_t^π,γ=r_ _t+1+ _ _t+1V_t^π,γ, similarly to the finite-horizon setting. Finally, given d∈Rd R, the value function V∞d∞,γV_∞^d^∞,γ is the unique fixed point of the Bellman operator ℒdL_d, i.e., ℒdV∞d∞,γ=V∞d∞,γL_dV_∞^d^∞,γ=V_∞^d^∞,γ, while the optimal value function V∞∗,γV_∞ ,γ is the unique fixed point of the Bellman operator ℒL, i.e., ℒV∞∗,γ=V∞∗,γLV_∞ ,γ=V_∞ ,γ. As a consequence, for any d∈Rd R and u∈ℬ()u∈ B(S), ℒd∞u=V∞d∞,γL_d^∞u=V_∞^d^∞,γ and ℒ∞u=V∞∗,γL^∞u=V_∞ ,γ. 3 Optimal Policies for Finite-Horizon MDPs In this section, we describe and analyse our quantum algorithm for computing ε -optimal policies for finite-horizon MDPs.444All the results of this section can be generalised to time-dependent MDPs ⟨,,phh∈[H],rhh∈[H],H⟩ ,A,\p_h\_h∈[H],\r_h\_h∈[H],H . We stick to the time-independent case for simplicity. The starting point are the optimality equations VH≡0andVh=ℒVh+1∀h∈[H]. V_H≡ 0 V_h=LV_h+1 ∀ h∈[H]. It is well known (puterman2014markov, , Theorem 4.5.1) that any set of solutions Vhh∈[H]\V_h\_h∈[H] to the above equations are such that Vh=Vh∗,HV_h=V_h ,H for all h∈[H]h∈[H]. The standard value iteration algorithm puterman2014markov simply solves the optimality equations in an iterative fashion in time O(HS2A)O(HS^2A) if the stochastic kernel p is known. If one has sampling access to p instead, then the quantities (aVh+1)(s)=∑s′∈p(s′|s,a)Vh+1(s′)(P_aV_h+1)(s)= _s p(s |s,a)V_h+1(s ) are approximated to sufficient precision by taking enough samples s′∼p(⋅|s,a)s p(·|s,a) for all (s,a)∈×(s,a) ×A. An ε -optimal policy can be obtained by simply approximating (aVh+1)(s)(P_aV_h+1)(s) up to εH H precision for all (s,a,h)∈×[H−1](s,a,h) ×A×[H-1], leading to a classical query complexity of O(H5SAε2)O ( H^5SA ^2 ) or a quantum query complexity of O(H3SAε)O ( H^3SA ). As discussed in Section 1, Sidford et al. sidford2018near reduced the classical complexity down to the optimal value O~(H3SAε2) O ( H^3SA ^2 ) by employing the variance-reduction and total-variance techniques. In the quantum setting, it is possible to use quantum maximum finding to improve upon the naive approach and obtain a complexity of O~(H3SAε) O ( H^3S A ). This means approximating the quantities (aVh+1)(s)(P_aV_h+1)(s) within quantum maximum finding in order to find the maximum value quadratically faster. More precisely, one uses the quantum mean estimation subroutine as an oracle smean:|a⟩|0¯⟩↦|a⟩(1−δa|μ~h+1(s,a)⟩|garbage(a)⟩+δa|⟂a⟩)∀s∈, mean_s:|a | 0 |a ( 1- _a| μ_h+1(s,a) |garbage(a) + _a| _a ) ∀ s , for quantum maximum finding in order to find maxa∈r(s,a)+μ~h+1(s,a) _a \r(s,a)+ μ_h+1(s,a)\. Here δa∈[0,1) _a∈[0,1) is the failure probability behind quantum mean estimation within the branch of the wave function described by the component |a⟩|a , μ~h+1(s,a)∈ℝ μ_h+1(s,a) is a good enough approximation of (aVh+1)(s)(P_aV_h+1)(s), |garbage(a)⟩|garbage(a) are “garbage” unit vectors, and |⟂a⟩| _a are unit vectors orthogonal to |μ~h+1(s,a)⟩|garbage(a)⟩| μ_h+1(s,a) |garbage(a) . As previously mentioned, this was precisely the approach followed by Ambainis et al. ambainis2025bit and Luo et al. luo2025quantum together with the approximation |μ~h+1(s,a)−(aVh+1)(s)|≤εH| μ_h+1(s,a)-(P_aV_h+1)(s)|≤ H. Both works also quantised the modern value iteration algorithm of Sidford et al. sidford2018near , which improves the dependence on H but hinders the use of quantum maximum finding, leading to the alternative query complexity O~(H2.5SAε) O ( H^2.5SA ). Our quantum algorithm (Algorithm 1) is based on nesting quantum mean estimation within quantum maximum finding, similarly to ambainis2025bit ; luo2025quantum , but we further incorporate the total-variance technique from sidford2018near in order to improve the dependence on H. This means that we approximate μ~h+1(s,a)≈(aVh+1)(s) μ_h+1(s,a)≈(P_aV_h+1)(s) using its variance σh+1(s,a)=(aVh+12)(s)−(aVh+1)2(s) _h+1(s,a)=(P_aV^2_h+1)(s)-(P_aV_h+1)^2(s). Modern versions of quantum mean estimation like the one from Kothari and O’Donnell Kothari2023mean do not require prior knowledge of σh+1(s,a) _h+1(s,a) in order to compute μ~h+1(s,a) μ_h+1(s,a). However, since we need an approximation with one-side error, we also approximate σh+1(s,a) _h+1(s,a) within quantum maximum finding. This means enhancing the oracle constructed with quantum mean estimation (and to be employed by quantum maximum finding) to smean:|a⟩|0¯⟩↦|a⟩(1−δ|μ^h+1(s,a)⟩|μ~h+1(s,a)⟩|σ~h+1(s,a)⟩|garbage(a)⟩+δ|⟂a⟩), mean_s:|a | 0 |a ( 1-δ| μ_h+1(s,a) | μ_h+1(s,a) | σ_h+1(s,a) |garbage(a) + δ| _a ), where μ~h+1(s,a)≈(aVh+1)(s) μ_h+1(s,a)≈(P_aV_h+1)(s), σ~h+1(s,a)≈σh+1(s,a) σ_h+1(s,a)≈ _h+1(s,a), and μ^h+1(s,a) μ_h+1(s,a) is a shifted version of μ~h+1(s,a) μ_h+1(s,a) so that μ^h+1(s,a)≤(aVh+1)(s) μ_h+1(s,a)≤(P_aV_h+1)(s). Ultimately, the registers |μ~h+1(s,a)⟩|σ~h+1(s,a)⟩| μ_h+1(s,a) | σ_h+1(s,a) are treated as garbage by the quantum maximum finding subroutine and only the values μ^h+1(s,a) μ_h+1(s,a) are needed. The dependence on the variance then guarantees that the error accumulation is smaller than a naive linear dependence (Fact 3 below). We now formally prove the correctness and query complexity of Algorithm 1. Fact 3 ((sidford2018near, , Lemma F.4)). Given policy π=(πh)h∈[H]π=( _h)_h∈[H], let σh+1π∈ℬ()σ^π_h+1∈ B(S) be defined as σh+1π=πh(Vh+1π,H)2−(πhVh+1π,H)2 _h+1^π=P_ _h(V_h+1^π,H)^2-(P_ _hV_h+1^π,H)^2 for h∈[H]h∈[H]. For any policy π=(πh)h∈[H]π=( _h)_h∈[H] and h∈[H]h∈[H],555We note the typo in (sidford2018near, , Lemma F.4) where ∥⋅∥∞2\|·\|_∞^2 should be ∥⋅∥∞\|·\|_∞. ‖∑h′=hH−1(∏i=h′−1πi)σh′+1π‖∞≤H3/2. \| _h =h^H-1 ( _i=h^h -1P_ _i ) _h +1^π \|_∞≤ H^3/2. Theorem 1. Let ⟨,,p,r,H⟩ ,A,p,r,H be a finite-horizon MDP. Let δ∈(0,1)δ∈(0,1) and ε∈(0,H] ∈(0, H]. Algorithm 1 computes functions Vhh∈[H]⊂ℬ()\V_h\_h∈[H]⊂ B(S) and deterministic policy π=(πh)h∈[H]π=( _h)_h∈[H] such that, with probability 1−δ1-δ, Vh∗,H−ε≤Vh≤Vhπ,H≤Vh∗,H∀h∈[H]. V ,H_h- 1≤ V_h≤ V^π,H_h≤ V ,H_h ∀ h∈[H]. Its query complexity is O(H2.5SAεlog(HSAδ)log(HSδ)). O ( H^2.5S A ( HSAδ ) ( HSδ ) ). Proof. The proof is by induction on h∈[H]h∈[H], with the base case h=Hh=H being trivial since VH≡0V_H≡ 0. Assume then that (the inequality is entry-wise) Vh′∗,H−ε≤Vh′≤Vh′π,H≤Vh′∗,H∀h′=h+1,h+2,…,H. V ,H_h - 1≤ V_h ≤ V_h ^π,H≤ V ,H_h ∀ h =h+1,h+2,…,H. The main idea is to employ Fact 2 to compute approximations for the true quantities μh+1(s,a):=(aVh+1)(s)andσh+1(s,a):=(aVh+12)(s)−(aVh+1)2(s). _h+1(s,a):=(P_aV_h+1)(s) _h+1(s,a):=(P_aV_h+1^2)(s)-(P_aV_h+1)^2(s). Let θ:=ε7H3/2θ:= 7H^3/2. We claim that Fact 2 can be adapted to perform all of its steps in superposition without any need for intermediary measurements. This means that we can invoke Fact 2 twice to construct a unitary s(h):|a⟩|0¯⟩↦|a⟩(1−δa|μ~h+1(s,a)⟩|σ~h+1(s,a)⟩|garbage(a)⟩+δa|⟂a⟩), _s^(h):|a | 0 |a ( 1- _a| μ_h+1(s,a) | σ_h+1(s,a) |garbage(a) + _a| _a ), (2) where δa∈[0,1) _a∈[0,1) is the failure probability of quantum mean estimation within the branch |a⟩|a of the wave function, |garbage(a)⟩|garbage(a) is a “garbage” unit complex vector accumulated through the computation, |⟂a⟩| _a is a unit complex vector orthogonal to |μ~h+1(s,a)⟩|σ~h+1(s,a)⟩|garbage(a)⟩| μ_h+1(s,a) | σ_h+1(s,a) |garbage(a) , and ∀(s,a)∈×:|μ~h+1(s,a)−μh+1(s,a)|≤θσh+1(s,a),|σ~h+1(s,a)−σh+1(s,a)|≤2θH2, ∀(s,a) ×A: aligned &| μ_h+1(s,a)- _h+1(s,a)|≤θ _h+1(s,a),\\ &| σ_h+1(s,a)- _h+1(s,a)|≤ 2θ H^2, aligned (3) using that the standard deviation of Vh+12V^2_h+1 is at most H2H^2 and thus one can compute approximations of (aVh+12)(s)(P_aV_h+1^2)(s) and (aVh+1)2(s)(P_aV_h+1)^2(s) with error at most θH2θ H^2 each. Using (3), ∀(s,a)∈×:|μ~h+1(s,a)−μh+1(s,a)|≤θσ~h+1(s,a)+2θ3/2H. ∀(s,a) ×A: | μ_h+1(s,a)- _h+1(s,a)|≤θ σ_h+1(s,a)+ 2θ^3/2H. Define then the quantities ∀(s,a)∈×:μ^h+1(s,a):=μ~h+1(s,a)−θσ~h+1(s,a)−2θ3/2H, ∀(s,a) ×A: μ_h+1(s,a):= μ_h+1(s,a)-θ σ_h+1(s,a)- 2θ^3/2H, which have one-side error. We can express the above quantity using the optimal-policy variance σh+1∗(s,a):=(a(Vh+1∗,H)2)(s)−(aVh+1∗,H)2(s) _h+1 (s,a):=(P_a(V_h+1 ,H)^2)(s)-(P_aV_h+1 ,H)^2(s) since ∀(s,a)∈×:σ~h+1(s,a)≤σh+1(s,a)+2θH≤σh+1∗(s,a)+ε+2θH, ∀(s,a) ×A: σ_h+1(s,a)≤ _h+1(s,a)+ 2θH≤ σ _h+1(s,a)+ + 2θH, using (3) and that Var[Vh+1]≤Var[Vh+1∗,H]+Var[Vh+1∗,H−Vh+1]≤Var[Vh+1∗,H]+ε Var[V_h+1]≤ Var[V ,H_h+1]+ Var[V ,H_h+1-V_h+1]≤ Var[V ,H_h+1]+ if ‖Vh+1∗,H−Vh+1‖∞≤ε\|V ,H_h+1-V_h+1\|_∞≤ according to the induction hypothesis. This means that ∀(s,a)∈×:μ^h+1(s,a)≤μh+1(s,a),μ^h+1(s,a)≥μh+1(s,a)−2θσh+1∗(s,a)−2θε−42θ3/2H. ∀(s,a) ×A: aligned & μ_h+1(s,a)≤ _h+1(s,a),\\ & μ_h+1(s,a)≥ _h+1(s,a)-2θ σ _h+1(s,a)-2θ -4 2θ^3/2H. aligned By subtracting the content of register |σ~h+1(s,a)⟩| σ_h+1(s,a) from the register |μ~h+1(s,a)⟩| μ_h+1(s,a) in (2), it is then possible to effectively construct a black-box oracle s(h):|a⟩|0¯⟩↦|a⟩(1−δa|μ^h+1(s,a)⟩+δa|⟂a⟩)U_s^(h):|a | 0 |a ( 1- _a| μ_h+1(s,a) + _a| _a ) using oracle p,p†Q_p,Q_p (up to garbage states). The maximum over a∈a of r(s,a)+μ^h+1(s,a)r(s,a)+ μ_h+1(s,a) can thus be found by using quantum maximum finding (Fact 1) with unitary s(h)U_s^(h), leading to Vh(s)=maxa∈r(s,a)+μ^h+1(s,a)V_h(s)= _a \r(s,a)+ μ_h+1(s,a)\ and πh(s)=argmaxa∈r(s,a)+μ^h+1(s,a) _h(s)= *arg\,max_a \r(s,a)+ μ_h+1(s,a)\ with probability 1−δHS1- δHS. This means that ∀s∈:Vh(s)≤(ℒπhVh+1)(s),Vh(s)≥(ℒπh∗Vh+1)(s)−2θσh+1∗(s,πh∗(s))−2θε−42θ3/2H. ∀ s : aligned V_h(s)&≤(L_ _hV_h+1)(s),\\ V_h(s)&≥(L_ _h V_h+1)(s)-2θ σ _h+1(s, _h (s))-2θ -4 2θ^3/2H. aligned Note that Vh(s)≤(ℒπhVh+1)(s)≤(ℒπhVh+1π,H)(s)=Vhπ,H(s)V_h(s)≤(L_ _hV_h+1)(s)≤(L_ _hV_h+1^π,H)(s)=V_h^π,H(s) by using the induction hypothesis to argue that Vh+1≤Vh+1π,HV_h+1≤ V_h+1^π,H. We are left with proving that Vh∗(s)−ε≤Vh(s)V _h(s)- ≤ V_h(s). For such, Vh∗,H−Vh V_h ,H-V_h ≤ℒπh∗Vh+1∗,H−ℒπh∗Vh+1+ξh=πh∗(Vh+1∗,H−Vh+1)+ξh, _π _hV ,H_h+1-L_π _hV_h+1+ _h=P_ _h (V ,H_h+1-V_h+1)+ _h, where we defined the function ξh(s)=2θσh+1∗(s,πh∗(s))+2θε+42θ3/2H _h(s)=2θ σ _h+1(s, _h (s))+2θ +4 2θ^3/2H. Solving the above recursion with the boundary condition VH−1≡VH−1∗,HV_H-1≡ V_H-1 ,H, Vh∗,H−Vh≤∑h′=hH−1(∏i=h′−1πi∗)ξh′. V_h ,H-V_h≤ _h =h^H-1 ( _i=h^h -1P_π _i ) _h . Using that (where σh+1∗=πh∗(Vh+1∗,H)2−(πh∗Vh+1∗,H)2∈ℬ() _h+1 =P_ _h (V_h+1 ,H)^2-(P_π _hV_h+1 ,H)^2∈ B(S)) ‖∑h′=hH−1(∏i=h′−1πi∗)σh′+1∗‖∞≤H3/2, \| _h =h^H-1 ( _i=h^h -1P_ _i ) _h +1 \|_∞≤ H^3/2, (by Fact 3) and that ‖∑h′=hH∏i=h′−1πi∗‖∞≤H\| _h =h^H _i=h^h -1P_π _i\|_∞≤ H, we get that Vh∗,H(s)−Vh(s)≤2θH3/2+2θHε+42θ3/2H2=ε(27+2ε7H+4273/2H1/4)<ε. V_h ,H(s)-V_h(s)≤ 2θ H^3/2+2θ H +4 2θ^3/2H^2= ( 27+ 2 7 H+ 4 27^3/2H^1/4 )< . (ε≤H ≤ H) We now analyse the success probability of Algorithm 1.666See (chen2021quantum, , Appendix A) for a similar argument. Ideally, we would like to implement the unitary s,ideal(h):|a⟩|0¯⟩↦|a⟩|μ^h+1(s,a)⟩U_s, ideal^(h):|a | 0 |a | μ_h+1(s,a) . In practice, however, we implement the unitary s(h):|a⟩|0¯⟩↦|a⟩(1−δa|μ^h+1(s,a)⟩+δa|⟂a⟩)U_s^(h):|a | 0 |a ( 1- _a| μ_h+1(s,a) + _a| _a ) (up to garbage states) for δaa∈⊂[0,1)\ _a\_a ⊂[0,1), where the register |μ^h+1(s,a)⟩| μ_h+1(s,a) holds the desired approximation μ^h+1(s,a) μ_h+1(s,a) and |⟂a⟩| _a is a normalised quantum state orthogonal to |μ^h+1(s,a)⟩| μ_h+1(s,a) . Let δ2:=maxa∈δa _2:= _a _a. Consider a unitary s(h)V_s^(h) such that, for all a∈a , 1. s(h)|a⟩(1−δa|μ^h+1(s,a)⟩+δa|⟂a⟩)=|a⟩|μ^h+1(s,a)⟩V_s^(h)|a ( 1- _a| μ_h+1(s,a) + _a| _a )=|a | μ_h+1(s,a) ; 2. s(h)|a⟩(δa|μ^h+1(s,a)⟩−1−δa|⟂a⟩)=|a⟩|⟂a⟩V_s^(h)|a ( _a| μ_h+1(s,a) - 1- _a| _a )=|a | _a (note that δ2|μ^h+1(s,a)⟩−1−δa|⟂a⟩ _2| μ_h+1(s,a) - 1- _a| _a is orthogonal to 1−δa|μ^h+1(s,a)⟩+δa|⟂a⟩ 1- _a| μ_h+1(s,a) + _a| _a ); 3. For every |ϕ⟩|φ orthogonal to span|μ^h+1(s,a)⟩,|⟂a⟩span\| μ_h+1(s,a) ,| _a \, s(h)|a⟩|ϕ⟩=|a⟩|ϕ⟩V_s^(h)|a |φ =|a |φ . Then s(h)s(h)|a⟩|0¯⟩=s(h)|a⟩(1−δa|μ^h+1(s,a)⟩+δa|⟂a⟩)=|a⟩|μ^h+1(s,a)⟩V_s^(h)U_s^(h)|a | 0 =V_s^(h)|a ( 1- _a| μ_h+1(s,a) + _a| _a )=|a | μ_h+1(s,a) . Therefore, we can just set s,ideal(h)=s(h)s(h)U_s, ideal^(h)=V_s^(h)U_s^(h) without loss of generality. As a consequence, ‖s(h)−s,ideal(h)‖=‖I−s(h)‖≤(1−1−δ2)2+δ2=2−21−δ2≤2δ2, \|U_s^(h)-U_s, ideal^(h)\|=\|I-V_s^(h)\|≤ (1- 1- _2)^2+ _2= 2-2 1- _2≤ 2 _2, using that 1−δ2≥1−δ2 1- _2≥ 1- _2. Moving on, the success probability of quantum maximum finding (Fact 1) is 1−δ11- _1 when employing s,ideal(h)U_s, ideal^(h), for some δ1∈[0,1) _1∈[0,1). However, since it employs s(h)U_s^(h) instead, the success probability decreases by at most the spectral norm of the difference between the “real” and the “ideal” total unitaries. To be more precise, the “ideal” quantum maximum finding is a sequence of gates W=U1E1U2E2⋯UNENW=U_1E_1U_2E_2·s U_NE_N, where Ui∈s,ideal(h),s,ideal(h)†U_i∈\U_s, ideal^(h),U_s, ideal^(h) \, EiE_i is a circuit of elementary gates, and N=cAlog1δ1N=c A 1 _1 with c constant is the number of queries to s,ideal(h)U_s, ideal^(h). The “real” implementation, on the other hand, is W~=U~1E1U~2E2⋯U~NEN W= U_1E_1 U_2E_2·s U_NE_N, where U~i∈s(h),s(h)† U_i∈\U_s^(h),U_s^(h) \. Then ‖W−W~‖≤cAlog(1δ1)‖s,ideal(h)−s(h)‖≤c2δ2Alog1δ1\|W- W\|≤ c A \! ( 1 _1 )\|U_s, ideal^(h)-U_s^(h)\|≤ c 2 _2A 1 _1 and the failure probability is δ1+c2δ2Alog1δ1 _1+c 2 _2A 1 _1. By taking δ1=O(δHS) _1=O ( δHS ) and δ2=O(δ12Alog2(1/δ1)) _2=O ( _1^2A ^2(1/ _1) ), the failure probability in outputting maxa∈r(s,a)+μ^h+1(s,a) _a \r(s,a)+ μ_h+1(s,a)\ is at most δHS δHS. By a usual union bound over all s∈s and h∈[H]h∈[H], the failure probability is at most δ. Regarding the query complexity, one call to the unitary s(h)U_s^(h) in order to compute μ~h+1(s,a) μ_h+1(s,a) and σ~h+1(s,a) σ_h+1(s,a) in (2) uses O(1θlog1δ2)=O(H3/2εlogHSAδ)O ( 1θ 1 _2 )=O ( H^3/2 HSAδ ) queries to p,p†Q_p,Q_p , while quantum maximum finding makes O(Alog1δ1)=O(AlogHSδ)O ( A 1 _1 )=O ( A HSδ ) queries to s(h)U_s^(h). Summing over all ×[H]S×[H], we obtain the stated query complexity. ∎ Algorithm 1 Quantum algorithm for optimal policies for finite-horizon MDPs 1:Finite state space S and action space A, horizon H, quantum sampling access to probability kernels p, failure probability δ∈(0,1)δ∈(0,1), error ε∈(0,H) ∈(0, H). 2:ε -optimal deterministic policy π. 3:θ←ε7H3/2θ← 7H^3/2 4:VH−1(s)←maxa∈r(s,a)V_H-1(s)← _a \r(s,a)\ and πH−1(s)←argmaxa∈r(s,a) _H-1(s)← *arg\,max_a \r(s,a)\ with probability 1−δHS1- δHS ∀s∈∀ s (Fact 1) 5:for h=H−2,H−3,…,0h=H-2,H-3,…,0 do 6: Let μh+1(s,a)=∑s′∈p(s′|s,a)Vh+1(s′) _h+1(s,a)= _s p(s |s,a)V_h+1(s ) ∀(s,a)∈×∀(s,a) ×A 7: Let σh+1(s,a)=∑s′∈p(s′|s,a)Vh+1(s′)2−(∑s′∈p(s′|s,a)Vh+1(s′))2 _h+1(s,a)= _s p(s |s,a)V_h+1(s )^2- ( _s p(s |s,a)V_h+1(s ) )^2 ∀(s,a)∈×∀(s,a) ×A 8: for s∈s do 9: Use Fact 2 to obtain a unitary s(h):|a⟩|0¯⟩↦|a⟩(1−δa|μ^h+1(s,a)⟩|μ~h+1(s,a)⟩|σ~h+1(s,a)⟩|garbage(a)⟩+δa|⟂a⟩) _s^(h)\!\!:|a | 0 |a ( 1\!-\! _a| μ_h+1(s,a) | μ_h+1(s,a) | σ_h+1(s,a) |\!garbage(a) \!+\! _a| _a ) with maxa∈δa=O~(δ2H2S2A) _a _a= O ( δ^2H^2S^2A ) and |μ~h+1(s,a)−μh+1(s,a)| | μ_h+1(s,a)- _h+1(s,a)| ≤θσh+1(s,a), ≤θ _h+1(s,a), |σ~h+1(s,a)−σh+1(s,a)| | σ_h+1(s,a)- _h+1(s,a)| ≤θH2, ≤θ H^2, μ^h+1(s,a):=μ~h+1(s,a)−θσ~h+1(s,a)−θ3/2H. μ_h+1(s,a):= μ_h+1(s,a)-θ σ_h+1(s,a)-θ^3/2H. 10: Use quantum maximum finding with unitary s(h)U_s^(h) (Fact 1 with s(h)U_s^(h)) to obtain Vh(s)V_h(s) and πh(s) _h(s) such that, with probability 1−δHS1- δHS, Vh(s)=maxa∈r(s,a)+μ^h+1(s,a)andπh(s)=argmaxa∈r(s,a)+μ^h+1(s,a) V_h(s)= _a \r(s,a)+ μ_h+1(s,a)\ _h(s)= *arg\,max_a \r(s,a)+ μ_h+1(s,a)\ 11: end for 12:end for 13:return π=(π0,…,πH−1)π=( _0,…, _H-1) 4 Optimal Policies for Infinite-Horizon Discounted MDPs In this section, we describe our quantum algorithm for computing ε -optimal policies for infinite-horizon discounted MDPs. Once again, the starting point is the set of equations V0≡0andVt+1=ℒVt∀t∈ℕ. V_0≡ 0 V_t+1=LV_t ∀ t . Since V∞∗,γV_∞ ,γ is the unique fixed point of ℒL, the solution VtV_t to the above equations converges to the optimal value as t→∞t→∞. The standard value iteration algorithm puterman2014markov iteratively computes VtV_t according to the above equations until ‖Vt+1−Vt‖∞≤ε2γΓ\|V_t+1-V_t\|_∞≤ 2γ , at which point ‖Vt+1−V∞∗,γ‖∞≤ε2\|V_t+1-V_∞ ,γ\|_∞≤ 2 and dε∞d_ ^∞ with dε∈argmaxd∈DℒdVt+1d_ ∈ *arg\,max_d D\L_dV_t+1\ is an ε -optimal policy (puterman2014markov, , Theorem 6.3.1). By the contractive property of ℒL, one must solve O(ΓlogΓε)O ( ) iteration steps. Therefore, an ε -optimal policy can thus be obtained in time O~(ΓS2A) O( S^2A) given full knowledge of the stochastic kernel p. With sampling access to p instead, approximating the quantities (PaVt)(s)(P_aV_t)(s) up to additive error εΓ leads to an ε -optimal value function and Γε -optimal greedy policy (in the worst case) after O~(Γ) O( ) iterations. The final classical or quantum complexities are O~(Γ7SAε) O ( ^7SA ) and O~(Γ4SAε) O ( ^4SA ), respectively. Similarly to the finite-horizon setting, these naive complexities can be vastly improved. Using the monotonicity, variance-reduction, and total-variance techniques briefly explained in Section 1, Sidford et al. sidford2018near proposed a modern value iteration algorithm with optimal complexity O~(Γ3SAε2) O ( ^3SA ^2 ). We stress that maintaining the monotonicity property Vt≤ℒπtVtV_t _ _tV_t throughout the algorithm is vital to guarantee an ε -optimal policy from an ε -optimal value function. In the quantum setting, quantum maximum finding can be employed with quantum mean estimation serving as an oracle in order to quadratically improve the dependence on A. By leveraging the simple approximation |μ~t(s,a)−(aVt)(s)|≤εΓ| μ_t(s,a)-(P_aV_t)(s)|≤ and keeping the monotonicity condition, Wang et al. wang2021quantum obtained a quantum algorithm with complexity O~(Γ3SAε) O ( ^3S A ). By instead directly quantising the classical algorithm of Sidford et al. sidford2018near , which improves the dependence on Γ but hinders the use of quantum maximum finding, the authors also obtained an alternative complexity of O~(Γ1.5SAε) O ( ^1.5SA ). Just like the finite-horizon setting, our quantum algorithm (Algorithm 2) works by nesting the more advanced quantum mean estimator of Kothari and O’Donnell Kothari2023mean — which takes variance into account — within quantum maximum finding, thus incorporating the total-variance technique from sidford2018near in order to improve the dependence on Γ . We also keep the monotonicity condition Vt≤ℒπtVtV_t _ _tV_t throughout the algorithm. Two calls to quantum mean estimation construct the oracle (to be employed by quantum maximum finding) smean:|a⟩|0¯⟩↦|a⟩(1−δa|μ^t(s,a)⟩|μ~t(s,a)⟩|σ~t(s,a)⟩|garbage(a)⟩+δa|⟂a⟩), mean_s:|a | 0 |a ( 1- _a| μ_t(s,a) | μ_t(s,a) | σ_t(s,a) |garbage(a) + _a| _a ), where μ~t(s,a)≈(aVt)(s) μ_t(s,a)≈(P_aV_t)(s), σ~t(s,a)≈σt(s,a) σ_t(s,a)≈ _t(s,a), and μ^t(s,a) μ_t(s,a) is a shifted version of μ~t(s,a) μ_t(s,a) so that μ^t(s,a)≤(aVt)(s) μ_t(s,a)≤(P_aV_t)(s). The monotonicity condition is guaranteed by keeping the maximum between maxa∈r(s,a)+γμ^t(s,a) _a \r(s,a)+γ μ_t(s,a)\ and the value Vt(s)V_t(s) from the previous iteration. Before proving the correctness and complexity of Algorithm 2, we bound in the next result the error accumulation in the presence of the variance. Lemma 1. Given policy π=(πt)t∈ℕπ=( _t)_t , define σtπ∈ℬ()σ^π_t∈ B(S) as σtπ=πt+1(Vtπ,γ)2−(πt+1Vtπ,γ)2 _t^π=P_ _t+1(V_t^π,γ)^2-(P_ _t+1V_t^π,γ)^2 for t∈ℕt . For any policy π=(πt)t∈ℕπ=( _t)_t and t∈ℕt , ‖∑t′=0t(∏i=t′+2t+1γπi)γσt′π‖∞≤2Γ2. \| _t =0^t ( _i=t +2^t+1 _ _i )γ _t ^π \|_∞≤ 2 ^2. Proof. Observe that γσtπ γ _t^π ≤γπt+1(Vtπ,γ)2−(γπt+1Vtπ,γ)2 ≤ _ _t+1(V_t^π,γ)^2-( _ _t+1V_t^π,γ)^2 =γπt+1(Vtπ,γ)2−(Vt+1π,γ−rπt+1)2 = _ _t+1(V_t^π,γ)^2-(V_t+1^π,γ-r_ _t+1)^2 (Vt+1π,γ=rπt+1+γπt+1Vtπ,γV_t+1^π,γ=r_ _t+1+ _ _t+1V_t^π,γ) ≤γπt+1(Vtπ,γ)2−(Vt+1π,γ)2+2Vt+1π,γ. ≤ _ _t+1(V_t^π,γ)^2-(V_t+1^π,γ)^2+2V_t+1^π,γ. (rπt+1≤r_ _t+1 1) Therefore, ∑t′=0t(∏i=t′+2t+1γπi)γσt′π _t =0^t ( _i=t +2^t+1 _ _i )γ _t ^π ≤∑t′=0t(∏i=t′+2t+1γπi)(γπt′+1(Vt′π,γ)2−(Vt′+1π,γ)2+2Vt′+1π,γ) ≤ _t =0^t ( _i=t +2^t+1 _ _i ) ( _ _t +1(V_t ^π,γ)^2-(V_t +1^π,γ)^2+2V_t +1^π,γ ) ≤2Γ2(1−γt+1)+∑t′=0t(∏i=t′+1t+1γπi)(Vt′π,γ)2−∑t′=0t(∏i=t′+2t+1γπi)(Vt′+1π,γ)2 ≤ 2 ^2(1-γ^t+1)1+ _t =0^t\! ( _i=t +1^t+1\! _ _i )\!(V_t ^π,γ)^2- _t =0^t\! ( _i=t +2^t+1\! _ _i )\!(V_t +1^π,γ)^2 (‖Vt′+1π,γ‖∞≤Γ\|V_t +1^π,γ\|_∞≤ and ‖∑t′=0t∏i=t′+1tγπi‖∞≤Γ(1−γt+1)\| _t =0^t _i=t +1^t _ _i\|_∞≤ (1-γ^t+1)) =2Γ2(1−γt+1)+(∏i=1t+1γπi)(V0π,γ)2−(Vt+1π,γ)2 =2 ^2(1-γ^t+1)1+ ( _i=1^t+1 _ _i )(V_0^π,γ)^2-(V_t+1^π,γ)^2 (telescope sum) ≤(2Γ2(1−γt+1)+γt+1) ≤(2 ^2(1-γ^t+1)+γ^t+1)1 (‖V0π,γ‖∞≤1\|V_0^π,γ\|_∞≤ 1) ≤2Γ2. ≤ 2 ^21. ∎ Theorem 2. Let ⟨,,p,r,γ⟩ ,A,p,r,γ be an infinite-horizon discounted MDP with γ∈[0,1)γ∈[0,1). Let δ∈(0,1)δ∈(0,1), ε∈(0,1] ∈(0,1], and T:=Γ⌈ln(Γ/ε)⌉T:= ( / ) . Algorithm 2 computes functions Vtt∈[T]⊂ℬ()\V_t\_t∈[T]⊂ B(S) and deterministic policy π=(πt)t∈[T]π=( _t)_t∈[T] such that, with probability 1−δ1-δ, Vt∗,γ−ε≤Vt≤Vtπ,γ≤Vt∗,γandV∞∗,γ−(ε+Γγt+1)≤Vt≤V∞πt∞,γ≤V∞∗,γ∀t∈[T]. V ,γ_t- 1≤ V_t≤ V^π,γ_t≤ V ,γ_t V ,γ_∞-( + γ^t+1)1≤ V_t≤ V_∞ _t^∞,γ≤ V_∞ ,γ ∀ t∈[T]. In particular, V∞∗,γ−2ε≤V∞πT−1∞,γ≤V∞∗,γV ,γ_∞-2 1≤ V _T-1^∞,γ_∞≤ V ,γ_∞. Its query complexity is (up to polyloglogpoly factors) O~(Γ2.5SAεlog(ΓSAδ)log(ΓSδ)log(Γε)). O ( ^2.5S A ( SAδ ) ( Sδ ) ( ) ). Algorithm 2 Quantum algorithm for optimal policies for infinite-horizon discounted MDPs 1:Finite state space S and action space A, discount factor γ∈[0,1)γ∈[0,1), quantum sampling access to probability kernels p, failure probability δ∈(0,1)δ∈(0,1), error ε∈(0,Γ] ∈(0, ]. 2:2ε2 -optimal stationary deterministic policy πT−1∞ _T-1^∞. 3:Let T←Γ⌈ln(Γ/ε)⌉T← ( / ) and θ←ε7Γ3/2θ← 7 ^3/2 4:V0(s)←maxa∈r(s,a)V_0(s)← _a \r(s,a)\ and π0(s)←argmaxa∈r(s,a) _0(s)← *arg\,max_a \r(s,a)\ with probability 1−δTS1- δTS ∀s∈∀ s (Fact 1) 5:for t∈[T−1]t∈[T-1] do 6: Let μt(s,a)=∑s′∈p(s′|s,a)Vt(s′) _t(s,a)= _s p(s |s,a)V_t(s ) ∀(s,a)∈×∀(s,a) ×A 7: Let σt(s,a)=∑s′∈p(s′|s,a)Vt(s′)2−(∑s′∈p(s′|s,a)Vt(s′))2 _t(s,a)= _s p(s |s,a)V_t(s )^2- ( _s p(s |s,a)V_t(s ) )^2 ∀(s,a)∈×∀(s,a) ×A 8: for s∈s do 9: Use Fact 2 to obtain a unitary s(t):|a⟩|0¯⟩↦|a⟩(1−δa|μ^t(s,a)⟩|μ~t(s,a)⟩|σ~t(s,a)⟩|garbage(a)⟩+δa|⟂a⟩) _s^(t):|a | 0 |a ( 1- _a| μ_t(s,a) | μ_t(s,a) | σ_t(s,a) |garbage(a) + _a| _a ) with maxa∈δa=O~(δ2T2S2A) _a _a= O ( δ^2T^2S^2A ) and |μ~t(s,a)−μt(s,a)| | μ_t(s,a)- _t(s,a)| ≤θσt(s,a), ≤θ _t(s,a), |σ~t(s,a)−σt(s,a)| | σ_t(s,a)- _t(s,a)| ≤θΓ2, ≤θ ^2, μ^t(s,a):=μ~t(s,a)−θσ~t(s,a)−θ3/2Γ. μ_t(s,a):= μ_t(s,a)-θ σ_t(s,a)-θ^3/2 . 10: Use quantum maximum finding with unitary s(t)U_s^(t) (Fact 1 with s(t)U_s^(t)) to obtain Vt+1′(s)V _t+1(s) and πt+1′(s)π _t+1(s) such that, with probability 1−δTS1- δTS, Vt+1′(s)=maxa∈r(s,a)+γμ^t(s,a)andπt+1′(s)=argmaxa∈r(s,a)+γμ^t(s,a) V _t+1(s)= _a \r(s,a)+γ μ_t(s,a)\ π _t+1(s)= *arg\,max_a \r(s,a)+γ μ_t(s,a)\ 11: if Vt+1′(s)≥Vt(s)V_t+1 (s)≥ V_t(s) then Vt+1(s)←Vt+1′(s)V_t+1(s)← V _t+1(s) and πt+1(s)←πt+1′(s) _t+1(s)← _t+1 (s) 12: else Vt+1(s)←Vt(s)V_t+1(s)← V_t(s) and πt+1(s)←πt(s) _t+1(s)← _t(s) 13: end if 14: end for 15:end for 16:return (π0,…,πT−1)( _0,…, _T-1) Proof. The proof is similar to Theorem 1. We shall prove by induction on t∈ℕt that Vt∗,γ−ε≤Vt≤Vtπ,γ≤Vt∗,γandVt≤V∞πt∞,γ≤V∞∗,γ∀t∈[T]. V ,γ_t- 1≤ V_t≤ V^π,γ_t≤ V ,γ_t V_t≤ V_∞ _t^∞,γ≤ V_∞ ,γ ∀ t∈[T]. The inequality V∞∗,γ−(ε+Γγt+1)≤VtV ,γ_∞-( + γ^t+1)1≤ V_t then follows from the above and the fact that (let d∗∈argmaxd∈DV∞d∞,γd ∈ _d DV^d^∞,γ_∞ be an optimal deterministic decision rule) V∞∗,γ(s) V_∞ ,γ(s) =[∑t′=0∞γt′r(st′,d∗(st′))|s0=s,si∼p(⋅|si,d∗(si))] =E [ _t =0^∞γ^t r(s_t ,d (s_t ))~ |~s_0=s,s_i p(·|s_i,d (s_i)) ] ≤[∑t′=0tγt′r(st′,d∗(st′))|s0=s,si∼p(⋅|si,d∗(si))]+∑t′=t+1∞γt′ [ _t =0^tγ^t r(s_t ,d (s_t ))~ |~s_0=s,s_i p(·|s_i,d (s_i)) ]+ _t =t+1^∞γ^t (r(s,a)≤1r(s,a)≤ 1) ≤Vt∗,γ(s)+γt+1Γ. ≤ V_t ,γ(s)+γ^t+1 . Moreover, γTΓ≤e−T(1−γ)Γ≤εγ^T ≤ e^-T(1-γ) ≤ if T=Γ⌈ln(Γ/ε)⌉T= ( / ) , using that x≤e−(1−x)x≤ e^-(1-x) for all x∈ℝx . The base case t=0t=0 of the induction is trivial since V0(s)=maxa∈r(s,a)=V0∗,γ(s)V_0(s)= _a \r(s,a)\=V_0 ,γ(s) and π0(s)=argmaxa∈r(s,a) _0(s)= *arg\,max_a \r(s,a)\. Assume then that Algorithm 2 has computed functions V0,…,VtV_0,…,V_t and decision rules π0,…,πt _0,…, _t (which form policy π) such that Vt′∗,γ−ε≤Vt′≤Vt′π,γ≤Vt′∗,γandVt′≤V∞πt′∞,γ≤V∞∗,γ∀t′=0,…,t, V ,γ_t - 1≤ V_t ≤ V^π,γ_t ≤ V ,γ_t V_t ≤ V_∞ _t ^∞,γ≤ V_∞ ,γ ∀ t =0,…,t, and consider the time step t+1t+1. Let the true quantities μt(s,a):=(aVt)(s)andσt(s,a):=(aVt2)(s)−(aVt)2(s). _t(s,a):=(P_aV_t)(s) _t(s,a):=(P_aV_t^2)(s)-(P_aV_t)^2(s). Let θ:=ε7Γ3/2θ:= 7 ^3/2. Once again we invoke Fact 2 twice to construct the unitary s(t):|a⟩|0¯⟩↦|a⟩(1−δa|μ~t(s,a)⟩|σ~t(s,a)⟩|garbage(a)⟩+δa|⟂a⟩), _s^(t):|a | 0 |a ( 1- _a| μ_t(s,a) | σ_t(s,a) |garbage(a) + _a| _a ), (4) where δa∈[0,1) _a∈[0,1) is the failure probability of quantum mean estimation within the branch |a⟩|a of the wave function, |garbage(a)⟩|garbage(a) is a “garbage” unit complex vector accumulated through the computation, |⟂a⟩| _a is a unit complex vector orthogonal to |μ~t(s,a)⟩|σ~t(s,a)⟩|garbage(a)⟩| μ_t(s,a) | σ_t(s,a) |garbage(a) , and ∀(s,a)∈×:|μ~t(s,a)−μt(s,a)|≤θσt(s,a),|σ~t(s,a)−σt(s,a)|≤2θΓ2, ∀(s,a) ×A: aligned &| μ_t(s,a)- _t(s,a)|≤θ _t(s,a),\\ &| σ_t(s,a)- _t(s,a)|≤ 2θ ^2, aligned (5) using that the standard deviation of Vt2V^2_t is at most Γ2 ^2 and thus one can compute approximations of (aVt2)(s)(P_aV_t^2)(s) and (aVt)2(s)(P_aV_t)^2(s) with error at most θΓ2θ ^2 each. Using (5), ∀(s,a)∈×:|μ~t(s,a)−μt(s,a)|≤θσ~t(s,a)+2θ3/2Γ. ∀(s,a) ×A: | μ_t(s,a)- _t(s,a)|≤θ σ_t(s,a)+ 2θ^3/2 . Define then the quantities ∀(s,a)∈×:μ^t(s,a):=μ~t(s,a)−θσ~t(s,a)−2θ3/2Γ, ∀(s,a) ×A: μ_t(s,a):= μ_t(s,a)-θ σ_t(s,a)- 2θ^3/2 , which have one-side error. We can express the above quantity using the optimal-policy variance σt∗(s,a):=(a(Vt∗,γ)2)(s)−(aVt∗,γ)2(s)σ _t(s,a):=(P_a(V_t ,γ)^2)(s)-(P_aV_t ,γ)^2(s) since ∀(s,a)∈×:σ~t(s,a)≤σt(s,a)+2θΓ≤σt∗(s,a)+ε+2θΓ, ∀(s,a) ×A: σ_t(s,a)≤ _t(s,a)+ 2θ ≤ _t (s,a)+ + 2θ , where we used (5) and that Var[Vt]≤Var[Vt∗,γ]+Var[Vt∗,γ−Vt]≤Var[Vt∗,γ]+ε Var[V_t]≤ Var[V ,γ_t]+ Var[V ,γ_t-V_t]≤ Var[V ,γ_t]+ if ‖Vt∗,γ−Vt‖∞≤ε\|V ,γ_t-V_t\|_∞≤ according to the induction hypothesis. Hence ∀(s,a)∈×:μ^t(s,a)≤μt(s,a),μ^t(s,a)≥μt(s,a)−2θσt∗(s,a)−2θε−42θ3/2Γ. ∀(s,a) ×A: aligned & μ_t(s,a)≤ _t(s,a),\\ & μ_t(s,a)≥ _t(s,a)-2θ _t (s,a)-2θ -4 2θ^3/2 . aligned By subtracting the content of register |σ~t(s,a)⟩| σ_t(s,a) from the register |μ~t(s,a)⟩| μ_t(s,a) in (4), it is then possible to effectively construct a black-box unitary s(t):|a⟩|0¯⟩↦|a⟩(1−δa|μ^t(s,a)⟩+δa|⟂a⟩)U_s^(t):|a | 0 |a ( 1- _a| μ_t(s,a) + _a| _a ) using oracle p,p†Q_p,Q_p (up to garbage states). The maximum over a∈a of r(s,a)+γμ^t(s,a)r(s,a)+γ μ_t(s,a) can thus be found by using quantum maximum finding (Fact 1) with unitary s(t)U_s^(t), leading to Vt+1′(s)=maxa∈r(s,a)+γμ^t(s,a)V _t+1(s)= _a \r(s,a)+γ μ_t(s,a)\ and πt+1′(s)=argmaxa∈r(s,a)+γμ^t(s,a)π _t+1(s)= *arg\,max_a \r(s,a)+γ μ_t(s,a)\ with probability 1−δHS1- δHS. We then let Vt+1(s)=maxVt+1′(s),Vt(s)andπt+1(s)=πt+1′(s)ifVt+1′(s)≥Vt(s),πt(s)ifVt+1′(s)<Vt(s). V_t+1(s)= \V_t+1 (s),V_t(s)\ _t+1(s)= cases _t+1 (s)&if~V_t+1 (s)≥ V_t(s),\\ _t(s)&if~V_t+1 (s)<V_t(s). cases This means that ∀s∈:Vt+1(s)≥(ℒπt+1∗Vt)(s)−2γθσt∗(s,πt+1∗(s))−2γθε−42γθ3/2Γ. ∀ s : V_t+1(s)≥(L_π _t+1V_t)(s)-2γθ _t (s, _t+1 (s))-2γθ -4 2γθ^3/2 . (6) We now prove that Vt+1≤ℒπt+1Vt=Vt+1π,γ≤ℒπt+1Vt+1V_t+1 _ _t+1V_t=V_t+1^π,γ _ _t+1V_t+1. There are two cases to analyse. Case I: Vt+1′(s)≥Vt(s)V _t+1(s)≥ V_t(s). Then Vt+1(s)=r(s,πt+1(s))+γμ^t(s,πt+1(s))≤(ℒπt+1Vt)(s)≤(ℒπt+1Vt+1)(s), V_t+1(s)=r(s, _t+1(s))+γ μ_t(s, _t+1(s))≤(L_ _t+1V_t)(s)≤(L_ _t+1V_t+1)(s), since μ^t(s,a)≤μt(s,a) μ_t(s,a)≤ _t(s,a) and Vt+1≥VtV_t+1≥ V_t. Case I: Vt+1′(s)<Vt(s)V _t+1(s)<V_t(s). Then Vt+1(s)=Vt(s)≤(ℒπtVt)(s)=(ℒπt+1Vt)(s)≤(ℒπtVt+1)(s), V_t+1(s)=V_t(s)≤(L_ _tV_t)(s)=(L_ _t+1V_t)(s)≤(L_ _tV_t+1)(s), using the induction hypothesis in Vt(s)≤(ℒπtVt)(s)V_t(s)≤(L_ _tV_t)(s) and that Vt+1≥VtV_t+1≥ V_t and πt+1(s)=πt(s) _t+1(s)= _t(s). This proves that Vt+1≤Vt+1π,γ≤ℒπt+1Vt+1V_t+1≤ V_t+1^π,γ _ _t+1V_t+1, which by the monotonicity of the Bellman operator ℒπt+1L_ _t+1 and the fact that V∞πt+1∞,γV_∞ _t+1^∞,γ is its fixed point, leads to Vt+1≤ℒπt+1∞Vt+1=V∞πt+1∞,γ≤V∞∗,γV_t+1 _ _t+1^∞V_t+1=V_∞ _t+1^∞,γ≤ V_∞ ,γ. We move on to proving that Vt+1∗,γ−ε≤Vt+1V ,γ_t+1- 1≤ V_t+1. For such, Vt+1∗,γ−Vt+1 V_t+1 ,γ-V_t+1 ≤ℒπt+1∗Vt∗,γ−ℒπt+1∗Vt+γξt+1=γπt+1∗(Vt∗,γ−Vt)+γξt+1, _ _t+1 V ,γ_t-L_ _t+1 V_t+γ _t+1= _ _t+1 (V ,γ_t-V_t)+γ _t+1, (by (6) and Vt+1∗,γ=ℒπt+1∗Vt∗,γV_t+1 ,γ=L_ _t+1 V_t ,γ) where we defined ξt+1(s)=2θσt∗(s,πt+1∗(s))+2θε+42θ3/2Γ _t+1(s)=2θ _t (s, _t+1 (s))+2θ +4 2θ^3/2 . Let σt∗=πt+1∗(Vt∗,γ)2−(πt+1∗Vt∗,γ)2∈ℬ()σ _t=P_ _t+1 (V_t ,γ)^2-(P_ _t+1 V_t ,γ)^2∈ B(S). Solving the above recursion with the boundary condition V0∗,γ≡V0V_0 ,γ≡ V_0, Vt+1∗,γ−Vt+1 V_t+1 ,γ-V_t+1 ≤∑t′=1t+1(∏i=t′+1t+1γπi∗)γξt′. ≤ _t =1^t+1 ( _i=t +1^t+1 _ _i )γ _t . Using that ‖∑t′=0t(∏i=t′+2t+1γπi∗)γσt′∗‖∞≤‖Γ∑t′=0t(∏i=t′+2t+1γπi∗)γ2σt′∗‖∞1/2≤2Γ3/2, \| _t =0^t ( _i=t +2^t+1 _ _i )γ _t \|_∞≤ \| _t =0^t ( _i=t +2^t+1 _ _i )γ^2 _t \|_∞^1/2≤ 2 ^3/2, (by Cauchy-Schwarz and Lemma 1) and that ‖∑t′=1t+1∏i=t′+1t+1γπi∗‖∞≤∑t′=0tγt′≤Γ\| _t =1^t+1 _i=t +1^t+1 _ _i \|_∞≤ _t =0^tγ^t ≤ , then finally Vt+1∗,γ(s)−Vt+1(s)≤22θΓ3/2+2θΓε+42θ3/2Γ2=ε(227+2ε7Γ+4273/2Γ1/4)<ε. V_t+1 ,γ(s)-V_t+1(s)≤ 2 2θ ^3/2+2θ +4 2θ^3/2 ^2= ( 2 27+ 2 7 + 4 27^3/2 ^1/4 )< . (θ=ε7Γ3/2θ= 7 ^3/2 and ε≤Γ ≤ ) The error analysis of Algorithm 2 is very similar to Algorithm 1. The failure probability is δ1+c2δ2Alog1δ1 _1+c 2 _2A 1 _1, where δ1 _1 is the error associated with quantum maximum finding (Fact 1) and δ2 _2 is the error behind quantum mean estimation (Fact 2). Choosing δ1=O(δTS) _1=O ( δTS ) and δ2=O(δ12Alog2(1/δ1)) _2=O ( _1^2A ^2(1/ _1) ) leads to outputting maxa∈r(s,a)+γμ^t(s,a) _a \r(s,a)+γ μ_t(s,a)\ with probability at least 1−δTS1- δTS. A union bound over all (s,t)∈×[T](s,t) ×[T] leads to a failure probability at most δ. Regarding the query complexity, for each s∈s , one call to the unitary s(t)U_s^(t) in order to compute μ~t(s,a) μ_t(s,a) and σ~t(s,a) σ_t(s,a) in (4) uses O(1θlog1δ2)=O~(Γ3/2εlogΓSAδ)O ( 1θ 1 _2 )= O ( ^3/2 SAδ ) queries to pQ_p, while quantum maximum finding makes O(Alog1δ1)=O~(AlogΓSδ)O ( A 1 _1 )= O ( A Sδ ) queries to s(t)U_s^(t). Summing over all ×[T]S×[T], we obtain the stated query complexity. ∎ References [1] Rajeev Acharya, Dmitry A. Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C. Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A. Browne, Brett Buchea, Bob B. Buckley, David A. Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Yu Chen, Zijun Chen, Ben Chiaro, Desmond Chik, Charina Chou, Jahan Claes, Agnetta Y. Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L. Crook, Ben Curtin, Sayan Das, Alex Davies, Laura De Lorenzo, Dripto M. Debroy, Sean Demura, Michel Devoret, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Thomas Edlich, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Edward Farhi, Vinicius S. Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G. Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Élie Genois, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A. Gross, Steve Habegger, John Hall, Michael C. Hamilton, Monica Hansen, Matthew P. Harrigan, Sean D. Harrington, Francisco J. H. Heras, Stephen Heslin, Paula Heu, Oscar Higgott, Gordon Hill, Jeremy Hilton, George Holland, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J. Huggins, Lev B. Ioffe, Sergei V. Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Amir H. Karamlou, Kostyantyn Kechedzhi, Julian Kelly, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V. Klimov, Andrey R. Klots, Bryce Kobrin, Pushmeet Kohli, Alexander N. Korotkov, Fedor Kostritsa, Robin Kothari, Borislav Kozlovskii, John Mark Kreikebaum, Vladislav D. Kurilovich, Nathan Lacroix, David Landhuis, Tiano Lange-Dei, Brandon W. Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Joonho Lee, Kenny Lee, Yuri D. Lensky, Shannon Leon, Brian J. Lester, Wing Yan Li, Yin Li, Alexander T. Lill, Wayne Liu, William P. Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Fionn D. Malone, Ashley Maloney, Salvatore Mandrà, James Manyika, Leigh S. Martin, Orion Martin, Steven Martin, Cameron Maxfield, Jarrod R. McClean, Matt McEwen, Seneca Meeks, Anthony Megrant, Xiao Mi, Kevin C. Miao, Amanda Mieszala, Reza Molavi, Sebastian Molina, Shirin Montazeri, Alexis Morvan, Ramis Movassagh, Wojciech Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Hartmut Neven, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Chia-Hung Ni, Murphy Yuezhen Niu, Thomas E. O’Brien, William D. Oliver, Alex Opremcak, Kristoffer Ottosson, Andre Petukhov, Alex Pizzuto, John Platt, Rebecca Potter, Orion Pritchard, Leonid P. Pryadko, Chris Quintana, Ganesh Ramachandran, Matthew J. Reagor, John Redding, David M. Rhodes, Gabrielle Roberts, Eliott Rosenberg, Emma Rosenfeld, Pedram Roushan, Nicholas C. Rubin, Negar Saei, Daniel Sank, Kannan Sankaragomathi, Kevin J. Satzinger, Henry F. Schurkus, Christopher Schuster, Andrew W. Senior, Michael J. Shearn, Aaron Shorter, Noah Shutty, Vladimir Shvarts, Shraddha Singh, Volodymyr Sivak, Jindra Skruzny, Spencer Small, Vadim Smelyanskiy, W. Clarke Smith, Rolando D. Somma, Sofia Springer, George Sterling, Doug Strain, Jordan Suchard, Aaron Szasz, Alex Sztein, Douglas Thor, Alfredo Torres, M. Mert Torunbalci, Abeer Vaishnav, Justin Vargas, Sergey Vdovichev, Guifre Vidal, Benjamin Villalonga, Catherine Vollgraff Heidweiller, Steven Waltman, Shannon X. Wang, Brayden Ware, Kate Weber, Travis Weidel, Theodore White, Kristi Wong, Bryan W. K. Woo, Cheng Xing, Z. Jamie Yao, Ping Yeh, Bicheng Ying, Juhwan Yoo, Noureldin Yosri, Grayson Young, Adam Zalcman, Yaxing Zhang, Ningfeng Zhu, Nicholas Zobrist, Google Quantum AI, and Collaborators. Quantum error correction below the surface code threshold. Nature, 638(8052):920–926, Feb 2025. [2] Leonardo Alchieri, Davide Badalotti, Pietro Bonardi, and Simone Bianco. An introduction to quantum machine learning: from quantum logic to quantum deep learning. Quantum Machine Intelligence, 3(2):28, Nov 2021. [3] Jonathan Allcock, Jinge Bao, Joao F. Doriguello, Alessandro Luongo, and Miklos Santha. Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates. Quantum, 8:1530, November 2024. [4] Andris Ambainis, Joao F Doriguello, and Debbie Lim. A bit of freedom goes a long way: Classical and quantum algorithms for reinforcement learning under a generative model. arXiv preprint arXiv:2507.22854, 2025. [5] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, Oct 2019. [6] Karl Johan Åström. Optimal control of Markov processes with incomplete state information I. Journal of mathematical analysis and applications, 10:174–205, 1965. [7] Nicole Bäuerle and Ulrich Rieder. Markov decision processes with applications to finance. Springer Science & Business Media, 2011. [8] Casey C Bennett and Kris Hauser. Artificial intelligence framework for simulating clinical decision-making: A Markov decision process approach. Artificial intelligence in medicine, 57(1):9–19, 2013. [9] Dimitri Bertsekas. Dynamic programming and optimal control: Volume I, volume 4. Athena scientific, 2012. [10] Dimitri Bertsekas. Abstract dynamic programming. Athena Scientific, 2022. [11] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195–202, Sep 2017. [12] Liuhua Chen, Haiying Shen, and Karan Sapra. Distributed autonomous virtual resource management in datacenters using finite-Markov decision process. In Proceedings of the ACM Symposium on Cloud Computing, pages 1–13, 2014. [13] Yanlin Chen and Ronald de Wolf. Quantum algorithms and lower bounds for linear regression with norm constraints. arXiv preprint arXiv:2110.13086, 2021. [14] Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, and Pooya Ronagh. Reinforcement learning using quantum boltzmann machines. Quantum Info. Comput., 18(1–2):51–74, February 2018. [15] Daoyi Dong, Chunlin Chen, Hanxiong Li, and Tzyh-Jong Tarn. Quantum reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 38(5):1207–1220, 2008. [16] João F Doriguello, Alessandro Luongo, and Ewin Tang. Do you know what q-means? arXiv preprint arXiv:2308.09701, 2023. [17] Christoph Dür and Peter Høyer. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014, 1996. [18] Eugene A Feinberg and Adam Shwartz. Handbook of Markov decision processes: methods and applications, volume 40. Springer Science & Business Media, 2012. [19] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91(3):325–349, Jun 2013. [20] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Architectures for a quantum random access memory. Phys. Rev. A, 78:052310, Nov 2008. [21] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett., 100:160501, Apr 2008. [22] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996. [23] Yassine Hamoudi. Quantum Algorithms for the Monte Carlo Method. Theses, Université Paris Cité, July 2021. [24] Yassine Hamoudi. Quantum Sub-Gaussian Mean Estimator. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [25] Yassine Hamoudi and Frédéric Magniez. Quantum Chebyshev’s Inequality and Applications. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [26] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103:150502, Oct 2009. [27] Qiying Hu and Wuyi Yue. Markov decision processes with their applications, volume 14. Springer Science & Business Media, 2007. [28] Samuel Jaques and Arthur G. Rattew. QRAM: A Survey and Critique. Quantum, 9:1922, December 2025. [29] Sofiene Jerbi, Arjan Cornelissen, Maris Ozols, and Vedran Dunjko. Quantum Policy Gradient Algorithms. In Omar Fawzi and Michael Walter, editors, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), volume 266 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:24, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [30] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003. [31] Michael Kearns, Yishay Mansour, and Andrew Y. Ng. A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine Learning, 49(2):193–208, Nov 2002. [32] Michael Kearns and Satinder Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. Advances in neural information processing systems, 11, 1998. [33] Michael Kearns and Satinder Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. In M. Kearns, S. Solla, and D. Cohn, editors, Advances in Neural Information Processing Systems, volume 11. MIT Press, 1998. [34] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: A quantum algorithm for unsupervised machine learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. [35] Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [36] Robin Kothari and Ryan O’Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1186–1215, 2023. [37] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12861–12872. Curran Associates, Inc., 2020. [38] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv:1307.0411, 2013. [39] Bin Luo, Yuwen Huang, Jonathan Allcock, Xiaojun Lin, Shengyu Zhang, and John C.S. Lui. Quantum algorithms for finite-horizon Markov decision processes. In Forty-second International Conference on Machine Learning, 2025. [40] Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015. [41] Mausam Natarajan and Andrey Kolobov. Planning with Markov decision processes: An AI perspective. Springer Nature, 2022. [42] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. [43] Warren B Powell. Approximate Dynamic Programming: Solving the curses of dimensionality, volume 703. John Wiley & Sons, 2007. [44] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. [45] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Phys. Rev. Lett., 113:130503, Sep 2014. [46] V. Saggio, B. E. Asenbeck, A. Hamann, T. Strömberg, P. Schiansky, V. Dunjko, N. Friis, N. C. Harris, M. Hochberg, D. Englund, S. Wölk, H. J. Briegel, and P. Walther. Experimental quantum speed-up in reinforcement learning agents. Nature, 591(7849):229–233, Mar 2021. [47] Renato Cesar Sato and Désirée Moraes Zouain. Markov models in health care. Einstein (São Paulo), 8:376–379, 2010. [48] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56(2):172–185, 2015. [49] P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. [50] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving Markov decision processes with a generative model. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. [51] Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving Markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, page 770–787, USA, 2018. Society for Industrial and Applied Mathematics. [52] Lauren N Steimle and Brian T Denton. Markov decision processes for screening and treatment of chronic diseases. Markov Decision Processes in Practice, pages 189–222, 2017. [53] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press Cambridge, 1998. [54] Csaba Szepesvári. Algorithms for Reinforcement Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Springer Cham, 2010. [55] Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, and Martin Roetteler. Quantum algorithms for reinforcement learning with a generative model. In International Conference on Machine Learning, pages 10916–10926. PMLR, 2021. [56] Mengdi Wang. Randomized linear programming solves the discounted Markov decision problem in nearly-linear (sometimes sublinear) running time. arXiv preprint arXiv:1704.01869, 2017. [57] Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Info. Comput., 15(3–4):316–356, March 2015. [58] Simon Wiedemann, Daniel Hein, Steffen Udluft, and Christian B. Mendl. Quantum policy iteration via amplitude estimation and Grover search – towards quantum advantage for reinforcement learning. Transactions on Machine Learning Research, 2023. [59] Han Zhong, Jiachen Hu, Yecheng Xue, Tongyang Li, and Liwei Wang. Provably efficient exploration in quantum reinforcement learning with logarithmic worst-case regret. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024.