Quantum Policy Iteration via Amplitude Estimation and Grover Search – Towards Quantum Advantage for Reinforcement Learning
Authors: Simon Wiedemann
Daniel Hein
Steffen Udluft
Christian B. Mendl
Venue: Accepted by TMLR ()

Abstract: We present a full implementation and simulation of a novel quantum reinforcement learning method. Our work is a detailed and formal proof of concept for how quantum algorithms can be used to solve reinforcement learning problems and shows that, given access to error- free, efficient quantum realizations of the agent and environment, quantum methods can yield provable improvements over classical Monte-Carlo based methods in terms of sample complexity. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which is quadratically more efficient compared to an analogous classi- cal Monte Carlo estimation and is based on a quantum mechanical realization of a finite Markov decision process (MDP). Building on QPE, we derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate.

Published in Transactions on Machine Learning Research (03/2023)
Quantum Policy Iteration via Amplitude Estimation and Grover Search Towards Quantum Advantage for Reinforcement Learning
Simon Wiedemann'
simono wwg.ooww.iiieeeeenn@Ba...dddd
Technical University of Munich, Germany
Daniel Hein
hein. heinn.daniell@siimeen.. com
Siemens Technology, Munich, Germany
Steffen Udluft
steffen. setteeuudllff@@@eeems.cmomm com
Siemens Technology, Munich, Germany
Christian B. Mendl
Murislian.merdllllne
Technical Universily of Munich, Germany
Reviewed on OpenReview: https: // openreview. net/ forum? id= HC1 PCM1P
Abstract
We present full implementation and simulation of a novel quantum reinforcement learning method. Our work detailed and formal proof of concept for how quantum algorithms can be used to solve reinforcement lcarning problems and shows that, given access to error- free, efficient quantum realizations of the agent and environment, quantum methods can yield provable improvements over classical Monte- Carlo based methods in terms of sample complexity. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which quadratically more efficient compared to an analogous classi- cal Monte Carlo estimation and based on a quantum mechanical realization of a finite Markov decision process (MDP). Building QPE, derive quantum policy itcration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate.
1 Introduction
Successful reinforcement lcarning (RL) algorithms for challenging tasks come at the cost of computationally expensive training Silver et al. 2016) Since quantum computers can perform certain complex tasks much
faster than classical machines (Grover 1996 Shor 1999 hope is that quantum computers might also enable more efficient RL algorithms. Today, there theoretical and practical evidence that quantum interaction between agent and environment can indeed reduce the time it takes for the agent to learn (Section 2 In this work, we show that another possible source for quantum advantage in RT might come in the form of roducing the number of agent-environment interactions needed to find optimal policy. We make this point by explicitly constructing quantum policy iteration algorithı whose policy evaluation step is provably more sample efficient than a comparable classical Monte-Cart (MC) approach.
In particular, we describe an optimization-basee quantum algorithm for RL that makes use of a direct quantum mechanical realization of finite MDP, which agent and environment are modelled by unitary operators and exchange states, actions, and rewards in superposition (Section 4.1 A brief introduction to concepts from discrete quantum computing (including quantum superposition and unitary operators on
Work done while Siemens.

---

Published in Transactions on Machine Learning Research (03/2023)
quantum states) that are necessary to understand this construction is given in Section 3 Using the quantum realization of an MDP; we show in detail how to use amplitude estimation to estimate the value function of a policy in a finite MDP with finite horizon (Section 4.2). This quantum policy evaluation (QPE) algorithm can be compared to a MC method, i.., sampling from agent-environment interactions to estimate the value function. QPE uses quantum samples (qsamples) instead of classical ones and provides a quantum advantage over any possible classical MC approach; it needs quadratically fewer qsamples to estimate the value function of a policy up a given precision. We embed QPE into an optimization scheme that uses repeated Grover- like searches of the set of policies to find decision rule with e-optimal performance (Section 4.3) The resulting routine shares similarities with the policy iteration method from dynamic programming Sutton &
Barto 2018) and, thus, we call it quantur (upprozimate) policy iteration.
Our detailed description of quantum policy iteration shows how to solve a general MDP using only quantum methods and no classical sub-routines. We provide explicit constructions of all unitary operators used in our methods. The major contribution of our work is an in-depth description of QPE for finite MDPs and a proof of its quantum-advvntlag over classical MC. In the experiments, we exemplify QPE and quantum policy iteration on the level of single and multi qubit gates on a digital quantum computer. Simulations of this implementation numerically confirm the mathematically proven quantum advantage of QPE over classical MC policy evaluation and illustrate the convergence behavior of quantum policy iteration (Section
2
Related Work
Most existing quantum RL approaches can be roughly divided into two categorics: quantum enhancod agents that learn in classical environments, and scenarios where the agent and environment can interact quantum mechanically. For both approaches, there is evidence that quantum methods could indeed outperform clas- sical approaches.
An example for the first category, is quantum projective simulation (Briegel & De las Cuevas 2012 where an agent makes decisions using a quantum random walk on a learned graph that represents its internal memory. In this approach, the special properties of quantum walks allow for fast decision making and thus less active learning time than classical agents. Furthermore, various mnantum-cnhanee that learn in classical environments by replacing components of classical learning algorithms with quantum counterparts. There are approaches for deep Q-learning and policy gradient methods, where classical artificial neural networks are replaced by analogous varialional quantum circwils (VQCs) with trainable parameters
agents have been described
CChn et al. 2020 Lockwood & Si 2020
Moll & Kunczik 2021 Skolik et al. 2021 Jerbi et al. 2021
Thcoretical work by Dunjko et al. 2015 indicates that the possibility of quantum interaction between agent and environment can be leveraged to design quantum-enhanced agents that provably outperform the best
possible classical learner in certain environments (Dunjko et al., 2015 2016 2017a).. One such approach is related to our ideas and uses Grover searches in deterministic environments find sequences of actions that lead to high rewards (Dunjko et al. 2016). The possibility of using amplitude estimation similar to QPE to be applied to st.chastic environments are also discussed. Further extensions were proposed by Dunjko et al.
(017b) and Hamann et al. 2020)).
Another related direction of quantum RL research is the development of methods based on DP. Naguleswaran & White (0055) propose to use quantum search methods to speed up a discrete maximization step during value itcration. [Wang et al. (2021) used similar tools as in this work (i.c., amplitude estimation and quantum optimization) to obtain quantum speedups for subroutines of otherwise classical DP algorithms. Recently, Cherrat et al. (2022) developed quantum policy iteration algorithm in which the Bellman equations for policy evaluation are solved using a quantum method for solving systems of linear equations.
Contrary to the methods by Naguleswaran & White (2055), Wang et al. 2021) and Cherrat el al. (2022) our novel quantum (approximate) policy iteration is not a quantum-enhant enhancced version of an existing classical DP method and uses no classical subroutines. It also differs from the idcas of Dunjko et al. (2016) as it directly searches for the optimal policy instead of looking for rewarded actions that are then used improve the decision rule.
2

---

Published in Transactions on Machine Learning Research (03/2023)
3 Background
This work is largely concerned with quantum algorithms. These are routines that process information in the form of quantum states and follow the rules of quantum mechanics. To facilitate reading for readers with little or no background in quantum mechanics, we give a brief introduction to the most important concepts in this section. Thereby, we restrict ourselves to discrete quantum states which can be thought of as vectors in a finteeddimensioall complex Hilbert space and operations on the states can be expressed using linear algebra. Discrete quantum mechanics is still wide field, and limit the content. of this section to those concepts that are necessary to understand our work and omit most physical details. For detailed introduction to quantum computing, we refer readers to the extensive textbook by Nielson & Chuang (2002).
The quantum algorithms in this work process information on the states, actions and rewards of an MDP. If we want to find the best policy for an MDP on a classical computer, we would first have to encode the states, actions and rewards using classical bits and then use algorithms such as dynamic programming to determine the best policy. If we instead want use a quantum computer, we first have to encode the states, actions and rewards as discrete quantum mechanical objects. Consider for example the set of all actions A of the MDP. We now discuss how to express this set and the elements therein in the language of quantum computing, Assume there are N = |A| actions. We identify each action an E A with a member of an orthonormal basis of the Hilbert space CN,, which we call the action space A. For convenience, we choose the standard basis. This identificatinn looks as follows
On + lan) A (0,...
O)T
index n
The notation ja,) emphasizes that this is a quantum state and considered a vector. Note that (am)aa)) = 8m, where (I) denotes the inner product, and 8m, the Kronecker delta. Encoding MDP states and rewards works analogously and is described in Section
So far, there is nothing quantum mechanical in our construction. This changes when we consider quantum superpositions. We again use the actions as an example. As we encoded each action as an orthonormal basis vector in a Hilbert space, we can consider linear combinations of actions such as for example
Σ
Cn lan)-
(2)
The state (T) is superposition of the basis actions (n))...,(um) In order for (V) to be valid quantum state, the coefficients on have to satisfy the normalization property
Σ
Cn 2 =1
(3)
Note that this directly implics (V) = 1, and every quantum state has to satisfy this condition. The reason for this requirement becomes evident when we discuss the concept of projeclive measurement. The quantum state (V) from Equation (2) is not classical information in the sense that even if it "exists" on a quantum computer, we cannot directly observe the coefficients en that uniquely determine it. This is due to fundamental properties of quantum systems and we refer to more detailed introductions to quantum computing or mechanics (Nielsen & Chuang, 2002 Taahon-Ta al.) 1977). The only way we can gain classical, caumann-nterrretabbl information on the state (V) is via measurement. This is stochastic operation that returns any basis action state (a,,) with probability 12 In this way, we can consider the state (V) to be a quantum encoding of probability distribution of the actions. In general, one can use the superposition principle to express any probability distribution over finitely many values as a quantum state. We will hcavily use this fact in Section 4.1 As long as we do not measure the state [V), it remains in superposition, which is what is often thought of as being in all of the states (a1) "u......o.r (a.) "at the same time". The measurement process destroys the superposition and leads to a so-called collapse: If a mcasurement yields a basis action Jan), the state of ( collapses to this measured basis action (a,) and all other information that encoded in the superposition is lost. We can think of measurement as sampling from the distribution encoded by
3

---

Published in Transactions on Machine Learning Research (03/2023)
the coefficients Cy. Therefore, any superpasition state can be considered quantum sample (gsample) of the probability distribution it encodes. Via. measurement, we can turn a qsample into classical sample. Note that if we had access to M copies of the quantum state [V), we could conduct M measurements and use the results to approximate the squared moduli of the coefficients On via averaging.
A specific quantum system that is very important for quantum computing and which we also use in this work is the qubit. It is a two-dimensional system whose state space can therefore be thought of as C2, The basis states (basis vectors) are often denoted by (0) and [1] which reminds of the two classical states "O" and 'I', A qubit can be regarded generalization of classical bit. In this sense, it is the smallest unit of information a quantum computer can process.
So far, we only discussed one quantum mechanical state in isolation. For our quantum mechanical realization of a classical MDP, we have to proceed to joint quantum states which describe multiple quantum mechanical systems simultancously. While individual quantum states can be used to express and sample from probability distributions of single random variable, joint states behave analogously for joint distributions. To give a concrete example for joint state of two systems, consider the following scenario: Assume agent starts an MDP at a random state where it chooses random first action. This is determined by a set of probabilities a(s,a) for all state-action pairs (s,a) E S x A. We now want to express this distribution in quantum mechanical terms. Following the description above, we encode the states and actions as basis vectors of a complex and action space A. The quantum analogue of a state-action tuple (s, a) is a joint state
[s) =
2 la) (s)
A.
where denotes the Kronecker product. We say that this state has two subsystems, one for the state and one for the action. These two subsystems form the state-action space S @ A which has, by properties of the Kronecker product, an orthonormal basis given by the set {[s) |a) hes,,ee and is therefore |S| dimensional. We can express the distribution of initial states and actions as superposition
(D)
Σ =E3,
Ca.a 18) la).
(5)
where the coefficients 6s are any complex numbers that satisfy |cx,a2 P(s, The joint state (b), too, can be measured as described above. A measurement of the state ( in the [s) (a) basis would yield a state-action pair with the corresponding probability. However, instead of mcasuring both subsystems, we can also measure only one of them. Say measure the first subsystem. Then we observe a specific state |s") with probability Eaca L 2 - a() Therefore, measuring the first subsystem returns a sample of the marginal distribution P(s) of the states that is induced by the joint distribution P(s, a). Like above, this measurement also results in a collapse. Assume again that we observed a specific state (s'). This changes the sate of (6) to
I+b) Σcole
Coler la),
(6)
aeA
where the coefficients of the superposition are given by
Cals' VLNEA csral
Ca.a
(7)
Note that 12 12 = P(als'), which means that (+') is a quantum encoding of the conditional probability distribution s'a In summary, measuring the first subsystem does two things: It returns a (classical) sample of the states and leaves us with the conditional distribution of the actions given the observed state.
So far, only discussed how the information we wish to process with the quantum computer is encoded. Now we focus on how the computer processos the information, i.c., how it changes quantum states. We alrcady saw one possibility to modily a quantum state which is via measuring one or more subsystems. Apart from measurement, the only possibility a quantum computer has to change a quantum state is via unitary quantum gates. For discrete quantum mechanical systems, these gates correspond to unitary operators. The requirement of unitarity is important since it preserves the normalization of quantum states. Again, this is best. understood by considering an example. For simplicity, consider single qubit with its two-dimensional
4

---

Published in Transactions on Machine Learning Research (03/2023)
state space. The Hodamard gate H (which we also use in Section 4.2 is defined as the linear extension of the mapping
1
1 (0) 11)).
10) v2 (10) + (1)),
[1]
(8)
By identifying the basis states (0) and [1) with the canonical basis of C², we can express the Hadamard gate H as matrix, i.c.,
H = 4)
(9)
It is easy to see that the Hadamard gate is a unitary operator. In general, quantum gates on n-dimensional systems correspond to unitary operators (matrices) that act on the n-dimensional state-space. In the follow- ing, we denote the group of unitary operators on a Hilbert space H by U UHH). Analogously to quantum gates that act on individual systems, quantum gates on joint systems are unitaries on the Kronecker product of the quantum stato-spaces of the systems. For example, quantum gate that acts on the spaces A and S of MDP actions and states must be a member of U(A @ S).
A special case of quantum gates on joint systems that play central role in Section 4.1 and in many quantum algorithms in general are controlled gates which are also closoly related to the concept of entanglement. We illustrate both concepts using the following example: Consider an MDP with two states and actions, i.e., (so, $1} and A {aa.aj) a1}. Assume the agent follows the deterministic policy π that chooses action do in state so and action a in state 81; i.c., T(ao|so)) <(,,ss) = 1. We can describe this deterministic policy using controlled quantum gate. More precisely, we will now discuss how to express the policy using controlled not (CNOT) gate. This gate operates on the joint state of two qubits and its action is given by
(x)) ly +1 mod 2) i (x)) ly)
(x) (v)
CNOT,
(10)
else
In other words: The CNOT gate flips the state of the second qubit whenever the first qubit, the so-called control qubit is in state [1] and leaves both states unchanged if the control qubit is in state [0). Now we return to our concrete example situation and the discrete policy. As the state and action spaces are two-dimensional, we can represent them using qubits, i.c.,
80 + 10)s $1 + (1/s and
an + 10) a1 + A
(11)
where the subscripts S and A emphasize that the two qubits come from the (separate) state and action Hilbert spaces. Using this identification, we see that the CNOT gate realizes precisely the action of the deterministic policy т. This is concrete example of the policy operator which we define in Section 4.1
Let us extend out example and consider the situation where the agent is in state so and $1 with equal probability and in each state chooses an action according to the deterministic policy æ that corresponds to the CNOT gate. As discussed above, the distribution of the agent's state can be encoded by the equal superposition state (10)s +))ss) A direct calculation shows that
2 ( (0)s + (1)s) & 10)_ CNOT 1 (10)s +
(1)s (1)))11)))
(12)
V2
This means that if we apply the CNOT gate a joint system that encodes the agent's random state, we get a qsample of the resulting probability distribution of stale-action pairs that arise from the deterministic
policy x. The state
1 ) 1))00++1111) 11)s 11)++11)11)2))
10)s ( V2
(13)
is so-called Bell state and is a famous example of the class of entangled states. Entanglement is property of joint quantum systems and, loosely speaking, encodes dependency of quantum systems. In classical RL, the action of an agent is typically dependent on the state it is in. Note that here, too, the state (T) encodes a dependent distribution of states and actions. In our quantum MDP construction in Section 4.1, we use controllod gates to produce entangled states that encode joint distributions of states, actions and rewards with stochastic dependencies. Entanglement an important resource of many quantum algorithms such as the phase estimation algorithm (Figure I which we use for policy evaluation.
5

---

Published in Transactions on Machine Learning Research (03/2023)
4 Quantum (Approximate) Policy Iteration
4.1 Quantum Mechanical Realization of a Finite Markov Decision Process
In this section, we use the concepts discussed in Section 3 to develop a quantum version of the classical MDP. The main difference between our construction and the classical one is that we use the superposition principle to model the stochasticity of the agent-environment interaction. Everything else designed to be completely analogous to the classical case.
Consider (classical) MDP with finitely many states S, actions A and rewards R. As already described in Section 3 we can identify these sets with finite-dimensional complex Hilbert spaces S, A and R, which we call state, action and reward spaces. Formally, we use maps from the sets to the corresponding spaces, i.e,
la),
Ir).
(14)
We require that the states, actions and rewards are orthonormal, i.c.
(s|s') 80,s' (ala') 8a,a', (rlr') 8,,r
(15)
holds for all pairs s, s E S, a,a' and r, r,r' E R. On a quantum computer that operates on qubits, we can for example arbitrarily enumerate all states and actions and use systems (strings) of qubits as quantum representatives, i.e., 8; + [bin(i)) and aj + bin(j)), where bin(k) denotes the binary representation of an integer k. The rewards can be approximated by fixed point binaries which can also be represented as strings of qubits.
Agent and environment are modelled by unitary operators that act on S, A and R. For any policy x, we define the policy operator, as a unitary operator II E US x A) which satisfies
{s) A
(T2)
Σ aca
Cala la)
(16)
for all states E S. The state 1 is an arbitrary reference state in A and each amplitude Cals E C has to satisfy |cajel2 = T(als). In the language of Scction 3 the policy operator can be described as a collection of controlled operators: For each MDP state, there is a controlled operator on S 8 A that prepares a qsample of the agent's 's policy in that state.
The policy operator can be chosen as any unitary operator that satisfies Equation 16 To see why such an operator always exists for any arbitrary stochastic policy म, note that Equation 16 describes a bijection between two orthonormal bases (ONBs) of two subspaces of S & A. We can extend both ONBs ONBs of the full space and define an arbitrary bijection between the newly added basis states while maintaining the action described in Equation (16) on the original ones. The linear extension of this assignment is then unitary by construction. Using an analogous argument, we define the environment operator E E U US Ø A @ R & S) as any unitary operator that satisfies
(s) la) 10) 10)s
E -
Σ r.a"
Crar (s) la) (r) (s').
(17)
with amplitudes that satisfy |c.l2| p(r, s'|s s/|s, a) for all statc-action pairs E S, a E A single interaction between agent and environment is modelled by the step operalor S Eo II. For any state 8 S, holds
that
(s) 10), O0) 10)s S.
Σ
(s)
(18)
where ca = Call We use S to construct a unitary operator that prepares a quantum state which represents the distribution of all trajectories with a fixed finite horizon H. We call it MDP operator and denote as M. While the step operator acts on S & A R & S, the MDP operator is a unitary on the trajectory space T = S & (A 8 R 8 s) @H which is large enough to store H quantum agent-environment interactions. The states in this space represent trajectories of length H and are of type
n 1sb") lab") |r1") 1>1"")
1r 10())
(19)
6

---

Published in Transactions on Machine Learning Research (03/2023)
We define the MDP operator
H M = S S e UT""),
(20)
h=1
where S₁ denotes a local version of S that acts on the h-th S @ A @ R @ S subsystem of 7 It holds that
|s) @ (10) 10) 50)s)
ON M Σ E2
G 1n
(21)
where 10 = p(( which is the classical probability of trajectory 8 This can be seen via inductive application of the relation given in Equation [SS.. Note that by construction, the state from Equation 21
is a qsample of the trajectorios of length H.
For QPE, need qsamples of the returns in order to approximate the value function. With this in mind, use the qsample of the trajectories and calculate for each trajectory state |t the associated return defined as G(t")= = Eh=17 1 - where y [0, 1] is fixed discount factor. As the reward states of (t")) are qubit binary encodings of (real) numbers, we use quantum arithmetic to calculate their discounted sum. Formally, we use unitary return operator G that maps
Irt) (rt)-.-(rll (r--1ra)00) 10)g - (11)....//
Σ
Th
(22)
where 10)g is a reference state in the relurn space G. which represents a system of sufficiently many qubits to encode all returns. Ruiz-Perez & Garcia-Escaa Escartin (0177) show an explicit construction of such an operator which performs the weighted addition the Fourier domain. By letting G act on all reward subsystems and the return component of T G, we can define G o M which satisfies
10)
G-M
Σ can (t [G(t
(23)
As all | IG(t states are (by construction) orthonormal, it follows that if measure the second sub- system of [4),, we receive an individual return with the classical probability determined by the MDP and the agent's policy. Therefore, (the second subsystem of) the state (4b) is as qsample of the return.
4.2 Quantum (Approximate) Policy Evaluation
Consider the problem of (approximately) evaluating the value function w of policy æ for some finite horizon Hl E N. The value function defined pointwise via
u (s) = E,a [S) s].
(24)
where E S is the initial state, and the expectation is taken with respect to the distribution of all trajectories of length H. Even if we assume perfect knowledge of the MDP dynamics evaluating v (s) exactly is usually infeasible: the complexity of directly calculating the expectation grows exponentially in the horizon H. Techniques from DP such as ilerative policy evaluation reduce the computational complexity but come at the cost of high memory consumption (Sutton & Barto 2018). An alternative approach to use an MC method to estimate of (s). The arguably most straightforward MC algorithm for policy evaluation is to collect dataset of trajectories and to average the returns. This requires the possibility to sample from the distribution of the trajectories.
Montanaro 2015) developed a quantum algorithm to estimate the expectation of a random variable using qsamples. The method is quadratically more sample efficient than the best possible classical MC routine and it forms the foundation of QPE. To approximate the expected return, we use qsamples of the returns which we have access via the operator AqPE == G M from Equation (23). The first step towards QPE is to note that we can encode of (s) amplitude of basis vector in a quantum superposition. To this end,
7

---

Published in Transactions on Machine Learning Research (03/2023)
10]
H
(0)
H
(0)
H
QFT
X
10)
H
1
QOPE
QQPE
Q
20 Q
Figure 1: Phase estimation circuit for amplitude estimation in QPE.
assume that we know a lower bound g and an upper bound 9 # g on all returns. Using an affine function ø defined by <(x:) (z g) g), we construct a unitary operator that maps
xx) 10) - (VI-o(z) 11(x)
(25)
where (a)) is binary (qubit) representation of a real number E R and the second subsystem is a single qubit. If we now apply & to the return component of (&b) from Equation 23 and an additional qubit, we get
(wb) = (8) == co 11) + ea Wi),
(26)
where
w&t & cau ((
(27)
The state wb) contains all the states in which the last qubit is in state (0) and therefore orthonormal to (w9)). The amplitude C, which is the norm of the nton-normalized] state on the right-hand side of Equation 27 satisfies
Σ ((G(H)) = E, [
la
(28)
By affinity of 6, it holds that
o (1c = E, [G(t#]] = (s).
(29)
Therefore, approximately evaluating the value function can be done by estimating 1e,13. This task which is commonly referred to amplitude estimation.
One way to estimate |e]|2 (or any amplitude in general) is to encode it via the phases of two eigenvalues of unitary operator and to estimate them using phase estimation. Following the original construction of Brassard et al. (2002), we define this unitary as
QQPE == AA So
(AQPF) -
(idy o Z),
(30)
where A are == (idy# @ क) AqrE- In this expression, + acts on the return subsystem and the ancillary qubit. The operator So is a phase oracle that, considering the basis states, flips the phase state precisely when all components (in this case the trajectory and the return component well as the additional qubit) are in the corresponding (0) ground states. The Z operator corresponds to Pauli-Z gate and therefore the last operator is also phase oracle which flips the phase of state precisely when the ancillary qubit is in state [1). Brassard et al. (2002) showed that ( can be decomposed as (v6²) c4 (vb)) + c. IvL) where WT) and ( are orthonormal, |c+12 = |2_ = 1/2 and QqpE (Vf) 220i0 w which means that ( are eigenstates of QqrE- The phase is the unique value in [0, 1) that satisfies sin ( = sin)(- = la|2.
Therefore, we can use a phase estimation algorithm to estimate and - The classical phase estimation routine is described in Figure The figure shows quantum circuit which representation of a quantum algorithm. Starting from the left, the quantum states are processed with the unitary gates illustrated
8

---

Published in Transactions on Machine Learning Research (03/2023)
boxes. Here, H denotes the Hadamard gate discussed in Section 3 and all systems except of ((0)) are qubits. The black dots at the qubits and the connection between them and the QQPE gates denote that the QQPE gates are controlled by the corresponding qubits (c.f. Section 3). The last boxes behind the QFT (quantum Fourier transform) gate stand for quantum measurements, For detailed analysis of the phase estimation algorithm, we refer readers to the textbook by Nielsen & Chuang (002).
We see that the phase estimation circuit from Figure
uses a system of
1 1 28 2
1
t n=
loga
(31)
qubits where n E and ó E (0, 1] are arbitrary. The basis states of these qubits are interpreted as binary numbers. Phase estimation exploits the fact that (w2) are eigenstates of QQPE to bring the qubits into a joint state X which, when measured, satisfics
P( - 11/mat) 2 1/2
8/2,
(32)
P P( + +0| s 1/2nt1)
> 1/2 6/2,
(33)
i.c., the distribution of X/22 is concentrated at A and 8. In case t = n, we get the same result with total probability at least 8/72. These bounds follow from a detailed analysis of the phase estimation circuit was done for example by Cleve et al. (1998).
As |q|2 = (iff and " (s) = x ((ca1)) we define the QPE approximation (s) of u (s) for any realization x of X as
6 (s) = 0= sin? (mx/2²)).
(34)
The approximation error of 0 given in Equation 32 can be translated to an approximation error of the value function
P(O (s) - a (s)l {) 21-5,
(35)
where the error is (as shown in the Appendix) given by
6 6= =ā - (==
E (11/2").
(36)
Phase estimation uses O(2²)= = O(1/E 1/5) applications of A APE and (AOP)) (via QOPE) to achieve this error bound (c.f. Figure D. Each such application corresponds to the collection (preparation) of one qsample. According to the optimality results on MC methods due to Dagum el al. (2000), the sample efficiency of the best possible classical MC type algorithm to estimate v (x) via averaging has sample complexity in Q(1/e" log, (1/6)). Therefore, QPE yields a quadratic reduction of the sample complexity with respect to the approximation error c. This quantum advantage holds over the best possible classical MC approach for policy evaluation. An advantage over other approaches is not guaranteed. Comparing the sample complexity of QPE to those of other classical methods is an interesting direction for future research. For more discussion the exact nature of the quantum advantage of QPE and the conditions under which it holds, refer the reader to the conclusion in Section G
4.3 Quantum Policy Improvement
The task of improving a given policy μ is to find another policy jí' such that ()) 2 ! (s) holds for all e S and that striet inequality holds for at least one s' E S. Once we know the value function oif of μ, such a p¹ can be explicitly constructed via greedification. In this section, derive quantum policy improvement (QPI) which instead uses a Grover search over set of policies to find an improved decision rule. For simplicity, we assume from now on that the MDP always starts in some fixed initial state so E S. In this case, instead of using the whole value function, we can restrict ourselves to the value of policy x which, under abuse of notation, we define as o := .!l (so).
QPI uses Grover search on QPE results to find an improved decision rule. For fixed policy n, QPE can be summarized as one unitary QPE (consisting of the phase estimation eircuit from Figure] without the
9

---

Published in Transactions on Machine Learning Research (03/2023)
measurements) that maps 0) policies. By mapping each π E P onto a member (s) of an ONB of some suitable Hilbert space P, we can construct a unitary, r-controlled version QPE, QPE that satisfies
QPE,
( Now consider the finite set P that contains all deterministic
(x' (0) -
m) Wrrr) (T) 10)
il it=
(37)
else
for all policies x' E Using these operators, we define another unitary that prepares the search state for QPI Grover search. Consider
QPE
A AqrI ==
(Hp 0 id),
(38)
where Hp is a Hadamard transform on P. By construction, this operator maps
AQPE 1
p 10)
(T) (VPP))
(39)
TEP
As the @pE)) states encode the value of policy π, we can define suitable oracle and use it to amplify the amplitudes of those policies that are likely to yicld higher returns. For a policy and an approximation '/2 of its value, consider phase oracle Se that satisfies
lx)
if o (xin ip
(40)
(x)
else
Using this oracle, we define the QPI Grover operator as
Q Qqpi == AqpI o So o A o (idp & 0xa.).
(41)
According to the principle of amplitude amplification, which is used in Grover search and was described in detail by Brassard et al. (2002). if we apply this operator a certain number of times to the search state prepared by AQPI, this amplifies the amplitude of all (T)) (z) states whose (z) component satisfies the oracle condition o- o-(sinn' (T) > Un.- As a result, the probability of mcasuring a policy that has better performance than Ün (up to an error of e) is increased. Due to the QPE failure probability of 6, the procedure may also amplify amplitudes of policies that do not yield an improvement (within c) as QPE may iverestimate their performance. However, the probability of such errors can be limited by choosing small values for 6.
For the amplitude amplification to work, we need to specify the number of Grover rotations, i.c., the number of times we apply QhrE, which determines how the amplitudes of the desired states are scaled. Although there a theoretically optimal number of Grover rotations, this value is inaccessible in QPT as it would require knowledge of the probability of obtaining a desired state when measuring the search state (Brassard To circumvent this problem, use the exponential Grover search strategy introduced by Boyer (1988) We initialize parameter m== 1. In each iteration, we uniformly sample the Grover rotations et al.
ct al.
2002).
{0, .... m 1]} and measure the resulting state. If the result corresponds to an improvement, we reset + 1. Otherwise, we overwrite m + Am for some À > which stays the same over all iterations. For a theoretical justification of this technique, please refer to the original work of Boyer et al. (1998).
from
m
Quantum (approximate) policy itcration as described in Algorithm I starts with an initial policy mo and repeatedly applies QPI to generale a sequence of policies with increasing values. Note that the procedure is similar to a quantum minimization algorithm introduced by Dürr & Høyer (1996). In each iteration k. quantum policy iteration runs QPI which is Grover search and can therefore also fail to produce policy whose estimated value exceeds the current best dg- In this case, the policy and its value are not updated. As we typically do not know the value of the optimal policy, the algorithm uses a patience criterion to interrupt the iteration there was no improvement in the last C' steps.
As quantum policy iteration relies on QPE, can only find a policy with e-optimal behavior and may also fail to do so. This is because QPE yields an e-approximation of the value only with probability 1 1- 8. We
10

---

Published in Transactions on Machine Learning Research (03/2023)
Algorithm 1 Quantum Policy Iteration
input: A policy To E P, an estimate 8.. of its value, parameters for QPE and QPI output: Guesses H' E P and i* for x² and 2*
c 6-0
for k-1,,,3,... while e C do
Run QPI on Th-1, Unz-1 to obtain mk. 0k
if a U then
Th #kg Uk t Ükg C
else
T + 11 Uk t 11 ct
end if
end for return म" = IT; 0" oT from last iteration T
conjecture that the failure probability of quantum policy iteration can be made ar arbitrarily small by choosing a sufficiently small 5 which, however, comes at the cost of increasing the qubit complexity and run-time of QPE. Morcover, note that in some iteration i the QPE output U/ overestimates Uyz but still up < Us QPI may nevertheless find a policy *6+1 with Ur. > Uk- This miligates QPE errors.
We propose that the complexity of quantun policy iteration is best measured in terms of the total number of Grover rotations performed in all QPI steps. This number is proportional to the run-time of the procedure and also measures the number of times we ran QPE which relates via the MDP model to the total number of quantum gnvionenviromment interactions. Therefore, the number of Grover rotations also measures the qsample complexity. We conjecture that the complexity grows lincar in vIPl. Our intuition behind this is that quantum policy iteration is essentially Grover search except that it uses changing, inaccurate oracles.
5 Experiments
Existing quantum hardware is not yet ready to run QPE, let alone quantum policy iteration. Both methods use far more gates than what is possible with existing, non-error- crror-corrected digital quantum computers. Therefore, we have to resort to simulations. However, as quantum circuits are known to be hard to simulate classically, the complexity of the RL problems we can consider is limited. Simulating QPE alone requires processing a stale vector whose size grows exponentially with the horizon, which infeasíble for large enviromments that require many interactions. For example: For a 10x10 maze problem with four actions and horizon H. there are 400 trajectories which have to be encoded in single state vector in order to accurately simulate QPE. Processing such enormous arrays is infeasible even for short horizons. Considering these limitations, we resorted to a two-armed bandit problem. This setup is far too simple to use it to fully test our methods. Rather than that, the idea behind the simulation study in this section is to illustrate the steps needed to realize our algorithms on real quantum hardware in detail and to demonstrate their behavior.
A two-armed bandit can be thought of as slot machine with two arms (levers). Upon pulling an arm, one receives reward of either OS or 18. This translates an MDP with one state and two actions, i.e., A { where "t-" means 'pull the left arm' and "->' means "pull the right arm'. The reward set is R = 10. The MDP dynamics are determined by the two probabilities p(0) <-) and p(0) -) of losing, i.., 'winning' 08, when pulling the left or right arm. Each policy is determined by x(+) which denotes the probability of choosing the left arm. The learning problem is to identify the arm that yields the highest value 0², given by o" = max [p(1] --)p((1)+))
We encode the actions via |-) 1 and |+) [1) which can be done by using single qubit. We use another qubit. to encode the rewards (OS) 10)₂z and [1$) [1) In this encoding, we can represent the step operator S as quantum circuit shown in Figure 2 The angles of the Y-xxis rotations R, are given by HT 2 arccos (V (T)), g 2 arccos (vr(O) +)) and g 2 arccos (vp(0) +]). A direct calculation shows that this S indeed prepares qsample of one agent-environment interaction.
11

---

Published in Transactions on Machine Learning Research (03/2023)
0.60
epsilen bound
0.50
10) 10)x
(0T)
X
probabiitty
0.40
Ry (0*)
(l(
0.30
E
0.10
0.00
0.76
0.78
0.80
0.82
0.84
output
Figure 2: The step operator S for the two-armed bandit MDP in the form of a quantum circuit.
Figure 3: Distribution of the o output of QPE for the concrete instance of the two-armed bandit MDP.
estimaled value
m
Grover rolations
0.05
MC mediann
OPE error median
1.0
Median seproxination errer
OPE error bound
50
0.04
0.8
40
Grover rolaliens
0.03
polccy value
20
0.01
0.2
10
0.80
0.0
2000
3000
20
60
80
Number of (q/samples
iteration
Figure 4: Median approximation errors of 1000 runs of both QPE and classical MC for one round of two- armed bandit.
Figure 5: The estimated policy value and the Grover rolations applied during one successful run of quantum policy iteration.
Now consider the two-armed bandit for horizon H 2, i... the agent gets to play two rounds. The MDP operator of this decision process is given by two step operators according to Figure 2 that act on two separate A R subsystems represented by four qubits. For simplicity, we set the discount factor 1. The return operator G adds the two reward qubits and stores the result using another two-qubit subsystem that represents the return space G. can be implemented using two CNOT gates and one Toffoli gate (which is CNOT gate with two control qubits) return register must be set to [1) or [0) depending on the rewards. The gate & be realized using three coubly-controlledd Ry gates that rotate another ancillary qubit depending the two reward qubits.
realize the logical expressions that determine which qubit of the
5.1 Simulations of Quantum Policy Evaluation
Putting all of the above together, we reccive gate-decomposition of A To simulate QPE, we imple- mented the operator in IBM's qiskit [Aleksandrowicz el al. 2019) framework for the programming language Python. We chose a concrete bandit with dynamics p(0) - = 0.55 and p(0) -) = 0.65 and considered the policy given by T(-) 0.50 which has the value va 0.80. All of these values were chosen arbitrarily. We used simulated QPE obtain an estimate of this value with absolute error of at most 0.025. As maximum error probability, we chose 5 0.05. According to Equations (31 and (3)] have to
12

---

Published in Transactions on Machine Learning Research (03/2023)
160
mean
best linear fit
140
120
Grover rotations
100
80
20
1600
1764 1849
2025 2116 2209 2304 2401 2601 2704 2916 3025 3249 3364
3600
number policies
Figure 6: The total mumbers of Grover rotations until quantum policy iteration finds an e-optimal policy for the bandit problem.
7 11 qubits in the first register of the phase cstimation circuit to achieve the e-approximation with probability at least. 1- 5. The distribution of the QPE outputs for these parameters is shown in Figure 3 Qiskit offers the possibility to calculate measurement probabilities analytically, which is what we used to generate the plot. The probability distribution of the QPE output i is concentrated at the true value at vf = 0.80 and the mass that lies outside the region less than 0.025 which is even better than our guaranteed error probability bound of á 0.05.
Next, wanted to empirically confirm the quantum advantage of QPE over classical MC. To this end, we used both methods to evaluate fixed policy for fixed bandit using increasing number of (q)samples. To reduce computational complexity, we chose horizon H = 1. According to Equation (36). the approximation
error |o] - of QPE is in (112")), where n is from the definition of f in Equation (31 For our experiment,
we set. = n. From Figure 1 we see that QPE then uses 2 qsamples via applications of AqpE and App We chose range of integer values for and for each executed QPE 1000 times and calculated the median approximation error. Recall that the failure probability for QPE with the median delivers a run in which the algorithm indeed returned an e-approximation of the true value with high probability. The results of this experiment
is 8/x² taking
shown in Figure We also included the error bound according to Equation (36) and see that the approximation errors satisfy the theoretical guarantee. For each n, we also collected 2 -1 classical samples, averaged them, repeated this 1000 times and calculated the modian. The approximation error this classical MC approach is always higher than the one of QPE. This empirically confirms the quantum advantage of QPE over MC in terms of (q)sample complexity.
5.2 Simulations Quantum Policy Iteration
We now turn to policy iteration. As toy learning problem, we used two-armed bandit where the agent always loses when it chooses the left arm and always wins when it chooses the right arm, i.c., p(0) <-) = and p(1) +) = 0. In DP, one typically only considers deterministic policies as, under mild assumptions, every finite MDP has an optimal deterministic policy (Sutton & Barto 2018). For the two-armed bandit, there are only two such policies, which results in an uninteresting problem. To make the search for an optimal decision rule more challenging, we instead used a set of N stochastic policies given by
n -
PN = += =
N
(42)
N
13

---

Published in Transactions on Machine Learning Research (03/2023)
We let the agent start with the worst policy x² which chooses the left arm with unit probability and want to find the optimal decision rule n² p="=rt" =
Figure 5 documents one successful run of quantum policy iteration for the toy learning problem with N = 1000 policies and parameters E = 0.0125, 5 = 0.07, C = 30 and X = 8/7. We set = 1 so the agent plays one round and the value of the optimal policy is x² = 1. In the beginning, the policy value rapidly increases even when no or only few Grover rotations are applied. This is because the agent starts with the worst possible policy, and better policies are casily found by chance. The steep increase stops after few iterations, when the policy is close to optimal. It takes increasingly more rotations, ie., amplifications of the then small success probability of finding a better policy, and some minor improvements until the procedure makes the final jump marked by the dotted vertical line. After that, the values stagnate at the maximum of as from then on, no further improvement is possible. During the last iterations, the algorithm tries more and more Grover rotations as m (that determines their maximum number) grows exponentially.
Finally, we investigated our conjecture that the run-time of quantum policy iteration is proportional to vPpl. To empirically test this, we ran quantum policy iteration for the same bandit and using the same parameters in the previous experiment. We quadratically increased the size N of the policy set PN from N = 40 = 1600 to N = 60 = 3600. For each N, we ran quantum policy iteration 1000 times and calculated statistics of the resulting distribution of the number of Grover rotations. As the number of rotations depends on the patience C, we omitted the ones that happened in the last C iterations. We only considered 'successful" runs where quantum policy iteration returned an e-optimll policy. Due to the low QPE failure probability, more than 99% of all runs were successful for any N. The results of the complexity experiment are shown in Figure G We see that the average number of rotations indeed seems to grow linear with VN, i.e., quadratically with the number of policies N. The line through the means was found by linear regression and fits the data well; the mean squared error is 1.50. Note that for each N, the empirical distribution of the runtimes (we hid the outliers for the sake of clarity), appears symmetric and has a large interquartile range. This is expected because sometimes, the algorithm samples a near optimal policy carly by chance while in more unlucky runs, the optimum is found through many incremental improvements.
6 Conclusion
In this work, we described a novel quantum realization of a classical MDP. Based on this construction, we showed in detail how to combine amplitude estimation and Grover scarch to obtain a quantum algorithm that realizes the classical scheme of policy evaluation and improvement. This is concrete proof-of-concept for how to solve reinforcement learning problems exclusively on quantum computers. We showed that by leveraging the superposition principle, we can reduce the sample complexity of classical MC policy evaluation. This indicates that quantum advantage in RL might be achieved by lowering the number of agent-cnvironment interactions it takes for an agent to find the optimal policy.
In their current form and given the likely limitations of near-term quantum hardware, our methods are not applicable to real problems: The qubit and gate complexity of QPE scales linear with the horizon and quantum policy ileration requires enough qubits to enumerate all possible policies of a finite MDP. Moreover, the quantum advantage of QPE over classical MC-based policy evaluation holds only in terms of sample complexity and only if efficient, error-free implementations of policy and environment operators are readily available. These operators prepare qsamples of the agent's policy and the MDP dynamics, which are then used for amplitude estimation in QPE. Herbert (2021) showed that the quadratic quantum advantage of amplitude estimation over classical MC can be eradicated if the preparation of the distribution quantum state, that is in case performed by the policy and environment operators, is not efficient enough. However, more recently, the same author proposed another method for quantum MC that also yields a quadratic speedup, but may not suffer from efficiency problems with state preparation (Herbert) 2022). The investigation, if and how this method can be integrated into our framework as a sub-routine of QPE is left for future work. Another possible direction for future work would be to try to improve the policy improvement step. Note that QPE can be integrated with other quantum optimization methods than Grover-searches. It might also be possible combine QPE with quantum versions of dynamic programming which would be more efficient than directly searching for optimal policy.
14

---

Published in Transactions on Machine Learning Research (03/2023)
Acknowledgment
The project this report is based on was supported with funds from the German Federal Ministry of Education and Research in the funding program Quantum Technologies From Basic Research to Markel under project number 13N15644. The sole responsibility for the report's contents lies with the authors.
References
Gadi Aleksandrowicz, Thomas Alexander, Panagiotis Barkoutsos, Luciano Bello, Yael Ben-Haim, David Bucher, Francisco Jose Cabrera-Hernández, Jorge Carballo-Franquis Adrian Chen, Chun-Fu Chen, ot al. Qiskit: An Open-source Framework for Quantum Computing, January 2019.
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum scarching. Forlschrille der Physik: Progress of Physics, 46(4-5):493 505, 1998.
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Conlemporary Mathemalics, 305:53-75 74, 2002.
Hans Briegel and Gemma De las Cuevas. Projective simulation for artificial intelligence. Scientific reports, 2(1):1-16, 2012.
Samuel Yen-Chi Chen, Chao-Han Huck Yang, Jun Qi, Pin- Yu Chen, Xiaoli Ma, and Hsi-Sheng Goan. Variational quantum circuits for deep reinforcement learning. IEEE Access, 8:141007-141024, 2020.
El Amine Cherrat, lordanis Kerenidis, and Amupam Prakash. Quantum reinforcement learning via policy iteration. arXiv preprint arxi::203. 018,, 2022.
Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Pro- ceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454 (1969):339 354, 1998.
Claude Johen-Tannouin Bernard Diu, and Frank Laloë. Quantum Mechanics, Volume One. A Wiley Interscience publication. Wiley, 1977.
Paul Dagum, Richard Karp, Michael Luby, and Sheldon Ross. An optimal algorithm for Monte Carlo estimation. STAM Journal compuling, (9(5)) 1496, 2000.
Vedran Dunjko, Jacob M Taylor, and Hans Briegel. Framework for learning agents in quantum environ- ments. Xixi preprint 1x77:1507.8848 2015.
Vedran Dunjko, Jacob M Taylor, and Hans J Briegel. Guantum-enhaneee machine learning. Physical review letters, 117(11) 2016.
Vedran Dunjko, Yi-Kai Liu, Xingyao Wu, and Jacob M Taylor. Exponential improvements for quantum- accessible reinforcement learning. ar preprint arXiv:
2017a
Vedran Dunjko, Jacob M Taylor, and Hans J Briegel. Advances in quantum reinforcement learning. In 2017 IEEE International Conference on Systems, Mon, and Cybernetics (SMC), pp. 282 287. IEEE, 2017b.
Christoph Dürr and Peter Høyor. A quantum algorithm for finding the minimum. arXio preprint quant- ph/9607014, 1996.
Lov K Grover. A fast quantum mechanical algorithm for databaso scarch. In Proceedings of the twenty-eighth annual ACM symposium on Theory of compuling, 212 219, 1996.
Arne Hamann, Vedran Dunjko, and Sabine Wölk. Quantum-accessible reinforcement learning beyond strictly epochal environments. arXiv preprial arXiv:2008.01. 01481, 2020.
Steven Herbert. The problem with Grover- Grover-Rudolph state preparation for quantum Monte-Carlo. arXiv preprinl ar orXiv:2101.02..1 2021.
15

---

Published in Transactions on Machine Learning Research (03/2023)
Steven Herbert. Quantum Monte Carlo integration: the full advantage in minimal circuit depth. Quantum, 6:823, 2022.
Sofiene Jerbi, Casper Gyurik, Simon Marshall, Hans J Briegel, and Vedran Dunjko. Variational quantum policies for reinforcement learning. arXiv preprint arXi::2003.0577 00.3055777 2021.
Owen Lockwood and Mei Si. Reinforcement. learning with quantum variational circuits. In Proceedings of the AAA! Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 16, pp. 245-251 2020.
Maximilian Moll and Leonhard Kunczik. Comparing quantum hybrid reinforcement learning to classical methods. Human-Intelligent Systems Inlegration, 3(1):15 23, 2021.
Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Moth- ematical, Physical and Engineering Sciences, 471 (221 2015.
Sanjeev Naguleswaran and Langlord B White. Quantum search in stochastic planning. In Noise and Infor- mation in Nanoelectronies, Sensors, and Stondards III, volume 5846, pp. 34 45. SPIE, 2005.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
Lidia Ruiz-Perez and Juan Carlos Carcia-Escartie Quantum arithmetic with the quantum Fourier transform.
Quantum Information Processing, 16(6):152, 2017.
Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on quantum computer. SIAM review, 41(2):303 332, 1999.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Pannoershclvam, Marc Lanctot, et al. Mastcring the game go with deep neural nerworks and tree search. nature, 529(7588)::84 489, 2016.
Andrea Skolik, Sofiene Jerbi, and Vedran Dunjko. Quantum agents in the gym: a variational quantum algorithm for deep Q-learning. arXiv preprint arXic:2108.1508, 2021.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. ISBN 9780262039246.
Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, and Martin Roetteler. Quantum al- gorithms for reinforcement learning with generative model. In International Conference on Machine Learning, pp. 10916 10926. PMLR, 2021.
16

---

Published in Transactions on Machine Learning Research (03/2023)
A Proof of the error bound of QPE
In this appendix, we prove Equations
35 and
361. The proof uses the following technical result:
Lemma 1 (Brassard et al. 2002 Lemma 7). Let μ san and jt sàn with 0 a, 2x. Then it holds thal
ā al S <a= j Ml S 20 p( p) + +
(43)
To see that Equation 35 is true, recall from Equation 32 that the random variable X that corresponds
the final measurements of phase estimation in QPE satisfies
P P(11X/2' 01 s 1/2 {1x/2' + 01 s 1/2 2 2
(44)
We set A == sinn = ( (s)) and := == sin ( = o ( (s)) and obtain
P j pl S 2
π
π
2 P l nl S vu(1 - 1))
π
21 11-6 5,
(45)
2
2
22n+2
where the first inequality holds as form of as stated in Equation (36 follows from
1(l μu) S 1/2 and the second inequality is due to Lemma
Now the
(s) t [ ( (w)) (5-gl mlp
(46)
where in the last step, we used the definition of Φ.
17


Reviews:
[{"review_id": "asfXzDHyBC", "reviewer": "Reviewer_MaGx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n\nAt a very high-level, this work seems interesting and quite forward-looking (as the authors themselves point out, \"Existing quantum hardware is not yet ready to run QPE, let alone quantum policy iteration\").\n\nHowever, given that it was submitted to TMLR, my impression is that the main audience reading this will be the RL/ML community. With this in mind, I feel this paper is too detached from these communities. The authors seem to rely on lots of quantum background which most readers of this publication will lack. To contextualize my comments below: I have been working in RL for over 15 years, so I feel my understanding (or lack thereof) is likely a reasonable reflection of that of the larger community.\n\nI think for a paper like this to be accepted in TMLR it would require significant rewriting, and would need to elaborate the quantum concepts much more slowly, and connecting them to terms the RL community is familiar with.\n\nStarting from section 3.1 things are already difficult to follow. The maps presented in equations 1 - 5 seem to simply be rewriting a standard MDP definition, but using quantum notation. Is this so? What is the difference? For instance, is equation 5 just a rewriting of the standard MDP transitions or is there a difference? For someone not familiar with quantum terminology, this needs more contextualization.\n\nSection 3.2 was basically totally incomprehensible to me.\n\nOne last comment is that it wasn't totally clear to me how much of this paper was novel, and how much was reusing prior work. In particular, it seems to be leveraging results from Brassard et al. (2002) a fair bit. It would be good if the authors could also provide more clarity on the parts of the paper that are novel, and the parts that are reusing prior work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents quantum analogues of classical policy evaluation and policy improvement algorithms for quantum mechanical realizations of finite Markov decision processes, leveraging existing quantum techniques such as amplitude estimation and Grover search. As a proof-of-concept, they present empirical evaluations of their method on a simulated quantum process of a two-armed bandit problem.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think for a paper like this to be accepted in TMLR it would require significant rewriting, and would need to elaborate the quantum concepts much more slowly, and connecting them to terms the RL community is familiar with.\n\nI'd encourage the authors to consider resubmitting a (much more) expanded version of this work that is more accessible to the RL/ML community.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FdCUW2HwYm", "reviewer": "Reviewer_Hrjz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is easy to read and follow. They introduce and describe the quantum versions of the required classical objects well, and someone non familiar with quantum computing should be able to broadly follow the paper.\n\nThe premise of demonstrating quantum advantage directly on policy search interesting. \n\nThe authors show that quantum methods can improve over MC based methods of policy evaluation\n\nWeaknesses:\n\nThe proposed method has not got any insight into the standard RL setup. It ignores the entire dynamic programming/Bellman equation based framework of RL, and instead uses simple MC estimation.  Furthermore the bounds used by the authors to show quantum advantage do not hold for MDPs when one uses the dynamic programming/bellman methods.\n\nExperiments are on a bandit which is not really an MDP. While I agree that simulating large circuits is difficult; the current experimental setup  throws away any advantage of classical RL methods, as for a bandit they become some version of simple MC. I would have liked to see atleast a horizon of length 3, so that the classical techniques for MDP can actually be useful.\n\nI am not sure how much I can agree with the quantum MDP construction. Specifically since the transition and reward probabilities are directly encoded directly in the phase of the quantum state, in principal one can use amplitude estimation directly to compute the probabilities. If the model of the MDP is known, then the problem is significantly easier in the classical setting as well.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a quantum based method for finding the optimal policy (QPI). The algorithm is based on the concept of policy iteration, which involves alternating between two steps: policy evaluation and policy improvement.\nThe QPI algorithm works by representing the states, actions, and rewards as quantum states, and using unitary operators to model the interactions between the agent, the environment, and the rewards. These operators can be implemented on a quantum computer, allowing for the efficient computation. \n\nIn the policy evaluation step, the value function is calculated for all states under the current policy. This is done by using the policy operator and the environment operator to simulate the interactions between the agent, the environment, and the rewards, and summing up the expected reward for each state. This is effectively a quantum version of simple Monte-Carlo (MC).\n\nIn the policy improvement step, the policy is updated in order to improve the expected reward. This is done by first mapping all deterministic policies into the earlier policy operator space and then using quantum search on the resulting function.\n\nFinally they show simulation results of their algorithm on a 2-armed bandit.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "While the authors have explained their differences with methods like Wang et al (2021) and Duchko et al (2016). Specifically there are earlier works on directly using Grover search and Amplitude estimation for stochastic planning (Naguleswaran and White, 2005). Rosenwald et al (2004) also have used Grover search for control purposes on POMDP. More recently, Cherrat et al have also proposed a quantum version of policy iteration. \n\nAs mentioned earlier a more MDP-esque experimental setup would be important to claim any practical improvements over classical RL methods. The current set of experiments are uninformative in this regard. \n\nI also would generally like a method which combines quantum ideas with some classical RL ideas, or at the very least not consider it as a blind monte carlo estimator. For example, while the authors show that QPE has a better than classical sample complexity, the classical bounds applied dont hold for RL setting (for example Jiang and Li, 2015)\n\n-----------------------------------------------\nQuantum search in stochastic planning, S. Naguleswaran and L. White, 2005\n\nApplications of Quantum Algorithms to Partially Observable Markov Decision Processes, R. Rosenwald, D. Meyer, and H. Schmitt, 2004\n\nQuantum Reinforcement Learning via Policy Iteration E. Cherrat, I. Kerenides, A. Prakash, 2022\n\nDoubly Robust Off-policy Value Evaluation for Reinforcement Learning, N. Jiang and L. Li, 2015\n", "broader_impact_concerns": "I do not see any significant ethical implications from this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4t201orMAD", "reviewer": "Reviewer_4dsk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n- Construction of unitaries to achieve the task of Quantum Policy Evaluation, and use of standard quantum algorithms (Monte Carlo, Phase Estimation and Grover's search) for QPE, and its extension to Quantum Policy Improvement.\n\n- Numerical evidence for the sampling and accuracy scaling claims.\n\n- Sharing of code used for numerics. \n\n### Weaknesses:\n\n- The authors claim \"provable [Quantum] speedups\" in the abstract, whereas they have not addressed all of the resource requirements for this algorithm, only sampling complexity. A more detailed discussion is in the below section.\n\n- Some of the quantum algorithms used are unmodified from the original papers, whereas there have since been improvements that reduce resources, e.g. see Table 1 of [Babbush et. al 2018](doi.org/10.1103/PhysRevX.8.041015) for phase estimation improvements. I would not expect changes to address this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors show a method for constructing quantum algorithms for policy evaluation and policy improvement.\nThey combine some well-known quantum algorithms to achieve their aim, with the main contribution being the construction of unitaries that can achieve policy evaluation.\nThey then numerically evaluate their proposed algorithm via simulated circuits, demonstrating good evidence for their claims that the classical approximation error is larger than the quantum approximation error for a given number of samples and that the number of Grover rotations required scales as $\\sqrt{|P|}$.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The authors acknowledge that error correction will be required to run this algorithm, but there is no discussion of the overheads of error correction, and at what accuracy level the quadratic speedup from Quantum Monte Carlo could overcome these. A full T-gate complexity costing would demonstrate this, but is not expected for a single review.\n\n- There is no discussion of the resources required to build the $\\Pi$, E, S, M operators, i.e. loading the probability distribution to sample from into the quantum state and the errors that would be produced from this, see [Herbert 2021](doi.org/10.1103/PhysRevE.103.063302) for a discussion of the scaling of Monte Carlo in the presence of state preparation errors. The authors should demonstrate that this algorithm is not subject to such errors if a quantum speedup is available.\n\n- In section 3.3 they claim that the probability of a non-policy-improving error can be limited by choosing small values for $\\delta$, but they fail to discuss that this is related to the number of qubits required for phase estimation, which in turn scales exponentially with the number of calls to the $Q_{\\textrm{QPE}}$ oracle. I am aware that the logarithm of $1 / \\delta$ is taken for $t$, so an approximately linear dependence on the number of calls required, but reducing $\\delta$ does not come for free.\n\n- Definition of amplitude estimation in Section 3.2 is not novel and could be moved to an appendix (I do agree it would be useful for the audience of this journal).\n\n- The acronym QPE is already heavily in use referring to Quantum Phase Estimation, consider changing to avoid a clash.\n\n- The authors of qiskit request that it is cited via a Bibtex file found on the Github repo.\n\n- The claim of quantum speedup is not accurate without addressing these concerns, consider weakening the claim if a full resource estimation is not possible. \n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two experts in quantum RL were found to review this paper. In addition a senior RL researcher with no background in quantum was also brought in. During the first round issues with the utility of the bandit experiments were raised, but most critically the senior RL reviewer and the AC found the submission extremely difficult to understand.

The authors added a significant background section, and further contextualisation of the bandit experiment. The AC and two reviewers voting yes for acceptance.

There are some outstanding issues:
1)  add a short reference to section 3 in the intro, as it starts off talking about "unitary operators" and "exchange states" 
2) add entanglement into their background
3) make sure the justifications about the bandit experiments is fully integrated into the paper.
Decision: Accept (poster)