# Variational Quantum Circuit-Based Reinforcement Learning for POMDP and Experimental Implementation

Authors: Tomoaki Kimura; Kodai Shiba; Chih-Chieh Chen; Masaru Sogabe; Katsuyoshi Sakamoto; Tomah Sogabe
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Variational quantum circuit is proposed for applications in supervised learning and reinforcement learning to harness potential quantum advantage. However, many practical applications in robotics and time-series analysis are in partially observable environment. In this work, we propose an algorithm based on variational quantum circuits for reinforcement learning under partially observable environment. Simulations suggest learning advantage over several classical counterparts. The learned parameters are then tested on IBMQ systems to demonstrate the applicability of our approach for real-machine-based predictions.


---

## Body

## 1. Introduction

The combination of deep neural networks and reinforcement learning is demonstrated as an effective way to tackle computational problems that are difficult for other traditional approaches [1, 2]. In the usual reinforcement learning settings, the underlying model is the Markov decision process (MDP) [3, 4], where the information of environment can be completely obtained by the learning agent. However, in many real-world applications such as robotics [5], the observations are obtained from the sensors of mobile robots and hence are limited. In such cases, it is necessary to model the problem by the partially observable Markov decision process (POMDP) [6, 7]. POMDP is a framework for the environments where complete information cannot be obtained. One difficulty occurs in the POMDP in robotics setting is the perceptual aliasing problem, in which the learning agent cannot distinguish one state from another state due to the limitation of observation ability. To make proper decision under limited observation, the agent has to memorize its history to distinguish one state from the other.One traditional method for POMDP is the belief value iteration [5–7], where the agent maintains a belief distribution over possible states. The value function then becomes a functional over continuous functions and hence is computationally expensive. To deal with the computational difficulties, other methods using Monte Carlo [5, 8] and recurrent neural network [9, 10] have been proposed. These methods are difficult to execute without a sufficient computing capacity and memory. Complex-valued reinforcement learning has been proposed as a POMDP algorithm that can be executed with less computational resources [11]. In complex-valued reinforcement learning, the action value function gives a complex number, and there is another complex number internal reference vector that represents time series information. Tables [11, 12] and neural networks [13, 14] have been used to express complex action value functions. However, expressing correlated complex numbers using a classical computer is not considered to be a good choice from the viewpoint of memory efficiency. On the other hand, since quantum computers perform calculations over Hilbert space, it is reasonable to think that quantum processors can be used to represent complex-valued functions efficiently. If the abovementioned complex action value function can be expressed by a quantum computer, it may become a more memory efficient POMDP learning method.In this work, we propose a method for performing complex-valued reinforcement learning by expressing a complex action value function using a quantum computer. Previous works apply current quantum hardware [15] for supervised machine learning using the variational quantum circuit method [16–18]. The applications of variational quantum circuit to the value function in reinforcement learning problem are also demonstrated [19–22]. Some works use classical-quantum hybrid model to solve large problems [23, 24]. Other works use variational quantum circuit to represent policy in reinforcement learning [25, 26]. Variational quantum circuit is also applied to represent both policy and value function in actor-critic method [27]. Quantum algorithms are also applied to sampling from policy in deep energy-based reinforcement learning [28]. These quantum algorithms for reinforcement learning are based on MDP. We implement the variational quantum circuit for complex-valued action value function approximation and compare the performance against other methods like complex neural networks. The learning performance shows advantage over some other classical methods. We further use the parameters learned from simulation for predictions with IBMQ systems. The agent is able to reach the goal state with the predictions made by IBM machines. This discovery suggests that the use of variational quantum circuit for POMDP provides possible advantage.This paper is organized as follows. Background section introduces the concept of POMDP. In Methods section, variational quantum circuit and neural network are applied for complex-valued Q-learning. In Results and Discussion section, partially observable maze environment experiment results are shown. Conclusions section describes conclusion and future work.


### 1.1. Background

POMDP is a general framework for planning in the environments where perfect information cannot be gotten. In POMDP, the agent cannot fully observe the state but instead receives an observation from the environment, and the observation does not satisfy Markov property. A POMDP is defined as a tupleS,A,T,R,Ω,O,γ. S is the set of states. A is the set of actions. T is the state transition probability. R is the reward function. Ω is the set of observations. O is the observation probability. γ is the discount rate.When the agent executes an actiona in the environment, the state transitions from a state s to a next state s′ according to the state transition probability T=Prs′|s,a and the agent receives an observation o from the environment according to the observation probability O=Pro|s′,a and a reward r according to the reward function Rs,a. The history ht is the time series of actions and observations and is expressed as ht=a0,o1,a1,o2,…,at−1,ot. As the agent cannot fully observe state, it uses the belief state, which is the probability distribution that represents in which states the agent is. Belief state B is denoted by Bs,h=Prs|h, and it can be updated by the following formula:(1)Bs′,hao=∑sPro|s′,aPrs′|s,aBs,h∑s∑s″Pro|s″,aPrs″|s,aBs,h.The agent's policy is denoted byπh,a=Pra|h or πb,a=Pra|b. The purpose of the agent is to get a policy π∗ that maximizes the expected total reward Eπ∑i=tTγi−tri.There are two types of methods for planning POMDP. One method is based on value iteration method [7, 29]. This type of method updates the belief state and value function using a model. Belief state is updated by equation (1), and value function is updated by updating the set of alpha vectors. Another method is the method using a black box simulator [8]. Black box simulator is a model that receives state and action and returns next state, observation, and reward. This method executes Monte Carlo tree search and Monte Carlo update of belief state using this simulator. Although these two planning methods use model or black box model, as normally model is not given to the agent, algorithms learning model or algorithms not using model are needed. The former is model-based method, and the latter is model-free method.Model-based methods inference the model and then execute planning using the learned model. To learn the model, Bayesian method [30, 31] and nonparametric approach [32] are proposed. Model-free methods are RNN method [9, 10, 33], complex-valued reinforcement learning [11–13], etc. These methods do not use belief state but incorporate time series information directly into the value function. In this paper, we focus on the model-free method especially complex-valued reinforcement learning.


## 1.1. Background

POMDP is a general framework for planning in the environments where perfect information cannot be gotten. In POMDP, the agent cannot fully observe the state but instead receives an observation from the environment, and the observation does not satisfy Markov property. A POMDP is defined as a tupleS,A,T,R,Ω,O,γ. S is the set of states. A is the set of actions. T is the state transition probability. R is the reward function. Ω is the set of observations. O is the observation probability. γ is the discount rate.When the agent executes an actiona in the environment, the state transitions from a state s to a next state s′ according to the state transition probability T=Prs′|s,a and the agent receives an observation o from the environment according to the observation probability O=Pro|s′,a and a reward r according to the reward function Rs,a. The history ht is the time series of actions and observations and is expressed as ht=a0,o1,a1,o2,…,at−1,ot. As the agent cannot fully observe state, it uses the belief state, which is the probability distribution that represents in which states the agent is. Belief state B is denoted by Bs,h=Prs|h, and it can be updated by the following formula:(1)Bs′,hao=∑sPro|s′,aPrs′|s,aBs,h∑s∑s″Pro|s″,aPrs″|s,aBs,h.The agent's policy is denoted byπh,a=Pra|h or πb,a=Pra|b. The purpose of the agent is to get a policy π∗ that maximizes the expected total reward Eπ∑i=tTγi−tri.There are two types of methods for planning POMDP. One method is based on value iteration method [7, 29]. This type of method updates the belief state and value function using a model. Belief state is updated by equation (1), and value function is updated by updating the set of alpha vectors. Another method is the method using a black box simulator [8]. Black box simulator is a model that receives state and action and returns next state, observation, and reward. This method executes Monte Carlo tree search and Monte Carlo update of belief state using this simulator. Although these two planning methods use model or black box model, as normally model is not given to the agent, algorithms learning model or algorithms not using model are needed. The former is model-based method, and the latter is model-free method.Model-based methods inference the model and then execute planning using the learned model. To learn the model, Bayesian method [30, 31] and nonparametric approach [32] are proposed. Model-free methods are RNN method [9, 10, 33], complex-valued reinforcement learning [11–13], etc. These methods do not use belief state but incorporate time series information directly into the value function. In this paper, we focus on the model-free method especially complex-valued reinforcement learning.


## 2. Methods

### 2.1. Complex-Valued Q-Learning for POMDP

A POMDP problem that we are interested in here can be described by a tupleS,A,T,R,Ω,O,γ. S is a discrete set of states. A is a discrete set of actions. Ts′|s,a is a state transition probability matrix for s,s′∈S and a∈A. Rs,a is a reward function for s∈S and a∈A. Ω is a discrete set of observations. Oo|s,a is an observation probability matrix for o∈Ω, s∈S, and a∈A. γ∈0,1 is the discount rate. In the examples in this work, both the state transition and the observation are deterministic. We look for a policy for which the expected future cumulative reward is optimized. The policy can be derived from the action value Q-function in Q-learning.Complex-valued Q-learning is based on the iteration:(2)Q˙ot,at←1−αQ˙ot,at+αrt+1+γQ˙maxtβ˙,where Q˙ is the complex-valued observation-action value function. The dot notation X˙ for some quantity X is used throughout the manuscript to remind us that the quantity is complex-valued. ot and at are the observation and action at time t, respectively. The learning rate α∈0,1 is a real number. The reward rt is a real number. γ∈0,1 is the discounted rate, which is a real number. β˙=eiω is a complex hyperparameter for some real constant ω. Q˙maxt is defined as(3)Q˙maxt=Q˙ot+1,a,a=argmaxa′∈AℜQ˙ot+1,a′I˙¯t,I˙t=Q˙ot,atβ˙.Here,I˙¯t means the complex conjugation of I˙t. ℜ denotes taking the real part of a complex number. The learned time series is reproduced by updating each complex number in the opposite phase direction. An eligibility trace method is further implemented such that the action value function is updated according to(4)Q˙ot−k,at−k←1−αQ˙ot−k,at−k+αrt+1+γQ˙maxtu˙tk,where u˙tk=β˙k+1 for 0≤k<Ne and Ne is the trace length. This update rule is exact for the table where the complete Q˙-table must be stored in the memory. In the variational approaches, the Q˙ function is variationally optimized by minimizing the functional:(5)Lθ=12Q˙ot−k,at−k−rt+1+γQ˙maxtu˙tk2,with gradient descent θ←θ−α∂L/∂θ. Finally, the policy is the Boltzmann stochastic policy:(6)πot,a=ExpℜQ˙ot,aI˙¯t−1/T∑aExpℜQ˙ot,aI˙¯t−1/T,where T is a temperature hyperparameter.


### 2.2. Variational Quantum Circuit for Q-Function

TheQ˙ function is constructed by the expectation value:(7)Q˙θo,a=γQ0Uencoderθino,a†Wθ†Uoutθout,aWθUencoderθino,a0=γQψoutθ,θino,aUoutθout,aψoutθ,θino,a.where γQ is a scaling constant. θ is the set of trainable variational parameters for trainable unitary Wθ=∏i=1lUθl−i+1UentUθ0. The quantity l+1 will be called the circuit depth. θino,a is a set of input parameters which encode the observation o and action a. θino,a parameterizes the input layer local unitaries. Uoutθout,a is an output unitary to be measured by Hadamard test [34] against the output wave function ψout. Uoutθout,a is parameterized by some trainable θout and the action a. The circuit structure is depicted in Figure 1. We implement three types of encoding schemes, which are summarized in the following paragraphs.Figure 1
The variational quantum circuit. (a) The variational circuit. The encoder encodes action and observation with parametersθin. The output state of the circuit ψout will be measured against the output unitary to approximate the Q˙ function. (b) Trainable local unitaries. (c) The entangler. (d) The Hadamard test for output measurement.In Type 1 and Type 3 quantum circuits, the input layer isUencoder=⊗i=0n−1RZθinZRYθinY, where the index i means the local rotation is acting on i-th qubit. The parameters θinZ and θinY are uniform for all the qubits (independent of qubit index i). For Type 1 circuit, the encoding is θinY=sin−1o¯ and θinZ=cos−1o¯2, where o¯=2o−mino/maxo−mino−1 is the rescaled observation.For Type 3 circuit, the encoding isθinY=sin−1o¯ and θinZ=cos−1a¯, where a¯=2a−mina/maxa−mina−1. In Type 2 quantum circuit, the input layer is Uencoder=⊗i=0n−1RZθi,inZRXθi,inX, where the subscript i means the local rotation is acting on i-th qubit. The encoding is done by binary representation of observation o=b0b1b2b3 for binary numbers bi∈0,1. The observation is then encoded as state b0b1b2b3 with some phase factors by choosing θi,inZ=πbi and θi,inX=πbi.For the output unitary, Type 3 usesUoutθout=⊗i=0n−1RZθi,outZRYθi,outYRZθi,outZ′, where the subscript i means the local rotation is acting on i-th qubit. All the θi,outZ′, θi,outY, and θi,outZ are trainable. For Type 1 and Type 2, we use Uoutθout,a=⊗i∈0,a+1RZθi,a,outZRYθi,a,outYRZθi,a,outZ′ for an action a∈A. Figure 2 depicts the quantum circuits encoding used in this work.Figure 2
Three types of input encoders and output operators used in our experiments. In Type 1 circuit, the observation is encoded in the encoder, and the action is encoded by the output unitary. In Type 2 circuit, the observation is encoded in the encoder by binary state representation, and the action is encoded by the output unitary. In Type 3 circuit, both the observation and the action are encoded in the encoder.All circuit parameters are updated by gradient descent with loss function (5). The gradient of this loss function with respect to each parameter is calculated by the back propagation method on a classical simulator. As quantum circuit calculates the output state by the dot product of the gate matrix and the input state, this calculation is a special case of complex-valued neural networks. Therefore, back propagation method of complex-valued neural networks [35] can be used in the back propagation of quantum circuit.The gradient of loss function (5) with respect to Q˙ function is calculated by(8)∂Lθ∂Q˙θot−k,at−k=Q˙θot−k,at−k−Q˙Target,where Q˙Target=rt+1+γQ˙maxtu˙tk.Using the definitionψout′θout=Uoutθout,at−kψoutθ,θinot−k,at−k, the gradient calculation of expectation value (7) is as follows:(9)∂Lθ∂ψout′θout=∂Lθ∂Q˙θot−k,at−kγQ¯ψoutθ,θinot−k,at−k,∂Lθ∂ψoutθ,θinot−k,at−k=∂Lθ∂Q˙θot−k,at−kγQ¯Uoutθout,at−k†ψoutθ,θinot−k,at−k+∂Lθ∂Q˙θot−k,at−k¯γQψout′θout.Here, gradient∂Lθ/∂Q˙θot−k,at−k is gotten by equation (8). Figure 3(a) shows this gradient calculation. The gradients of output ψout′θout and ψoutθ,θinot−k,at−k are gotten. As the output ψout′θout is gotten by applying some gates with parameters θout to input ψoutθ,θinot−k,at−k, the gradient of the parameters θout are gotten by back propagating ∂Lθ/∂ψout′θout. Similarly, as the output ψoutθ,θinot−k,at−k is gotten by applying some gates with parameters θ to input Uencoderθinot−k,at−k0, the gradient of the parameters θ are calculated by back propagating ∂Lθ/∂ψoutθ,θinot−k,at−k. These back propagations are the almost same as the calculation of neural network back propagation, but using the quantum gates is different point. When a gate uϑ with parameter ϑ is applied to input ψi, the output ψo is gotten by |ψo=Uϑψi, where Uϑ is the transformed matrix from gate matrix uϑ to calculate the inner product. The gradient is gotten by(10)∂L∂Uϑ=∂L∂ψo⋅ψi¯T,∂L∂ψi=Uϑ¯T⋅∂L∂ψo,where ∂L/∂ψo is the gradient of loss function L with respect to the output ψo. The gradient with respect to parameter ϑ is calculated by(11)∂L∂ϑ=ℜ∑∂L∂|ψo⋅ψi¯Tij∂Uϑij∂ϑ,where Mij represents the i,j element of the matrix M. Figure 3(b) shows the back propagation of the gate calculation. The gradient of loss with respect to the last output is back propagated by equation (10), and parameters are updated by gradient of equation (11).Figure 3
Back propagation for circuit parameters update. Black line is feed forward calculation, and blue line is back propagation. (a) Back propagation of expectation value calculation. The gradients with respect toψout and ψout′ are calculated. The former gradient is back propagated to update θ, and the latter is back propagated to update θout. (b) Back propagation of calculation applying a quantum gate. The calculation of applying a gate uϑ to 0-th qubit is shown. The gradient with respect to ψi is then back propagated to the previous gate calculation.
(a)(b)


### 2.3. Neural Networks

For experimental comparison, we also implement complex-valued neural networks. The detail for the architecture of the neural networks is presented in this section. We use two types of neural networks for experiments. For both Type 1 and Type 2 neural networks, there are 3 layers: one input layer, one hidden layer, and one output layer. In Type 1 neural network, there are two input layer neurons and one output layer neuron. Both the actiona and the observation o are encoded in the input layer neurons. The output neuron then gives Q˙o,a. In Type 2 neural network, there is one input neuron and A output neurons. Only the observation o is encoded in the input layer neuron. Each output neuron then gives Q˙o,a for an action a. For both Type 1 and Type 2 neural networks, there is one hidden layer, and there are 30 neurons in the hidden layer. The networks are depicted in Figure 4. We use the learning rate 0.0001 for the hidden layer and 0.001 for the output layer. We defined the architecture type 1 based on the paper [13] and the architecture type 2 for comparison. We update the parameters by gradient descent using back propagation [35]. In complex-valued neural networks, fully connected layer is calculated by(12)z=fco,o=W⋅x+b.where x is the input vector. W is the weight matrix. b is the bias vector. o is the weighted sum of input. z is the output vector. They are all complex numbers. fcv is the activation function for complex numbers and defined by(13)fcv=fℜv+ifℑv,where fu is activation function for real numbers.Figure 4
Neural networks for the experiments. In Type 1 neural network, both the action and the observation are encoded through the input layer. In Type 2 neural network, only the observation is encoded in the input layer, and the value ofQ˙o,a is given by one output neuron for each action a.Back propagation equation to calculate gradient of loss functionL is(14)∂L∂o=ℜ∂L∂z∂ℜz∂ℜo+i∂ℜz∂ℑo+ℑ∂L∂z∂ℑz∂ℜo+i∂ℑz∂ℑo,∂L∂W=∂L∂o⋅x¯T,∂L∂b=∂L∂o,∂L∂x=W¯T⋅∂L∂o,where a¯ means the complex conjugation of a. ∂L/∂z is the gradient of loss L with respect to output vector z of this layer. The parameters are updated by gradient descent using these gradients.


### 2.4. The Maze Environment

The partially observable maze environment used in our experiments is depicted in Figure5. We defined the environment with reference to the maze environments of the paper [11, 12]. In particular, the structure is the same as in the maze of the paper [12]. Each cell in the maze represents a possible state. The agent starts from the start state and aims for the goal state. There are four possible actions A=⟶,←,↑,↓=0,1,2,3. The wall of the maze is represented by cells in dark gray color. If the agent executes an action which makes the agent hitting the wall, the agent's state is not transitioned. The numbers in cells are the observations Ω=1,2,3,4,5,6,7,8,9,10,11. The cells painted in the same color are different states with the same observation (except for the white color). The reward is +100 if the agent reaches the goal state, and 0 otherwise. Each episode ends either if the agent reaches the goal state, or the number of time steps reaches a maximum value.Figure 5
The partially observable maze environment. This is a 2D maze with 4 possible moving directions. Each cell denotes on possible state (location). The dark cells denote the wall which is not available to the agent. A number (and a color) in a cell denotes the corresponding observation received by the agent at that state. The start state and goal state are indicated.


## 2.1. Complex-Valued Q-Learning for POMDP

A POMDP problem that we are interested in here can be described by a tupleS,A,T,R,Ω,O,γ. S is a discrete set of states. A is a discrete set of actions. Ts′|s,a is a state transition probability matrix for s,s′∈S and a∈A. Rs,a is a reward function for s∈S and a∈A. Ω is a discrete set of observations. Oo|s,a is an observation probability matrix for o∈Ω, s∈S, and a∈A. γ∈0,1 is the discount rate. In the examples in this work, both the state transition and the observation are deterministic. We look for a policy for which the expected future cumulative reward is optimized. The policy can be derived from the action value Q-function in Q-learning.Complex-valued Q-learning is based on the iteration:(2)Q˙ot,at←1−αQ˙ot,at+αrt+1+γQ˙maxtβ˙,where Q˙ is the complex-valued observation-action value function. The dot notation X˙ for some quantity X is used throughout the manuscript to remind us that the quantity is complex-valued. ot and at are the observation and action at time t, respectively. The learning rate α∈0,1 is a real number. The reward rt is a real number. γ∈0,1 is the discounted rate, which is a real number. β˙=eiω is a complex hyperparameter for some real constant ω. Q˙maxt is defined as(3)Q˙maxt=Q˙ot+1,a,a=argmaxa′∈AℜQ˙ot+1,a′I˙¯t,I˙t=Q˙ot,atβ˙.Here,I˙¯t means the complex conjugation of I˙t. ℜ denotes taking the real part of a complex number. The learned time series is reproduced by updating each complex number in the opposite phase direction. An eligibility trace method is further implemented such that the action value function is updated according to(4)Q˙ot−k,at−k←1−αQ˙ot−k,at−k+αrt+1+γQ˙maxtu˙tk,where u˙tk=β˙k+1 for 0≤k<Ne and Ne is the trace length. This update rule is exact for the table where the complete Q˙-table must be stored in the memory. In the variational approaches, the Q˙ function is variationally optimized by minimizing the functional:(5)Lθ=12Q˙ot−k,at−k−rt+1+γQ˙maxtu˙tk2,with gradient descent θ←θ−α∂L/∂θ. Finally, the policy is the Boltzmann stochastic policy:(6)πot,a=ExpℜQ˙ot,aI˙¯t−1/T∑aExpℜQ˙ot,aI˙¯t−1/T,where T is a temperature hyperparameter.


## 2.2. Variational Quantum Circuit for Q-Function

TheQ˙ function is constructed by the expectation value:(7)Q˙θo,a=γQ0Uencoderθino,a†Wθ†Uoutθout,aWθUencoderθino,a0=γQψoutθ,θino,aUoutθout,aψoutθ,θino,a.where γQ is a scaling constant. θ is the set of trainable variational parameters for trainable unitary Wθ=∏i=1lUθl−i+1UentUθ0. The quantity l+1 will be called the circuit depth. θino,a is a set of input parameters which encode the observation o and action a. θino,a parameterizes the input layer local unitaries. Uoutθout,a is an output unitary to be measured by Hadamard test [34] against the output wave function ψout. Uoutθout,a is parameterized by some trainable θout and the action a. The circuit structure is depicted in Figure 1. We implement three types of encoding schemes, which are summarized in the following paragraphs.Figure 1
The variational quantum circuit. (a) The variational circuit. The encoder encodes action and observation with parametersθin. The output state of the circuit ψout will be measured against the output unitary to approximate the Q˙ function. (b) Trainable local unitaries. (c) The entangler. (d) The Hadamard test for output measurement.In Type 1 and Type 3 quantum circuits, the input layer isUencoder=⊗i=0n−1RZθinZRYθinY, where the index i means the local rotation is acting on i-th qubit. The parameters θinZ and θinY are uniform for all the qubits (independent of qubit index i). For Type 1 circuit, the encoding is θinY=sin−1o¯ and θinZ=cos−1o¯2, where o¯=2o−mino/maxo−mino−1 is the rescaled observation.For Type 3 circuit, the encoding isθinY=sin−1o¯ and θinZ=cos−1a¯, where a¯=2a−mina/maxa−mina−1. In Type 2 quantum circuit, the input layer is Uencoder=⊗i=0n−1RZθi,inZRXθi,inX, where the subscript i means the local rotation is acting on i-th qubit. The encoding is done by binary representation of observation o=b0b1b2b3 for binary numbers bi∈0,1. The observation is then encoded as state b0b1b2b3 with some phase factors by choosing θi,inZ=πbi and θi,inX=πbi.For the output unitary, Type 3 usesUoutθout=⊗i=0n−1RZθi,outZRYθi,outYRZθi,outZ′, where the subscript i means the local rotation is acting on i-th qubit. All the θi,outZ′, θi,outY, and θi,outZ are trainable. For Type 1 and Type 2, we use Uoutθout,a=⊗i∈0,a+1RZθi,a,outZRYθi,a,outYRZθi,a,outZ′ for an action a∈A. Figure 2 depicts the quantum circuits encoding used in this work.Figure 2
Three types of input encoders and output operators used in our experiments. In Type 1 circuit, the observation is encoded in the encoder, and the action is encoded by the output unitary. In Type 2 circuit, the observation is encoded in the encoder by binary state representation, and the action is encoded by the output unitary. In Type 3 circuit, both the observation and the action are encoded in the encoder.All circuit parameters are updated by gradient descent with loss function (5). The gradient of this loss function with respect to each parameter is calculated by the back propagation method on a classical simulator. As quantum circuit calculates the output state by the dot product of the gate matrix and the input state, this calculation is a special case of complex-valued neural networks. Therefore, back propagation method of complex-valued neural networks [35] can be used in the back propagation of quantum circuit.The gradient of loss function (5) with respect to Q˙ function is calculated by(8)∂Lθ∂Q˙θot−k,at−k=Q˙θot−k,at−k−Q˙Target,where Q˙Target=rt+1+γQ˙maxtu˙tk.Using the definitionψout′θout=Uoutθout,at−kψoutθ,θinot−k,at−k, the gradient calculation of expectation value (7) is as follows:(9)∂Lθ∂ψout′θout=∂Lθ∂Q˙θot−k,at−kγQ¯ψoutθ,θinot−k,at−k,∂Lθ∂ψoutθ,θinot−k,at−k=∂Lθ∂Q˙θot−k,at−kγQ¯Uoutθout,at−k†ψoutθ,θinot−k,at−k+∂Lθ∂Q˙θot−k,at−k¯γQψout′θout.Here, gradient∂Lθ/∂Q˙θot−k,at−k is gotten by equation (8). Figure 3(a) shows this gradient calculation. The gradients of output ψout′θout and ψoutθ,θinot−k,at−k are gotten. As the output ψout′θout is gotten by applying some gates with parameters θout to input ψoutθ,θinot−k,at−k, the gradient of the parameters θout are gotten by back propagating ∂Lθ/∂ψout′θout. Similarly, as the output ψoutθ,θinot−k,at−k is gotten by applying some gates with parameters θ to input Uencoderθinot−k,at−k0, the gradient of the parameters θ are calculated by back propagating ∂Lθ/∂ψoutθ,θinot−k,at−k. These back propagations are the almost same as the calculation of neural network back propagation, but using the quantum gates is different point. When a gate uϑ with parameter ϑ is applied to input ψi, the output ψo is gotten by |ψo=Uϑψi, where Uϑ is the transformed matrix from gate matrix uϑ to calculate the inner product. The gradient is gotten by(10)∂L∂Uϑ=∂L∂ψo⋅ψi¯T,∂L∂ψi=Uϑ¯T⋅∂L∂ψo,where ∂L/∂ψo is the gradient of loss function L with respect to the output ψo. The gradient with respect to parameter ϑ is calculated by(11)∂L∂ϑ=ℜ∑∂L∂|ψo⋅ψi¯Tij∂Uϑij∂ϑ,where Mij represents the i,j element of the matrix M. Figure 3(b) shows the back propagation of the gate calculation. The gradient of loss with respect to the last output is back propagated by equation (10), and parameters are updated by gradient of equation (11).Figure 3
Back propagation for circuit parameters update. Black line is feed forward calculation, and blue line is back propagation. (a) Back propagation of expectation value calculation. The gradients with respect toψout and ψout′ are calculated. The former gradient is back propagated to update θ, and the latter is back propagated to update θout. (b) Back propagation of calculation applying a quantum gate. The calculation of applying a gate uϑ to 0-th qubit is shown. The gradient with respect to ψi is then back propagated to the previous gate calculation.
(a)(b)


## 2.3. Neural Networks

For experimental comparison, we also implement complex-valued neural networks. The detail for the architecture of the neural networks is presented in this section. We use two types of neural networks for experiments. For both Type 1 and Type 2 neural networks, there are 3 layers: one input layer, one hidden layer, and one output layer. In Type 1 neural network, there are two input layer neurons and one output layer neuron. Both the actiona and the observation o are encoded in the input layer neurons. The output neuron then gives Q˙o,a. In Type 2 neural network, there is one input neuron and A output neurons. Only the observation o is encoded in the input layer neuron. Each output neuron then gives Q˙o,a for an action a. For both Type 1 and Type 2 neural networks, there is one hidden layer, and there are 30 neurons in the hidden layer. The networks are depicted in Figure 4. We use the learning rate 0.0001 for the hidden layer and 0.001 for the output layer. We defined the architecture type 1 based on the paper [13] and the architecture type 2 for comparison. We update the parameters by gradient descent using back propagation [35]. In complex-valued neural networks, fully connected layer is calculated by(12)z=fco,o=W⋅x+b.where x is the input vector. W is the weight matrix. b is the bias vector. o is the weighted sum of input. z is the output vector. They are all complex numbers. fcv is the activation function for complex numbers and defined by(13)fcv=fℜv+ifℑv,where fu is activation function for real numbers.Figure 4
Neural networks for the experiments. In Type 1 neural network, both the action and the observation are encoded through the input layer. In Type 2 neural network, only the observation is encoded in the input layer, and the value ofQ˙o,a is given by one output neuron for each action a.Back propagation equation to calculate gradient of loss functionL is(14)∂L∂o=ℜ∂L∂z∂ℜz∂ℜo+i∂ℜz∂ℑo+ℑ∂L∂z∂ℑz∂ℜo+i∂ℑz∂ℑo,∂L∂W=∂L∂o⋅x¯T,∂L∂b=∂L∂o,∂L∂x=W¯T⋅∂L∂o,where a¯ means the complex conjugation of a. ∂L/∂z is the gradient of loss L with respect to output vector z of this layer. The parameters are updated by gradient descent using these gradients.


## 2.4. The Maze Environment

The partially observable maze environment used in our experiments is depicted in Figure5. We defined the environment with reference to the maze environments of the paper [11, 12]. In particular, the structure is the same as in the maze of the paper [12]. Each cell in the maze represents a possible state. The agent starts from the start state and aims for the goal state. There are four possible actions A=⟶,←,↑,↓=0,1,2,3. The wall of the maze is represented by cells in dark gray color. If the agent executes an action which makes the agent hitting the wall, the agent's state is not transitioned. The numbers in cells are the observations Ω=1,2,3,4,5,6,7,8,9,10,11. The cells painted in the same color are different states with the same observation (except for the white color). The reward is +100 if the agent reaches the goal state, and 0 otherwise. Each episode ends either if the agent reaches the goal state, or the number of time steps reaches a maximum value.Figure 5
The partially observable maze environment. This is a 2D maze with 4 possible moving directions. Each cell denotes on possible state (location). The dark cells denote the wall which is not available to the agent. A number (and a color) in a cell denotes the corresponding observation received by the agent at that state. The start state and goal state are indicated.


## 3. Results and Discussion

We perform numerical simulations to compare the learning curves of different approaches. Figure6(a) shows the learning curves for Q˙-table (blue solid line with circle marker), complex neural networks (orange solid line and green dashed line), quantum circuit (red dotted line, purple dashed-dotted line, and brown solid line with “+” cross marker), and long short-term memory (LSTM, pink solid line with “x” cross marker). The vertical axis is the number of steps to the goal, so lower value means a better policy. The data is the average of 50 independent runs. Each episode has maximum number of steps 1000. The total number of episodes is 5000, and the data is further smoothed out by taking average over 500 sequential episodes. In all the Q˙ learning experiments, the trace length is Ne=6. For LSTM, the history sequence length is 6. All the quantum circuits are using 6 qubits with depth = 3. All the neural networks have one hidden layer consisting of 30 neurons. We observe that the Q˙-table method has the most stable learning curve, and the learned policy is able to reach the goal with lower number of steps. This is expected since Q˙-table does not use any approximation in the representation of Q˙-function. Type 3 quantum circuit gives bad result, where the learned policy does not really improve the reaching time to the goal. The performance of Type 1 quantum circuits is not significantly different comparing to other classical complex neural network approaches. We note that Type 2 quantum circuit provides the best result among all the Q˙ approximation schemes. It is even better than LSTM approach in our experiments.Figure 6
Learning curves comparison for different algorithms and different trace numbers from simulation. The data is the average of 50 independent runs, and the data is smoothed out by taking average over 500 sequential episodes. (a) Comparison for different algorithms. Blue solid line with circle marker isQ˙-table. Orange solid lines are Type 1 neural network. Green dashed line is Type 2 neural network. Red dotted line is Type 1 quantum circuit. Purple dashed-dotted line is Type 2 quantum circuit. Brown solid line with “+” marker is Type 3 quantum circuit. Pink solid line with “x” marker is LSTM. We observe that Type 2 quantum circuit provides the second-best performance. (b) Comparison for different trace number for Type 2 quantum circuit. Blue solid line with circle marker, orange solid line, green dashed line, red dotted line, purple dashed-dotted line, and brown solid line with cross marker correspond to trace number 1, 2, 4, 6, 8, and 10, respectively. We observe better performance for trace number around Ne=6.
(a)(b)We compare the results for various hyperparameters. Figure6(b) shows the learning curves for Type 2 quantum circuit with different trace number. We observe that the performance could be improved by using trace number 4 (green dashed line) rather than trace number 1 (blue solid line with circle marker) or 2 (orange solid line). However, the performance of trace number 10 (brown solid line with cross marker) is not good either. We observe the best learning curves for the trace number Ne around 6 (red dotted line).Since the best performance could be obtained by Type 2 circuit with trace number around 6, we then fix the circuit type to Type 2 and trace number to 6 and compare the learning curves for different widths and depths. Figure7(a) shows the learning curves for various circuit depths. It is observed that the learning curve could be improved by increasing circuit depth from 1 (blue solid line), 2 (orange dashed line), 3 (green dotted line), to 4 (red solid line with circle marker) for n=6. Figure 7(b) shows the learning curves for various circuit widths with fixed circuit depth = 4. We observe that higher circuit width makes the learning task more difficult. The learning curve for n=5 (blue solid line) is better than that of n=6 (orange dashed line) and n=7 (green dotted line).Figure 7
Learning curves comparison for different circuit widths and depths. The data is the average of 50 independent runs, and the data is smoothed out by taking average over 500 sequential episodes. (a) Comparison of different circuit depths for Type 2 quantum circuit withn=6. Blue solid line, orange dashed line, green dotted line, and red solid line with circle marker are lines for depth = 1, 2, 3, 4, respectively. (b) Comparison of different circuit widths for Type 2 quantum circuit, depth = 4. Blue solid line, orange dashed line, and green dotted line are lines for n=5,6,7, respectively.
(a)(b)We then take an offline learning scheme to compare prediction performances of different machines. That is, the parameters are obtained from state-vector simulator-based training process, and the predictions are done using various different methods. The test results are depicted in Figure8. We test the predictions by using a Numpy-based state-vector simulator [36], the QASM simulator provided by Qiskit [37], and the IBMQ system ibmq_guadalupe [38]. The horizontal axis “episode” indicates the number of episodes for training. Hence, episodes = 1000 means that 1000 episodes training is performed, and then the learned parameters are used for the corresponding prediction experiment. Each data point is the average of 5000 runs. The 5000 runs are conducted by 50 independently learned parameters, and for each learning, there are 100 prediction experiments. The number of shots for Hadamard-test estimation is 4096 for the QASM simulator. The quantum circuit type is Type 2. The number of qubits is 5, and circuit depth is 4. The trace number is 6. For the IBM Q system, a set of parameters trained with 5000 episodes is used for a prediction experiment. The number of shots is 1024. Five experiments are executed, and the number of steps to reach the target state is 67 steps, 1000 steps, 502 steps, 1000 steps, and 1000 steps, respectively. Since the maximum number of steps is 1000, “1000 steps” means that the agent does not reach the target in the experiment.Figure 8
Prediction test results using different prediction methods with state-vector simulator-based offline training. The blue-solid line is the result predicted by the state-vector simulator, while the orange-dashed line is the prediction result given by Qiskit QASM simulator with 4096 shots.


## 4. Conclusions

In this work, we propose the quantum circuit algorithm for POMDP based on the complex-valued Q learning. We implemented several encoding schemes and compare them to other classical approaches by numerical simulations. The observed learning curve suggests that, with suitable encoding, the learning efficiency of quantum complex-valued Q learning can be better than other classical methods like complex-valued neural networks. The performance of quantum circuit can be further improved by suitable choice of hyper-parameters. The learned parameters from simulators are then tested with IBMQ systems. The agent is able to reach the goal state with predictions made by real quantum machines. Our results provide a new method for POMDP problems with potential quantum advantage. The partially observable maze environment experiment executed in this work is a discrete state environment. For future works, our proposed method could be applied to the other simulation problems, such as partially observable continuous space environment Mountain Car [4, 39]. Since the encoding scheme showing better result in this work is only used for discrete space, to solve continuous problem without discretization, another new encoding scheme for continuous environment will be needed.



---

*Source: 3511029-2021-12-23.xml*