Quantum reinforcement learning: a heuristic approach to solve deterministic MDPs

Universidade do Minho Escola de Engenharia Departamento de Inform´ atica Renato Alberto Soares de Brito Quantum Reinforcement Learning A heuristic approach to solve deterministic MDPs February 2022 Universidade do Minho Escola de Engenharia Departamento de Inform´ atica Renato Alberto Soares de Brito Quantum Reinforcement Learning A heuristic approach to solve deterministic MDPs Master Dissertation Integrated Master’s in Physics Engineering Dissertation supervised by Lu´ıs Paulo Santos February 2022 DIREITOS DE AUTOR E CONDIC¸ ˜ OES DE UTILIZAC¸ ˜ A O D O TRABALHO POR TERCEIROS Este ´ e um trabalho acad ´ emico que pode ser utilizado por terceiros desde que respeitadas as regras e boas pr ´ aticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licen c¸ a abaixo indicada. Caso o utilizador necessite de permiss ˜ ao para poder fazer um uso do trabalho em condi c¸ ˜ oes n ˜ ao previstas no licenciamento indicado, dever ´ a contactar o autor, atrav ´ es do Reposit ´ oriUM da Universidade do Minho. Licenc¸a concedida aos utilizadores deste trabalho Atribuic¸˜ ao CC BY https://creativecommons.org/licenses/by/4.0/ i ACKNOWLEDGEMENTS This dissertation is the result of years of study and dedication, despite being a subject that I have not that much experience or practice I think it is a welcoming challenge. First of all, I would like to thank, first to my parents, for providing me this opportunity and love; second, to all the scientific community, a special thanks to those who came before me because the knowledge they shared is the foundation of this work and without them, this thesis would not be possible. Thank you to all the professors I encountered throughout my academic life; to my supervisor, professor Lu ´ ıs Paulo Peixoto Santos, and my colleague, Andr´ e Sequeira, for guiding me through this journey. ii STATEMENT OF INTEGRITY I hereby declare having conducted this academic work with integrity. I confirm that I have not used plagiarism or any form of undue use of information or falsification of results along the process leading to its elaboration. I further declare that I have fully acknowledged the Code of Ethical Conduct of the University of Minho. iii ABSTRACT This thesis works on Reinforcement Learning tree search and attempts to find the best possible sequence of actions the agent needs to execute to get the most reward while using less computational effort than by just applying a quantum maximum finding algorithm. To achieve this we will use the property that makes it possible to limit our search space to the elements that were marked by the oracle in Grover’s Algorithm, by marking a fourth of the search space and following it with a quantum maximum finding subroutine. From this, one of the marked elements is obtained and the information encoded in it is used to update a probabilistic distribution stored in a classical memory. The goal is to encounter the minimum amount of iterations of this process and compare the results, i.e., percentage of success which is measured as the number of times the algorithm produces a solution (element with maximum reward) and the number of queries used - with a traditional quantum maximum finding procedure. If this is observed, it is also hypothesized that the algorithm could be used to observe a step further into the future compared to the traditional procedure, i.e., use the same or fewer queries to evaluate a larger number of sequences fruit of increasing the horizon of the episodes. The last hypothesis tests the depth of the circuits, more specifically the number of gates used. If the algorithm evaluates shallower circuits than the quantum maximum finding, the approach can be applied on the current quantum machines (NISQ) because the shallower circuits produces more error-proof measurements. The results show that the proposed algorithm has no advantages compared to a traditional quantum maximum finding procedure due to using more queries to achieve the same rate of success which, consequently, invalidates the first and second hypothesis. For the third hypothesis, the gate complexity was not directly measured. Instead, was opted to measure the number of queries used by circuit which might not be sufficient to conclude that the algorithm uses shallower circuits. Keywords: Amplitude Amplification, Heuristic, Model-Free, Maximum Finding, Query Complexity iv RESUMO Esta tese trabalha com a busca em ´ arvores utilizando a Aprendizagem por Refor c¸ o para encontrar a melhor sequ ˆ encia poss ´ ıvel de a c¸ ˜ oes que o agente ter ´ a de executar de forma a obter o maior pr ´ emio poss ´ ıvel, isto enquanto usa menos esfor c¸ o computacional em compara c¸˜ ao com utilizar apenas um algoritmo de procura qu ˜ antica pelo m ´ aximo. Para atingir estes objectivos, usaremos a propriedade que possibilita limitar o espa c¸ o de procura para os elementos marcados pelo or ´ aclo no Algoritmo de Grover, marcando exatamente um quarto do espa c¸ o de procura, procedendo com uma procura qu ˆ antica. Disto resulta um dos elementos marcado e a informa c¸˜ ao codificada nele ser ´ a usada para atualizar uma distribui c¸˜ ao probabilistica guardada em mem´ oria cl´ assica. O objectivo ´ e encontrar o min ´ ımo de itera c¸ ˜ oes deste processo necess ´ aria para obter uma percentagem de sucesso - n ´ umero de vezes que o algoritmo retornou um elemento que ´ e solu c¸˜ ao do problema e o n ´ umero de queries usado - e comparar estes resultados com um procedimento tradicional de procura qu ˆ antica. Caso isto se obseve, ´ e colocada a hip ´ otese de se usar este algoritmo como forma de observar a c¸ ˜ oes futuras em compara c¸˜ ao com os algortimos tradicionais, isto ´ e, usar o mesmo ou menos queries para avaliar um maior n ´ umero de sequ ˆ encias fruto do aumento do horizonte dos epis ´ odios a avaliar. A ´ ultima hip ´ otese testa se a profundidade dos circuitos, mais concretamente o n ´ umero de gates usadas. Caso o algoritmo proposto utilize circuitos menos profundos que o algoritmo quantum maximum finding, este poder ´ a ser utilizado nas m ´ aquinas qu ˆ anticas atuais pois estes circuitos produzem medic¸ ˜ oes mais resistentes a erros. Os resultados mostraram que o algoritmo proposto n ˜ ao possui qualquer vantagem comparado ao quantum maximum finding por usar mais queries para atingir a mesma percentagem de sucesso o que, consequentemente, invalida a primeira e segunda hip ´ otese. Quanto ` a terceira hip ´ otese, o n ´ umero de gates usadas por circuito n ˜ ao foi medido diretamente. Em vez disso, optou-se por medir o n ´ umero de queris por circuito o que poder ´ a n ˜ ao ser suficiente para obter conclus˜ oes quanto ` a profundidade dos circuitos medidos. Palavras-Chave: Amplifica c¸˜ ao de Amplitude, Complexidade de Query, Heur ´ ıstica, Modelo Livre, Procura pelo M´ aximo v CONTENTS 1 introduction 1 1.1Motivation 1 1.2Contributions 2 1.3Structutre 3 2 brief introduction to quantum mechanics/information 4 2.1Quantum Mechanics 4 2.1.1Superposition 4 2.1.2Measurements and Operators 5 2.1.3Time evolution and Unitary Operators 6 2.1.4Composite systems and Entanglement 7 2.2Quantum Computation 7 2.2.1Qubit 8 2.2.2Quantum Gates 9 2.3Initialization 13 2.3.1Basis Encoding 13 2.3.2Amplitude Encoding 14 2.4Quantum Algorithms 16 2.4.1Grover’s Search and Amplitude Amplification 16 2.4.2Quantum Maximum Finding 20 3 reinforcement learning 21 3.1Markov Decision Processes 21 3.1.1Policies 23 3.1.2Value functions and Bellman Equations 23 3.2Dynamic Programming 25 3.2.1Policy Iteration by Howard 25 3.2.2Value Iteration 27 3.3Model-Free Techniques 27 3.3.1Monte-Carlo Methods 28 3.3.2Temporal Difference Learning (TD) 29 4 quantum reinforcement learning and tree search 31 4.1Branching factor ramifications 31 4.2Quantum Heuristic 33 5 proposed algorithm:g25 35 vi contents vii 5.1Quantum Maximum Finding with G25 35 5.1.1Selection 36 5.1.2Search 36 5.1.3Update 37 5.2Complexity 38 6 case study 40 6.1Simulations: the Gridworld 40 6.1.1Studied Gridworlds 41 6.2Results 42 7 conclusion and future work 50 7.1Conclusion 50 7.2Future work 51 2 BRIEF INTRODUCTION TO QUANTUM MECHANICS/INFORMATION In this chapter we will go over the theory behind quantum computation/information, introducing some quantum mechanics concepts and how they are applied in computations. Then, we give an overview of some relevant quantum gates, circuit examples and algorithms that will be used as subroutines. 2.1 quantum mechanics The contents of this section follow the introduction of [ 6 ] and are stated here for completion. Quantum mechanics describes systems at the subatomic/atomic scales. At this size, classical theories can not describe with certainty said systems. The key differences are the quantities of a bound system which are restricted to discrete values (quantization). Objects behave as particles and waves (wave-particle duality) and there are limits to how accurately the value of a physical quantity can be predicted before its measurement. Here is introduced the Dirac notation where a ket |ψ⟩ , which denotes a quantum state, is a complex vector and a bra ⟨ψ| , its complex conjugate. The norm of a vector is defined as the inner product, represented as abracket,||ψ|| =p⟨ψ|ψ⟩. 2.1.1Superposition The state of a quantum mechanical system is a vector, ψ that belongs to a complex Hilbert space. A quantum state can be an eigenvector of an observable, and if so, we call it an eigenstate, and the associated eigenvalue corresponds to the value of the observable in that eigenstate. Thus, a quantum state can be a linear combination of the eigenstates, a quantum superposition: |ψ⟩=α1|ψ1⟩+···+αN|ψN⟩(2) 4 where {α1···αN} is a complex amplitude vector. |ψ1⟩···|ψN⟩ and N is the total number of states in superposition. In general we can write: |ψ⟩=∑ i αi|ψi⟩(3) where |ψ⟩is normalized and the eigenstates are orthonormal: ∑ i|αi|2=1 (4) Thus |αi|2 is the probability of a measure collapsing the state |ψ⟩ to |ψi⟩ . The outer product is constructed as |ψ⟩⟨ψ| . For every vector there is an orthonormal basis ei,∀i∈N such as the inner product eiej=δij and: |ei⟩⟨ei|=    e1 . . . eN     (e1···eN) =     e1e1e1e2··· e1eN . . .. . ..... . . eNe1eNe2··· eNeN     (5) forms a projection operator that, when multiplied by some vector, projects the vector onto the subspace of the basis vector. The projection can be used to change basis, expressing some state (ψ) in the basis ei: P|ψ⟩=∑ i|ei⟩⟨ei|ψ⟩=∑ i⟨ei|ψ⟩|ei⟩(6) This operator is used in the process of measuring a quantum state. 2.1.2Measurements and Operators Other important entity are the operators, which in physics correspond to the observables like momentum and position, that act on a quantum state. Operators act linearly by left multiplication on a superposition state. Ameasurement on a state |ψ⟩is given by the Born Rule; lets say we have the state |ψ⟩=α1|ψ1⟩+α2|ψ2⟩(7) the probability of measuring each eigenstate is |⟨ψi|ψ⟩|2=   α2 1, if |ψi⟩=|ψ1⟩ α2 2, if |ψi⟩=|ψ2⟩(8) 5 If we have an operator ρ, acting on |ψ⟩, of the form ρ=∑ i ρi|ψi⟩⟨ψi|=ρ1|ψ1⟩⟨ψ1|+ρ2|ψ2⟩⟨ψ2|(9) this operator is also called the density operator and ρi describes the probability of measuring a pure state. This one describes a density matrix we will measure the system with probability: |⟨ψi|ρ|ψ⟩|2=   α2 1ρ2 1, if |ψi⟩=|ψ1⟩ α2 2ρ2 2, if |ψi⟩=|ψ2⟩(10) 2.1.3Time evolution and Unitary Operators The evolution of a quantum mechanical system is described by the well known Schr ¨ odinger equation: i¯hd dt |ψ⟩=ˆ H|ψ⟩(11) where ˆ H denotes the Hamiltonian of the system. The solution to this equation is the unitary operator ψ(t) = U(t)|ψ0⟩ ; here ψ0 is the initial state, ¯his the Planck constant and U(t)is the unitary time-evolution operator given by U(t) = e−it ¯hˆ H(12) Unitarity means that the operator preserves the inner product between the vectors in an Hilbert space. The Hamiltonian is hermitian ( H=H† ), which means that the possible measured energies (eigenvalues of the Hamiltonian), are always real numbers. The Born rule states that if an observable corresponding to an operator A is measured in a system with normalized wave function |ψ⟩, then: • the measured result will be one of the eigenstates of A • the probability of measuring a given eigenvalue will equal ⟨ψ|Pi|ψ⟩ , where Pi is the projection onto the eigenspace of A corresponding to ψi. Since the complex number ⟨ψi|ψ⟩ is known as the probability amplitude that the state vector |ψ⟩ assigns to the eigenvector |ψi⟩ , the Born rule generally says that this probability is equal to the amplitude-square |⟨ψi|ψ⟩|2. The Schr ¨ odinger equation is a linear differential equation meaning that if we have two wave functions that are solutions then a linear combination of both is also a solution allowing for the superposition principle that was mentioned before. 6 2.1.4Composite systems and Entanglement Suppose there are two quantum systems, A and B, with the respective Hilbert spaces HA and HB . These can be combined with the tensor product resulting in the system spanned over the Hilbert space H, which is given by H=HA⊗HB(13) Following this, we can introduce the concept of entanglement. Let us fix a basis {|i⟩A} for HAand {|j⟩B}for HB. The general state of His of the form |ψ⟩AB =∑ i,j cij |i⟩A⊗|j⟩B(14) This state is separable if exists the vectors cA i , cB j so that cij =cA icB j , yielding |ψ⟩A=∑icA i|i⟩A and |ψ⟩B=∑jcB j|j⟩B . If the state |ψ⟩AB is entangled, we can not describe each component of the subsystems A and B meaning, that for at least one pair of coordinates (cA i,cB j) , cij =cA icB j . Instead, a density matrix is defined which describes the statistics that can be obtained by making measurements on either component system alone. If a quantum system was perfectly isolated it would remain coherent but would be impossible to make any measurement on. During a measurement, occurs a loss of information to the environment (just as a heat bath [ 7 ]) resulting in coherence being lost over time. The dynamics between the state and the environment can be viewed as an entangled state, sharing quantum information. 2.2 quantum computation There are several quantum computing models, however, only a subset of them can offer universal quantum computation. Some examples are: quantum circuit model,quantum Turing machine,adiabatic quantum computer,blind quantum computing and others [8]. In terms of computability theory, quantum computers, offer no advantages over classical computers, meaning, that quantum computers and classical computers offer solutions to the same problems [ 9 ]. However, quantum computation, in several applications has a lower time complexity over the classical ones. Quantum computers are believed to quickly solve certain problems that no classical computer can solve in feasible time - also known as quantum supremacy. The advantages comes from exploiting quantum mechanics properties such as superposition,entanglement and interference. In the quantum circuit model, generally, the computation is composed of three steps: 7 • Initialization: usually this step involves transforming the ground state into a superposition of the sub-states that encode the information • Intended Computation: unitary transformations on the input state • Measurement: collapsing the final state into one of the substates present prior to the measurement 2.2.1Qubit Any two-level quantum-mechanical system can be used as a qubit. Multi-level systems can be used as well if they possess two states that can be decoupled from the rest. Some common examples are the polarization of a photon where the dual states are encoded as the horizontal and vertical polarization of the light [ 10 ], the spin of an electron [ 11 ], and the supercurrent phenomenon that flows through a Josephson junction [12]. The ground state of the two-level system can be expressed as the zero state |0⟩ and the first excited state as the |1⟩ state which form a orthonormal basis of an Hilbert space and is called the Computational basis, being isomorphic to C2 . The state of a qubit is represented by a linear combination of the basis states |0⟩ and |1⟩ . According to the Born rule, with probability |α0|2 we observe the state |0⟩ and with |α1|2 we observe |1⟩ , following the rule |α2 0|+|α2 1|=1. The state can also be represented in the standard basis as the vectors: |0⟩= 1 0!|1⟩= 0 1!(15) Another representation is the Bloch Sphere and can be parametrized as |ψ⟩=eiϕ(cosθ 2|0⟩+eiφsinθ 2|1⟩)(16) 8 Figure 1: Bloch Sphere. Image from Wikipedia. Note that, because α and β are complex numbers, we should expect four degrees of freedom. However, one degree of freedom is eliminated by the normalization constraint leaving us with equation 16. Additionally, for a single qubit, the overall phase of the state eiϕ has no physical observables resulting in eiφ being the only significant phase, presented in figure 2. We can represent a classical bit as being in either the north or south pole of the sphere, pure qubit states are spanned over the surface of the sphere and a mixed state can only be represented inside the sphere. In the circuit model of quantum computation, gates (unitary matrices that emulate quantum operators) operate over qubits mapping them to an arbitrary state. 2.2.2Quantum Gates The computation is performed by quantum logic gates. These are operators described as unitary matrices relative to some basis (usually the computational basis). This property makes these gates reversible meaning that, if we consider a state |ψ0⟩ and an unitary operator O, we can write |ψ1⟩=O|ψ0⟩and |ψ0⟩=O−1|ψ1⟩. The most known single qubit gates are the Pauli matrices: σx= 0 1 1 0!=X σy= 0−i i0!=Y σz= 1 0 0−1!=Z (17) 9 In general, a single qubit phase shift can be written as P(φ) = 1 0 0eiφ!and Z= 1 0 0eiπ!=P(π) S= 1 0 0eiπ 2!=Pπ 2=√Z T= 1 0 0eiπ 4!=Pπ 4=√S (18) The σxacts as a classical NOT gate inverting the state (often called the bit-flip gate) σx|0⟩= 0 1 1 0! 1 0!= 0 1!=|1⟩(19) The σz acts as a phase-flip gate inverting the phase of a quantum state |1⟩ while leaving the state |0⟩unchanged σz= 1 0 0−1! 1 0!= 1 0!=|0⟩(20) σz= 1 0 0−1! 0 1!=− 0 1!=−|1⟩(21) In this case the global phase is irrelevant, in fact, if we measure a state |1⟩ transformed by a gate σz resulting in −|1⟩ , we will measure it with the square amplitude, which in this case results in measuring the state |1⟩ all the time. Mind you that this is true if we do not perform any computation after flipping the phase; Grover’s Algorithm is a clear example of an algorithm where the global phase is determinant as we will see in Section 2.4.1. Rotation gates correspond to single qubit rotations on the corresponding axis of the Bloch Sphere. Equations 22,23 and 24 refer to rotations around the ˆ x,ˆ yand ˆ zaxis respectively Rx(θ) = cos(θ/2)−isin(θ/2) −isin(θ/2)cos(θ/2)!(22) 10 Ry(θ) = cos(θ/2)−sin(θ/2) sin(θ/2)cos(θ/2)!(23) Rz(θ) = e−iθ/2 0 0eiθ/2!(24) All single-qubit rotation gates can be translated into Pauli-matrices, using an angle of θ=πas represented in equation 25 Rx(π) = −iX Ry(π) = −iY Rz(π) = −iZ (25) An arbitrary single-qubit gate can be parametrized by three Euler angles as U(ϕ,θ,φ) = cos(θ/2)−eiϕsin(θ/2) eiφsin(θ/2)ei(θ+ϕ)cos(θ/2)!(26) The Hadamard gate is probably the most important logic gate, being responsible for creating quantum uniform superpositions over the basis state: H|0⟩=1 √2 1 1 1−1! 1 0!=1 √2" 1 0!+ 0 1!#=1 √2(|0⟩+|1⟩)(27) H|1⟩=1 √2 1 1 1−1! 0 1!=1 √2" 1 0!− 0 1!#=1 √2(|0⟩−|1⟩)(28) An arbitrary superposition state can be created using the Rygate as in equation 29 Ry(θ)|0⟩= cos(θ/2)−sin(θ/2) sin(θ/2)cos(θ/2)! 1 0!=cos(θ/2)|0⟩+sin(θ/2)|1⟩(29) From here is a matter of solving the equations α0=cos(θ/2);α1=sin(θ/2) for said superposition |ψ⟩=α0|0⟩+α1|1⟩. To operate over multiple qubits we have the fundamental two-qubit gate CNOT,controlledNOT gate or CX. This gate does a bit-flip on a qubit (target) dependent on the state of another one (control) 11 CNOT =      1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0       (30) In other words, if the control is zero, it applies the identity matrix on the target or applies a not gate if the control is one. In general, this gate can be modified to apply any other single-qubit gate U. Writing in Dirac notation CNOT =|0⟩⟨0|⊗1+|1⟩⟨1|⊗U(31) The CNOT gate in conjunction with the Hadamard is able to entangle qubits CNOT(H⊗1)(|0⟩⊗|0⟩) = CNOT 1 √2(|0⟩+|1⟩)⊗|0⟩)=1 √2(|0⟩⊗|0⟩+|1⟩⊗|1⟩) (32) Figure 2: CNOT circuit representation. Image from Wikipedia. Lastly, is the Toffoli gate also known as CCNOT being the quantum analog to the classic AND gate. This gate has 2control qubits and flips the third one if the controls are both in the state |1⟩ . The Toffoli gate needs to be decomposed into simpler gates to be implementable on actual hardware. The canonical Toffoli gate is decomposed as in figure 3, and further decomposed as in Figure 4for an arbitrary number of control qubits. Figure 3: Toffoli gate representation and its decomposition with elementary gates. Image from [1]. 12 Figure 4: V-Shape decomposition for multi control gates. Image from [2]. 2.3 initialization The most known state preparation methods are the Basis encoding and Amplitude encoding but there are others such as Qsample encoding,dynamic encoding,squeezing embedding,Hamiltonian encoding [ 13 ]. In this work, we will use the basis encoding method because of the constraints imposed by the algorithm that will be proposed later. First, let ´ s consider a classical binary input data set of M elements, D={x0,··· ,xM−1} where xm={0, 1}n , n being the bitstring length. 2.3.1Basis Encoding This method is the most straightforward, it just associates each element of the data set with a computational basis state of a qubit system. In this case, the amplitude of each quantum state carries no information and is only used as a way to ”mark” the state for posterior processes. An entire data set will be represented as: |D⟩=1 √M M−1 ∑ m=0|xm⟩(33) For example the data set of the string x0=01 and x1=10 is represented as |D⟩=1 √2|01⟩+1 √2|10⟩(34) 13 2.4.2Quantum Maximum Finding Algorithm 1can be used as a subroutine to find the minimum element in an unordered list as proposed in [ 20 ]- Although, in the article, the authors designed the algorithm to find the minimum, a magnitude comparator oracle that marks the states |x⟩ such that A[x]≥A[y] , where y is a threshold, can be trivially devised and was suggested in [21]. The algorithm uses the Qsearch as a subroutine. We start by randomly choosing one of the elements from the set to be the threshold of the Qsearch ( y ). The Qsearch is then applied to find an element that is larger than the threshold which becomes the new threshold. The authors claim that the probability is 1−1 2c where cis the number of iterations of the quantum maximum finding algorithm. The algorithm finds a solution in O(√N) iterations. Algorithm 2QMF(Quantum Maximum Finding) y←random(0, ..., N−1);it ←0; A[N]; while it ≤√Ndo Create |ψ⟩=1 √N∑N−1 i=0|i⟩; Apply the magnitude comparator oracle; Apply the Qsearch Algorithm 1; Measure |x⟩,x′←|x⟩; if A[x′]>A[y]then; y←x′; end if end while Return y 20 3 REINFORCEMENT LEARNING Reinforcement Learning (RL) is an area of machine learning together with supervised learning and unsupervised learning. In supervised learning, the agent receives a labeled dataset { x,y } where y is a ”flag” that classifies x. The goal of the agent is to design a function f:x7→ y , such that it learns all the correct labels associated with x. The goal is to generalize such functions to unseen data. In unsupervised learning, the parity present in the training set does not exist, and so, the agent has to find the patterns in the data. RL differs from the previous two. The RL agent receives information from the environment, namely the state is fully observable and more importantly the reward. The agent needs to interact with the surrounding environment and learn by trial and error. RL algorithms aim to maximize a reward which is a signal that indicates the degree of goodness of the performed action. RL techniques have a trade-off, the exploration v.s. exploitation problem, since the agent has no prior knowledge of the environment. This has been thoroughly studied through the multi-armed bandit problem and for finite state space, MDPs in [ 22 ]. Should we take an action that we already know the outcome or should we risk-taking an unknown action expecting a bigger reward? For RL problems, the environment can be fully observable, the agent can directly observe the environment, for example, the game of chess; or, it can be partially observable, where the agent has access to a particular piece of the entire environment like the game of poker. In this thesis, we will consider fully observable environments, which can be stated as Markov Decision Processes (MDP). 3.1 markov decision processes MDPs consist of states, actions, transitions between states, and a reward function definition. They form the basis of RL since it gives a clear definition of an environment and its dynamics. An MDP is described as a tuple ⟨S,A,T,R⟩ . An additional parameter might be added to 21 this tuple, the discounting factor γ, as we will see later. A set of states, S, is defined as the finite set S={s1,··· ,sN} . For example, in chess, any possible configuration of pieces disposed on the board is a state. A set of actions, A, is defined as A={a1,··· ,aK} . The set of actions that can performed in a state is described as A(s). Applying the action a∈A , in the state s∈S , the system performs a transition form s to a new state s′∈S , based on a probability distribution over the set of possible transitions.The transition function T is defined as T:S×A×S→[0, 1] , i.e., the probability of ending up in state s′ after taking action a in state s is denoted T(s,a,s′) . For each state-action pair, T needs to be normalized 0 ≤T(s,a,s′)≤1 and ∑s′∈ST(s,a,s′) = 1. The system being controlled is an MDP if the result of an action does not depend on the previous actions and visited states (history), but only depends on the current state, also known as the Markov Property P(st+1|st,at,st−1,at−1,···) = P(st+1|st,at)(52) Here the time is discrete, st denotes the state at time t . The idea of Markovian dynamics is that the current state s gives enough information to make an optimal decision. It is not important which states and actions preceded s. More general models can be characterized by being k-Markov, i.e., the last k states are enough. The Reward Function is responsible to assign rewards to the agent and can be designed mainly with two distinct strategies, namely, state-dependent rewards or state-action dependent rewards. The state reward function is defined as Rsa :S→ R specifying the rewards for being in a state. Other definitions are: R:S×A→ R or Rsa :S×A×S→ R . The first gives rewards for acting in a state, and the second gives rewards for particular transitions between states. The transition function T and the reward function R together define the model of the MDP. Often MDPs are depicted as a state transition graph where the nodes correspond to states/actions and (directed) edges denote transitions[ 23 ]. The reward is added to this representation that tells how good it is in a given state. The acumulated reward defines a trajectory in the graph, Gt , the return of some sequences of rewards, Gt=Rt+1+···+RT . This formulation may be problematic, in the case T=∞ , the reward will be infinite. The discount factor ensures that – even with an infinite horizon – the sum of the rewards obtained is finite. In episodic tasks, the discount factor is not needed, however, it is useful when h→∞ to prevent large reward summation that may difficult the optimization reward.To solve this, is added the discounting factor γ resulting in Gt=Rt+1+γRt+2+··· =∑∞ k=0γkRt+k+1 . There are three models of optimality in the MDP: the finite horizon, where the expected return is 22 given by Eh∑h t=0rti ; the discounted infinite horizon, E∑∞ t=0γtrt , and the average reward, limh→∞Eh1 h∑h t=0rti. 3.1.1Policies Given a MDP M , a policy π is a computable function that outputs for each state s∈S an action a∈A(s) . A deterministic policy is described as π:S→A or π:S×A→δSA ( for every s∈S , π(s,a)≥0 and ∑a∈Aπ(s,a) = 1 . A stochastic policy is defined as π:S×A→[0, 1]. Sampling trajectories under a policy πis done by: • a start state s0from the initial state distribution I is generated • the action a0=π(s0), calculated by the policy π, is performed • Based on the transition function T and reward function R , a transition is made to state s1, with probability T(s0,a0,s1)and a reward is received If the task is episodic, the process ends after some steps or if the agent reaches a terminal state. 3.1.2Value functions and Bellman Equations A value function represents an estimate of how good it is for the agent to be in a certain state. The value of a state s under a policy π , Vπ(s) is the expected return when starting in sand following π. Considering the infinite horizon model, this can be expressed as Vπ(s) = Eπ{ ∞ ∑ k=0 γkrt|st=s}(53) A similar state-action value function Qπ(s,a) , or Q-function, can be defined as the expected return starting from state s, taking action aand thereafter following policy π Qπ(s,a) = Eπ{ ∞ ∑ t=0 γtrt|st=s,at=a}(54) 23 One fundamental property of value functions is that they satisfy certain recursive properties. For any πand any state s,Vπ(s)can be recursively defined as a Bellman equation: Vπ(s) = Eπ{rt+γ1 t+1+γ2rt+2+···|st=s} =Eπ{rt+γVπ(st+1)|st=s} =∑ s′ T(s,π(s),s′)R(s,a,s′) + γVπ(s′) (55) This property denotes that the expected value of state is defined in terms of the immediate reward and values of possible next states weighted by their transition probabilities, and additionally a discount factor. Multiple policies can have the same value function, but for a given policy π,Vπis unique. The goal for any MDP is to find the optimal policy, the policy that maximizes the value function Vπ(s)for all s∈S, i.e., maximizes the reward. An optimal policy, π∗ , is such that Vπ∗(s)≥Vπ(s) , ∀s∈S and ∀π∈Π . The Bellman optimality equation V∗(s) = maxa∈A∑ s′ T(s,a,s′)R(s,a,s′) + γV∗(s′)(56) states that the value of a state under the optimal policy must be equal to the expected return for the best action in that state. To select an optimal action given the optimal state value function V∗the following rule can be applied: π∗(s) = argmaxa∑ s′ T(s,a,s′)R(s,a,s′) + γV∗(s′)(57) π∗ is called the greedy policy because it allways selects the best action using the value function V. The analogous optimal state-action value is: Q∗(s,a) = ∑ s′ T(s,a,s′)R(s,a,s′) + γmaxa′Q∗(s′,a′)(58) Q-functions are useful because they make the weighted summation over different alternatives. This is the reason for their preference in the model-free setting, i.e., in case T and R are unknown. The relation between Q∗and V∗is given by Q∗(s,a) = T(s,a,s′)R(s,a,s′) + γV∗(s′)(59) V∗(s) = maxaQ∗(s,a)(60) 24 And the optimal action (best policy) can be written as π∗(s) = argmaxaQ∗(s,a)(61) 3.2 dynamic programming Dynamic Programming (DP) is a method of solving a complicated problem by breaking it down into simpler sub-problems in a recursive manner. In the context of RL, the Bellman Equation acts as a recursive structure and its solution can be solved with DP techniques. There are two main models used, Policy Iteration and Value Iteration. We will assume a standard MDP <S,A,T,R,γ> where the state and action sets are finite and discrete such that they can be stored in tables. The reward and value functions are assumed to store values for all states and actions separately. 3.2.1Policy Iteration by Howard This technique is composed of two stages: the policy evaluation stage computes the value function of the current policy and the policy improvement stage computes an improved policy by a maximization over the value function. This is repeated until converging to an optimal policy. The first step is to find the value function Vπ of a fixed policy π . This is called the prediction problem. The Bellman equation is transformed into an update rule, turning the actual value function Vπ tinto Vπ t+1, the one-step lookahead. Vπ t+1(s) = Et{rt+γVπ k(st+1)|st=s} = ′ ∑ s T(s,π(s),s′)(R(s,π(s),s′) + γVπ k(s′)) (62) The update rule is applied to each state s∈S in each iteration. The old value-function is replaced with a new one based on the expected value of possible successor states, intermediate rewards, and weighted by their transition probabilities. This operation is called a full backup because it is based on all possible transitions from that state. At the end of policy evaluation, we ought to improve Vπ(s) .First, we identify the value of all actions: Qπ(s,a) = Et{rt+γVπ t(st+1)|st=s,at=a} =∑ s′ T(s,a,s′)(R(s,a,s′) + γVπ k(s′)) (63) If Qπ(s,a) is larger than Vπ(s) then a is chosen to update the policy for state s . This is done for every state of the MDP, generating our improved policy. That is, we can compute 25 the greedy policy, selecting the best action in each state, based on the current value function Vπ: π′(s) = argmaxaQπ(s,a) =argmaxaE{rt+γVπ(st+1)|st=s,at=a} =argmaxa ′ ∑ s T(s,a,s′)(R(s,a,s′) + γVπ k(s′)),∀s∈S (64) If π′(s) = π(s) , ∀s∈S then the agent converged to the optimal policy. For a finite MDP each πt+1 is strictly better than πt unless πt=π∗ in which case the algorithm stops. The algorithm is presented in Algorithm 3. Algorithm 3Policy Iteration (PI) Require: V(s)∈Randπ(s)∈A(s)f oralls ∈S Policy Evaluation repeat ∆←0 for all s∈Sdo v←Vπ(s) V(s)←∑′ sT(s,π(s),s′)(R(s,π(s),s′) + γV(s′)) ∆←max(∆,|v−V(s)|) end for until ∆<σ Policy Improvement p←true for all s∈Sdo b←π(s) π(s)←argmaxa∑′ sT(s,a,s′)(R(s,a,s′) + γV(s′)) if b=π(s)then p←f alse end if end for if pthen halt else go to Policy Evaluation end if 26 3.2.2Value Iteration This algorithm blends the policy improvement step into it. Vt+1(s) = maxa ′ ∑ s T(s,a,s′)(R(s,a,s′) + γVπ t(s′)) =maxaQt+1(s,a) (65) The value iteration algorithm spends less time in the evaluation part by removing the improvement step and, instead of initializing a policy randomly and alternating between evaluation and improvement, it initializes the value function arbitrarily. Both algorithms theoretically converge to the optimal policy, however, the difference in the update, makes the Value Iteration converge to the optimal policy faster. These algorithms operate over the entire state space of the MDP which, for some applications, may be too expensive. 3.3 model-free techniques In contrast with the algorithms discussed in the previous section, model-free methods do not rely on the availability of a priori model of the MDP. This generates a need to sample the MDP to gather statistical knowledge about this unknown model. The first one is to learn the transition and reward model from interacting with the environment. Once our model is sufficiently correct, the methods from the previous section can be applied. This is called model-based RL or indirect RL. The second option, direct RL, is to estimate values for actions, without even estimating the model of the MDP. Additionally, mixed forms between these two can exist. For example, one can still do a model-free estimation of action values, but use an approximated model to speed up value learning by using this model to perform more, and in addition, full backups of values. Aditionally, it is difficult to assess the utility of some action, if the real effects of this particular action can only be perceived much later. One possibility is to wait until the end of an episode and punish/reward specific actions along the path taken. However, this will take a lot of memory and, often, it is not known beforehand whether, or when, there will be an ”end”. Instead, similar mechanisms as in value iteration can be used to adjust the estimated value of a state based on the immediate reward and the estimated (discounted) value of the next state. This is generally called temporal difference learning. The general class of algorithms that interact with the environment and update their estimates after each horizon are called online RL. Here, the agent selects an action based on its current state, gets feedback in the form of the resulting state and associated reward, and updates its 27 estimated values stored in Vπ and Qπ . The selection of the action is based on the current state s and the value function. Algorithm 4Online RL for each episode do s∈Sis the starting state t←0 repeat choose an action a∈A(s)from π(s) perform action a observe the new state s′and reward r update T, R, Q and/or V using the experience ⟨s,a,r,s′⟩ s←s′ until s′is the goal state/terminal state or we reached the horizon end for Since model-free algorithms need to balance exploration and exploitation, the agent needs an action-selection mechanism that balances effectively, between informed actions and random actions. The most basic exploration strategy is the ϵ− greedy, where, the learner takes its current best action with probability 1−ε and other randomly selected action with probability ε . One natural way of balancing exploration/exploitation is through the Boltzmann exploration strategy where the agent stochastically selects an action from the probability distribution π in equation 66. π(a|s) = eQ(s,a) T ∑ieQ(s,ai) T (66) where T is known as the inverse temperature β=1 T . Higher values of T will move the selection strategy more towards a purely random strategy and lower values will move to a fully greedy strategy. We can combine the ϵ−greedy and the strategy in equation 66, selecting the best action with probability 1−ϵ and an action computed by the Boltzmann exploration strategy, with probability ϵ. 3.3.1Monte-Carlo Methods Monte-Carlo(MC) algorithms treat the long-term reward as a random variable and take as its estimate the sampled mean. It estimates values based on averaging sample returns observed during an interaction. Monte Carlo methods are defined only for episodic tasks, they are 28 incremental in an episode-by-episode sense, but not in a step-by-step (online) sense. As more returns are observed, the average should converge to the expected value. Suppose we are trying to estimate vπ(s) , the value of a state s under policy π , given a set of episodes obtained by following π . Each occurrence of state s in an episode is called a visit to s . The state s may be visited multiple times during an episode so let us call the first time it is visited first visit to s . The first-visit MC method estimates vπ(s) as the average of the returns following first visits to s, whereas the every-visit MC method averages the returns following all visits to s. Both these methods converge as the number of visits (or first visits) to s tends to infinity. The computational expense of estimating the value of a single state is independent of the number of total states. An interesting application of Monte-Carlo methods is the Monte-Carlo Tree Search where each episode is divided into four steps: selection, expansion, simulation and backpropagation. This technique was used to design software that was able to beat the world champions in games like chess and Go (see [24]). 3.3.2Temporal Difference Learning (TD) An advantage of TD methods is that they are naturally implemented in an online, incremental fashion such that they can be easily used in various circumstances. Only along experienced paths do values get updated, and updates are affected after each step. This is an advantage over Monte Carlo methods where we have to wait until the end of an episode. Also, Monte Carlo methods must ignore or discount episodes on which experimental actions are taken, which can greatly slow learning. TD(0) is used to evaluate a policy through the use of the following update rule: Vk+1(s) = Vk(s) + α(r+γVk(s′)−Vk(s)) (67) where α∈[0, 1] is the learning rate that determines how much the values get updated. The difference with DP backups is that the update is still done by bootstrapping but is based on an observed transition, it uses a sample backup instead of a full backup. Only the value of one successor state is used, instead of a weighted average of all possible successor states. The learning rate αhas to be decreased appropriately for learning to converge. Q-learning incrementally estimate Q-values for actions, based on feedback (rewards) and the agent’s Q-value function [25]. Qk+1(st,at) = Qk(st,at) + α(rt+γmaxaQk(st+1,a)−Qk(st,at)) (68) 29 sequences is less than the query complexity of the circuit acting on the totality of actions sequences. More importantly, it is hypothesized that this query complexity is maintained even though the proposed algorithm has to iterate multiple times. This hypothesis is experimentally tested in the next chapter. If it holds it will enable a reduction in the total number of queries required to find an optimal action for a given horizon. Additionally, it will allow for better decision-making by increasing the horizon while maintaining a similar number of queries as the original algorithm. This procedure is shown in Algorithm 5. Algorithm 5Proposed Algorithm: G25 Initialize the distribution: P=∑N i=11 N; repeat Initialize the quantum state |ψ⟩=R(∑N i=01 √N|a0···ah⟩⊗|0···0⟩); Selection: Sample a fourth of the sequences from P; Apply the G25 operator; SearchApply citerations of the Quantum Maximum Finding; Measure the state; Update the distribution P; until A set number of iterations were performed; 5.1.1Selection The Selection stage is just a classical sampling from the current distribution P , choosing a fourth of the total number of sequences. The distribution is initialized as a uniform discrete distribution over all the possible sequences of actions and updated over the course of the iterations performed. 5.1.2Search This step is performed by the quantum machine and to do so, the quantum state is initialized, followed by the application of the G25 operator and it is ended with the QMF algorithm. The initialization of the quantum state is done by creating a superposition over the action register. Then is applied an operator that entangles the action register with the reward register, R. By doing this we map each sequence of actions to its reward. Next, we apply the G25 operator. This operator is just a Grover’s operator (41), with exactly a fourth of the search space marked. A single application of this operator results in a superposition over the states that were marked by the oracle reducing the amplitude of the unmarked ones to 0. Next the QMF algorithm is applied, to be more precise, 3iterations of this algorithm will 36 be executed, giving a probability of the result being the maximum reward present in the superposition of 87,5% as was mentioned in section 2.4.2. Notice that, even though we may measure a sequence with the highest reward after just 1or 2iterations, the algorithm always performs the 3iterations because the agent does not know a priori the maximum reward that it may obtain and will keep searching for a better one. 5.1.3Update The updating is done by adding to the measured sequence the respective reward obtained and subtracting the adequate quantity to normalize the distribution. Normalization The measured sequence ”weigth” is updated by (76): psel =1+rsel t−1+rsel N+Rt−1+rsel (76) where sel refers to the measured sequence, rsel t−1 is the reward the sequence sel has acumulated, rsel is the measured reward and Rt−1 is the total acumulated reward by the measured sequences after titerations of the G25 algorithm. The rest of the sequences are updated by equation (77): pseq =1+rseq t−1 N+Rt−1+rsel (77) It can be proven that for each update of the distribution, the sum of the ”weights” is 1: psel +∑ seq∈S′ pseq =1+rsel t−1+rsel N+Rt−1+rsel +×∑seq∈S′(1+rseq t−1) N+Rt−1+rsel (78a) =1+rsel t−1+rsel + (N−1) + ∑seq∈S′rseq t−1 N+Rt−1+rsel (78b) =N+rsel + (∑seq∈S′rseq t−1+rsel t−1) N+Rt−1+rsel (78c) =N+Rt−1+rsel N+Rt−1+rsel (78d) where S′ represents all the sequences except the one that was measured by the algorithm at the iteration t. Notice that in 78c,∑seq∈S′rseq t−1+rsel t−1=Rt−1. After titerations of the algorithm, the distribution is given by equation (79): 37 P=∑ seq 1+xseq ×rseq t N+Rt (79) where xseq is the number of times the sequence seq was measured, N is the total number of possible sequences of actions and Rt is the reward acumulated over all measured sequences after t iterations of the algorithm, Rt=∑seq xseq ×rseq . As any discrete probabilistic distribution, ∑p=1: P=∑ seq 1+xseq ×rseq N+Rt =N+∑seq xseq ×rseq t N+Rt =N+Rt N+Rt =1 (80) Since the exact number of iterations of the G25 algorithm to achieve close to 100% success rate is hard to be determined mathematically, the experiments consist of applying 1to it iterations of the G25 algorithm (see Chapter 6). After each experiment, the sequence with the maximum ”weight” is picked as the output of the c iterations of the algorithm (seqout =argmaxP). Then the success rate, specifically, the number of experiences that result in a sequence with the maximum reward possible for that environment, is compared with the QMF algorithm. Notice that, in the latter, there is no distribution, so the 3iterations of the QMF are applied and the result is the output. 5.2 complexity Being a hybrid algorithm we will take into account the classical and quantum complexity of the algorithm. Since the algorithm proposed aims to reduce the number of queries, this will be the metric used to study its complexity. Specifically, in the quantum setting, this query complexity refers to the number of Grover’s operators that any given experiment is expected to utilize. The classical complexity is simply the number of elements to be searched in both the selection and update steps. It is easy to see that both these steps have a complexity of O(N): • the algorithm has to select exactly a fourth of the sequences resulting in a complexity of O(N 4) = O(N)when N→∞; • in the updating step, the machine will have to search the measured sequence over N and, for the same reasons as in the select step, this grows linearly with the increasing of the search space 38 The sequences generation was ignored. For the quantum computation, because we make use of the Quantum Maximum Finding algorithm, it inherits its complexity of O(√N) . Notice that, after the G25 operator we end up with a fourth of the original number of sequences so the complexity will be O(√N′)where N′=N 4. Despite the gain in the quantum complexity, the size of the circuits might be higher with the application of the G25 operator. For this thesis, only the number of queries (applications of the operator Q in the QMF algorithm) will be taken into account in the calculation of the complexity. If we look at the algorithm globally, its complexity will be O(N) (when N→∞ ) due to the logistics surrounding the distribution. How to solve this? For the selection, we can circumvent this by, instead of selecting a fourth of the search space every iteration, applying this selection only for the first iteration and in the next ones, substituting a set number of sequences of the previous selected with different ones resulting in a constant complexity, O(1) . The previous approach was not tested so its impact on the behavior of the algorithm and its results are not known. The second item was ignored by hashing the distribution. 39 6 CASE STUDY 6.1 simulations:the gridworld The modeled environment chosen was the Gridworld. As the name suggests, the environment is a grid/matrix of chosen dimensions where the states are each cell of the matrix, and the agents have four available actions at each time-step: move left, right, up, or down. There can be ”blocked” states, which can simulate a wall/object; goal states and we can add rewards to each state. The goal of the agent is to find the path that accumulates the most reward (if that is the case) or reaches a goal state avoiding blocked states along the path. This type of environment is easily scalable making it a perfect fit for this thesis. Our set of actions A={le f t,right,up,down} is basis encoded as the states A={le f t → |10⟩,right →|00⟩,up →|01⟩,down →|11⟩} . For this, we need two qubits for each step of the MDP, i.e, the horizon of each episode. In this work, we take into account the actions performed at states in the edge of the environment that lead the agent in that direction, for example, if the agent is in the bottom left entry of the grid and moves to the left, he will remain in the same state but the time step will continue. The goal state is different from the others by being the only one that offers a reward (this is not true for the 4x4Gridworld for reasons mentioned later). The minimum number of alternative sequences of actions is given by N=Ah , where A is the number of alternative actions available at each state (also referred to as the branching factor) and his the horizon (i.e., the length of the sequence of actions). It was considered that the maximum amount of reward collected at each timestep is 1leading to the possible maximum reward to be collected being given by h so that log2(h) + 1 qubits are needed to encode the reward of each sequence of actions. Another important consideration is the characteristic of the simulation. Because we are dealing with deterministic problems, the need to encode the states is removed, and only the actions are taken into account. Thereafter, the implementation uses only one register for the actions with log2(actions)∗horizon qubits and one register for the rewards with log2(h) + 1 qubits. 40 6.1.1Studied Gridworlds 2x2Grid The first case study was the 2x2Gridworld. The starting state is in the bottom left corner and the goal state is in the top right. In this case, the agent only needs 2steps to reach the end goal. However, it was simulated a horizon of three because if we only considered 2 actions, we would have a superposition of 16 quantum states. Performing the operator G25 in a superposition of 4states. If the selected states contain more than 1encoded sequence with a reward greater than the given threshold, the quantum maximum finding algorithm will not work (the amplification over the mean does not work for n=N 2 selected sequences, see 2.4.1). In this case, there are 4sequences with the maximum reward of 2,12 with reward 1, and the rest offer no reward. The total number of sequences is 43=64. Figure 8: The simulated 2x2Gridworld. In black is the starting state and in blue the goal state. 4x4Grid The last environment simulated was a GridWorld 4x4. In this case, we have two states that offer reward 1and the rest give no reward. The simulation was divided into two cases: one where the maximum reward is two and the other has a maximum reward of three. The reason is that in the first case it was intended that the reward availability was the same as in the 2x2Gridworld so that the difference in results would not interfere in the discussion; for the second case, the idea is to study the behavior with a different set of rewards. As we can conclude from the images 9and 10, for the agent to collect the desired rewards, two and three respectively, the horizon of each episode should be five resulting in a total of 45=1024 different sequences. In the case of Figure 9there are 6sequences of actions with reward two and 42 with reward 1. 41 Figure 9: The simulated 4x4Gridworld with a maximum reward of 2. In the case of Figure 10 there are 3desired rewards (reward 3), 31 with reward 2and 121 with reward 1. Figure 10: The simulated 4x4Gridworld with a maximum reward of 3. We can see that the number of solution sequences (sequences with the maximum reward) is closely the same between every simulation, however the pool of sequences from which we have to search increases from 64 in the 2x2case to 1024 in the 4x4case. 6.2 results For each of the previously described experimental environments, results are presented for different numbers of iterations of the proposed algorithm, specifically, 1to 5iterations. This algorithm is labeled as G25. Each experiment was performed 50 times. Tables 1,2and 3 present how many times (out of the 50 experiments) each possible reward was measured. The “Success rate” column presents the ratio the maximum possible reward was measured over the total number of experiments. The columns µqueries and σqueries present the average number of queries (executions of Grover’s operator) per experiment and the respective standard deviation. The row labeled with 0 refers to the original algorithm, I.e., performing the search over the total number of possible sequences of actions. Comparing the original with the G25 algorithm for the 2x2grid world (see table 1) a similar average number of queries is achieved for 3iterations of the latter. However, under these conditions, the former 42 #Iterations of G25 Reward 0Reward 1Reward 2Success µqueries σqueries 1 1 20 29 58%10 2 2 0 7 43 86%19 3 3 0 3 47 94%29 4 4 0 1 49 98%37 5 5 0 0 50 100%46 5 0 0 0 50 100%26 7 Table 1: Results for the 2x2Gridworld achieves a 100% success rate, whereas the latter succeeds at a lower rate of 94%. It is fair to conclude that in this case, the G25 algorithm provides no benefits compared to just performing a normal quantum search with the QMF. It actually is detrimental; to achieve close to 100% success rate, the results show the need for at least 4iterations which already have a higher query usage as may be seen in Figure 11. What if the search space has more sequences of actions? In the 4x4Gridworld, N=1024 and by the Qsearch algorithm the number of Grover operators (queries) to be applied can reach up to √N=32 ; adding to this, if the Qsearch does not return a solution (a sequence with reward higher than the threshold passed to the algorithm), the QMF algorithm will apply the Qsearch √N=32 times. Using the G25 operator these numbers are reduced to only 16 hopefully reducing the queries used. Figure 11: Success Rate v.s. Number of queries used for the 2x2Gridworld 43 In the table 2and figure 12 we can observe that the G25 algorithm achieves a success rate of 100% with only 3iterations and with a less average number of queries, showing some potential. G25 Iterations Reward 0Reward 1Reward 2Success µqueries σqueries 1 0 15 35 70%139 43 2 0 1 49 98%258 55 3 0 0 50 100%384 70 4 0 0 50 100%507 82 5 0 0 50 100%624 101 0 0 0 50 100%463 123 Table 2: Results for the Gridworld 4x4with a maximum reward of 2. Figure 12: Success Rate v.s. Number of queries used for the Gridworld 4x4with a maximum reward of 2. Lastly, it was simulated the same environment 4x4but where the agent can get a maximum reward of 3with 5actions. Table 3and Figure 13 show some interesting behaviour. Firstly, we see that the algorithm offers, again, no advantages. Secondly, the case where the quantum search is applied in the entire search space results in a higher standard deviation than the average meaning that in some experiments were needed a lot fewer queries, while in others this number is extremely high. Why does this happen? Recall that the QMF is iterated 3times and each iteration only terminates if a measurement retrieves a reward larger than the current threshold, otherwise, 44 G25 Iterations Reward 0Reward 1Reward 2Reward 3Success µqueries σqueries 1 0 0 26 24 48%91 52 2 0 0 10 40 80%160 69 3 0 0 6 44 88%221 82 4 0 0 4 46 92%268 87 5 0 0 1 49 98%328 98 0 0 0 0 50 100%139 185 Table 3: Results for the 4x4Gridworld with a maximum reward of 3. Figure 13: Success Rate v.s. Number of queries used for the Gridworld 4x4with a maximum reward of 3. it is performed √N searchs which can apply from 1to √N Grover operators (queries) (Remember: this number is chosen randomly and the interval grows with each iteration). The cases where a significantly low number of queries used are a result of in each iteration of the QMF was found a reward larger than the threshold, while on the other side of the spectrum, the high number of queries used are a product of the maximum reward being measured in the first iteration of the QMF causing the other 2to follow the second halt rule. Tables 5and 4show a ”dry running” of 2different experiments done without the G25 operator where, in table 5, was used a number of queries were in the low side of the spectrum because 3solutions were found (lines in bold), while, in the table 4, resulted in a high number of queries due to only 2solutions being found. Notice that the first solution is a reward of 2which means that, in the next attempts only a sequence with reward 3will halt the iteration and the last iteration of the QMF will execute the √N Qsearch evaluations. 45 BIBLIOGRAPHY [1] Vivek V. Shende and Igor L. Markov. On the CNOT-cost of TOFFOLI gates. arXiv e-prints, March 2008. [2] Keisuke Fujii. Quantum Computation with Topological Codes: from qubit to topological fault-tolerance. arXiv e-prints, April 2015. [3] Rituparna Maji, Bikash Behera, and Prasanta Panigrahi. Solving linear systems of equations by using the concept of grover’s search algorithm: An ibm quantum experience. 12 2017. [4] Lu ´ ıs Tarrataca and Andreas Wichert. Tree search and quantum computation. Quantum Information Processing,10(4):475–500, Nov 2010. [5] Lov K. Grover and Jaikumar Radhakrishnan. Is partial quantum search of a database any easier? arXiv e-prints, July 2004. [6] David J. Griffiths and Darrell F. Schroeter. Introduction to Quantum Mechanics. Cambridge University Press, 3edition, 2018. [7] D. Bacon. Decoherence, Control, and Symmetry in Quantum Computers. arXiv e-prints, May 2003. [8] Vedran Dunjko and Hans J Briegel. Machine learning & artificial intelligence in the quantum domain: a review of recent progress. jun 2018. [9] Manuel Vogel. Quantum computation and quantum information, by m.a. nielsen and i.l. chuang. Contemporary Physics - CONTEMP PHYS,52,11 2011. [10] C. Adami and N. J. Cerf. Quantum computation with linear optics. June 1998. [11] L. M. K. Vandersypen and M. A. Eriksson. Quantum computing with semiconductor spins. 60,2019. [12] T. P. Orlando, J. E. Mooij, Lin Tian, Caspar H. van der Wal, L. S. Levitov, Seth Lloyd, and J. J. Mazo. Superconducting persistent-current qubit. Physical Review B,60(22):15398–15413, Dec 1999. [13] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran. Quantum embeddings for machine learning. arXiv e-prints, January 2020. 52 [14] V.V. Shende, S.S. Bullock, and I.L. Markov. Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,25(6):1000–1010, Jun 2006. [15] Maria Schuld and Francesco Petruccione. Supervised learning with quantum computers. chapter 3. Springer Publishing Company, Incorporated, 1st edition, 2018. [16] Mikko Mottonen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa. Transformation of quantum states using uniformly controlled rotations. arXiv e-prints, July 2004. [17] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, Jun 1998. [18] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Quantum Computation and Information, page 53–74,2002. [19] Jon Bentley, Bruce Weide, and Andrew Yao. Optimal expected-time algorithms for closest point problems. ACM Trans. Math. Softw.,6:563–580,12 1980. [20] Christoph Durr and Peter Hoyer. A Quantum Algorithm for Finding the Minimum. arXiv e-prints, July 1996. [21] Ashish Ahuja and Sanjiv Kapoor. A Quantum Algorithm for finding the Maximum. arXiv e-prints, November 1999. [22] Michael N. Katehakis Apostolos N. Burnetas. Optimal adaptive policies for markov decision processes. 1997. [23] M. van Otterlo, M.; Wiering. Reinforcement learning and markov decision processes. Reinforcement Learning. Adaptation, Learning, and Optimization.2012. [24] G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; B. Bouzy. Progressive strategies for monte-carlo tree search. 2008. [25] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. 1998. [26] Warren Gilchrist. Statistical modelling with quantile functions. Chapman and Hall/CRC, 2000. 53