Quantum reinforcement learning: foundations, algorithms, applications

Universidade do Minho Escola de Engenharia André Sequeira Quantum Reinforcement Learning: Foundations, algorithms, applications January, 2025 Quantum Reinforcement Learning: Foundations, algorithms, applications André Sequeira UMinho |2025 ii Universidade do Minho Escola de Engenharia André Sequeira Quantum Reinforcement Learning: Foundations, algorithms, applications Doctorate Thesis Doctorate in Informatics (PDInf) Work developed under the supervision of: Luis Paulo Santos January, 2025 COPYRIGHT AND TERMS OF USE OF THIS WORK BY A THIRD PARTY This is academic work that can be used by third parties as long as internationally accepted rules and good practices regarding copyright and related rights are respected. Accordingly, this work may be used under the license provided below. If the user needs permission to make use of the work under conditions not provided for in the indicated licensing, they should contact the author through the RepositoriUM of Universidade do Minho. License granted to the users of this work Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International CC BY-NC-SA 4.0 https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en This document was created with the (pdf/Xe/Lua)L A T EX processor and the NOVAthesis template (v7.1.18) [120]. ii Acknowledgements Completing the PhD has been an incredible journey, one that I could not have navigated alone. I am deeply indebted to many individuals whose support and encouragement have been essential throughout this process. First and foremost, I would like to express my profound gratitude to my supervisors, Professor Luis Paulo Santos and Professor Luis Soares Barbosa. Luis Paulo, you have been more than just a supervisor; you have been a true friend. Your guidance, wisdom, and unwavering support have been invaluable and changed me forever. Luis Barbosa, your insightful feedback and mentorship have greatly enriched my research, and I am deeply thankful for your support and belief in my potential. To my family, your love and support have been the foundation upon which this journey has been built. To my parents, thank you for your unwavering belief in me and for the countless sacrifices you’ve made to help me achieve my dreams. To my brother, your humor and the countless laughs you provided were a breath of fresh air during most challenging times. A heartfelt thank you to Rita, my love and best friend. Your kindness, patience, and constant support have been my anchor through the ups and downs for many years. You kept reminded me of the importance of balance in life, pulling me out of so many moments of internal turmoil. I also want to thank all my friends who walked this journey with me. Sharing this experience with you felt like being cellmates in the PhD prison—serving time together, plotting our escape, and making the hard days just a bit more bearable with humor and camaraderie. Lastly, I would like also to acknowledge my institutions, the University of Minho and the High-Assurance Software Laboratory - HASLAB INESCTEC. Thank you for providing me with all the necessary conditions to sucessfully complete this thesis. This work is partially financed by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project UIDB/50014/2020 (DOI 10.54499/UIDB/50014/2020), and financed by National Funds through FCT - Fundação para a Ciência e a Tecnologia, I.P. (Portuguese Foundation for Science and Technology) within the project IBEX, with reference PTDC/CCI-COM/4280/2021 (DOI 10.54499/PTDC/CCI-COM/4280/2021). iii 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 Universidade do Minho. (André Sequeira) iv Resumo Os rápidos avanços na computação quântica abriram novas possibilidades para o aprimoramento da aprendizagem por reforço (RL), especialmente através de circuitos quânticos parametrizados (PQCs) como aproximadores de funções em algoritmos híbridos quântico-clássicos. Esta dissertação aborda desafios e oportunidades no uso de PQCs para RL, explorando o seu design, treino e potencial para alcançar vantagem quântica. A primeira parte investiga a expressividade e capacidade de treino de políticas baseadas em PQCs. Técnicas como reintrodução de dados e escalamento de entradas/saídas demonstram que os PQCs podem ter desempenho equivalente ou superior ao de redes neurais clássicas, frequentemente com menos parâmetros. No entanto, a capacidade de treino é limitada pelo fenómeno de Barren Plateau (BP), onde gradientes nulos dificultam a otimização. Esta dissertação identifica condições para mitigar BPs, garantindo treino em circuitos de profundidade logarítmica com medições locais. Com base nisso, a segunda parte explora técnicas de otimização para RL baseado em PQCs. Uma comparação entre gradientes naturais quânticos (QNG), com matriz de Fisher quântica (QFIM), e métodos com matriz de Fisher clássica (CFIM) revela compromissos entre otimizações no espaço de estados e de políticas. Embora QNGs ofereçam maior estabilidade, seus benefícios face à CFIM dependem do contexto. Para equilibrar treino eficiente e intratabilidade clássica, a terceira parte propõe políticas de PQCs baseadas em circuitos com geradores comutativos. Estes evitam o fenómeno de BP enquanto permanecem difíceis de simular classicamente, representando um caminho promissor para alcançar vantagem quântica. A parte final integra técnicas tolerantes a falhas com métodos baseados em PQCs, propondo uma estrutura para alcançar vantagem quântica provável em ambientes parcialmente observáveis, com demonstração de aceleração quadrática na complexidade amostral para atualizações de crenças via inferência Bayesiana quântica. Esta dissertação contribui para a compreensão do RL baseado em PQCs, oferecendo perspetivas sobre o seu design, treino e otimização, destacando o potencial da computação quântica para revolucionar o RL e viabilizar agentes quântico-aprimorados escaláveis. Palavras-chave: Aprendizagem por Reforço Quântica, Atualização Quântica de Convicções Barren Plateaus , Gradientes Naturais Quânticos, Instantâneos Polinomiais Quânticos v Abstract Quantum Reinforcement Learning: Foundations, algorithms, applications The rapid advancements in quantum computing have opened new avenues for enhancing reinforcement learning (RL), particularly through the use of parameterized quantum circuits (PQCs) as function approximators in hybrid quantum-classical algorithms. This dissertation addresses critical challenges and opportunities in leveraging PQCs for RL, exploring their design, trainability, and potential for achieving quantum advantage. The first part of this work investigates the expressivity and trainability of PQC-based policies. By introducing techniques such as data reuploading, input scaling, and output scaling, we demonstrate that PQCs can achieve performance on par with or superior to classical neural networks, often with fewer trainable parameters. However, PQC trainability is hindered by the Barren Plateau (BP) phenomenon, where vanishing gradients impede optimization. This dissertation identifies conditions under which BPs can be mitigated, ensuring trainability in logarithmic-depth circuits with local measurements. Building on these findings, the second part explores optimization techniques for PQC-based RL agents. A critical comparison of quantum natural gradients (QNG), leveraging the quantum Fisher information matrix (QFIM), and classical Fisher information matrix (CFIM)-based updates reveals tradeoffs in state-space versus policy-space optimizations. While QNG provides stability and informed updates, its benefits over CFIM-based methods are context-dependent. To address the balance between trainability and classical intractability, the third part proposes PQC-based policies derived from commuting-generator circuits. These circuits are designed to be efficiently trainable, avoiding the BP phenomenon, while remaining classically hard to simulate. These present a promising route toward achieving quantum advantage in RL. Finally, a fault-tolerant quantum framework was proposed to achieve provable quantum advantage in partially observable environments, supported by a demonstrated quadratic speedup in belief updates using quantum Bayesian inference. This dissertation contributes to the foundational understanding of PQC-based RL, offering insights into their design, trainability, and optimization. The results highlight the potential of quantum computing to revolutionize RL, paving the way for scalable and advantageous quantum-enhanced agents. Keywords: Barren Plateaus, Instantaneous Quantum Polynomial, Quantum Natural Gradients, Quantum Policy Gradients, Quantum Reinforcement Learning vi Contents List of Figures xi List of Tables xviii List of Algorithms xx Acronyms xxii 1 Introduction 1 1.1 Motivation..................................... 2 1.2 Relatedwork.................................... 5 1.3 Thesis structure and synopsis . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Listofpublications................................. 9 I Background 10 2 Quantum Information and Computation 11 2.1 Statespace .................................... 11 2.2 Timeevolution................................... 13 2.3 Composite systems and entanglement . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Measurements and expectation values . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Parameterized quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6 Parameter estimation and Fisher information . . . . . . . . . . . . . . . . . . . . 21 2.7 Universality and classical simulation . . . . . . . . . . . . . . . . . . . . . . . . 24 3 Variational quantum algorithms 27 3.1 Classical data encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2 Expressivity of quantum machine learning models . . . . . . . . . . . . . . . . . 32 3.3 Optimization of parameterized quantum circuits . . . . . . . . . . . . . . . . . . 35 3.4 The barren plateau phenomenon . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4 Reinforcement learning 44 vii 45 Cumulative rewards obtained by the Born policies in the Acrobot environment: (a) UQC with a number of qubits in {1,2,4}and (b) Jerbi architecture. The action-projector-like policy is labeled global inthelegend............................... 108 46 Entanglement during training for the Born policies in the Acrobot environment: (a) UQC with a number of qubits in {1,2,4}and (b) Jerbi architecture. The action-projector-like policy is labeled global inthelegend............................... 108 47 Cumulative rewards obtained by the Born policies with softmax activation in the Cartpole environment: (a) UQC with {1,2,4}qubits, and (b) Jerbi architecture. The action-projectorlike policy is labeled global inthelegend......................... 109 48 Entanglement during training for the Born policies with softmax activation in the Cartpole environment: (a) UQC with {1,2,4}qubits, and (b) Jerbi architecture. The action-projectorlike policy is labeled global inthelegend......................... 110 49 Cumulative rewards obtained by the Born policies with softmax activation in the Acrobot environment: (a) UQC with {1,2,4}qubits, and (b) Jerbi architecture. The action-projectorlike policy is labeled global inthelegend......................... 110 50 Entanglement during training for the Born policies with softmax activation in the Acrobot environment: (a) UQC with {1,2,4}qubits, and (b) Jerbi architecture. The action-projectorlike policy is labeled global inthelegend......................... 111 51 Local softmax policy in the Cartpole environment: (a) cumulative reward and (b) entanglement during training. The UQC with {1,2,4}qubits and Jerbi architecture is considered. 112 52 Local softmax policy in the Acrobot environment: (a) cumulative reward and (b) entanglement during training. The UQC with {1,2,4}qubits and Jerbi architecture is considered. . . . 112 53 (a) Variance of the probability of measuring the all-zero state under a global projector. (b) log plot for the variance of Tr[𝜌𝜃P], where Pis either the global or local projector as described above. The variance is plotted versus the number of qubits for 1000 randomly sampled parameters 𝜃∈𝑈(−𝜋, 𝜋)........................... 120 54 Entangled PQC composed of two Bell states in a four qubit system. . . . . . . . . . . . 122 55 Variance of the log policy gradient for three distinct entangled states. (a) Simplified two design. (b) Strongly entangling layers. (c) Random states composed of Pauli rotations sampled uniformly at random followed by randomly selected CZ gates. (d) Variance as a function of the number of qubits for 𝑁layers of building blocks of each of the circuits (a)-(c). . . . . 124 56 The simplified two-design ansatz with an additional rotation layer (in purple) for state encoding 𝑆(𝑠). Each of the 𝑁qubits encodes a feature of 𝑠.................... 129 57 Variance of the log policy gradient for a contiguous-like Born policy: (a) and (b) vs. |𝐴|, and (c) a semi-log plot vs. number of qubits. Unclipped probabilities. . . . . . . . . . . . . 130 58 Variance of the log policy gradient for a contiguous-like Born policy under polynomial clipping: (a) vs. |𝐴|, and (b) a semi-log plot vs. 𝑁......................... 130 xiv 59 Variance of the log policy gradient for a parity-like Born policy: (a) and (b) vs. |𝐴|, and (c) a semi-log plot vs. 𝑁. Unclipped probabilities. . . . . . . . . . . . . . . . . . . . . . . 131 60 Variance of the log policy gradient for a parity-like Born policy under polynomial clipping: (a) vs. |𝐴|, and (b) a semi-log plot vs. 𝑁. ......................... 131 61 Eigenvalue distribution of the FIM for the parity-like Born policy, comparing |𝐴|=2(a) and |𝐴|=2𝑁(b) as 𝑁grows................................ 132 62 Eigenvalue distribution of the FIM for the contiguous-like Born policy, comparing |𝐴|=2(a) and |𝐴|=2𝑁(b) as 𝑁grows.............................. 132 63 Results with |𝐴|=𝑁: (a,b) Probability of picking the best arm for contiguous-like vs. paritylike Born policies; (c) variance of the log policy gradient. . . . . . . . . . . . . . . . . 133 64 Results with |𝐴|=2𝑁−4: (a,b) Probability of picking the best arm for contiguous-like vs. parity-like Born policies; (c) variance of the log policy gradient. . . . . . . . . . . . . . 133 65 Parameterized Quantum Circuits (PQCs) used: (a) simplified 2-design, (b) SEL (general single-qubit gates 𝐺), (c) random ansatz (random single-qubit rotations 𝑃). The purple (shaded) boxes illustrate one layer. . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 66 Log-scale variance of the log-policy gradient for local and global softmax policies in (a) simplified 2-design, (b) SEL, (c) random ansatz. . . . . . . . . . . . . . . . . . . . . . . 138 67 Log-scale variance of the partial derivative of the log policy for global, local, and partial observables in each of the three PQCs. . . . . . . . . . . . . . . . . . . . . . . . . . . 138 68 Log-scale variance of 𝜕𝜃log 𝜋(𝑎|𝜃)under global, local, and partial observables, for different |𝐴| ∈ {2,4,8,16}. ................................ 139 69 Probability of picking the best arm over 100 episodes for global, local, and partial softmax policies......................................... 139 70 Agent-environment interface for the Quantum Natural Policy Gradient (QNPG) algorithm. The agent interacts with the environment to generate a trajectory 𝑇of states and actions. An information matrix (the CFIM or Quantum Fisher Information Matrix (QFIM)) is estimated from these data and used to update the policy parameters. . . . . . . . . . . . . . . . 145 71 Parameterized quantum circuit used in the numerical experiments. Data reuploading follows [93], but input scaling is omitted to facilitate more accurate QFIM matrix estimation. 153 72 Performance of NPG (and its generalized quantum counterpart) in the Cartpole environment. Subfigure (a) uses a Born policy, while subfigure (b) uses a Softmax policy. The cumulative reward is shown on the y-axis, over training episodes on the x-axis. . . . . . . . . . . . 154 73 Performance of NPG (and its generalized quantum counterpart) in the Acrobot environment. Subfigure (a) uses a Born policy, while subfigure (b) uses a Softmax policy. . . . . . . 154 74 The SWAP test circuit for estimating the distance between policies. . . . . . . . . . . . 158 75 IQP circuit. (a) Z-program. (b) X-program. . . . . . . . . . . . . . . . . . . . . . . . 160 76 IQP circuits with two layers. (a) Z-program. (b) X-program. . . . . . . . . . . . . . . . 160 xv 77 Diagonal gate pattern for IQP circuits. (a) Brick-like. (b) Pyramid-like. (c) Next nearest neighbor. (d) All to all connectivity. (e) Single-qubit gates added. . . . . . . . . . . . . . . . 162 78 IQP circuit with two layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 79 Light-cone of the O(1)-local term in the contribution for next-nearest neighbor IQP circuits. 169 80 IQP circuits with single and two-qubit diagonal gates considered in the numerical simulations. (a) Next-nearest neighbor connectivity with a single layer. (b) Next-nearest neighbor connectivity with two layers. (c) All-to-all connectivity with a single layer. . . . . . . . . . 173 81 variance of the cost function for IQP circuits with (a) next-nearest neighbor connectivity singlelayer, (b) All to all connectivity. Variance is estimated as a function of the number of qubits for |𝐴|=𝑁2and |𝐴|=2𝑁actions........................... 173 82 variance of the cost function for IQP circuits with (a) next-nearest neighbor connectivity twolayers, (b) next-nearest neighbor connectivity three-layers. Variance is estimated as a function of the number of qubits for |𝐴|=𝑁2and |𝐴|=2𝑁actions. . . . . . . . . . . . . . . 174 83 performance of the IQP-based contiguous-like Born policy with and without Softmax activation in the contextual bandit setting. The average reward is plotted with the number of episodes as a function of the number of qubits in the policy. . . . . . . . . . . . . . . . . . . . 176 84 performance of the IQP-based contiguous-like Born policy with Softmax activation in the contextual bandit setting and respective comparison with classical neural network policies. Classical models are identified by the flag ”hs”indicating the hidden size layersℎ𝑠 ={4,8,16,32} present in the fully connected neural networks. The average reward is plotted with the number of episodes as a function of the number of qubits in the policy. (a) IQP-based models with 𝐿={1,2,3}layers. (b) Classical neural network vs IQP-based models with 𝐿=2layers. (c) Classical neural network vs IQP-based models with 𝐿=3layers. . . . . . . . . . . 177 85 Modified Agent-environment interface for quantum Q-learning. . . . . . . . . . . . . . 181 86 Hardware-efficient circuits considered in the numerical experiments. (a) Skolik architecture inspired by Skolik et.al [185]. (b) Universal Quantum Classifier (UQC) architecture inspired by the single-qubit universal approximator proposed by Salinas et.al [152]. . . . . . . . 192 87 Performance of Baseline Models (on the left) and Data Re-Uploading models (on the right) in the (a) CartPole-v0 environment and (b) Acrobot-v1 environment. Results plot the training with and without trainable input and/or output scaling. The returns are averaged over 10 agents. The full set of hyperparameters can be seen in Table 13 . . . . . . . . . . . . 193 88 Trainability of Baseline Models (on the left) and Data Re-Uploading models (on the right) in the (a) CartPole-v0 environment and (b) Acrobot-v1 environment. In both Subfigures, the left graph represents the gradient’s norm throughout training and the right graph the variance of thenorm........................................ 194 89 Cumulative reward (top graph) and the respective loss function evolution as a function of 𝐶 for Skolik reuploading model in (a) Cartpole-v0 and (b) Acrobot-v1, environments. The full set of hyperparameters can be seen in Table 14. . . . . . . . . . . . . . . . . . . . . 196 xvi 90 Gradient norm and variance for the Skolik reuploading model with increasing values of 𝐶in (a) Cartpole-v0 and (b) Acrobot-v1 environments. . . . . . . . . . . . . . . . . . . . . 197 91 Performance of the UQC architecture with Full and Partial Encoding considering in the (a) CartPole-v0 and (b) Acrobot-v1 environments. The results are plotted for 2 and 4 qubits, with and without entanglement. The full set of hyperparameters can be seen in Table 15. . . 199 92 Circuit for the UQC architecture with Full Encoding and linear entanglement for 4 qubits. 199 93 Trainability of the UQC architecture with Full Encoding and linear entanglement for (a) Cartpolev0 and (b) Acrobot-v1 environments. The gradient norm and variance are plotted as a function of the number of qubits and the number of training steps. The full set of hyperparameters canbeseeninTable16................................. 201 94 Variance of the gradient for the UQC architecture with Full Encoding and linear entanglement for the Cartpole-v0 environment considering local and global cost functions. The results are plotted as a function of the number of qubits. ..................... 202 95 Training and validation accuracies and MSE loss for (a) Skolik Data Re-uploading and (b) Multi-Qubit UQC models in the binary classification problem. The results are plotted as a function of the number of qubits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 96 Gradient norm and variance for the (a) Skolik Data Re-uploading and (b) Multi-Qubit UQC models in the binary classification problem. The results are plotted as a function of the numberofqubits.................................... 204 97 A simple Bayesian network with three nodes. . . . . . . . . . . . . . . . . . . . . . . 207 98 Generic representation of a Dynamic Bayesian Network (DBN). . . . . . . . . . . . . . 208 99 Generic representation of a Dynamic Decision Network (DDN) with action and reward nodes clearly illustrated for two time steps. . . . . . . . . . . . . . . . . . . . . . . . . . . 209 100 Quantum circuit for the Quantum Bayesian Network (QBN) for the example in Figure 97. . 210 101 A simple one-time-step DDN for a Partially Observable Markov Decision Process (POMDP). 212 102 Quantum circuit for the single time step DDN for a POMDP. . . . . . . . . . . . . . . 214 103 Lookahead search tree for horizon two. Belief nodes are pentagonally shaped and observation nodes are circle shaped. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 104 Illustration of the POMDPs considered in the numerical experiments. (a) The tiger problem. (b) The robot exploration problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 105 Cumulative reward difference for the one-step lookahead in (a) tiger problem and (b) robot explorationproblem................................... 219 106 Cumulative reward difference for the two-step lookahead in (a) tiger problem and (b) robot explorationproblem................................... 220 xvii List of Tables 1 Characteristics of different types of Born policies. . . . . . . . . . . . . . . . . . . . . 78 2 Applicability of input and output scaling in PQC-based policies. . . . . . . . . . . . . . 87 3 Gradient recipes for each policy and their respective parameters, including the Gaussian policy.......................................... 92 4 Policy gradient ranges and respective gradient estimation sample complexity for PQC-based policies......................................... 96 5 Number of parameters trained for both environments. Env: environment; I: Input layer; O: Output layer; #N: neurons; #R: rotations per qubit; 𝑤: output-scaling; #P: total parameters. ......... 101 6 Number of parameters for the UQC and Jerbi circuits, where |𝑠|is the number of features, 𝐿is the number of layers, and 𝑁is the number of qubits. . . . . . . . . . . . . . . . 105 7 Observables for the Softmax policy in different environments . . . . . . . . . . . . . . 111 8 Summary of results. The first column indicates the type of information matrix considered. The second and third columns indicate whether the norm and approximation error inequalities are guaranteed, respectively. The fourth column indicates if the regret is improved. . . . 150 9 Simulability of contiguous-like Born policies composed of commuting-generator circuits, as a function of the number of actions |𝐴|. ......................... 163 10 Complexity comparison between classical and quantum rejection sampling algorithms. 𝑁 is the number of variables, 𝑀is the number of parents of any variable and 𝑃(𝑒)is the probability of the evidence taking value 𝑒. ....................... 211 11 Characterization of the environments considered in the numerical experiments. . . . . 248 12 Characterization of the PQC’s considered in the numerical experiments. 𝑃𝑖indicates the projector in the computational basis in decimal. For the Cartpole environment a single-qubit was measured and the probability of each basis state associated to an action. In the Acrobot environment, the action assignmment was made using 𝑖𝑛𝑡 (𝑏)mod 3=𝑎for a particular basis state 𝑏. ..................................... 249 13 PQC-based DQN hyperparameters for the numerical experiments of Section 9.5.1. . . . . 251 xviii 14 Complexity comparison between classical and quantum rejection sampling algorithms. 𝑁 is the number of variables, 𝑀is the number of parents of any variable, and 𝑃(𝑒)is the probability of the evidence taking value 𝑒. ....................... 252 15 Hyperparameters of Models for Figure 91 . . . . . . . . . . . . . . . . . . . . . . . 253 16 Hyperparameters of Models for Figure 93 . . . . . . . . . . . . . . . . . . . . . . . 254 xix List of Algorithms 1 Estimating the expressivity of a PQC ensemble . . . . . . . . . . . . . . . . . . . 21 2 Q-Learning..................................... 54 3 DeepQ-Learning.................................. 57 4 REINFORCE .................................... 60 5 Natural Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6 Quantum Natural Policy Gradient (QNPG) . . . . . . . . . . . . . . . . . . . . . . 146 7 PQC-based Deep Q-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 8 Quantum rejection sampling algorithm [121] where the operator 𝐺2𝑘comes from the exponential progression of the amplitude amplification algorithm, provided the optimal number of iterations is not known [28]. . . . . . . . . . . . . . . . . . . . . . . . 211 xx Listings 5.1 Example Python Command . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 xxi Acronyms BN Bayesian Network (pp. 206, 207, 210, 211, 213) BP Barren Plateau (pp. 3, 4, 6–9, 29, 32, 39–43, 69, 116, 117, 121, 126–128, 130, 131, 133, 134, 163, 166–170, 172–174, 178, 222, 223) CFIM Classical Fisher Information Matrix (pp. xiii, xv, 4, 8, 22, 23, 34, 37, 61, 101, 102, 117, 127–129, 131, 140, 141, 143–148, 150–153, 155, 157, 178, 223) DBN Dynamic Bayesian Network (pp. xvii, 208, 209, 211) DDN Dynamic Decision Network (pp. xvii, 209, 212–215) DLA Dynamical Lie Algebra (pp. 34, 41–43, 164–167, 174) DQN Deep Q-Network (pp. 5, 6) IQP Instantaneous Quantum Polynomial (pp. xi, xvi, 8, 25, 26, 159, 160, 162–179, 223, 224) MDP Markov Decision Process (pp. 46, 47, 79, 206, 213) ML Machine Learning (pp. 1, 41, 43, 120, 157) NISQ Noisy Intermediate-Scale Quantum (pp. 1, 25, 27) NPG Natural Policy Gradient (pp. 3, 61, 62, 64, 65, 143, 144, 147, 223) POMDP Partially Observable Markov Decision Process (pp. xvii, 206, 207, 212–218, 220, 221) PQC Parameterized Quantum Circuit (pp. x, xi, xiii, xiv, xviii, xx, 1–9, 11, 18–23, 27–35, 37–39, 42, 43, 67–69, 72, 74, 78–83, 86–89, 91, 94–96, 98–100, 102–106, 108, 113–119, 121–123, 125, 127–129, 132, 134, 139–149, 152–157, 159, 164, 166, 167, 170, 178, 180–187, 189–195, 197, 198, 200–205, 221–225, 250–252, 254) QBN Quantum Bayesian Network (pp. xvii, 209–211) QFIM Quantum Fisher Information Matrix (pp. xv, 3, 4, 6, 8, 23, 34, 38, 143–150, 152, 153, 155–157, 178, 223) QML Quantum Machine Learning (pp. xi, 1, 2, 19, 29, 30) xxii ACRONYMS xxiii QNG Quantum Natural Gradient (pp. 38, 178) QNPG Quantum Natural Policy Gradient (pp. xv, 3, 143, 145–147) QRAM Quantum Random Access Memory (pp. xi, 1, 2) QRL Quantum Reinforcement Learning (pp. xi, 2–5, 9, 29, 157) RL Reinforcement Learning (pp. xii, 2–8, 22, 23, 29, 44, 46, 48, 50, 51, 55, 56, 60, 62–64, 67, 69–72, 75, 79, 84, 96, 114, 118, 121, 125, 127, 129, 134, 136, 142, 143, 151, 158, 180, 191, 192, 202, 203, 206, 208, 209, 211, 212, 222–225) VQA Variational Quantum Algorithm (pp. xi, 18, 27–29, 35, 71) 1.3. THESIS STRUCTURE AND SYNOPSIS Part I provides the foundational knowledge required to understand the dissertation’s core contributions. This section comprises three chapters: 1. Chapter 2: Quantum Information and Computation Provides an introduction to the principles of quantum information and computation, covering foundational topics such as quantum states, unitary operations, and measurement postulates. It also delves into essential concepts like the expectation value of observables and quantum entanglement, setting the stage for the application of PQCs in machine learning and RL. 2. Chapter 3: Variational Quantum Algorithms The chapter examines the mathematical structure of PQCs, their capacity as universal function approximators, and techniques such as data encoding and ansatz design. It also addresses challenges like BPs, gradient optimization, and the tradeoff between expressivity and scalability, providing a comprehensive understanding of how PQCs are employed in hybrid quantum-classical algorithms. 3. Chapter 4: Reinforcement Learning Provides a comprehensive overview of RL, starting with foundational concepts such as the agent-environment interaction loop, reward functions, and value functions. It covers classical tabular methods, including policy and value iteration, as well as modelfree approaches like Q-learning. The chapter then progresses to advanced topics, such as policy optimization techniques, function approximation, and the integration of neural networks in deep RL. Special attention is given to challenges such as the exploration-exploitation tradeoff, sample efficiency, and scalability, setting the stage for the application of quantum methods in RL. Part II presents the dissertation’s primary contributions, each addressing specific research questions posed in Chapter 1. Each chapter adapts and extends findings from a collection of authored research articles: 1. Chapter 5: Quantum Policy Gradients This chapter addresses the first part of Research Question RQ1, focusing on the design and expressivity of PQC-based policies. Key strategies such as data reuploading, input scaling, and output scaling are introduced to enhance performance. These contributions are based on: • Policy Gradients using Variational Quantum Circuits , Quantum Machine Intelligence, Springer, DOI: 10.1007/s42484-023-00101-8, 2023. The chapter demonstrates that PQC-based policies with singly encoded states can achieve comparable or superior performance to classical neural networks while using fewer trainable parameters. Enhanced expressivity through data reuploading further improves agent performance. 7 CHAPTER 1. INTRODUCTION 2. Chapter 6: Trainability Issues in Quantum Policy Gradients This chapter explores the second part of Research Question RQ1, focusing on the trainability challenges posed by the BP phenomenon in PQC-based policies. The results are published in: • Trainability Issues in Quantum Policy Gradients , IOP Machine Learning: Science and Technology, DOI: 10.1088/2632-2153/ad6830, 2024. • Trainability Issues in Quantum Policy Gradients with Softmax Activations , IEEE International Conference on Quantum Computing and Engineering (QCE), 2024. Key contributions include conditions under which vanishing gradients can be expected and mitigated. It is shown that BPs are present in every PQC-based instance under uniformly random initialization in models comprised of local 2-designs. Although, such policies provide a trainable region at logarithmic depth, provided local measurements are performed, thus avoiding vanishing gradients. 3. Chapter 7: Quantum Natural Policy Gradients This chapter addresses Research Question RQ2 by exploring second-order optimization techniques to enhance the training of PQC-based policies using the QFIM. The results are based on: • Quantum Natural Policy Gradients , IEEE Transactions on Quantum Engineering, DOI: 10.1109 / TQE.2024.3418094, 2024. Key findings demonstrate that quantum natural gradients yield more stable and informed updates compared to Euclidean gradients, enhancing the convergence and performance of quantum policies. However, through an analysis of Löwner inequalities between the CFIM and QFIM, it is shown that PQC-based policies do not, in general, consistently benefit from updates preconditioned by the QFIM over the CFIM. This chapter provides a critical comparison between state-space and policyspace updates, shedding light on the practical tradeoffs of employing QFIM in RL contexts with classical data. 4. Chapter 8: Efficiently Trainable Quantum Circuits for Classically Intractable Policy Gradients This chapter addresses Research Question RQ4, developing PQC-based policies derived from the class of Instantaneous Quantum Polynomial (IQP) circuits. The key finding is that there are circuits from this class that enable a trainable and classically hard-to-simulate window, provided the policy is obtained from measuring more than log(𝑁)qubits and O(poly(𝑁)) actions. This approach balances the tradeoff between efficient trainability and classical intractability, advancing the design of PQC-based agents for achieving quantum advantage. A manuscript is currently in preparation. 5. Chapter 9: Tradeoff Between Trainability and Expressivity This chapter revisits Research Question RQ1, examining the interplay between trainability and expressivity in PQC-based value function approximators. It is based on: 8 1.4. LIST OF PUBLICATIONS • VQC-Based Reinforcement Learning with Data Re-uploading: Performance and Trainability , Quantum Machine Intelligence, Springer, DOI: 10.48550/arXiv.2401.11555, 2024. The chapter identifies a new phenomenon where gradients tend to increase with training, depending on target network updates and moving targets in deep Q-learning. Even though gradients increase with training, BPs can indeed occur for random initialization in local 2-design models. However, it is rigorously demonstrated that vanishing gradients can be avoided provided logarithmic depth and local measurements. 6. Chapter 10: Quantum Bayesian Reinforcement Learning This chapter addresses Research Question RQ4, proposing a novel framework for planning in partially observable environments using quantum Bayesian inference. The results build on quantum rejection sampling techniques for efficient belief updates. I was demonstrated a quadratic speedup in sample complexity for belief updates in a near-optimal horizon-based planning algorithm, for partially observable environments. A manuscript is currently in preparation. Finally, Chapter 11 provides a comprehensive summary of the dissertation’s main contributions and integrates the insights gained from addressing the research questions. While each chapter concludes with its own findings and prospects for future work, this chapter unifies these individual conclusions to present a cohesive perspective on the broader implications of the research. Additionally, it highlights potential directions for future exploration in the field of QRL, offering a roadmap for advancing the application and understanding of PQC-based frameworks. 1.4 List of publications • Policy Gradients using Variational Quantum Circuits - Quantum Machine Intelligence, Springer, DOI: 10.1007/s42484-023-00101-8, 2023. Analyzed and extended in Chapter 5. • Trainability Issues in Quantum Policy Gradients - IOP Machine Learning: Science and Technology, DOI: 10.1088/2632-2153/ad6830, 2024. Analyzed in Chapter 6. • Trainability Issues in Quantum Policy Gradients with softmax activations - IEEE International Conference on Quantum Computing and Engineering (QCE), 2024. Analyzed in Chapter 6. • Quantum Natural Policy Gradients - IEEE Transactions on Quantum Engineering, DOI: 10.1109/ TQE.2024.3418094, 2024. Analyzed in Chapter 7. • VQC-Based Reinforcement Learning with Data Re-uploading: Performance and Trainability - Quantum Machine Intelligence, Springer, DOI: 10.48550/arXiv.2401.11555, 2024. Analyzed and extended in Chapter 9. 9 Part I Background 10 C h a p t e r 2 Quantum Information and Computation The field of quantum information and computation lies at the crossroads of quantum mechanics and computer science, offering transformative perspectives on how information can be processed, stored, and manipulated. This chapter provides a comprehensive overview of the fundamental concepts, notation, and principles that underlie quantum information and computation, serving as the theoretical basis for the discussions throughout this dissertation. Sections 2.1 to ?? introduce the foundational postulates of quantum mechanics and their mathematical representation. We begin by examining how quantum states are described using Dirac notation, state vectors, and density matrices, followed by an exploration of quantum measurement processes and the estimation of expectation values for physical observables. Building upon these foundational elements, Section 2.5 turns to the concept of PQCs and the variational principle. These circuits form the core computational model considered in this dissertation, enabling the integration of classical optimization techniques with quantum operations. We then delve deeper into the connection between PQCs and parameter estimation in Section 2.6, which provides insights into how Fisher information can quantify sensitivity and trainability in parameterized quantum models. 2.1 State space Quantum states are represented as vectors in a Hilbert space H ⊆ ℂ𝐾. A state is typically denoted by the ket |𝜓i=(𝛼0, . . . , 𝛼𝐾−1)𝑇. The norm of this vector is expressed through the inner product, written in Dirac notation as h·|·i, where h·| is the conjugate transpose (bra) of the vector ket. For two vectors |𝜓i and |𝜙iin H, the following identity holds: h𝜓|𝜙i∗=h𝜙|𝜓i,(2.1) and the norm of |𝜓iis ||𝜓|| =ph𝜓|𝜓i. 11 CHAPTER 2. QUANTUM INFORMATION AND COMPUTATION Let {|𝑒𝑖i}𝑖∈ℕbe an orthonormal basis for the Hilbert space H. A general quantum state can then be expanded in this basis as |𝜓i=Õ 𝑖|𝑒𝑖i h𝑒𝑖|𝜓i |{z} 𝛼𝑖 =Õ 𝑖 𝛼𝑖|𝑒𝑖i,(2.2) where each 𝛼𝑖is a probability amplitude , and |𝑒𝑖ih𝑒𝑖|acts as the projection operator onto the basis state |𝑒𝑖i. The completeness or resolution of the identity condition states that Õ 𝑖|𝑒𝑖ih𝑒𝑖|=𝐼, where 𝐼is the identity operator. This decomposition is fundamental for analyzing measurement outcomes on quantum states. A canonical example of an orthonormal basis in the two-dimensional case is the computational basis {|0i,|1i}, which defines a two-level quantum system known as a qubit . A generic qubit state can be written as a linear combination of these basis states: |𝜓i=𝛼0|0i + 𝛼1|1i.(2.3) When |𝜓iis a pure state, it can be visualized as a point on the surface of the Bloch sphere , as depicted in Figure 3. Figure 3: Bloch sphere representation of a single-qubit state. Image source: Machine Learning with Quantum Computers by Schuld et al. [168] In practice, one often encounters uncertainty about the exact state due to environmental noise or imperfect isolation of the system. In such scenarios, the state is not purely described by a single ket but may exist in a statistical mixture of pure states, referred to as a mixed state . Geometrically, mixed states lie in the 12 2.2. TIME EVOLUTION interior of the Bloch sphere (for one qubit), rather than on its surface. These mixtures are described by a density matrix (or density operator )𝜌, formally written as 𝜌=Õ 𝑗 𝑝𝑗|𝜓𝑗ih𝜓𝑗|,(2.4) where each |𝜓𝑗iis a pure state and 𝑝𝑗is the probability of preparing that pure state. A pure state |𝜓iis itself a special case, in which 𝜌=|𝜓ih𝜓|. Thus, whether a state is pure or mixed, density matrices offer a powerful and general formalism for describing quantum states in realistic settings. 2.2 Time evolution The time evolution of a closed quantum system is governed by the Schrödinger equation. If |𝜓(𝑡)i is the state of the system at time 𝑡and 𝐻is the Hamiltonian (i.e., the total energy operator), then 𝑖ℏ𝑑 𝑑𝑡 |𝜓(𝑡)i =𝐻|𝜓(𝑡)i,(2.5) where ℏis the reduced Planck constant. The formal solution to this equation is given by the unitary operator 𝑈(𝑡), |𝜓(𝑡)i =𝑈(𝑡) |𝜓(0)i,(2.6) with 𝑈(𝑡)=𝑒−𝑖 ℏ𝐻 𝑡 . The unitarity of 𝑈(𝑡)ensures that quantum evolution is reversible and preserves the normalization of quantum states, reflecting the deterministic nature of quantum mechanics for closed systems. When the system’s initial state is described by a density matrix 𝜌(0)at 𝑡=0, the corresponding time-evolved state is 𝜌(𝑡)=𝑈(𝑡)𝜌(0)𝑈†(𝑡),(2.7) a formalism known as the Schrödinger picture [144]. Alternatively, one may move all time dependence to the observables themselves in the Heisenberg picture , a concept revisited in Section 3. In the context of quantum computing, particularly in the circuit-based model, the time evolution under a Hamiltonian 𝐻can be viewed as the application of a unitary gate on qubits. These gate operations, represented by unitary matrices, capture the allowed evolutions of quantum states in a computational setting. Consequently, the Hamiltonian 𝐻effectively serves as a generator of unitary transformations [144]. It is crucial to note that real-world quantum systems often interact with external environments, leading to open quantum systems , where the rules of evolution differ. In such cases, one must incorporate environmental effects into the Hamiltonian. However, throughout this dissertation, only closed systems are considered. For details on open quantum systems, see [33]. 13 CHAPTER 2. QUANTUM INFORMATION AND COMPUTATION One of the fundamental consequences of unitary evolution in quantum mechanics is the no-cloning theorem , which prohibits the perfect copying of arbitrary unknown quantum states [208]. A direct corollary of this theorem is that non-orthogonal quantum states cannot be perfectly distinguished [15]. 2.3 Composite systems and entanglement Composite quantum systems are described via the tensor product of the individual Hilbert spaces of their constituent subsystems. For example, if two quantum subsystems have Hilbert spaces H𝐴⊆ℂ𝑁and H𝐵⊆ℂ𝑁, the combined system lives in the tensor product space H=H𝐴⊗ H𝐵. A pure state |𝜓i ∈ H is called a product state (or separable state) if and only if there exist individual states |𝜙i ∈ H𝐴and |𝜑i ∈ H𝐵such that |𝜓i=|𝜙i ⊗ |𝜑i.(2.8) If no choice of product states exists in any basis, the state is said to exhibit correlations or, more formally, it is entangled . In other words, the reduced state of any one subsystem cannot be specified without referencing the other subsystem. Consider the uniform superposition of all basis states in an 𝑁-qubit system, |𝜓i=1 2𝑁|00 ···00i + |00 ···01i + ··· + |11 ···11i.(2.9) It can be factored into a product of single-qubit states as |𝜓i= 2𝑁−1 Ì 𝑖=0 1 √2|0i+|1i,(2.10) indicating that this particular state is not entangled. A central example of entanglement occurs in two-qubit Bell states : |Φ+i=1 √2|00i+|11i,|Φ−i=1 √2|00i−|11i, |Ψ+i=1 √2|01i+|10i,|Ψ−i=1 √2|01i−|10i.(2.11) Collectively, these four states form the Bell basis . They are maximally entangled in the sense that a projective measurement on one qubit yields completely random outcomes. Bell-basis measurements are integral to quantum protocols such as quantum teleportation [144]. 14 2.3. COMPOSITE SYSTEMS AND ENTANGLEMENT Measuring the degree of entanglement in a quantum state is crucial for understanding and exploiting quantum effects in computation and communication tasks. The Schmidt decomposition [122] provides one way to characterize bipartite pure states. Any bipartite state |𝜓ican be written as |𝜓i= 𝑑 Õ 𝑖=0 𝑎𝑖𝜙𝑖i⊗|𝜑𝑖,(2.12) where 𝑑=min(𝑑𝐴, 𝑑𝐵)is the smaller dimension of the two subsystem Hilbert spaces, and {|𝜙𝑖i}, {|𝜑𝑖i} are orthonormal sets. The Schmidt number 𝑆is the count of nonzero coefficients 𝑎𝑖. A pure bipartite state is entangled if and only if 𝑆≥2. Larger Schmidt number indicates a greater level of entanglement. Closely tied to the Schmidt decomposition is the von Neumann entropy , commonly used to quantify entanglement in bipartite pure states. For a bipartite density matrix 𝜌𝐴𝐵, the reduced density matrix of subsystem 𝐴is defined as 𝜌𝐴=Tr𝐵𝜌𝐴𝐵. The von Neumann entropy of 𝜌𝐴is 𝑆(𝜌𝐴)=−Tr𝜌𝐴log 𝜌𝐴.(2.13) For a pure bipartite state, 𝑆(𝜌𝐴)=𝑆(𝜌𝐵), highlighting that the entanglement is invariant under which subsystem is traced out. A maximally entangled state in a 𝑑-dimensional subsystem has von Neumann entropy log 𝑑. In contrast, for mixed global states, the von Neumann entropy no longer provides a straightforward measure of entanglement. In multiparticle systems with 𝑁qubits, understanding global entanglement (i.e., how entanglement is distributed among many qubits) can be more nuanced. One approach is the Meyer–Wallach measure (MWM) [129], which captures the extent of entanglement across the entire 𝑁-qubit state rather than focusing on pairwise entanglement. For a pure state |𝜓iof 𝑁qubits, the MWM is defined as 𝑄|𝜓i=4 𝑁 𝑁 Õ 𝑘=1 𝐷𝜌𝑘,(2.14) where 𝜌𝑘=Tr𝑘|𝜓ih𝜓|is the reduced density matrix of the 𝑘-th qubit, and 𝐷(𝜌𝑘)=1−Tr𝜌2 𝑘is the linear entropy . The measure 𝑄is invariant under local unitaries and normalized to lie within [0,1], with 𝑄=0for product states and 𝑄=1for maximally entangled states. One limitation of MWM is its insensitivity to the specific type of entanglement in the state. For instance, the product of two Bell pairs can give the same MWM as a four-qubit Greenberger–Horne–Zeilinger (GHZ) state [32], even though these states exhibit qualitatively different multipartite entanglement structures. 15 CHAPTER 2. QUANTUM INFORMATION AND COMPUTATION 2.4 Measurements and expectation values Once a quantum state has evolved in time, a measurement must be performed to extract classical information from it. During this process, the wavefunction collapses , irreversibly destroying the quantum information in the state. Conceptually, this collapse can be interpreted as a classical observer interacting with (or “looking at”) the quantum system, thus forcing the system to produce outcomes in the classical domain. A measurement is typically associated with a physical observable, represented by a Hermitian operator Mwith a discrete spectrum: M=Õ 𝑚 𝜇𝑚𝑃𝑚,(2.15) where each 𝜇𝑚is an eigenvalue associated with eigenstate |𝑚i, and 𝑃𝑚=|𝑚i h𝑚|is the corresponding projector. The simplest measurement scheme is a projective measurement , where the operators {𝑃𝑚} project the system onto the eigenstates |𝑚iof M. Suppose the quantum state |𝜓iis expressed as a superposition of the eigenstates of M: |𝜓i=Õ 𝑚 𝛼𝑚|𝑚i.(2.16) When Mis measured on |𝜓i, the probability of observing a particular eigenstate |𝑚iis given by the Born rule : 𝑝(𝑚)=h𝜓|𝑃𝑚|𝜓i=|h𝑚|𝜓i|2=|𝛼𝑚|2,(2.17) or, more generally for a density matrix 𝜌, 𝑝(𝑚)=Tr𝑃𝑚𝜌.(2.18) These relations highlight the probabilistic nature of quantum mechanics and the notion of wavefunction collapse upon measurement. By preparing and measuring the same (or identically prepared) states repeatedly, a distribution of outcomes consistent with 𝑝(𝑚)is obtained. In the single-qubit case, with computational basis {|0i,|1i}, the measurement operators are 𝑃0=|0ih0| and 𝑃1=|1ih1|. If |𝜓i=𝛼0|0i+𝛼1|1i, then measuring in this basis produces outcome |𝑖iwith probability |𝛼𝑖|2. Afterward, the state becomes |𝜓i←− 𝑃𝑚|𝜓i ph𝜓|𝑃𝑚|𝜓i,(2.19) in accord with the Born rule. More general measurement schemes are described by positive operatorvalued measures (POVMs) {𝐴𝑖}that satisfy Í𝑖𝐴† 𝑖𝐴𝑖=𝐼[168]. 16 2.6. PARAMETER ESTIMATION AND FISHER INFORMATION are directly observable, so the measurement operator must be considered. The measurement can be decomposed into projectors Π𝑙=|𝑙ih𝑙|, yielding probabilities 𝑝(𝑙|𝜃)=Tr𝜌(𝜃)Π𝑙.(2.37) Hence, 𝑝M(𝜃)forms a parameterized probability distribution over outcomes. A natural way to quantify the distribution’s sensitivity to 𝜃is by introducing a distance measure, such as the Kullback–Leibler (KL) divergence or relative entropy [113], 𝐷KL 𝑝M(𝜃) k𝑝M(𝜃+𝛿)=Õ 𝑙 𝑝(𝑙|𝜃)logh𝑝(𝑙|𝜃) 𝑝(𝑙|𝜃+𝛿)i.(2.38) A second-order Taylor expansion of this divergence around 𝛿=0recovers the CFIM [130]: 𝐼(𝜃)𝑖𝑗 =Õ 𝑙∈M 1 𝑝(𝑙|𝜃) 𝜕 𝑝(𝑙|𝜃) 𝜕𝜃𝑖 𝜕 𝑝(𝑙|𝜃) 𝜕𝜃𝑗,(2.39) which can be interpreted as the Hessian of the relative entropy. Large entries imply strong parameter sensitivity. It should also be noted that alternative differentiable distance measures would yield a CFIM differing only by a multiplicative constant. Classical probability distributions can be viewed as special cases of quantum states with diagonal density matrices [130]. A more general framework considers distances between quantum states themselves, rather than the measurement-induced distributions. In this scenario, a distance measure such as the fidelity is often chosen, as it provides a natural monotone metric for pure states [155]: 𝑓|𝜓(𝜃)i,|𝜓(𝜃+𝛿)i=h𝜓(𝜃)|𝜓(𝜃+𝛿)i2. A corresponding distance is then 𝑑|𝜓(𝜃)i,|𝜓(𝜃+𝛿)i=1−𝑓|𝜓(𝜃)i,|𝜓(𝜃+𝛿)i. Expanding this fidelity-based distance to second order in 𝛿produces the QFIM for pure states: F𝑖 𝑗 =4 Re[𝜕𝑖𝜓(𝜽)|𝜕𝑗𝜓(𝜽)−h𝜕𝑖𝜓(𝜽)|𝜓(𝜽)i𝜓(𝜽)|𝜕𝑗𝜓(𝜽) (2.40) exactly as described in [130]. Crucially, there is a matrix inequality relating CFIM and QFIM: 𝐼(𝜃) ≤ F(𝜃), which is derived using the Löwner order for positive semidefinite matrices [23], stating that F(𝜃)−𝐼(𝜃) ≥ 0is positive semi-definite. It implies that the QFIM provides an upper bound on the CFIM generated by any measurement scheme performed on the quantum state. As will be discussed in Chapter 7, these Fisher information matrices and their relationships are integral to understanding the optimization of PQC-based RL agents. 23 CHAPTER 2. QUANTUM INFORMATION AND COMPUTATION 2.7 Universality and classical simulation One of the core insights of quantum computing is the promise of universal quantum computation: the ability to implement any unitary operation (or approximate it arbitrarily well) using a finite set of gates. This notion of universality underpins the computational power of quantum devices, enabling them to, in principle, solve certain problems more efficiently than classical computers. However, not all quantum gate sets are equal in expressive power; some can be efficiently simulated by classical means, while others are believed to transcend classical capabilities. A quantum gate set is called universal if any unitary operation on 𝑛qubits can be realized (exactly or to arbitrary precision) using a finite combination of gates from this set. In particular, universal gate sets can densely generate the group 𝑆𝑈 (2𝑛). A well-known example of a universal set is composed of arbitrary single qubit rotations and controlled-NOT operations, {𝑅𝑥(𝜃), 𝑅𝑦(𝜃), 𝑅𝑧(𝜃),CNOT}[144]. The two-qubit controlled-NOT entangling gate in combination with arbitrary single-qubit gates, can approximate any 𝑛-qubit operation. A foundational result concerning universality is the Solovay-Kitaev theorem [58] stating that any unitary in 𝑆𝑈 (2𝑛)can be approximated to within 𝜖by a circuit of size O(log𝑐(1/𝜖)), where 𝑐is a constant typically near 3 or 4. The SolovayKitaev theorem guarantees that universal gate sets are not merely theoretical constructs but also efficiently implementable , as it rules out exponential overhead in gate decompositions. Another commonly used universal gate set is the Clifford+T set, which includes the Clifford gates and the T-gate or 𝜋/8gate - {𝐻, 𝑆, CNOT,𝑇 }The T-gate is a non-Clifford gate that, when added to the Clifford set, makes the gate set universal. It turns out that circuits consisting solely of Clifford gates, along with stabilizer-state inputs and measurement in the computational basis, are classically simulable in polynomial time by virtue of the Gottesman-Knill theorem [144]. When discussing whether a quantum circuit can be classically simulated , one typically distinguishes two regimes [142]: •Weak simulation: The task is to sample from the same output distribution produced by the quantum circuit. A weak simulator produces bitstrings with probabilities identical (or arbitrarily close) to those of the quantum device. This amounts to generating samples in the same manner as the quantum circuit without necessarily computing exact probabilities. •Strong simulation: The task is to compute exact probabilities (or approximate them up to a certain precision) of the quantum circuit’s measurement outcomes. Strong simulation is typically more demanding than weak simulation, as it requires knowledge of the complete probability distribution rather than just the ability to generate samples. Weak simulation asks whether we can simply sample from the same distribution as the quantum circuit, while strong simulation requires computing exact probabilities or probability amplitudes to a certain precision. Therefore, the Gottesman-Knill theorem states that the final measurement outcomes of Clifford circuits can be strongly simulated classically in polynomial time. This demonstrates that entanglement 24 2.7. UNIVERSALITY AND CLASSICAL SIMULATION alone—such as the one generated by cnot gates—does not necessarily yield universal quantum computation nor surpass classical methods. Moreover, notice that at least in the NISQ regime, quantum devices suffer from noise that hinders the ability of a quantum device exactly compute the output probabilities. Therefore, in practice, quantum advantage proposals revolve around the weak simulation setting demonstrating that no efficient weak simulation is likely, for certain families of circuits, highlighting a fundamental gap between classical and quantum computational power. Definition 2.7.1 (IQP circuits).Quantum circuits in which all gates commute and can thus be considered to act “instantaneously.” Typically, the gates are diagonal in the computational (𝜎𝑧) basis. Formally, an IQP circuit on 𝑁qubits generate distributions 𝑝𝑖=|h𝑖|𝐻⊗𝑁𝑈𝑧𝐻⊗𝑁|𝑖i|2(2.41) where 𝑈𝑧is composed of O(poly(𝑁)) commuting gates in the Z basis, for instance, {𝑇, 𝑍,𝐶𝑍,𝐶𝐶𝑍 ...}. A prominent example of a circuit family that is conjectured to be hard to simulate are IQP circuits, as defined in Definition 2.7.1. These circuits have been employed in several quantum supremacy proposals, as they can produce highly nontrivial sampling distributions despite their seemingly simple structure of commuting gates. Given N qubits, IQP circuits start in the |+i⊗𝑁state and are measured in the Hadamard basis. In between, they apply a unitary 𝑈𝑧composed of O(poly(𝑁)) commuting gates, for instance, {𝑇, 𝑍,𝐶𝑍,𝐶𝐶𝑍 ...}[178] , as illustrated in Figure 6. They are called instantaneous because all gates commute and there is no temporal order. Figure 6: Example of a standard IQP circuit. Figure taken from [63]. The IQP circuits are conjectured to be hard to weakly simulate classically under computational complexity assumptions such as the collapse of the polynomial hierarchy to its second level [125]. IQP circuits serve as an important example of a subuniversal model of quantum computation - they are neither universal in the standard sense nor trivial to simulate. Despite their apparent simplicity (commuting gates, low depth), it is widely conjectured that no efficient classical algorithm can sample from the same distribution produced by a sufficiently large IQP circuit unless the polynomial hierarchy in classical complexity 25 CHAPTER 2. QUANTUM INFORMATION AND COMPUTATION theory collapses. Consequently, IQP circuits have featured prominently in proposals for demonstrating quantum enhancements over classical methods [66] suggesting that even low-depth QAOA could achieve an exponential quantum speedup for optimization problems [138]. Not all restricted circuit families, however, are conjectured to be classically intractable. A notable opposite example is provided by matchgate circuits [99], which can indeed be efficiently simulated on a classical computer. Matchgates are structured 𝐺(𝐴, 𝐵)gates such that, 𝐺(𝐴, 𝐵)=©« 𝑝0 0 𝑞 0𝑤 𝑥 0 0𝑦 𝑧 0 𝑟0 0 𝑠 ª®®®®®¬ 𝐴= 𝑝 𝑞 𝑟 𝑠 !𝐵= 𝑤 𝑥 𝑦 𝑧 !(2.42) where 𝐴and 𝐵are both in 𝑆𝑈 (2)with det(𝐴)=det(𝐵). Matchgate circuits were shown to be weakly simulable for arbitrary product state inputs and/or the measurements are over arbitrarily many output qubits, although, provided that matchgates act only on nearest neighbor qubits [35]. In practice, matchgate circuits form a subuniversal model analogous to IQP circuits in their restricted structure. However, matchgates become universal when next nearest neighbor connectivity is allowed. 26 C h a p t e r 3 Variational quantum algorithms VQAs have emerged as powerful tools for tackling computationally demanding problems in the NISQ era, with the anticipation of achieving quantum advantages [22]. These algorithms make use of PQCs, as described in Section 2.5, and operate in a manner that parallels the structure of classical neural networks [77]. In essence, a VQA includes: • A cost function based on the outputs of measurements performed on a PQC. • A set of tunable free parameters in the circuit, adjusted by a classical optimization procedure until a desired target (encoded in the cost function) is approached. Due to the analogy with neural networks, such models are sometimes referred to as quantum neural networks [168, 5]. Figure 7: Schematic depiction of a VQA in a hybrid quantum–classical framework. Adapted from [45]. 27 CHAPTER 3. VARIATIONAL QUANTUM ALGORITHMS A generic VQA, illustrated in Figure 7, typically follows an iterative hybrid quantum–classical loop with two principal stages: 1. State preparation and measurement : A PQC prepares an initial hypothesis, also known as Ansatz , that aims to solve the target problem, and a cost function is evaluated using measurements of an observable on the resulting quantum state. 2. Classical optimization : A classical optimizer updates the free parameters in the PQC, steering the quantum state closer to the solution in an iterative manner. In quantum-enhanced machine learning [168], where a quantum device is employed to solve a classical machine learning task, it becomes necessary to embed classical data into the quantum system. Various encoding techniques exist, each with distinct trade-offs and complexities [112]. These will be addressed in Subsection 3.1. Formally, if data points are drawn from a dataset 𝑥∼𝐷, and the parameterized quantum circuit produces a density matrix 𝜌(𝑥, 𝜃), a cost function of the form 𝑓𝜃(𝑥)=𝔼𝑥∼𝐷h𝑓Tr𝜌(𝑥,𝜃)𝑂i(3.1) can be defined, where 𝑂is the measurement operator, and 𝑓denotes a classical post-processing function of the expectation value. Here, 𝜌(𝑥, 𝜃)=|𝜓(𝑥, 𝜃)ih𝜓(𝑥,𝜃)|=𝑈(𝜃)𝑆(𝑥)|0ih0|𝑆(𝑥)†𝑈(𝜃)†, with 𝑆(𝑥)injecting the data 𝑥into the circuit, and 𝑈(𝜃)comprising the learnable circuit parameters. Alternatively, in the Heisenberg picture [122], the data encoding is captured by 𝜌(𝑥)alone, while the parameters are encapsulated in a transformed observable 𝑂𝜃=𝑈(𝜃)†𝑂 𝑈 (𝜃): 𝑓𝜃(𝑥)=𝔼𝑥∼𝐷h𝑓Tr𝜌(𝑥)𝑂𝜃i,(3.2) where 𝜌(𝑥)=𝑆(𝑥)|0i⊗𝑁h0|⊗𝑁𝑆(𝑥)†. In either picture, the cost function is minimized by choosing 𝜃∗=arg min𝜃𝐶(𝜃),(3.3) where 𝜃∗are the optimal parameters of the circuit. Depending on the specific observables and tasks, standard loss functions such as mean squared error or log-likelihood can be adapted to PQC-based scenarios [197]. The outputs of PQC-based models can be interpreted in two primary ways, as shown in Figure 8 [168]: 1. Deterministic models: The observable is measured to obtain a single scalar value (or multiple scalar values if multiple observables are measured). This approach is commonplace in supervised learning settings, leading to variational quantum classifiers [69, 171]. For example, consider an 28 observable 𝑂=Ë𝑁−1 𝑖=0𝜎(𝑖) 𝑧in an 𝑁-qubit system, where 𝑓𝜃(𝑥) ∈ [−1,1]acts analogously to a logistic or linear classifier. Binary classification can then be performed by thresholding: ˆ𝑦=sign𝑓𝜃(𝑥). Such circuits are often regarded as explicit quantum linear models , because they effectively implement linear functions in the induced feature space F[166, 167], i.e., 𝑓𝜃(𝑥)=h𝜙(𝑥),𝑤𝜃iF, with 𝜙(𝑥)representing the data embedding and 𝑤𝜃the learnable parameters. 2. Probabilistic (generative) models: Rather than returning a single scalar, the full probability distribution over computational basis states is considered. For instance, if Π𝑦=|𝑦ih𝑦|are projectors onto basis states, then the model outputs 𝑝(𝑦|𝑥)=Tr𝜌(𝑥)Π𝑦. Such models are relevant for unsupervised learning , serving as generative quantum models, also referred to as Born machines [50]. In certain architectures based on Ising-type Hamiltonians, it has been shown that the distributions realized by these PQCs cannot be efficiently sampled classically, thereby indicating quantum learning supremacy [55]. Figure 8: PQC-based models depicted as (a) deterministic (single scalar observable) and (b) probabilistic/- generative (distribution over basis states). Adapted from [168]. 𝑆(𝑥)denotes the data encoding unitary, and 𝑊(𝜃)the learnable circuit. Both deterministic and probabilistic formulations play essential roles in QML and QRL settings. This thesis explores both perspectives in Chapter 5, where PQC-based agents for RL are analyzed under various modeling assumptions. The remainder of this chapter is divided into four main sections, each addressing a core aspect of VQAs. Section 3.1 focuses on the methods by which classical information can be embedded into a quantum circuit. It examines various encoding strategies, discussing their tradeoffs in terms of circuit depth, resource overhead, and expressivity. Section 3.2 covers strategies to increase the expressive power of PQC-based models. Section 3.3 covers the methods used to train these circuits in practice. It reviews classical optimization algorithms and gradient-based techniques, including how gradients can be estimated on quantum hardware. Lastly, Section 3.4 present one of the most significant obstacles in training PQCs - the BP problem. This section defines the phenomenon, characterizing how gradients can vanish along with strategies to mitigate its effects. 29 CHAPTER 3. VARIATIONAL QUANTUM ALGORITHMS 3.1 Classical data encoding Classical data has historically been encoded into quantum states via amplitude encoding [168], where a feature vector 𝑥=(𝑥0, . . . , 𝑥𝑀−1)is mapped to the amplitudes of a quantum state: |𝑥i=1 k𝑥kÕ 𝑖 𝑥𝑖|𝑖i,(3.4) with k𝑥kas the norm of 𝑥, and |𝑖ithe 𝑖th basis state. If 𝑀is not a power of two, the vector is padded with zeros. Amplitude encoding is particularly useful in fault-tolerant QML algorithms, such as the quantum support vector machine [160], where amplitude-based manipulations are beneficial. However, in PQCbased models, amplitude encoding typically becomes impractical due to the large circuit depth involved: although the number of qubits scales only logarithmically with 𝑀, an exponential number of gates is usually required [168]. An alternative, called unary encoding , was proposed in [98] to reduce circuit depth. Each feature 𝑥𝑖is encoded in the amplitude of a one-hot basis state |00 ···1𝑖···0i, i.e., only those states of Hamming weight one. By restricting the encoding to a smaller subset of basis states, unary encoding can still produce complex, entangled feature maps for certain quantum classification schemes, as shown in a QML-based nearest centroid classifier [98]. It also underlies the design of orthogonal quantum neural networks preserving the Hamming weight [103]. A more direct approach is basis encoding , which transforms data features into binary strings and encodes them into orthogonal basis states. Consequently, all data points become pairwise orthogonal in the Hilbert space, trivially guaranteeing linear separability. However, because every data point is orthogonal to every other, distance-based or inner-product-based algorithms (e.g., SVMs) may not fully exploit this encoding [168]. Another widely employed method in QML is angle encoding , wherein each data component 𝑥𝑖is converted into a single-qubit Pauli rotation, often with a number of qubits scaling linearly in 𝑀[168]. For instance, |𝑥i= 𝑀−1 Ì 𝑖=0 𝑅𝜎𝑖𝑥𝑖|0i,(3.5) where 𝑅𝜎𝑖(𝑥𝑖)=exp𝑖 𝑥𝑖 2𝜎𝑖is the Pauli rotation operator, and 𝜎𝑖is the chosen Pauli matrix (e.g., 𝑋, 𝑌, or 𝑍). One immediate consideration is the periodicity : the model cannot distinguish 𝑥𝑖from 𝑥𝑖+2𝜋, necessitating normalization or preprocessing in many tasks. Despite this, angle encoding is powerful in generating varied data embeddings, since an exponential number of Pauli string combinations (up to O(4𝑁)in the 𝑁-qubit case) might be used. In this setting, the model’s expressivity can be increased by repeating the data encoding steps (often called data reuploading [170, 151]), interleaved with parameterized blocks, as depicted in Figure 9. Perez-Salinas et al. [151] proposed a one-qubit ansatz composed of repetitions of a fundamental gate 𝑈𝑈𝐴𝑇 , named for its relation to the universal approximation theorem 30 3.1. CLASSICAL DATA ENCODING [90]. Specifically, 𝑈𝑈𝐴𝑇 ®𝑥, ®𝑤, 𝛼, 𝜑=𝑅𝑧2®𝑤· ®𝑥+2𝛼𝑅𝑦2𝜑,(3.6) 𝑈𝑥, Θ= 𝐿−1 Ö 𝑘=0 𝑈𝑈𝐴𝑇 ®𝑥, ®𝑤(𝑘), 𝛼(𝑘), 𝜑(𝑘),(3.7) where Θ={®𝑤, 𝛼, 𝜑}𝑘is the collection of trainable parameters and 𝐿denotes the number of repetitions. In the limit 𝐿→ ∞, the circuit can approximate a broad class of functions, thus serving as a universal function approximator in the quantum setting. Multiqubit generalizations incorporate entangling gates between these single-qubit blocks, thus resembling fully connected classical neural networks (see Figure 10). Figure 9: A “series” data reuploading architecture for a single qubit, repeating encoding and parameterized blocks multiple times. Figure 10: A multi-qubit data reuploading scheme. Each repetition interleaves data encoding with parameterized operations, akin to fully connected layers in classical neural networks. Figure source: Pennylane’s tutorial on data reuploading. Although the universal function-approximating property is well-understood for single-qubit architectures, its full generalization to multiqubit systems remains an area of ongoing research [170]. However, the prevailing viewpoint is that a Fourier-based analysis of PQC-based models supports potential universality in multiqubit circuits as well. Data reuploading models generally cannot be expressed as a standard quantum linear model since 𝑓𝜃(𝑥)=Tr[𝜌(𝑥, 𝜃)𝑂𝜃]and data gates appear at multiple layers. In principle, such layering precludes collecting all parameterized gates at the end of the circuit (i.e., commuting everything into a single block). However, Jerbi et al. [95] showed that both approximate and exact linear realizations of data reuploading circuits can be constructed in higher-dimensional Hilbert spaces. For instance, an approximate realization may be achieved by combining basis-encoded features in separate registers, then applying controlled gates to emulate the original data reuploading blocks [Figure 11(a)]. A fully exact linear mapping can also be done using gate teleportation, moving all data-dependent gates into ancillas [Figure 11(b)]. These results highlight that data reuploading circuits, while not trivially linear in the original space, can nonetheless exhibit explicit linearity in a suitably enlarged or modified configuration. 31 CHAPTER 3. VARIATIONAL QUANTUM ALGORITHMS Figure 11: Approximate (left) and exact (right) linear realizations of data reuploading models, using (a) basis encoding and (b) gate teleportation. Adapted from [95]. Overall, the choice of data encoding significantly influences the representational power and trainability of quantum models. The next sections explore the expressivity of PQC-based models and the challenges in optimizing them, including phenomena such as BPs. 3.2 Expressivity of quantum machine learning models In Subsection 2.5, the expressivity of PQCs was discussed in terms of Hilbert space coverage : circuits that more closely approximate a Haar-random unitary are deemed more expressive. However, in the context of machine learning, a data-dependent notion of expressivity is required, one that explicitly characterizes the family of functions a PQC-based model can generate to fit given data. Indeed, any PQC-based model can be written as a truncated Fourier series [170]. For the simplest case of one-dimensional data 𝑥, a PQC-based function can be expressed as 𝑓𝜃(𝑥)=Õ 𝑤∈Ω 𝑐𝑤(𝜃)exp𝑖 𝑤 𝑥,(3.8) where the frequency set Ωis finite and 𝑐𝑤(𝜃)=𝑐𝑤(𝜃)∗. As a concrete example, consider a data reuploading model of the form 𝑈(𝑥, 𝜃)=𝑊𝜃𝐿𝐿−1 Ö 𝑘=0 𝑆(𝑥)𝑊𝜃𝑘(3.9) acting on 𝑁qubits. Here, 𝑆(𝑥)is an encoding unitary, which can often be viewed as 𝑆(𝑥)=exp𝑖 𝑥 𝐻 , with 𝐻an 𝑁-qubit Hermitian matrix of dimension 𝑑≤2𝑁. Without loss of generality, 𝐻may be taken to be diagonal (or unitarily transformed into a diagonal form). As illustrated in Figure 12, repeated application of such diagonal encodings, followed by parameterized unitaries 𝑊(𝜃𝑘), yields terms that commute in their exponential expansions, giving rise to sums of exponentials of eigenvalue sums. When 𝑆(𝑥)is diagonal, the amplitudes of the final quantum state amount to products of exponentials of the form 𝑒𝑖 𝜆𝑗𝑥, and these exponentials commute. For instance, the 𝑖th entry of 𝑈(𝑥, 𝜃)|0i𝑖can be written as a sum over products of exponentials, 𝑈(𝑥, 𝜃)|0i𝑖= 𝑑 Õ 𝑗1,...,𝑗𝐿=1 exph−𝑖𝜆𝑗1+···+𝜆𝑗𝐿𝑥i×𝑊(𝐿+1) 𝑖 𝑗𝐿··· 𝑊(2) 𝑗2𝑗1𝑊(1) 𝑗11,(3.10) 32 3.4. THE BARREN PLATEAU PHENOMENON 3.4 The barren plateau phenomenon To estimate gradients while reusing the quantum device via parameter-shift rules (Subsection 3.3) is indeed a valuable feature for PQC-based models. However, compared with classical backpropagation, parameter-shift typically does not achieve equally favorable scaling, particularly as the number of parameters grows. Moreover, even if gradients can be obtained efficiently, a further challenge arises in the form of BPs, where the training landscape becomes exponentially flat with respect to the number of qubits, thereby hindering optimization at scale. Figure 14 illustrates the flattening effect. Figure 14: Barren plateaus and the flattening of the training landscape for random parameterized quantum circuits as a function of the number of qubits. Image source: Machine Learning with Quantum Computers by Schuld et al. [168]. The investigation of BPs in the training landscape is often referred to as the trainability analysis of PQC models. In this setting, gradients are averaged over a random sampling of parameters 𝜃. In a BP the average gradient is zero. However, examining the average gradient alone is insufficient; the second moment (variance) of these gradients must also be considered to ascertain how quickly these fluctuate, and how are they concentrating near their average value of zero. BPs tend to arise whenever the circuit effectively “scrambles” information, for example by being sufficiently deep or using global measurements [127], by operating under noisy conditions [201], or by generating states with high entanglement entropy in relation to another system [124]. The underlying causes of this phenomenon will be explored, beginning with the seminal work of McClean et,al. [127] and extending to more recent advances. For a PQC-based cost function 𝐶(𝜃)=h0|𝑉(𝜃)†𝑂 𝑉 (𝜃)|0i,(3.27) the variance of the partial derivative with respect to a parameter 𝜇is expressed as 𝕍(𝜕𝜇𝐶(𝜃)) =h𝜕𝜇𝐶(𝜃)2i𝑉− h𝜕𝜇𝐶(𝜃)i2 𝑉,(3.28) where the expectation is taken over the unitaries 𝑉(𝜃)in the ansatz. In a BP, h𝜕𝜇𝐶(𝜃)i =0and the variance decays exponentially with the system size 𝑁, which means that the partial derivative concentrates 39 CHAPTER 3. VARIATIONAL QUANTUM ALGORITHMS exponentially around zero as the number of qubits grows. Because the variance vanishes exponentially in 𝑁, an exponentially growing number of shots is necessary to distinguish directions in the landscape, causing the optimizer to perform a random walk [127]. Arrasmith et al. [12] showed that BPs are equivalent to the cost function itself “concentrating,” rather than merely the partial derivative, i.e., 𝕍(𝜕𝜇𝐶(𝜃)) ∈ O1 𝛼𝑁=⇒𝕍𝐶(𝜃+𝜎) −𝐶(𝜃)∈ O1 𝛼𝑁.(3.29) Hence, BPs affect not only gradient-based, but also gradient-free methods [11], and error mitigation alone does not resolve them [200]. The question then arises as to which unitaries 𝑉(𝜃)yield vanishing gradients. In the seminal work by McClean et al. [127], the assumption was that 𝑉(𝜃)is sampled from the Haar distribution (Subsection 2.5). Because the variance is a second moment, the result is valid for unitary 2-designs (i.e., expectations appear Haar-like up to second order, see Definition 3.4.1). Definition 3.4.1 (Unitary 𝑡-design).A probability distribution Dover the unitary group U(𝑑)(where 𝑑 is the dimension of the Hilbert space) is called a unitary 𝑡 -design if it reproduces the moments of the Haar measure up to order 𝑡. Concretely, for any polynomial 𝑝of degree up to 𝑡in the matrix elements of 𝑈 and 𝑈†, the average of 𝑝under Dmatches that under the Haar distribution up to the 𝑡-th moment. By splitting 𝑉(𝜃)into left/right unitaries 𝑈𝐿,𝑈𝑅around a single-parameter gate 𝐺(𝜇), McClean et al. showed that 𝕍(𝜕𝜇𝐶(𝜃)) ∈ O(2−𝑁),(3.30) provided that at least one of 𝑈𝐿or 𝑈𝑅is a 2-design. This analysis did not constrain the measurement observable nor the input state, considering a global observable acting on all qubits. In practice, unitaries in most ansatz constructions follow a periodic structure : 𝑉(𝜃)= 𝐿−1 Ö 𝑙=0 𝑈(𝜃𝑙)𝑊𝑙,(3.31) where each layer 𝑈(𝜃𝑙)is parameterized, and 𝑊𝑙is a 𝜃-independent unitary repeated 𝐿times. Cerezo et al. [42] later showed that prior results can differ under local measurements, so BPs also depend on circuit depth: local measurements on sufficiently deep entangled circuits effectively behave as global. In particular, when local 2-designs (i.e., each layer is a 2-design) are combined with local measurements, a favorable trainable region is observed at logarithmic depth, as illustrated in Figure 15. When log(𝑁)qubits are measured topologically, the partial-derivative variance vanishes polynomially in 𝑁, 𝕍(𝜕𝜇𝐶(𝜃)) ∈ Ω1 poly(𝑁),(3.32) under log(N)-depth conditions, thus enabling a trainable region where only a polynomial number of shots is required. At depth O(poly(log(𝑁))), the decay outpaces any polynomial but remains subexponential, 𝕍(𝜕𝜇𝐶(𝜃)) ∈ Ω1 2poly(log(𝑁)).(3.33) 40 3.4. THE BARREN PLATEAU PHENOMENON Figure 15: Trainability region as a function of circuit depth. Image source: Cost function dependent barren plateaus in shallow quantum neural networks by Cerezo et al. [42]. Rudolph et al. [162] extended this result to algebraically local (or low-bodied ) observables. In deeper circuits forming a 2-design, local measurements effectively act as global ones. In many ML tasks, data is first encoded into a (possibly entangled) quantum state, which can introduce BPs even if the subsequent ansatz is simple or even form a product state [197]. Leone et al. [114] posited that hardware-efficient circuits with area-law entangled data states can be promising for demonstrating quantum advantage, but remain subject to a “deadly triad” of circuit expressivity, global measurements, and entangled encoding states. Ragone et al. [158] proposed a unifying Lie-algebraic framework, shown in Figure 16, that accounts for these major BP sources. In that work, it was shown that if 𝑂∈𝑖𝔤or 𝜌∈𝑖𝔤(with 𝔤as the DLA from Definition 3.2.1), then the mean of the loss function vanishes over semisimple components 𝔤1⊕ ··· ⊕𝔤𝑘−1, and the variance behaves as: 𝕍𝜽𝐶(𝜃)= 𝑘−1 Õ 𝑗=1 P𝔤𝑗(𝜌)P𝔤𝑗(𝑂) dim(𝔤𝑗),(3.34) where P𝔤𝑗(𝜌)and P𝔤𝑗(𝑂)denote the purity of 𝜌and 𝑂restricted to subalgebra 𝔤𝑗. This result excludes 41 CHAPTER 3. VARIATIONAL QUANTUM ALGORITHMS Figure 16: Unified theory of barren plateaus connecting multiple prior results. Image source: A Unified Theory of Barren Plateaus for Deep Parametrized Quantum Circuits by Ragone et al. [158]. states or measurements outside the DLA, but an exponentially large dim(𝔤)can still induce expressivitybased BPs [43] i.e. dim(𝔤)=𝛼𝑛, 𝛼 >1=⇒𝕍𝜽ℓ𝜽(𝜌,𝑂)∈ O1 𝛼𝑛.(3.35) By contrast, polynomially large DLAs alone do not necessarily produce BPs; the input state and measurement determine whether those arise. Equation 3.34 further provides exact expressions for the variance in the assumption that the circuit forms a 2-design at sufficient depth. 𝜖approximate 2-designs are generated when the number of parameterized blocks 𝐿satisfies 𝐿≥log(1/𝜖) log(1/k𝐴k2),(3.36) where k𝐴k2is the Hilbert–Schmidt norm characterizing how much the second moments of one circuit layer deviate from Haar (cf. Algorithm 1). A single layer already forms a 2-design if k𝐴k2=0. Such 𝑡-design assumptions do not usually hold in practice. Letcher et al. [115] derived tight loss and gradient bounds for broad classes of PQCs and arbitrary observables, without relying on 𝑡-design arguments. For a circuit obeying Equation (3.31) and any 𝐻=Í𝑖𝛼𝑖𝑃𝑖with 𝑃𝑖∈ {𝐼, 𝑋, 𝑌, 𝑍 }𝑁, every Pauli term contributes independently to the variance: 𝕍𝜃[𝐶(𝜃)] =Õ 𝑖 𝛼2 𝑖𝕍𝜃[𝐶(𝜃)𝑖] where each contribution is tightly bounded by Ω(𝜌)𝔼𝜃h1 4Δ𝜃 𝑖i≤𝕍𝜃𝐶(𝜃)𝑖≤𝔼𝜃h1 2Δ𝜃 𝑖i,(3.37) where Δ𝜃 𝑖is the backwards light-cone of 𝑃𝑖, i.e. the number of qubits on which 𝑈†(𝜃)𝑃𝑖𝑈(𝜃)acts nontrivially, and Ω(𝜌)=Õ 𝑖 Tr𝑃𝑖𝜌2 represents a measure of orthogonality that quantifies the portion of 𝜌orthogonal to the first layer of rotations. 42 3.4. THE BARREN PLATEAU PHENOMENON Several strategies have been explored to mitigate BPs, including layerwise learning [187], specialized parameter initializations [78, 210, 164], and carefully designed shallow-depth architectures [154]. Nonetheless, Cerezo et al. [44] proved that while certain restrictive approaches may avoid BPs, they often render the model classically simulable, complicating efforts to achieve quantum advantage. Yet, a contrived example was also provided, indicating that “smarter initializations” might enable powerful, nonclassically simulable PQC-based models. Crucially, all these BP results hold independently of a ML objective, as most bounds are derived under a linear expectation-value cost without explicit data. Thanasilp et al. [197] found that standard ML losses, such as mean squared error and log-likelihood , do not significantly alter BP behavior, although data encoding can introduce additional complexity. Moreover, far less is known about how data reuploading affects the trainability of models. On one hand, it may enable faster entry into the overparameterized regime and mitigate spurious minima [111], but on the other, it also increases the model’s overall expressivity and depth, which is known to exacerbate BPs. Furthermore, circuits with exponentially large DLAs generally require an exponential number of parameters to reach overparameterization, thus necessitating significant depth that leads to a 2-design, flattening the training landscape. How to balance the expressive power introduced by data reuploading with guaranteed trainability still remains an open question. 43 Chapter 4 Reinforcement learning The supervised learning framework of machine learning can be interpreted as having an agent learn from a teacher that knows the correct answer to every question— labels . Therefore, the agent is usually limited to the amount of knowledge imposed by the teacher and cannot easily surpass or properly answer questions outside the mentor’s expertise. Reinforcement Learning (RL), on the other hand, removes the teacher and lets the student—referred to as the agent —learn by interacting with the environment, which ultimately captures the consequences of the agent’s actions. This different learning paradigm brings us closer to general artificial intelligent agents [182]. Crucially, it closely reflects how humans actually learn, being strongly inspired by biological models of learning [194]. RL is responsible for major breakthroughs in artificial intelligence, such as the famous AlphaZero [181], which beat the world champion of Go, or MuZero [165], which generalized the algorithm to other complex environments. More recently, RL has been used to solve complex problems outside of games and provide solutions to real-world challenges, such as faster matrix multiplication and sorting algorithms [70, 123], quantum feedback control [73], quantum circuit optimization [72], and more. In this chapter, we introduce the basic concepts of RL and the main algorithms used in the field and covered in this work. We begin with the mathematical foundations of RL in Subsection 4.1. Then, we present the concepts of policies, value functions, and how the agent can achieve optimal behavior in Subsection 4.2. Afterwards, we explore approximation algorithms for estimating value functions and policies in Subsections 4.3 and 4.4, respectively. 4.1 Foundations The RL paradigm consists of two entities: the Agent and the Environment , forming the well-known AgentEnvironment interface [194], as illustrated in Figure 17. In this setting, the agent learns directly from 44 4.1. FOUNDATIONS interactions with its surrounding environment, without requiring supervision or complete models of the environment. Figure 17: Agent-Environment interface. Image adapted from Reinforcement Learning: An introduction by Sutton et al. [194]. 𝑂𝑡,𝐴𝑡, and 𝑅𝑡are the observation, action, and reward of the agent at time step 𝑡. Let 𝑆and 𝐴be the space of all possible states and actions defined for a given environment, respectively. At time step 𝑡, the agent observes the state of the environment 𝑂𝑡, which can be a partial observation of the true state 𝑠𝑡∈𝑆(e.g., the current state in a game of poker, where the agent observes only the cards on the table without information about the remaining cards). Given such a state, the action set can be state-dependent, so the agent selects an action 𝑎𝑡from the set of available actions for that state, 𝐴𝑜𝑡. This action alters the environment’s state. Indeed, such actions can have deterministic or stochastic outcomes. For instance, in chess, an action always leads to the same resulting state, whereas a cleaning robot that performs a forward motion action might slip and end up in a different state than intended. Thus, in general, the environment is described by a transition function that captures the dynamics of the environment as a probability distribution over the possible next states, given the current action and state of the environment, 𝑝(𝑠𝑡+1|𝑠𝑡, 𝑎𝑡), such that Í𝑠𝑡+1𝑝(𝑠𝑡+1|𝑠𝑡, 𝑎𝑡)=1. Since this information is encoded in the environment, the agent does not have access to it. Every time the agent performs an action, it observes the new state 𝑠𝑡+1of the environment and receives a reward 𝑟𝑡+1. The reward is a scalar value that quantifies the immediate benefit of the action taken by the agent. The way the reward is delivered varies with the environment, as the reward can be state-dependent and/or state-action-dependent. Nonetheless, since the reward is the feedback of the action taken, the main goal of the agent is to maximize the expected reward . The multi-armed bandit (MAB) environment is perhaps the simplest environment. In this setting, there are 𝑘slot machines that the agent may choose from. We can interpret the MAB as a stateless environment since the agent pulls one of the 𝑘arms, receives a reward, and moves to the next time step, corresponding effectively to the same state. The agent’s goal is to learn the best arm to pull in order to maximize the expected reward. However, in most practical learning scenarios, tasks are more complicated since the agent will indeed be performing actions in a continuing task with multiple states. In that case, the agent is faced with the concept of delayed reward : it must learn how to balance immediate and long-term rewards. Indeed, the agent should look ahead before making a decision, but not too far into the future. Rewards can be penalized or discounted by a discount factor 𝛾∈ [0,1]that weighs future rewards such that immediate reward weighs more than rewards farther into the future: 45 CHAPTER 4. REINFORCEMENT LEARNING 𝐺𝑡=∞ Õ 𝑘=0 𝛾𝑘𝑟𝑡+𝑘+1.(4.1) 𝐺𝑡is also known as the return of the agent—the cumulative discounted reward the agent gets starting at time step 𝑡. Thus, considering 0≤𝛾<1ensures that the return is finite even for infinitely long trajectories. In practice, a task is usually truncated with a finite horizon 𝑇, 𝐺𝑡= 𝑇−𝑡−1 Õ 𝑘=0 𝛾𝑘𝑟𝑡+𝑘+1,(4.2) where the effective horizon depends entirely on the discount factor𝛾used for the task. Typically,𝑇effective = O( 1 1−𝛾)[6]. The discount factor influences the policy, which in turn influences the environment, which influences the data the agent actually sees during training. This is a challenging problem since the agent must learn how to balance exploration and exploitation. The agent must explore the environment to learn its dynamics and exploit the knowledge it has to maximize the expected reward. This is also known as the exploration-exploitation dilemma , as illustrated in Figure 18. Figure 18: Exploration-Exploitation dilemma. Image from the UC Berkeley AI course. The agent must not explore at all times, since that would effectively reduce to a brute-force search. On the other hand, the agent must not exploit at all times, or it would not learn the environment’s dynamics, potentially sticking to a suboptimal policy. Therefore, a proper balance between exploration and exploitation is essential, and so is the design of the policy under which actions are performed in the environment. The mathematical framework behind an RL problem is the Markov Decision Process (Markov Decision Process (MDP)), which encapsulates such sequential decision-making problems in the environment’s formulation. It can be viewed as a directed graph where nodes are possible states of the environment, and edges represent the transition function for a given state-action pair. This graph is extended with the reward function associated with state or state-action pairs, as illustrated in Figure 19. 46 4.1. FOUNDATIONS Figure 19: Racing car MDP. Image from the UC Berkeley AI course. The MDP is represented with a set of states 𝑆={Cool,Warm,Overheated}and a set of actions 𝐴={Slow,Fast}. The reward function in this environment depends on state-action pairs. The environment is thus assumed to be Markovian, respecting the Markov property — the future is independent of the past given the present : 𝑝(𝑠𝑡+1|𝑠0, . . . ,𝑠𝑡)=𝑝(𝑠𝑡+1|𝑠𝑡).(4.3) An MDP is a tuple (𝑆, 𝐴, 𝑃, 𝑅,𝛾)where 𝑆is the set of states, 𝐴is the set of actions, 𝑃is the transition function, 𝑅is the reward function, and 𝛾is the discount factor. The MDP serves as a model of the environment, which the agent uses to learn the optimal policy 𝜋∗that maximizes the expected return. The policy 𝜋:𝑆→𝐴maps states to actions. Typically, the policy is interpreted as deterministic once the agent knows which action is optimal in a given state. In general, however, the policy will be a probability distribution over the set of available actions for each state, 𝜋(𝑎|𝑠), also denoted as 𝜋(𝑎|𝑠)=𝑝(𝑎𝑡=𝑎|𝑠𝑡=𝑠).(4.4) The optimal policy 𝜋∗can indeed be stochastic , for instance, in settings where the environment can only be partially observed. Nevertheless, in a fully observed environment, there always exists an optimal deterministic policy [193]. As the agent follows a policy by interacting with the environment, it sequentially collects (or generates) trajectories 𝜏of states, actions, and rewards, 𝜏=(𝑠0, 𝑎0,𝑟1,𝑠1, 𝑎1, 𝑟2, . . . , 𝑠𝑇).(4.5) Therefore, the agent experiences a trajectory with probability 𝑝(𝜏)= 𝑇−1 Ö 𝑡=0 𝜋(𝑎𝑡|𝑠𝑡)𝑝(𝑠𝑡+1|𝑠𝑡, 𝑎𝑡).(4.6) 47 CHAPTER 4. REINFORCEMENT LEARNING It is also crucial to note two main paradigms in RL: model-based and model-free RL. In the former, the agent has access to or learns the environment’s dynamics. Here, RL reduces to planning in large stateaction spaces where dynamic programming is exploited [194]. In the latter, which is the most common scenario in RL, the agent does not have access to the environment’s dynamics. It must learn the optimal policy by interacting with the environment—usually from the reward provided as feedback. Many advanced RL algorithms combine both paradigms, often in simulation-based settings, where experience can be gathered via standard trial-and-error while also learning a model of the world to perform optimal planning [165]. In practice, however, we may not wish to learn the environment’s model (e.g., because it might be unnecessary or too complicated). Model-free RL is generally the most versatile paradigm, enabling learning of optimal behaviors for diverse environments without needing to learn the environment’s dynamics, as long as the cost of environment sampling is not too high. In this work, we focus on model-free RL algorithms and thus will not cover model-based RL algorithms, referring the reader to [194] for a comprehensive introduction to that topic. 4.2 Value functions and optimal behavior To learn without knowing the environment’s dynamics, understanding the role of value functions is crucial. These functions estimate the expected return of the agent, starting from a given state and following a given policy, and thus quantify how beneficial it is for the agent to be in a certain state or to perform a certain action in that state. The state-value function 𝑉𝜋(𝑠)for a state 𝑠∈𝑆is the expected return, starting from state 𝑠and following policy 𝜋over a horizon 𝑇: 𝑉𝜋(𝑠)=𝔼𝜋[𝐺𝑡|𝑠𝑡=𝑠]=𝔼𝜋h𝑇−𝑡−1 Õ 𝑘=0 𝛾𝑘𝑟𝑡+𝑘+1𝑠𝑡=𝑠i.(4.7) Similarly, the action-value function 𝑄𝜋(𝑠, 𝑎)for a state-action pair (𝑠, 𝑎) ∈ 𝑆×𝐴is the expected return starting from state 𝑠, taking action 𝑎, and following policy 𝜋for a horizon 𝑇: 𝑄𝜋(𝑠, 𝑎)=𝔼𝜋[𝐺𝑡|𝑠𝑡=𝑠, 𝑎𝑡=𝑎]=𝔼𝜋h𝑇−𝑡−1 Õ 𝑘=0 𝛾𝑘𝑟𝑡+𝑘+1𝑠𝑡=𝑠, 𝑎𝑡=𝑎i.(4.8) These value functions are vital for determining optimal behavior. They can be defined recursively, forming the well-known Bellman equations : 48 4.3. VALUE-BASED METHODS Figure 22: Cartpole environment. Image adapted from Grokking Deep Reinforcement Learning by Morales et al. [139]. The agent must balance the pole by moving the cart left or right. Cartpole is a well-known environment [19] in which the agent applies left or right impulses to keep the pole balanced. Thus, the action space is small, but the state space—represented by the cart’s position, velocity, the pole’s angle, and angular velocity—is continuous. A lookup table for all state-action pairs is thus infeasible. Multiple solutions have been studied in RL to address this curse of dimensionality —for example, abstraction [6] and dimensionality reduction [189]. One widely successful approach is to use function approximators for the action-value function, commonly via Neural Networks since they are universal function approximators [77]. This combination of Deep Learning and RL is known as Deep Reinforcement Learning [139]. In this setting, the action-value function is parameterized by a neural network 𝑄(𝑠, 𝑎;𝜃). We then seek to learn the parameter vector 𝜃∗that approximates the optimal action-value function 𝑄∗(𝑠, 𝑎). This network is called a Deep Q-Network (DQN) [136]. Figure 23 shows an abstract DQN for Cartpole. Figure 23: Deep Q-Network for the Cartpole environment. Image adapted from Grokking Deep Reinforcement Learning by Morales et al. [139]. The agent encodes the state into the network, which outputs the action-value for each action. Parameterized models allow a single forward pass to estimate the action-value function for all actions, as 55 CHAPTER 4. REINFORCEMENT LEARNING in Figure 23. Importantly, for 𝜃∈ℝ𝑘, we desire 𝑘 |𝑆||𝐴|, so the model generalizes effectively to unseen states. Otherwise, we revert to something close to the tabular regime. In this context, the TD update rule (Equation (4.22)) is modified for gradient-based updates. The loss function becomes the mean squared error between the TD target and the network prediction: L(𝜃)=𝔼h𝑟+𝛾max 𝑎0𝑄(𝑠0, 𝑎0;𝜃) −𝑄(𝑠, 𝑎;𝜃)2i,(4.23) where the expectation is over transitions (𝑠, 𝑎, 𝑟, 𝑠0)sampled from the environment. The gradient of L with respect to 𝜃updates the network via 𝜃←𝜃−𝜂𝔼h𝑟+𝛾max 𝑎0𝑄(𝑠0, 𝑎0;𝜃) −𝑄(𝑠, 𝑎;𝜃)∇𝜃𝑄(𝑠, 𝑎;𝜃)i,(4.24) where the target remains constant for the gradient step. Whereas tabular Q-learning updates a single entry in isolation, parameterized models propagate the update through shared weights, allowing them to learn correlations between states and actions and discover complex, nonlinear relationships. However, convergence is not guaranteed with parameterized models—indeed, the algorithm can be unstable or even diverge. One source of instability is that gradient-descent requires independent and identically distributed (i.i.d.) data and stationary targets, while in RL the data is non-i.i.d. (as it comes from a changing policy) and the targets are ever-shifting (the estimates themselves improve over time). One popular approach to mitigate these issues is experience replay combined with a target network [136]. Experience replay stores transitions (𝑠, 𝑎, 𝑟, 𝑠0)in a replay buffer and samples mini-batches to update the network, breaking correlation between samples. A target network is a copy of the original network used to compute the target max𝑎0𝑄(𝑠0, 𝑎0;𝜃−)with parameters 𝜃−that are periodically synced with 𝜃. This stabilizes training by reducing the non-stationarity of the target. Pseudocode is presented in Algorithm 3. Various refinements have been proposed to further stabilize training or reduce dependence on the target network [14]. Nonetheless, the ultimate goal of an RL agent is to learn the optimal policy directly. We now turn to policy-based methods , which enable the agent to learn a parameterized policy without needing to estimate action values first. 56 4.4. POLICY GRADIENT METHODS Algorithm 3: Deep Q-Learning Input: Behavior policy 𝜋, learning rate 𝜂, horizon 𝑇, environment env. Initialize 𝑄(𝑠, 𝑎;𝜃); initialize target network 𝑄(𝑠, 𝑎;𝜃−); initialize replay buffer D; target update frequency 𝐶. Output: Approximation to optimal action-value function 𝑄∗(𝑠, 𝑎). 1while not converged do 2𝑠=𝑠0 3for 𝑡=0. . .𝑇 −1do 4𝑎∼𝜋(· | 𝑠,𝜃) 5𝑠0,𝑟 =env(𝑠, 𝑎) 6D ← D ∪ (𝑠, 𝑎, 𝑟, 𝑠0) 7B ← sample(D) 8for (𝑠, 𝑎, 𝑟, 𝑠0) ∈ B do // Update network 9𝜃←𝜃−𝜂𝔼Bh𝑟+𝛾max𝑎0𝑄(𝑠0, 𝑎0;𝜃−) −𝑄(𝑠, 𝑎;𝜃)∇𝜃𝑄(𝑠, 𝑎;𝜃)i 10 if 𝑡mod 𝐶=0then 11 𝜃−←𝜃// Update target network 12 𝑠←𝑠0 4.4 Policy gradient methods Let us consider the long corridor environment in Figure 24, with several states in a long chain. The agent starts an episode in a randomly chosen state along the chain and aims to reach one of the goal states located at the ends of the chain as quickly as possible. Each time step spent in a non-goal state has a reward of −1, while the goal states have zero reward. The agent has two actions, 𝐴={move right,move left}. Figure 24: Long corridor environment. The agent starts in one of the middle states. The optimal policy in the exact middle state is stochastic, with a 50/50 chance of going left or right, while states to the immediate left/right of the middle have deterministic preferred directions. Because the chain is symmetric, the optimal policy in the middle state of the chain is stochastic. Indeed, moving left or right yields the same reward. Also observe that the environment’s structure makes it questionable whether a value-based approach is efficient, since for the middle state, one simply needs to pick randomly. More important, many partially observed environments naturally benefit from a stochastic policy. Finally, some environments have continuous action spaces. For example, a continuous version of Cartpole allows a continuum of torques to be applied to the cart. Estimating values for all possible actions is daunting or impossible. Even for large but discrete action sets, the necessary max𝑎0operation can scale 57 CHAPTER 4. REINFORCEMENT LEARNING poorly. Directly learning a policy that removes the maximization step might be preferable. Policy-based methods optimize a parameterized policy directly. Among them, policy gradients [195] are widely used. Here, the policy 𝜋(𝑎|𝑠, 𝜃)is differentiable in 𝜃, and we use gradient-based optimization to learn 𝜃∗, maximizing expected return and yielding the optimal policy. For example, consider a parameterized softmax policy like in Subsection 4.1. A tabular form might be: 𝜋(𝑎|𝑠, 𝜃)=exp𝜃𝑠,𝑎 Í𝑎0exp𝜃𝑠,𝑎0,(4.25) where 𝜃∈ℝ|𝑆||𝐴|. However, this is not very expressive. More commonly, one uses neural networks, e.g., 𝜋(𝑎|𝑠, 𝜃)=expℎ(𝑠, 𝑎, 𝜃) Í𝑎0expℎ(𝑠, 𝑎0,𝜃),(4.26) where ℎ(𝑠, 𝑎, 𝜃)is the network’s “preference” for (𝑠, 𝑎). Note that 𝜋is differentiable. For deterministic policies, the gradient can vanish. Hence, a sufficiently expressive parameterization that yields a welldefined gradient for all actions is preferred. Here, we shift the objective from value-based methods to maximizing the expected return directly with respect to 𝜃. This is on-policy , as the agent’s policy fully determines the data it collects. To compute ∇𝜃𝐽(𝜃)of the policy’s performance, we use the policy gradient theorem [194]. For a simplified derivation [57], let 𝑝𝜃(𝜏)be the trajectory probability under 𝜋(· | 𝑠, 𝜃): 𝑝𝜃(𝜏)= 𝑇−1 Ö 𝑡=0 𝑝(𝑠𝑡+1|𝑠𝑡, 𝑎𝑡)𝜋(𝑎𝑡|𝑠𝑡, 𝜃).(4.27) Then the expected return is 𝐽(𝜃)=Õ 𝜏 𝑝𝜃(𝜏)𝐺(𝜏),(4.28) where 𝐺(𝜏)is the trajectory’s return (cumulative discounted reward). Its gradient is: 58 4.4. POLICY GRADIENT METHODS ∇𝜃𝐽(𝜃)=Õ 𝜏∇𝜃𝑝𝜃(𝜏)𝐺(𝜏) =Õ 𝜏 𝑝𝜃(𝜏)∇𝜃log 𝑝𝜃(𝜏)𝐺(𝜏),(4.29) using the log-likelihood trick ∇𝜃𝑝𝜃(𝜏)=𝑝𝜃(𝜏)∇𝜃log 𝑝𝜃(𝜏). Next, ∇𝜃log 𝑝𝜃(𝜏)=∇𝜃 𝑇−1 Õ 𝑡=0 log 𝑝(𝑠𝑡+1|𝑠𝑡, 𝑎𝑡)𝜋(𝑎𝑡|𝑠𝑡, 𝜃) = 𝑇−1 Õ 𝑡=0∇𝜃log 𝜋(𝑎𝑡|𝑠𝑡, 𝜃),(4.30) since the transition probabilities do not depend on 𝜃. Substituting into Equation (4.29), we get: ∇𝜃𝐽(𝜃)=Õ 𝜏 𝑝𝜃(𝜏) 𝑇−1 Õ 𝑡=0∇𝜃log 𝜋(𝑎𝑡|𝑠𝑡, 𝜃)𝐺(𝜏)=𝔼𝜏∼𝑝𝜃(𝜏)h𝑇−1 Õ 𝑡=0∇𝜃log 𝜋(𝑎𝑡|𝑠𝑡, 𝜃)𝐺(𝜏)i. (4.31) Hence, the gradient of the expected return is the expected value (under the policy) of the log-policy gradient multiplied by return. This allows an empirical gradient estimate from sampled trajectories: ∇𝜃𝐽(𝜃) ≈ 1 𝑁 𝑁 Õ 𝑖=1 𝑇−1 Õ 𝑡=0∇𝜃log 𝜋(𝑎𝑖 𝑡|𝑠𝑖 𝑡,𝜃)𝐺(𝜏𝑖),(4.32) where (𝑎𝑖 𝑡,𝑠𝑖 𝑡)is the action and state in trajectory 𝑖. Equation (4.32) is the foundation of the REINFORCE algorithm [207]. Gradient ascent on 𝜃then follows: 𝜃←𝜃+𝜂∇𝜃𝐽(𝜃),(4.33) where 𝜂is the learning rate. In practice, variance is often reduced by subtracting from 𝐺(𝜏𝑖)a statedependent baseline 𝑏(𝑠𝑡): ∇𝜃𝐽(𝜃) ≈ 1 𝑁 𝑁 Õ 𝑖=1 𝑇−1 Õ 𝑡=0∇𝜃log 𝜋𝑎𝑖 𝑡|𝑠𝑖 𝑡,𝜃𝐺(𝜏𝑖) −𝑏(𝑠𝑖 𝑡).(4.34) 59 CHAPTER 4. REINFORCEMENT LEARNING The baseline is often an estimate of the state-value function or the average discounted reward of that state. Algorithm 4 summarizes REINFORCE. Algorithm 4: REINFORCE Input: Policy 𝜋(· | 𝑠, 𝜃), learning rate 𝜂, number of trajectories 𝑁, horizon 𝑇, environment env. Initialize policy parameters 𝜃. Output: Approximation to the optimal policy 𝜋∗. 1while not converged do 2for 𝑖=1. . . 𝑁 do 3𝑠=𝑠0 4for 𝑡=0. . .𝑇 −1do 5𝑎∼𝜋(· | 𝑠,𝜃) 6𝑠0,𝑟 =env(𝑠, 𝑎) 7𝜏𝑖←𝜏𝑖∪ (𝑠, 𝑎, 𝑟, 𝑠0) 8𝑠←𝑠0 9for 𝑖=1. . . 𝑁 do 10 for 𝑡=0. . .𝑇 −1do 11 𝜃←𝜃+𝜂1 𝑁Í𝑁 𝑖=1Í𝑇−1 𝑡=0∇𝜃log 𝜋𝑎𝑖 𝑡|𝑠𝑖 𝑡,𝜃𝐺(𝜏𝑖) −𝑏(𝑠𝑖 𝑡) REINFORCE is a foundational algorithm in RL and can be implemented in only a few lines. However, it is sample-inefficient, requiring many trajectories to form a low-variance gradient estimate. Moreover, performance is sensitive to the baseline choice. Often the baseline is learned with a neural network, giving rise to Actor-Critic methods [107], which combine policy gradient with a learned value function. Actor-Critic methods underlie many of today’s best-performing RL algorithms, such as Proximal Policy Optimization (PPO) [173], widely used in industry (e.g., training of GPT [36]). Recall there are many ways to parameterize 𝜋. In classical RL, a parameterized softmax policy is most common. Its gradient expression can be expanded: ∇𝜃log 𝜋(𝑎|𝑠,𝜃)=∇𝜃log expℎ(𝑠, 𝑎, 𝜃) Í𝑎0expℎ(𝑠, 𝑎0,𝜃) =∇𝜃ℎ(𝑠, 𝑎, 𝜃) − Õ 𝑎0 𝜋(𝑎0|𝑠, 𝜃)∇𝜃ℎ(𝑠, 𝑎0,𝜃),(4.35) i.e., the gradient is the gradient of the action’s preference minus the average gradient weighted by 𝜋. Notice that one could incorporate an “inverse temperature” to tune exploration, but typically, one allows the policy to learn stochastic or near-deterministic behavior directly. Still, neural networks might collapse to a deterministic policy prematurely, hampering exploration. Entropy regularization [135] is often added to the objective, 60 4.4. POLICY GRADIENT METHODS 𝐻𝜃(𝜋)=−Õ 𝑎 𝜋(𝑎|𝑠, 𝜃)log 𝜋(𝑎|𝑠, 𝜃),(4.36) and the policy optimization objective becomes 𝐽(𝜃)=𝔼𝜏∼𝑝𝜃(𝜏)h𝑇−1 Õ 𝑡=0∇𝜃log 𝜋(𝑎𝑡|𝑠𝑡, 𝜃)𝐺(𝜏) −𝑏(𝑠𝑡)+𝛽 𝐻𝜃(𝜋)i,(4.37) where 𝛽is an entropy coefficient encouraging stochasticity. This can yield faster training and improved stability [8]. 4.4.1 Natural Policy Gradients and Trust Regions Several strategies improve policy optimization convergence. One theoretically grounded approach is to use natural gradients [9] within the policy optimization framework, leading to Natural Policy Gradients (NPG) [100]. The idea is to precondition ∇𝜃𝐽(𝜃)by the (classical) CFIM, capturing the sensitivity of the distribution 𝜋to parameter changes. Formally, 𝐼(𝜃)=𝔼𝑠∼𝑑𝜋𝜃, 𝑎∼𝜋(·|𝑠,𝜃)h∇𝜃log 𝜋(𝑎|𝑠, 𝜃)∇𝜃log 𝜋(𝑎|𝑠, 𝜃)𝑇i,(4.38) where 𝑑𝜋𝜃is the state-visitation distribution under 𝜋𝜃. Then ∇𝜃𝐽(𝜃)can be adapted to 𝜃←𝜃+𝜂 𝐼−1(𝜃)∇𝜃𝐽(𝜃),(4.39) which is the natural policy gradient . While ∇𝜃𝐽(𝜃)is in Euclidean space, natural gradients measure changes in the “information geometry” of the parameter space, often improving convergence [100]. However, computing and inverting 𝐼(𝜃)at each step is expensive when 𝜃is high-dimensional. Hence, various approximations and heuristics have been developed. One concept is to ensure the new policy remains close (in KL-divergence) to the old one, forming a trust region [174]. In standard policy gradient, a single gradient step can drastically alter 𝜋. A Trust Region Policy Optimization (TRPO) approach restricts the change in 𝜋by bounding the KL distance from the old policy: max 𝜃𝐽(𝜃)subject to 𝐷𝐾𝐿𝜋𝜃old 𝜋𝜃≤𝛿. (4.40) 61 CHAPTER 4. REINFORCEMENT LEARNING Approximating the KL constraint quadratically yields an analytic solution akin to NPG, with an adaptive step size dependent on 𝛿. The policy update under NPG can be summarized as 𝜃←𝜃+s2𝛿 ∇𝜃𝐽𝑇 𝜃old 𝐼(𝜃)∇𝜃𝐽𝜃old 𝐼−1(𝜃)∇𝜃𝐽(𝜃).(4.41) This guarantees the policy improvement is monotonic. Algorithm 5 shows a high-level outline of NPG. Algorithm 5: Natural Policy Gradient Input: Policy 𝜋, policy divergence 𝛿, learning rate 𝜂, number of trajectories 𝑁, horizon 𝑇, environment env. Initialize policy parameters 𝜃. Output: Approximation to the optimal policy 𝜋∗. 1while not converged do 2for 𝑖=1. . . 𝑁 do 3𝑠=𝑠0 4for 𝑡=0. . .𝑇 −1do 5𝑎∼𝜋(· | 𝑠,𝜃) 6𝑠0,𝑟 =env(𝑠, 𝑎) 7𝜏𝑖←𝜏𝑖∪ (𝑠, 𝑎, 𝑟, 𝑠0) 8𝑠←𝑠0 // Policy update with NPG step 9for 𝑖=1. . . 𝑁 do 10 for 𝑡=0. . .𝑇 −1do 11 𝜃←𝜃+r2𝛿 ∇𝜃𝐽𝑇 𝜃old 𝐼(𝜃)∇𝜃𝐽𝜃old 𝐼−1(𝜃)∇𝜃𝐽(𝜃) In practice, the TRPO optimization problem can be tackled via an unconstrained version with a KL penalty: 𝜃𝑡+1=2 max 𝜃h𝐽(𝜃) − 𝛽 𝐷𝐾𝐿𝜋𝜃old 𝜋𝜃i,(4.42) where 𝛽is a KL penalty factor. However, picking 𝛽is nontrivial. Proximal Policy Optimization (PPO) [173] tackles this by defining a clipped surrogate objective that maintains a monotonic improvement guarantee. PPO is the backbone of many state-of-the-art RL agents [139, 173], though it is out of scope here. 62 4.5. EVALUATION AND PERFORMANCE OF REINFORCEMENT LEARNING AGENTS 4.5 Evaluation and performance of Reinforcement Learning agents Several strategies are used to assess and compare RL agents. In practice, the most common metric is the average reward under the agent’s policy. Thus, we often empirically evaluate performance by plotting moving averages of cumulative rewards over episodes or time steps, as shown in Figure 25. Figure 25: Performance of various RL agents using different policy optimization algorithms, plotted against the number of policy iterations. Image from Trust Region Policy Optimization by Schulman et al. [174]. In finite-horizon environments, there is often a clear “solved” criterion. For instance, in the Cartpole environment (Subsection 4.2), the agent receives +1 per time step, with a maximum of 200 (or 500). The environment is considered solved if the agent achieves the maximum reward for 100 consecutive episodes. Hence, a moving average of rewards can reveal how quickly each agent converges. In more open-ended tasks, we still use such plots to see which agent obtains higher reward within a certain training budget. From a theoretical perspective, performance is usually analyzed via sample complexity [101], also referred to in RL as the number of state-action visits required to achieve a near-optimal policy, often measured through regret . The regret is the difference between the reward the agent collects and the reward an oracle optimal agent would collect: R𝑇=𝔼h𝑁−1 Õ 𝑛=0𝑉∗(𝑠𝑘 0) − 𝑉𝜋(𝑠𝑘 0)i,(4.43) 63 CHAPTER 4. REINFORCEMENT LEARNING where 𝑇=𝑁𝐻 for horizon 𝐻, and the expectation is over the environment and the agent’s sampling. RL algorithms can be highly data-hungry. Under general assumptions, sample efficiency is difficult; many algorithms have complexity exponential in the horizon |𝑆||𝐴|𝐻[101]. NPG (Algorithm 5) is a core RL method with solid convergence properties. Agarwal et al. [7] show it has logarithmic regret in terms of the total number of environment actions for suitable parameterized policies. Regret Lemma (Lemma 6.2) from [7] will be used later in the context of PQC-based policies, so we restate it for completeness. First, a concept called compatible function approximation [195] is needed. Let 𝑓𝑤(𝑠, 𝑎)approximate the advantage function 𝐴(𝑠, 𝑎). Then: 𝜓(𝑠, 𝑎)=∇𝜃log 𝜋(𝑎|𝑠, 𝜃), 𝑓𝑤(𝑠, 𝑎)=𝑤𝑇𝜓(𝑠, 𝑎).(4.44) 𝑓𝑤is said to be “compatible” with 𝜋because the corresponding policy gradient is still exact [195]. That is, the linear model 𝑓𝑤uses ∇𝜃log 𝜋(𝑎|𝑠,𝜃)as features, which can be beneficial in actor-critic setups. Also, let 𝑤∗minimize the squared error 𝑤∗=2 min 𝑤 𝔼𝑠∼˜ 𝑑, 𝑎∼e𝜋(·|𝑠)𝐴(𝑠, 𝑎) −𝑤𝑇∇𝜃log 𝜋(𝑎|𝑠,𝜃)2,(4.45) where ˜ 𝑑and e𝜋are reference state distribution and policy. Kakade [100] showed the optimum satisfies 𝑤∗=𝐹−1∇𝜃log 𝜋(𝑎|𝑠,𝜃),(4.46) where 𝐹is the Fisher information matrix. The Regret Lemma 4.5.1 leverages this. Lemma 4.5.1 (NPG Regret Lemma [7]). Fix a comparison policy ˜𝜋 and a state distribution 𝜌 . Assume for all 𝑠∈ S and 𝑎∈ A that log 𝜋(𝑎|𝑠, 𝜃) is 𝛽 -smooth in 𝜃 . Consider 𝜋(0) as the uniform distribution over actions at each state, and let 𝑤(0), . . . ,𝑤(𝑇) be the sequence of weights with k𝑤(𝑡)k2≤𝑊 . Define the approximation error at time 𝑡 : 𝜖𝑡=𝔼𝑠∼˜ 𝑑, 𝑎∼e𝜋(·|𝑠)𝐴(𝑡)(𝑠, 𝑎) −𝑤(𝑡)·∇𝜃log 𝜋(𝑡)(𝑎|𝑠). 64 5.1. PARAMETERIZED QUANTUM POLICIES where models with data reuploading are converted to 𝑈(𝑠, 𝜃)reup =𝑊(𝜃0) 𝐿 Ö 𝑙=1 𝑆(𝑠)𝑊(𝜃𝑙)(5.8) Here, 𝜃𝑙∈ℝ𝑘is the vector of parameters within layer 𝑙.𝑊(𝜃𝑙)is usually decomposed into a sequence of single-qubit and two-qubit parameterized gates to control expressivity and reduce the number of trainable parameters. These models allow us to consider hardware-efficient ansätze (HEA) that are suitable for near-term VQAs due to their low-depth structure, resulting in lower-noise circuits. Additionally, 𝑤(𝜃𝑙)is usually followed by a series of unparameterized gates (CNOT/CZ gates) acting on neighboring qubits to include entanglement into the system. The neighboring condition is usually considered to accommodate qubit connectivity within the hardware, thus saving heavier swap operations, as illustrated in Figure 28. Figure 28: Long range CNOT gate decomposed with swap gates in a device supporting nearest neighbor connectivity. The neighboring condition can be lifted, once considering all-to-all qubit connectivity to accommodate more complex entanglement patterns. Additionally, the entanglement itself should also be tuned to the problem at hand by considering parameterized gates instead of fixing the entanglement pattern via unparameterized CNOT/CZ gates. However, in this work, we consider single-qubit parameterized gates to avoid the burden of decomposing two-qubit gates that lead to circuits with increased depth. Moreover, with single-qubit parameterized gates we allow less expressive circuits that are also easier to train via gradient optimization (See Subsection 3.4). In the context of model-free RL, we do not have access to the environment’s model and do not possess feature engineering tools. That is, the agent can only see the current state it is in but does not know how the features are correlated. Therefore, one approach to designing an ansatz is to consider arbitrary parameterized single-qubit gates with unparameterized gates exploring both shortand long-range correlations in the input data. As an example, consider three layers of the Strongly Entangling Circuit [171], as illustrated in Figure 29. 71 CHAPTER 5. QUANTUM POLICY GRADIENTS Figure 29: Strongly Entangling Circuit proposed in [171], composed of three layers. The Strongly Entangling Circuit is composed of arbitrary parameterized single-qubit gates 𝐺(𝜃𝑙 𝑖)where 𝜃𝑙 𝑖∈ℝ3is the parameter vector for the decomposition of the gate acting on qubit 𝑖in layer 𝑙. For instance, the decomposition can be 𝐺(𝜃𝑙 𝑖)=𝑅𝑧(𝜃𝑙 𝑖,0)𝑅𝑦(𝜃𝑙 𝑖,1)𝑅𝑧(𝜃𝑙 𝑖,2). Qubits are then entangled with the controls of the CNOT gates acting chronologically on the 𝑁qubits, 𝑗={0, . . . , 𝑁 −1}, and the target qubit derived through (𝑖+𝑟)mod 𝑁, where 𝑟is the range of the control. It has been shown that this way, all qubits with numbers that are a multiple of gcd(𝑁,𝑟)can be entangled with a controllable number of gates. Furthermore, such an ansatz uses significantly fewer CNOT/CZ gates (O(𝑁𝐿)) compared to a standard all-to-all entanglement pattern that uses 𝑁 𝑘𝐿=𝑁! 𝑘!(𝑁−𝑘)!𝐿gates and tries to entangle all qubits already at the first layer. Any PQC considered in other forms of learning can, in theory, also be considered in RL. The crucial aspect in the design of a PQC-based policy is the measurement scheme. Recall that we intend to use the PQC as a policy generator for the agent. Thus, we need to be able to generate a classical probability distribution over the action space. 5.1.1 Discrete action spaces Let us assume that the action space is discrete and composed of |𝐴|actions. The simplest approach is to resort to the Born rule of quantum mechanics (see Subsection ??) and use the Pauli-Z measurement to obtain a probability distribution over the computational basis states. Suppose we have a PQC 𝜌𝑠𝑡,𝜃 =|𝜓(𝑠𝑡,𝜃)ih𝜓(𝑠𝑡, 𝜃)| encoding the state of the agent at time step 𝑡. Let |𝐴|=2𝑁. In this setting, the 𝑎th basis state, where 𝑎∈ {0,1,2, . . . , 2𝑁−1}, can be associated with action 𝑎∈𝐴. Therefore, the policy can be estimated directly from the expectation value, 𝜋(𝑎|𝑠𝑡,𝜃)=Tr𝜌𝑠𝑡,𝜃𝑂𝑎(5.9) 72 5.1. PARAMETERIZED QUANTUM POLICIES where 𝑂𝑎=|𝑎ih𝑎|is the projector onto the 𝑎th basis state. The policy can then be used to sample actions 𝑎∼𝜋(·|𝑠𝑡,𝜃)and interact with the classical environment. Notice, however, that this approach works only for the case |𝐴|=2𝑁, which is not always the case. Indeed, the number of qubits present in the circuit depends not only on the number of actions but also on the number of features in the encoding state. If we consider single-qubit angle encoding of features, then the number of qubits 𝑁is equal to the number of features 𝑁=|𝑠𝑡|. However, in this setting, we have three distinct cases depending on the number of actions: 1. |𝐴|=2𝑁— The number of actions is equal to the number of basis states. In this case, the policy can be directly estimated from the expectation value as in Equation (5.9). 2. |𝐴|>2𝑁— The number of actions is greater than the number of basis states. In this case, the number of qubits present in the system is not sufficient. The number of qubits should be increased, besides the number of features, to accommodate the number of actions. 3. |𝐴|<2𝑁— The number of actions is less than the number of basis states. In this case, we have to consider a partition of the basis states into |𝐴|groups. Notice that the measurement itself does not need to be restricted to the computational basis. Indeed, we can consider any set of eigenstates of arbitrary Hermitian observables. Therefore, in the most general form, let us denote the Born policy , obtained from the probability of measuring a partition of the eigenstates of an observable, as in Definition 5.1.1. Definition 5.1.1. (Born policy) Let 𝑠∈ S be a state embedded in an 𝑛-qubit parameterized quantum state, 𝜌𝑠,𝜃 =|𝜓(𝑠, 𝜃)ih𝜓(𝑠, 𝜃)|, where 𝜃∈ℝ𝑘. The probability associated with a given action 𝑎∈𝐴in the Born framework is given by: 𝜋(𝑎|𝑠, 𝜃)=Tr𝜌𝑠,𝜃 𝑃𝑎(5.10) where 𝑃𝑎=Í𝑣∈𝑉𝑎|𝑣ih𝑣|is the projector into a partition 𝑉𝑎⊆𝑉of |𝑉𝑎|eigenstates of an observable 𝑂= 2𝑁−1 Õ 𝑖=0 𝜆𝑖|𝑖ih𝑖|.(5.11) Moreover, Ð𝑎∈𝐴𝑉𝑎=𝑉and 𝑉𝑎∩𝑉𝑎0=∅. Definition 5.1.1 accommodates the most general version of the Born policy. The main difficulty resorts to the partition function. Indeed, finding the optimal partitioning of basis states into groups of actions is extremely challenging. Furthermore, in practice, we need strategies to distinguish actions without resorting to the actual probability vector in order to make the algorithm efficient, since we would need to store a number of elements that increases exponentially with the number of qubits. One way is to consider the bitstrings that result from the measurement of the quantum state. Then we need a post-processing 73 CHAPTER 5. QUANTUM POLICY GRADIENTS function that maps the bitstring to the correct action group encoding the partition function. That way, the policy can be estimated with shot-based learning, as illustrated in Figure 30. Figure 30: Agent-environment interface with PQC-based policy using shot-based learning. The policy is estimated at each time step from the measurement outcomes using a post-processing function 𝑓that maps a bitstring to the action group. Let us define the post-processing function 𝑓:{0,1}𝑁→ {0,1, . . . , |𝐴| −1}that maps the bitstring to the action group. For a number of measurements 𝐶, the shot-based Born policy is estimated as 𝜋(𝑎|𝑠𝑡,𝜃)=1 𝐶 𝐶−1 Õ 𝑐=0 𝛿𝑓(𝑏𝑐)=𝑎(5.12) where 𝑏𝑐is the bitstring obtained from the 𝑐th measurement. Interestingly, note that, considering the post-processing function 𝑓, the action at time-step 𝑡can be obtained with a single shot. However, recall that for the policy optimization step (i.e., to optimize 𝜃), one needs to estimate 𝜕𝜃log 𝜋(𝑎|𝑠, 𝜃), which does require knowledge of the actual probability vector 𝜋(𝑎|𝑠, 𝜃). Hence, more shots would generally be needed to estimate the gradient accurately. Despite gradient optimization, there is a multitude of post-processing functions, each leading to a different policy. It is crucial to note that the partitioning function is ultimately linked with the amount of information extracted from the policy, which is in turn linked to the number of qubits we need to measure. Let us ignore, for now, the extreme case of |𝐴|=2𝑁, since in that scenario the policy is a one-to-one mapping. Instead, focus on the case |𝐴|<2𝑁. In this setting, we need clever assignments for the measured bitstrings, so the post-processing function indeed plays a significant role. Recall that information theory provides a fundamental way to determine the lower bound on the number of bits required to encode information through the concept of entropy, which quantifies the average amount of information produced by a stochastic source of data. Since we need to distinguish between |𝐴|<2𝑁 74 5.1. PARAMETERIZED QUANTUM POLICIES actions, the lower bound on the number of bits necessary is log |𝐴|. It is not possible to work with fewer bits. Therefore, the theoretical minimum leads to log |𝐴|qubits being measured. Nonetheless, there are still 𝑁 log |𝐴|possible partitions with the same amount of extracted information. As an example, let us consider the RL base case where the number of actions |𝐴|=2. In this case, a single bit is necessary to discern between the two actions. Let the number of qubits be 𝑁=3again. Figure 31 illustrates three alternative partition functions. Figure 31: Three possible partition functions that attain the lower bound of 1 bit for |𝐴|=2and 𝑁=3, illustrated as a uniform distribution over all 23basis states. Figures (a),(b) and (c) represent the partition functions obtained from measuring qubits 𝑖,𝑗, and 𝑘respectively, highlighted in red in the figure. In general, for an 𝑁-qubit system, a contiguous-like partitioning of the basis states can be generated followed by the measurement of log |𝐴| adjacent qubits, as defined in Definition 5.1.2. Definition 5.1.2. (Contiguous-like Born policy) Let 𝑠∈ S be a state embedded in an 𝑁-qubit parameterized quantum state, 𝜌𝑠,𝜃 =|𝜓(𝑠,𝜃)ih𝜓(𝑠, 𝜃)|, where 𝜃∈ℝ𝑘. Let w.l.g |𝐴|<2𝑁be the number of actions. The contiguous-like Born policy is given by 𝜋(𝑎|𝑠, 𝜃)=Tr𝜌𝑠,𝜃 𝑃𝑎(5.13) where 𝑃𝑎=Í𝑣∈𝑉𝑎|𝑣ih𝑣|is the projector onto a partition 𝑉𝑎⊆𝑉of |𝑉𝑎|generated from the measurement of log |𝐴|adjacent qubits—where adjacency here means numerical adjacency in the binary representation of the basis states. The Contiguous-like Born policy forms the lower bound on the globality of the measurement operator. Indeed, there are other partitions with more extracted information. In theory, the upper bound is 𝑁 qubits. For |𝐴|=2actions, one could, for instance, consider two of the 2𝑁basis states and normalize their probabilities to form the policy. For instance, 75 CHAPTER 5. QUANTUM POLICY GRADIENTS 𝜋(𝑎0|𝑠, 𝜃)=Tr𝜌𝑠,𝜃 𝑃𝑎0 Tr𝜌𝑠,𝜃 𝑃𝑎0+Tr𝜌𝑠,𝜃 𝑃𝑎1(5.14) 𝜋(𝑎1|𝑠, 𝜃)=Tr𝜌𝑠,𝜃 𝑃𝑎1 Tr𝜌𝑠,𝜃 𝑃𝑎0+Tr𝜌𝑠,𝜃 𝑃𝑎1(5.15) where 𝑃𝑎𝑖=|𝑎𝑖ih𝑎𝑖|is the projector onto the 𝑎th 𝑖basis state, as in Definition 5.1.3. Definition 5.1.3. (Action-projector-like Born policy) Let 𝑠∈ S be a state embedded in an 𝑁-qubit parameterized quantum state, 𝜌𝑠,𝜃 =|𝜓(𝑠, 𝜃)ih𝜓(𝑠, 𝜃)|, where 𝜃∈ℝ𝑘. Let |𝐴|<2𝑁be the number of actions. The action-projector-like Born policy is given by 𝜋(𝑎|𝑠, 𝜃)=Tr𝜌𝑠,𝜃 𝑃𝑎 Í𝑎0∈𝐴Tr𝜌𝑠,𝜃 𝑃𝑎0(5.16) where 𝑃𝑎=|𝑎ih𝑎|is the projector onto the 𝑎th basis state. The action-projector-like Born policy is characterized by an 𝑁-local measurement. However, the policy is highly inefficient, particularly when the number of qubits is significantly larger than the number of actions (𝑁 |𝐴|). In this case, despite having a global measurement (which attains the upper bound on the information), it is itself detrimental in terms of policy optimization. This is because the probability of measuring one of the basis states is vanishing exponentially with the number of qubits, requiring an exponential number of shots to estimate the policy faithfully. In essence, for a large number of qubits, we would likely never witness the eigenstate of interest. We need partition functions that balance the information extracted and do not discard the vast majority of the basis states. For instance, one can consider the Hamming distance between the bitstring and the action group usually used in cryptographic protocols. This way, we would be considering a larger number of basis states compared with the action-projector-like policy. An immediate problem in this case would be a limitation to a maximum of |𝐴|=𝑁+1possible actions. Consider the case 𝑁=3qubits once more. In this scenario, we could generate the following partitions: 𝑉0={000}(5.17) 𝑉1={001,010,100}(5.18) 𝑉2={011,101,110}(5.19) 𝑉3={111}(5.20) The Hamming distance policy is defined in Definition 5.1.4. 76 5.1. PARAMETERIZED QUANTUM POLICIES Definition 5.1.4. (Hamming-like Born policy) Let 𝑠∈ S be a state embedded in an 𝑁-qubit parameterized quantum state, 𝜌𝑠,𝜃 =|𝜓(𝑠,𝜃)ih𝜓(𝑠, 𝜃)|, where 𝜃∈ℝ𝑘. Let w.l.g |𝐴| ≤ 𝑁+1be the number of actions. The Hamming-like Born policy is given by 𝜋(𝑎|𝑠, 𝜃)=Tr𝜌𝑠,𝜃 𝑃𝑎(5.21) where 𝑃𝑎=Í𝑣∈𝑉𝑎|𝑣ih𝑣|is the projector onto a partition 𝑉𝑎⊆𝑉of |𝑉𝑎|generated from eigenstates 𝑣 with Hamming weight 𝑎. Besides the limitation on the number of actions, the Hamming-like Born policy generates uneven distributions, i.e., giving different priorities to different basis states. For instance, Hamming weight 0 would always consider just the all-zero basis state. This is not ideal since the policy would be highly biased toward states with larger Hamming weights, making the action 𝑎0less explored in the environment while also being more difficult to optimize, as its probability becomes exponentially small with the number of qubits. While the Hamming-like policy produces uneven distributions and limits the size of the action space, one can still leverage the Hamming weight idea to form a different 𝑁-local policy. For the base case |𝐴|=2, we can consider a parity post-processing function, which is simply a Hamming weight mod2 of the bitstring. Thus, the policy is represented as: 𝜋(𝑎|𝑠, 𝜃)=⊕𝑏=𝑎 Õ 𝑏∈{0,1}𝑛h𝜓(𝑠, 𝜃)|𝑏ih𝑏|𝜓(𝑠, 𝜃)i (5.22) where 𝑎∈ {0,1}. Such an assignment constitutes a global measurement, and the authors of [132] showed that it corresponds to the assignment that maximizes the extracted information. Notice that instead of the Pauli-Z measurement on every qubit, one could instead measure either a single-qubit or an ancilla, as illustrated in Figure 32. Figure 32: Decomposition of a global measurement using a single-qubit measurement. 77 CHAPTER 5. QUANTUM POLICY GRADIENTS For an arbitrary number of actions |𝐴| ≤ 2𝑁, provided that |𝐴|is a power of two, a recursive parity function can be applied to the bitstring to discern among actions, as proposed by Meyer et al. [132]. Let 𝑚=log |𝐴|be the number of recursive calls and 𝒃be an 𝑛-bit bitstring measured through sampling from the PQC. Then, the partition can be defined recursively as C(𝑚) [𝑎]2=(𝒃| 𝑛−1 Ê 𝑖=𝑚 𝑏𝑖=𝑎0∧𝒃∈ C(𝑚−1) 𝑎𝑚···𝑎2(𝑎1⊕𝑎0))(5.23) where [𝑎]2=𝑎𝑚. . . 𝑎0is the binary expansion of action 𝑎. Since we require each of the 𝑛bits for computing the parity, a parity-based policy will be composed of a global measurement (or 𝑛-local) for |𝐴|=2as the base case. Thus, it will always be global regardless of the number of actions. The parity-like Born policy is defined in Definition 5.1.5. Definition 5.1.5. (Parity-like Born policy) Let 𝑠∈ S be a state embedded in an 𝑁-qubit parameterized quantum state, 𝜌𝑠,𝜃 =|𝜓(𝑠, 𝜃)ih𝜓(𝑠, 𝜃)|, where 𝜃∈ℝ𝑘. Let |𝐴| ≤ 2𝑁be the number of actions and a power of two. Let 𝑚=log |𝐴|be the number of recursive calls. The Parity-like Born policy is given by: 𝜋(𝑎|𝑠, 𝜃)=Tr𝜌𝑠,𝜃 𝑃𝑎(5.24) where 𝑃𝑎=Í𝑣∈𝑉𝑎|𝑣ih𝑣|is the projector onto a partition 𝑉𝑎⊆𝑉of |𝑉𝑎|generated from eigenstates respecting the recursive partition C(𝑚) [𝑎]2=(𝒃| 𝑛−1 Ê 𝑖=𝑚 𝑏𝑖=𝑎0∧𝒃∈ C(𝑚−1) 𝑎𝑚···𝑎2(𝑎1⊕𝑎0)).(5.25) A wide range of post-processing functions can be applied to a Born policy. In this work, we focus on the policy formulations discussed above, which are summarized in Table 1. Born policy Measurement operator Output distribution Contiguous-like log |𝐴|-local (adjacent qubits) Even distribution but lower bound on information. Action-projector-like 𝑁-local Even distribution and upper bound on information, but exponentially hard to estimate. Hamming-like 𝑁-local Upper bound on information, but uneven distribution. Parity-like 𝑁-local Even distribution and upper bound on information for |𝐴|a power of two. Table 1: Characteristics of different types of Born policies. 78 5.1. PARAMETERIZED QUANTUM POLICIES Each Born policy has its own advantages and disadvantages, as summarized in Table 1. However, every Born policy shares a common limitation: none can properly adjust its greediness. Recall that in RL, the agent needs to balance exploration and exploitation. Stochastic policies are desired for their exploratory behavior. However, for the vast majority of the environments designed as MDPs, the agent needs at some point to converge to a deterministic optimal policy in which the agent knows the best strategy to exploit the environment and maximize the reward. In classical RL, we introduced the Softmax policy with a greediness control hyperparameter (see Subsection 4.2). In the quantum setting, one can apply the non-linear Softmax activation to the output distribution of any of the Born policies to add a control over its greediness. Let h𝑃𝑎i𝑠,𝜃 be the expectation value of the projector 𝑃𝑎resulting from any Born policy. The Softmax policy can be defined as 𝜋(𝑎|𝑠, 𝜃)=𝑒𝛽h𝑃𝑎i𝑠,𝜃 Í𝑎0∈𝐴𝑒𝛽h𝑃𝑎0i𝑠,𝜃 (5.26) where 𝛽=1 𝜏is the inverse temperature parameter that controls the greediness of the policy. Nevertheless, recall that it is an extremely challenging task to find an optimal annealing schedule since this is often problem-dependent. Therefore, in practice, the greediness should be controlled or learned automatically by the policy’s parameterization using experience from the environment. Furthermore, notice that the softmax function normalizes the vector it receives as input to form a probability distribution. As a consequence, we do not need to consider strictly non-negative inputs derived from the Born rule of quantum mechanics but can generalize it to the expectation value of arbitrary Hermitian operators. Let h𝑂𝑎i𝑠,𝜃 be the expectation value of a Hermitian observable 𝑂𝑎that encodes the preference of action 𝑎. A PQC-based Softmax policy can be defined as in Definition 5.1.6. Definition 5.1.6. (Softmax policy) Let 𝑠∈ S be a state embedded in an 𝑁-qubit parameterized quantum state, 𝜌𝑠,𝜃 =|𝜓(𝑠, 𝜃)ih𝜓(𝑠, 𝜃)|, where 𝜃∈ℝ𝑘. Let 𝑂𝑎be an arbitrary Hermitian observable and the expectation value h𝑂𝑎i𝑠,𝜃 =Tr𝜌𝑠,𝜃𝑂𝑎(5.27) represent the numerical preference of action 𝑎∈𝐴. The probability associated with the action is given by: 𝜋(𝑎|𝑠, 𝜃)=𝑒h𝑂𝑎i𝑠,𝜃 Í𝑎0𝑒h𝑂𝑎0i𝑠,𝜃 .(5.28) The Softmax policy allows one to consider O(|𝐴|) different observables. Thus, it varies significantly from any of the Born policies defined previously, allowing, in theory, greater expressive power. There are, 79 CHAPTER 5. QUANTUM POLICY GRADIENTS however, several components that play a role in the expressivity of the PQC-based policy. This is covered in greater detail in Section 5.2. 5.1.2 Continuous action spaces Let us now consider continuous action spaces, i.e., the action space is a subset of ℝ𝑑. Neither the Born nor the Softmax policies proposed in Subsection 5.1.1 can be directly applied to continuous action spaces. One can, however, discretize the action space and apply the same policies as before, but this is not practical since the number of actions would be too large, thus enforcing an exponential number of measurements to faithfully estimate the policy. Therefore, we need to consider a different approach. One simple strategy is to use the PQC to learn the optimal parameters of a Gaussian distribution —namely the mean and variance . Gaussian policies provide a natural and flexible way to represent continuous actions because they can model a wide range of behaviors through the manipulation of their parameters (mean and variance). The mean (𝜇) shifts the center of the distribution, directing the likely actions, while the variance (𝜎2) adjusts the exploration level by controlling the distribution’s spread around the mean. Figure 33 illustrates the effect of changing the mean and variance of a Gaussian distribution, producing different policies. Figure 33: Effect of changing the mean and variance of a Gaussian distribution. Therefore, the probability density function of a PQC-based Gaussian policy is given by 𝜋(𝑎|𝑠, 𝜃)=1 p2𝜋𝜎 (𝑠, 𝜃)2exp−(𝑎−𝜇(𝑠, 𝜃))2 2𝜎(𝑠, 𝜃)2,(5.29) where the probability is given by the integral of the probability density function over the action space. 80 5.2. EXPRESSIVITY Figure 36: Softmax policy with (a) a single observable for every action with one output scaling parameter per action, and (b) one output scaling parameter for every action with different observables. Notice that the total number of trainable parameters has increased significantly. The output scaling alone can depend on the total number of actions. Recall that function approximation is only worthwhile provided that the number of parameters does not exceed |𝑆||𝐴|. In intermediate domains—those not containing too large action spaces—it could be feasible to consider a single output scaling parameter for every action. As an example, consider the Cartpole environment once more. In this setting |𝐴|=2. There is an evident correlation between the two actions; therefore, considering a single-output scaling is sufficient, as that parameter changes both actions simultaneously. However, for environments with larger action spaces, the behavior is not entirely clear. For that reason, we need to inspect the gradient behavior to properly address this question. This is done in Section 5.3. Despite these hurdles, recall that so far we have explored the role of the output scaling just for the PQCbased Softmax policy. Indeed, adaptive greediness control in the form of output scaling for the Born policy is not possible. This helps us conclude that the Softmax policy can be more expressive and malleable to a wider range of environments. The applicability of input and output scaling in both PQC-based policies is summarized in Table 2. Policy Input scaling Output scaling Born 3 7 Softmax 3𝑊∈ℝor 𝑊∈ℝ|𝐴| Table 2: Applicability of input and output scaling in PQC-based policies. 87 CHAPTER 5. QUANTUM POLICY GRADIENTS 5.3 Gradient estimation The policy improvement step in the policy gradient formalism is based on gradient-based optimization. Indeed, gradient ascent is performed on the expected return with respect to the policy parameters. Recall that the foundational REINFORCE algorithm (see Algorithm 4) performs gradient ascent on the log likelihood weighted by the cumulative reward as 𝜃←𝜃+𝜂∇𝜃𝐽(𝜃)where ∇𝜃𝐽(𝜃)=1 𝑁 𝑁−1 Õ 𝑖=0 𝑇−1 Õ 𝑡=0∇𝜃log 𝜋(𝑎𝑖 𝑡|𝑠𝑖 𝑡,𝜃)𝐺(𝜏𝑖)(5.44) for 𝑁episodes of horizon 𝑇, where 𝜂is the learning rate. Therefore, to use the PQC-based policies proposed in Section 5.1, we need to be able to efficiently estimate the gradient of the log policy. If the model itself is being simulated on a classical device, it can be considered like any other classical parameterized model, and the gradient can be estimated using automatic differentiation. However, with a real quantum device, gradients must be estimated on the device itself, and thus the policy gradient must be expressed in a form where parameter-shift rules (see Subsection 3.3) can be applied. Fortunately, parameter-shifts can still be used through the chain rule of calculus. 5.3.1 Gradient recipes Let us start with Born policies (see Definition 5.1.1). In general, the Born policy is represented with a PQC 𝜌𝑠,𝜆,𝜃 =|𝜓(𝑠, 𝜆, 𝜃)ih𝜓(𝑠, 𝜆,𝜃)| and a partition function 𝑃𝑎for action 𝑎. Gradients are required to be estimated for input scaling parameters 𝜆and weights 𝜃. The gradient of the log policy is expressed by ∇𝜃log 𝜋(𝑎|𝑠,𝜃)=1 𝜋(𝑎|𝑠, 𝜃)∇𝜃𝜋(𝑎|𝑠, 𝜃) =1 2𝜋(𝑎|𝑠, 𝜃)Tr𝜌𝑠,𝜆,𝜃+𝜋 2𝑃𝑎−Tr𝜌𝑠,𝜆,𝜃−𝜋 2𝑃𝑎(5.45) with the parameter-shift applied to the data-encoding-independent gates. Similarly, for input scaling parameters, ∇𝜆log 𝜋(𝑎|𝑠, 𝜃)=1 2𝜋(𝑎|𝑠, 𝜃)Tr𝜌𝑠,𝜆+𝜋 2,𝜃 𝑃𝑎−Tr𝜌𝑠,𝜆−𝜋 2,𝜃 𝑃𝑎.(5.46) Therefore, the gradient vector of the log policy for a Born policy can be estimated using two more expectation value estimations for each parameter. Recall that the denominator 𝜋(𝑎|𝑠, 𝜃)is already estimated for policy evaluations and sampling, so it does not contribute to the computational cost of gradient estimation. In essence, the partial derivative can be estimated up to error 𝜖using O(𝜖−2)shots. Notice 88 5.3. GRADIENT ESTIMATION that 𝜋(𝑎|𝑠, 𝜃)cannot be zero since in the context of policy gradients we are estimating the gradient of the policy entry that was selected based on sampling. If the action was sampled from the distribution, the probability is greater than zero. However, the probability can be arbitrarily close to zero. Therefore, we see that for Born policies, the gradient is unbounded , which can lead to numerical instability, as we discuss in Chapter 6. Let us now turn our attention to the PQC-based Softmax policy. Softmax policies (see Definition 5.1.6), in their general form, can depend on a set of three parameters {𝜃, 𝜆,𝑤}, where 𝜃are the weights of the parameterized gates, 𝜆are the input scaling parameters, and 𝑤is the output scaling parameter. For simplicity of analysis, let us ignore the inverse temperature hyperparameter since it is untrainable and provides only a constant scaling factor to the gradient. Let the softmax policy be represented as 𝜋(𝑎|𝑠, 𝜃, 𝜆,𝑤)=𝑒𝑤h𝑂𝑎i𝑠,𝜃,𝜆 Í𝑎0𝑒𝑤h𝑂𝑎0i𝑠,𝜃,𝜆 .(5.47) Then, the gradient of the log policy can be obtained as a function of the expectation values estimated with the quantum device, by expanding the log policy operator (as we did in Equation 4.35): ∇𝜃log 𝜋(𝑎|𝑠,𝜃, 𝜆,𝑤)=∇𝜃log 𝑒𝑤h𝑂𝑎i𝑠,𝜃,𝜆 Í𝑎0𝑒𝑤h𝑂𝑎0i𝑠,𝜃,𝜆 =∇𝜃𝑤h𝑂𝑎i𝑠,𝜃,𝜆 −log Õ 𝑎0 𝑒𝑤h𝑂𝑎0i𝑠,𝜃,𝜆  =𝑤∇𝜃h𝑂𝑎i𝑠,𝜃,𝜆 −Í𝑎0𝑒𝑤h𝑂𝑎0i𝑠,𝜃,𝜆 ∇𝜃h𝑂𝑎0i𝑠,𝜃,𝜆 Í𝑎0𝑒𝑤h𝑂𝑎0i𝑠,𝜃,𝜆 =𝑤∇𝜃h𝑂𝑎i𝑠,𝜃,𝜆 −Õ 𝑎0 𝑤∇𝜃h𝑂𝑎0i𝑠,𝜃,𝜆 𝜋(𝑎0|𝑠, 𝜃, 𝜆,𝑤).(5.48) As opposed to the Born policy, the gradient depends on every action’s expectation value and on the policy itself. Similarly, for the input scaling parameters, ∇𝜆log 𝜋(𝑎|𝑠, 𝜃, 𝜆,𝑤)=𝑤∇𝜆h𝑂𝑎i𝑠,𝜃,𝜆 −Õ 𝑎0 𝑤∇𝜆h𝑂𝑎0i𝑠,𝜃,𝜆 𝜋(𝑎0|𝑠,𝜃, 𝜆, 𝑤),(5.49) where for parameters {𝜃, 𝜆}the gradient of the expectation value can be estimated through parametershift rules: 89 CHAPTER 5. QUANTUM POLICY GRADIENTS ∇𝜃h𝑂𝑎i𝑠,𝜃,𝜆 =1 2h𝑂𝑎i𝑠,𝜃+𝜋 2,𝜆 − h𝑂𝑎i𝑠,𝜃−𝜋 2,𝜆, ∇𝜆h𝑂𝑎i𝑠,𝜃,𝜆 =1 2h𝑂𝑎i𝑠,𝜃,𝜆+𝜋 2− h𝑂𝑎i𝑠,𝜃,𝜆−𝜋 2.(5.50) The gradient for the output scaling depends on the number of output parameters we have. If we consider a single output scaling parameter for all actions (𝑤∈ℝ), the gradient is given by ∇𝑤log 𝜋(𝑎|𝑠, 𝜃, 𝜆,𝑤)=h𝑂𝑎i𝑠,𝜃,𝜆 −Õ 𝑎0h𝑂𝑎0i𝑠,𝜃,𝜆 𝜋(𝑎0|𝑠, 𝜃, 𝜆,𝑤).(5.51) If we consider a distinct output scaling parameter for each action (𝑤∈ℝ|𝐴|), the gradient is ∇𝑤log 𝜋(𝑎|𝑠, 𝜃, 𝜆,𝑤)=h𝑂𝑎i𝑠,𝜃,𝜆 − h𝑂𝑎i𝑠,𝜃,𝜆 𝜋(𝑎|𝑠,𝜃, 𝜆,𝑤).(5.52) The gradient expressions in Equations (5.51) and (5.52) help clarify the behavior of the output scaling parameters. Notice that if multiple output scaling parameters are considered, a single parameter 𝑤𝑎is updated while only taking into account the expectation value of that action. However, if a single output scaling parameter is considered, the gradient with respect to that parameter is obtained from the difference between the numerical preference of action 𝑎and the expectation over all action numerical preferences. Thus, the latter uses an average over the action space to update the parameters, as opposed to the former, which updates the parameters individually. The two different approaches lead to different behaviors and associated complexities. A single parameter: • Simplifies the model, reducing the number of parameters that need to be learned. This can be particularly advantageous in environments where data are sparse or the learning rates need to be very carefully managed to avoid overfitting. • Applies the same level of exploration or exploitation across all actions. This uniformity ensures that no single action is inherently more explorative or exploitative purely due to the parameter setting. • Does not allow for action-specific adjustments in exploration tendencies. For example, if certain actions require finer control or more cautious exploration due to their consequences in the environment, a single parameter cannot accommodate this. • In complex environments where different actions have vastly different scales of rewards or utilities, a single scaling factor might not be optimal for learning the best policy across all actions. 90 5.3. GRADIENT ESTIMATION Multiple parameters: • Each action can have its own scaling factor, allowing the policy to adapt more finely to different parts of the action space. This can be especially useful in heterogeneous environments where actions vary significantly in their effects, risks, or rewards. • Different actions may require different levels of exploration. For instance, some actions might be safe and well-understood and thus can be exploited more, whereas others might be risky or less understood and thus require more exploration. • More parameters mean a higher risk of overfitting, especially with limited data. It also complicates the learning process, potentially requiring more sophisticated algorithms or regularization techniques. Additionally, more parameters can mean slower convergence and higher computational costs. It may also require more interactions with the environment to accurately estimate the best values for each parameter, affecting sample efficiency. In general, the choice between a single or multiple output scaling parameters depends on the complexity of the environment, the nature of the actions, and the available data. On a different note, let us now consider the PQC-based Gaussian policy as in Definition 5.1.7. For completeness, let two distinct PQCs encode the parameterized mean and variance with parameters {𝜃𝜇,𝜃𝜎}. The Gaussian policy is represented as 𝜋(𝑎|𝑠, 𝜃𝜇,𝜃𝜎)=1 p2𝜋𝜎 (𝑠, 𝜃𝜎)exp−(𝑎−𝜇(𝑠,𝜃𝜇))2 2𝜎(𝑠,𝜃𝜎)2.(5.53) The gradient of the log policy can be expressed as a function of the expectation values for both sets of parameters. For the mean and variance parameters, the gradient recipe is ∇𝜃𝜇log 𝜋(𝑎|𝑠,𝜃𝜇, 𝜃𝜎)=𝑎−𝜇(𝑠,𝜃𝜇) 𝜎(𝑠, 𝜃𝜎)2∇𝜃𝜇𝜇(𝑠, 𝜃𝜇), ∇𝜃𝜎log 𝜋(𝑎|𝑠,𝜃𝜇, 𝜃𝜎)=(𝑎−𝜇(𝑠,𝜃𝜇))2 𝜎(𝑠, 𝜃𝜎)3−1 𝜎(𝑠, 𝜃𝜎)∇𝜃𝜎𝜎(𝑠, 𝜃𝜎),(5.54) The gradient recipes for each policy and their respective parameters are summarized in Table 3. 91 CHAPTER 5. QUANTUM POLICY GRADIENTS Policy Parameter Gradient recipe Born 𝜃1 2h𝑂𝑎i𝑠,𝜃+𝜋 2− h𝑂𝑎i𝑠,𝜃 −𝜋 2 Born 𝜆1 2h𝑂𝑎i𝑠,𝜆+𝜋 2,𝜃 − h𝑂𝑎i𝑠,𝜆−𝜋 2,𝜃  Softmax 𝜃 𝑤∇𝜃h𝑂𝑎i𝑠,𝜃,𝜆 − Í𝑎0𝑤∇𝜃h𝑂𝑎0i𝑠,𝜃,𝜆 𝜋(𝑎0|𝑠, 𝜃, 𝜆,𝑤) Softmax 𝜆 𝑤∇𝜆h𝑂𝑎i𝑠,𝜃,𝜆 − Í𝑎0𝑤∇𝜆h𝑂𝑎0i𝑠,𝜃,𝜆 𝜋(𝑎0|𝑠, 𝜃, 𝜆,𝑤) Softmax 𝑤∈ℝh𝑂𝑎i𝑠,𝜃,𝜆 −Í𝑎0h𝑂𝑎0i𝑠,𝜃,𝜆 𝜋(𝑎0|𝑠, 𝜃, 𝜆, 𝑤) Softmax 𝑤∈ℝ|𝐴|h𝑂𝑎i𝑠,𝜃,𝜆 − h𝑂𝑎i𝑠,𝜃,𝜆 𝜋(𝑎|𝑠,𝜃, 𝜆,𝑤) Gaussian 𝜃𝜇𝑎−𝜇(𝑠,𝜃𝜇) 𝜎(𝑠,𝜃𝜎)2∇𝜃𝜇𝜇(𝑠,𝜃𝜇) Gaussian 𝜃𝜎(𝑎−𝜇(𝑠,𝜃𝜇))2 𝜎(𝑠,𝜃𝜎)3−1 𝜎(𝑠,𝜃𝜎)∇𝜃𝜎𝜎(𝑠,𝜃𝜎) Table 3: Gradient recipes for each policy and their respective parameters, including the Gaussian policy. 5.3.2 Sample complexity The sample complexity of the gradient estimation procedure is a crucial aspect to consider in policy gradient algorithms. Recall that the policy gradient is being empirically estimated through the loglikelihood trick (see Subsection 4.4). Therefore, sample complexity here refers to the number of training examples required to have a faithful estimation of the policy gradient. The number of samples is defined as the number of visited states. Since there are 𝑁trajectories 𝜏𝑖, each visiting 𝑇states, the total number of samples is O(𝑁𝑇). We want a tighter bound on this quantity. Lemma 5.3.1 establishes an upper bound on the number of samples required to 𝜖-estimate the policy gradient ˆ ∇𝜃𝐽(𝜃)assuming w.l.g that ∇𝜃log 𝜋(𝑎|𝑠,𝜃) ≤ G. Let us analyze the lemma and only then specify the type of policy and the implications for gradient estimation. The most relevant insight from the lemma is that it clarifies that the number of samples required to estimate the gradient grows only logarithmically with the number of trainable parameters, which is favorable for the scalability of the algorithm. Lemma 5.3.1. Let 𝜃∈ℝ𝑘 and ∇𝜃𝐽(𝜃) be the expected policy gradient empirically estimated through 𝑁 trajectories of horizon 𝑇 with 𝑅max being the maximum possible reward in any time step. Let 𝛾∈ [0,1] be the discount factor. Assume ∇𝜃log 𝜋(𝑎|𝑠,𝜃) ≤ G . An 𝜖 -approximation of the policy gradient ˆ ∇𝜃𝐽(𝜃) , |ˆ ∇𝜃𝐽(𝜃) −∇𝜃𝐽(𝜃)| ≤ 𝜖(5.55) can be obtained with probability 1−𝛿 , using a number of samples given by 𝑁𝑇 ≈ OG2𝑅2 max𝑇3 𝜖2(𝛾−1)4log2𝑘 𝛿.(5.56) 92 5.3. GRADIENT ESTIMATION Proof. Recall that the policy gradient for 𝑁trajectories with horizon 𝑇is ∇𝜃𝐽(𝜃)=1 𝑁 𝑁−1 Õ 𝑖=0 𝑇−1 Õ 𝑡=0∇𝜃log 𝜋(𝑎𝑖 𝑡|𝑠𝑖 𝑡,𝜃)𝐺(𝜏𝑖), where we replace the static return 𝐺(𝜏𝑖)by a return per time step 𝐺𝑡(𝜏𝑖)to distinguish every action. Let us start by defining a trivial upper bound on the return per trajectory, considering a maximum reward per time step 𝑅max: 𝐺(𝜏)= 𝑇−1 Õ 𝑡=0 𝛾𝑡𝑟𝑡+1≤𝑅max 𝑇−1 Õ 𝑡=0 𝛾𝑡=𝑅max 𝛾𝑇−1 𝛾−1.(5.57) Using the expression for the sum of 𝑇terms of a geometric progression, we get: 𝑇−1 Õ 𝑡=0 𝐺𝑡(𝜏) ≤ 𝑅max 𝑇−1 Õ 𝑡=0 𝛾𝑇−𝑡−1 (𝛾−1)≤𝑅max 𝑇 (𝛾−1)2.(5.58) Assuming that ∇𝜃log 𝜋(𝑎|𝑠, 𝜃) ≤ G for all 𝑎and 𝑠, and considering the above bound on the return, we can bound each step 𝑡≤𝑇of the policy gradient as follows: ∇𝜃log 𝜋(𝑎|𝑠,𝜃)𝐺𝑡(𝜏𝑖) ≤ G𝑅max 𝑇 (𝛾−1)2.(5.59) Let us assume that 𝑋𝑛=Í𝑇−1 𝑡=0∇𝜃log 𝜋(𝑎|𝑠,𝜃)𝐺𝑡(𝜏𝑖)is the sum of 𝑇bounded random variables 𝑋𝑛∈ [0,G𝑅max 𝑇 (𝛾−1)2]. Then, Hoeffding’s inequality can be used to bound the probability that the sum of the policy gradient is 𝜖-inaccurate: ℙh1 𝑁 𝑁 Õ 𝑖=1𝑋𝑖−𝔼[𝑋𝑖]≥𝜖i≤2 exp−2𝑁𝜖2 (𝑏−𝑎)2,(5.60) where 𝑋𝑖∈ [𝑎,𝑏]. Replacing the variables, ℙh|∇∗ 𝜃𝐽(𝜃) −∇𝜃𝐽(𝜃)| ≥ 𝜖i≤2 exp−2𝑁𝜖2(𝛾−1)4 G2𝑅2 max𝑇2.(5.61) Using the union bound for all 𝜃∈ℝ𝑘, 93 CHAPTER 5. QUANTUM POLICY GRADIENTS ℙhØ 𝑘 2 exp−2𝑁𝜖2(𝛾−1)4 G2𝑅2 max𝑇2i ≤2𝑘exp−2𝑁𝜖2(𝛾−1)4 G2𝑅2 max𝑇2.(5.62) Let 𝛿=ℙ[|∇∗ 𝜃𝐽(𝜃) −∇𝜃𝐽(𝜃)| ≥ 𝜖]. Then, 1−𝛿=ℙh|∇∗ 𝜃𝐽(𝜃) −∇𝜃𝐽(𝜃)| ≤ 𝜖i ≥1−2𝑘exp−2𝑁𝜖2(𝛾−1)4 G2𝑅2 max𝑇2, 𝛿≤2𝑘exp−2𝑁𝜖2(𝛾−1)4 G2𝑅2 max𝑇2. (5.63) Thus, an upper bound on 𝑁is 𝑁≤G2𝑅2 max𝑇2 𝜖2(𝛾−1)4log2𝑘 𝛿.(5.64) Considering 𝑁𝑇 samples completes the proof. □ The lemma provides an upper bound on the number of samples required to estimate the policy gradient. The bound grows logarithmically with the number of trainable parameters. However, we need to clarify the bound on the log policy gradient for specific PQC-based policies. Let us start with the PQC-based Softmax policy. The gradient with respect to 𝜃for the log policy is ∇𝜃log 𝜋(𝑎|𝑠,𝜃, 𝜆,𝑤)=𝑤∇𝜃h𝑂𝑎i𝑠,𝜃,𝜆 −Õ 𝑎0 𝑤∇𝜃h𝑂𝑎0i𝑠,𝜃,𝜆 𝜋(𝑎0|𝑠, 𝜃, 𝜆,𝑤).(5.65) Therefore, without loss of generality, we can assume that the observable whose expectation value represents the numerical preference of action 𝑎is a sum of 𝑀terms: 𝑂𝑎= 𝑀−1 Õ 𝑚=0 𝑐𝑖𝑃𝑖,(5.66) where 𝑃𝑖∈ {𝕀, 𝜎𝑥, 𝜎𝑦, 𝜎𝑧}⊗𝑁is a Pauli string acting on the 𝑁qubits and 𝑐𝑖∈ℝits real coefficient. Let 𝑐𝑖∈ [−𝐶,𝐶]for some 𝐶∈ℝ. Then the expectation value of the observable is bounded as h𝑂𝑎i𝑠,𝜃,𝜆 ∈ [−𝐶𝑀,𝐶𝑀]. Therefore, the gradient of the log policy, using parameter-shift rules, is bounded as 94 5.3. GRADIENT ESTIMATION ∇𝜃log 𝜋(𝑎|𝑠,𝜃, 𝜆,𝑤) ∈ [−2𝑤𝐶𝑀, 2𝑤𝐶𝑀].(5.67) Hence, 𝑁𝑇 ≈ O4𝑤2𝐶2𝑀2𝑅2 max𝑇3 𝜖2(𝛾−1)4log2𝑘 𝛿.(5.68) The bound on the number of samples required to estimate the policy gradient for the PQC-based Softmax policy depends heavily on the output scaling parameter 𝑤, the number of terms in the observable 𝑀, and their respective real coefficients 𝐶. Nonetheless, the gradient expression is still bounded, and thus the number of samples can be increased arbitrarily to ensure a faithful estimation of the policy gradient. Let us now consider the PQC-based Born policy. Recall that for an arbitrary Born policy (see Definition 5.1.1) with a partition function 𝑃𝑎associated to action 𝑎, the gradient of the log policy with respect to 𝜃is ∇𝜃log 𝜋(𝑎|𝑠,𝜃)=1 2𝜋(𝑎|𝑠, 𝜃)Tr𝜌𝑠,𝜆,𝜃+𝜋 2𝑃𝑎−Tr𝜌𝑠,𝜆,𝜃−𝜋 2𝑃𝑎.(5.69) Since we maintain the partition function for the shifting, it produces a new probability distribution. Therefore, the shifting operation remains bounded, as Tr𝜌𝑠,𝜆,𝜃±𝜋 2𝑃𝑎∈ [0,1]for all 𝑎. The denominator itself is also bounded 𝜋(𝑎|𝑠, 𝜃) ∈ [𝑏, 1]. It is not bounded in the full range [0,1]because we are estimating the gradient for the selected action at a given time step. Therefore, the probability itself cannot be strictly zero in the gradient estimation phase. However, it can become arbitrarily close to zero. Indeed, the probability of selecting the action may decrease exponentially with the number of qubits, which makes the gradient itself exponentially large. Thus, the log policy gradient is bounded above by ∇𝜃log 𝜋(𝑎|𝑠,𝜃) ∈ h−1 2,1 2𝑏i,(5.70) indicating that the number of samples required to faithfully estimate the policy gradient for the PQCbased Born policy can increase exponentially with the number of qubits. This is a clear indication of the trainability issues that can arise when using the Born policy. These training instabilities are further discussed in Chapter 6. The sample complexity for the PQC-based Born policy is 𝑁𝑇 ≈ O𝑅2 max𝑇3 𝑏2𝜖2(𝛾−1)4log2𝑘 𝛿.(5.71) 95 CHAPTER 5. QUANTUM POLICY GRADIENTS The policy gradient ranging conditions and respective gradient estimation sample complexity for PQCbased policies are summarized in Table 4. Policy Policy gradient range Sample complexity Born ∇𝜃log 𝜋(𝑎|𝑠, 𝜃) ∈ −1 2,1 2𝑏O𝑅2 max𝑇3 𝑏2𝜖2(𝛾−1)4log2𝑘 𝛿 Softmax ∇𝜃log 𝜋(𝑎|𝑠, 𝜃, 𝜆,𝑤) ∈ [−2𝑤𝐶𝑀, 2𝑤𝐶𝑀]O4𝑤2𝐶2𝑀2𝑅2 max𝑇3 𝜖2(𝛾−1)4log2𝑘 𝛿 Table 4: Policy gradient ranges and respective gradient estimation sample complexity for PQC-based policies. 5.4 Numerical experiments This section delves into the practical application and empirical analysis of various quantum policy networks proposed in Section 5.1, through a series of detailed numerical experiments. These experiments provide insights not only into the operational dynamics of these policies but also into empirical performance on standard RL benchmark environments, compared with classical parameterized models typically used to solve these tasks. Subsection 5.4.1 starts with a simple exploration of a basic softmax policy framework without considering data reuploading. This model, evaluated in our preliminary research article [175], sets a foundational baseline model for subsequent experimental inquiries. Subsection 5.4.2 then investigates the effect of data reuploading on the performance of the quantum policy networks. The experiments are conducted on both Born and Softmax policies proposed in Section 5.1. 5.4.1 A single-frequency softmax policy This subsection summarizes the empirical results obtained in our preliminary research article [175]. The main objective of this experiment is to evaluate the performance of a simple softmax policy without data reuploading in a set of standard classical control RL benchmarking environments [194]. In [93], the authors solved these environments using a parameterized form with multiple layers of data reuploading gates. Moreover, they showed that the PQC-based softmax policy (see Definition 5.1.6) has better sample complexity guarantees compared with the Born policy (see Definition 5.1.1). However, reuploading increases both the circuit depth and the number of trainable parameters (considering input scaling), leading to the well-known expressivity-trainability tradeoff [183]. Thus, in this experiment, we aimed to investigate whether a simple softmax model without data reuploading could also solve these environments, with the goal of effectively reducing the total number of trainable parameters and the circuit depth. Indeed, for such environments, data reuploading was not necessary for solving them. However, regarding sample complexity, it was ultimately shown that the data reuploading model required fewer samples to achieve the same performance—highlighting the importance of model expressivity. 96 5.4. NUMERICAL EXPERIMENTS 5.4.2 Data reuploading effect on performance In the previous subsection, a simple softmax policy was evaluated through classical benchmarking environments. Nonetheless, there are several PQC-based Born policies, as proposed in Section 5.1, whose performance should also be investigated. Furthermore, these should be compared against the PQC-based softmax policy. In that regard, we compare policies in three different scenarios: 1. Born policies — We consider the contiguous-like (see Definition 5.1.2), parity-like (see Definition 5.1.5), and action-projector-like (see Definition 5.1.3). 2. Born policies w/ softmax activation — The same Born policies as in 1) but with a softmax post-processing activation to add greediness control. 3. Softmax policy — A general PQC-based softmax policy (see Definition 5.1.6) with Hermitian observables. Furthermore, we choose a small set of classical benchmarking environments and different PQC architectures. In so doing, we can properly assess and compare different policies. We consider the same set of classical environments as in the previous subsection with the same minor modifications, described below for completeness: •Cartpole: This simulation involves a cart that moves along a frictionless track with an inverted pendulum attached. The system is described by four features: the cart’s position and velocity, and the angle and angular velocity of the pole. The agent has two possible actions: moving the cart left or right. The primary objective is to keep the pole balanced upright, with the agent receiving a reward of +1 for each time step that the pole remains upright, with a maximum of 200 steps. Therefore, the maximum possible reward is 200. •Acrobot: Consisting of a two-link robotic arm, the Acrobot environment originally features six state variables: the cosine and sine of the two joint angles and their respective velocities. However, to simplify and unify the feature space with the Cartpole environment, we consider only the angles directly, reducing the feature count to four. This adaptation focuses on the essential dynamic characteristics of the system. The agent controls the torque at the second joint and has three action choices: leftward torque, no torque, or rightward torque. The goal is to swing the lower link to a specific height as quickly as possible. The agent receives a reward of -1 for each timestep until the target is reached. The maximum number of steps is 500, but there is no fixed maximum reward since the agent can reach the target in fewer steps. For this environment only, the action-projectorlike and contiguous-like policies are considered because the action space is not a power of two; thus, the parity-like policy is not applicable. 103 CHAPTER 5. QUANTUM POLICY GRADIENTS The environments’ full description can be found in Table 11. For simplicity and scalability, the number of features for the Acrobot environment was reduced from six to four, such that we can consider the same PQC in both environments and effectively reduce significantly the number of trainable parameters. This is crucial to improve the algorithm’s time complexity. Regarding the PQC architecture, two circuits were selected that use only single-qubit parameterized gates. Two-qubit gates are applied in a non-parameterized fashion to generate entanglement in the circuit without increasing the number of trainable parameters. The circuits are defined as follows: 1. Jerbi — Ansatz composed of single-qubit parameterized rotations about two orthogonal axes {𝑅𝑧, 𝑅𝑦}, followed by an all-to-all entanglement pattern of CZ gates, as proposed by Jerbi et al. [93]. The data-encoding procedure is done via standard angle-encoding, using two rotation axes as well but in the opposite order {𝑅𝑦, 𝑅𝑧}, and is applied after the parameterized block. The circuit has as many qubits as the number of features in the input state. A layer of the PQC is illustrated (shaded purple) in Figure 42(a). 2. Universal Quantum Classifier (UQC) — A single-qubit architecture composed of two orthogonal rotation axes {𝑅𝑦, 𝑅𝑧}, with a set of trainable parameters Θ={𝜑,𝑤, 𝛼}. The angle for the 𝑧-rotation is expressed similarly to a classical neuron: h𝑠,𝑤i+𝛼, where h𝑠, 𝑤iis the inner product between the state and trainable parameters 𝑤.𝛼plays the role of a bias term as in a classical linear model. The axis of rotation can be flipped; orthogonality is the necessary condition. Salinas et al. [152] proved that in the limit of infinite repetitions, the UQC circuit is a universal approximator. In this work, we consider the UQC circuit as it enables finer control over the number of qubits, as it is independent of the number of features. Therefore, we test the performance of the UQC for a finite number of qubits {1,2,4}, with four being the maximum allowed to match the number of qubits used in the Jerbi architecture. For more than a single qubit, a nearest-neighbor entangling block of CZ gates is applied. The circuit is illustrated in Figure 42(b). 104 5.4. NUMERICAL EXPERIMENTS Figure 42: Parameterized quantum circuits considered for the experiment. (a) Jerbi architecture, and (b) UQC circuit for a four-qubit system. The fundamental layer is shaded purple for both circuits. The range of qubits for the UQC circuit was chosen to be {1,2,4}, enabling a fair comparison with the Jerbi circuit, which also uses four qubits when matching the number of features. The number of trainable parameters of the UQC circuit increases with the number of qubits, eventually matching the total number of parameters of the Jerbi circuit at 𝑁=2. The total number of parameters for both circuits is expressed in Table 6. Circuit Number of parameters Jerbi 4|𝑠|𝐿 UQC 𝑁(|𝑠| +2)𝐿 Table 6: Number of parameters for the UQC and Jerbi circuits, where |𝑠|is the number of features, 𝐿is the number of layers, and 𝑁is the number of qubits. PQC-based policies are trained using the REINFORCE algorithm (see Algorithm 4) by maximizing the average reward collected throughout trajectories, with a learning rate of 0.01 and a discount factor of 𝛾=0.99. To evaluate the performance of different policies, we consider the methodology described in Subsection 5.3.2: the policy is trained for 500 episodes, and the reward is collected and plotted as a function of the number of episodes. The reward is averaged over 10 runs with different sets of randomly initialized parameters from a Gaussian distribution N(0,1). In the following subsections, we analyze the performance of the model in both environments regarding the policies in question. Furthermore, 105 CHAPTER 5. QUANTUM POLICY GRADIENTS to analyze the quantum state at the end of training, we monitor the entanglement during training, to better understand the quantumness of the resulting state. We consider the Meyer-Wallach measure of entanglement, due to its scalability and ease of computation (see Section 2.3). Crucially, if the PQC has low entanglement at the end of training, the quantum model can effectively be replaced with a classical model, indicating that the quantum device harnessed entanglement to train, and indeed at testing phase the model can be readily deployed with a classical device, saving multiple resources. 5.4.2.1 Cumulative reward To keep the analysis as straightforward as possible, we break it into three parts, corresponding to the three distinct policy sets introduced at the start of this subsection. In each part, we analyze both the reward and the entanglement for each environment. 1) Born policies The Born policies considered in this experiment are the contiguous-like , parity-like , and action-projectorlike policies. Consider the following measurement apparatus for both environments using an 𝑁-qubit PQC-based policy: 1. Cartpole — |𝐴|=2 a) Contiguous-like — Recall from Definition 5.1.2 that the contiguous partition is obtained from a log |𝐴|-local measurement. Therefore, in this setting, we measure only a single qubit. b) Parity-like — The parity-like policy is obtained from an 𝑁-local measurement. In this setting, the standard parity function without recursion is applied (see Definition 5.1.5). c) Action-projector-like — The action-projector-like policy is also obtained from an 𝑁-local measurement. In this setting, we consider the projectors 𝑃0=|0ih0|and 𝑃1=|1ih1|. 2. Acrobot — |𝐴|=3 a) Contiguous-like — We split the 2𝑁basis states in a contiguous fashion for the three available actions. b) Action-projector-like — We consider the projectors 𝑃0=|0ih0|,𝑃1=|1ih1|, and 𝑃2=|2ih2|. The cumulative reward obtained during training by the different Born policies, using the UQC and Jerbi PQCs, is depicted in Figure 43. 106 5.4. NUMERICAL EXPERIMENTS Figure 43: Cumulative rewards obtained by the Born policies in the Cartpole environment: (a) UQC with a number of qubits in {1,2,4}and (b) Jerbi architecture. The action-projector-like policy is labeled global in the legend for conciseness. Figures 43 (a) and (b) show the cumulative rewards obtained by the Born policies in the Cartpole environment using the UQC and Jerbi architectures, respectively. The results readily indicate an overall superior performance of the Jerbi-based policies compared to the UQC-based policies. However, surprisingly, a single-qubit UQC is able to maintain a satisfactory performance. Nevertheless, the parity-based policy is the best-performing policy in both circuits, highlighting the expressivity of the parity function. Interestingly, the best-performing UQC model is composed of two qubits, indicating that having the same number of trainable parameters alone does not guarantee better performance. Indeed, a major challenge with the UQC is encoding every feature into the same qubit, which can scramble the information. Meanwhile, the Jerbi circuit possesses an all-to-all entanglement pattern, enabling more correlations between pairs of features and increasing the expressivity. Figure 44 shows the entanglement during training. Figure 44: Entanglement during training for the Born policies in the Cartpole environment: (a) UQC with a number of qubits in {1,2,4}and (b) Jerbi architecture. The action-projector-like policy is labeled global in the legend. Figures 44 (a) and (b) show that the Jerbi circuit generally displays higher entanglement during training compared with the UQC circuit, particularly when comparing the contiguous-like policies. This is expected because the Jerbi circuit has an all-to-all entanglement pattern, whereas the UQC circuit has a nearestneighbor entanglement pattern. Note also that both parity-like policies successfully maintain entanglement 107 CHAPTER 5. QUANTUM POLICY GRADIENTS throughout training. By contrast, the action-projector-like and contiguous-like policies in both circuits with four qubits exhibit a tendency for their entanglement to decrease. Their performance is not better than the parity-like policy, suggesting that entanglement could be a key factor in the power of PQC-based policies. Regarding the Acrobot environment, the results are depicted in Figure 45. Figure 45: Cumulative rewards obtained by the Born policies in the Acrobot environment: (a) UQC with a number of qubits in {1,2,4}and (b) Jerbi architecture. The action-projector-like policy is labeled global in the legend. Figures 45 (a) and (b) show the cumulative rewards obtained by the Born policies in the Acrobot environment using the UQC and Jerbi architectures, respectively. Again, the Jerbi circuit demonstrates superior performance compared with the UQC circuit. Moreover, the increased complexity of this environment has also increased the variance in the results. The UQC circuit remains notably more unstable than the Jerbi circuit. Interestingly, for both circuits, the contiguous policy is the best-performing one (parity-like is not applicable in a three-action setting). Figure 46 illustrates the entanglement over the course of training. Figure 46: Entanglement during training for the Born policies in the Acrobot environment: (a) UQC with a number of qubits in {1,2,4}and (b) Jerbi architecture. The action-projector-like policy is labeled global in the legend. The results indicate that the entanglement pattern during training for the Born policies remains roughly the same for both environments when using the UQC. The Jerbi circuit shows higher entanglement early 108 5.4. NUMERICAL EXPERIMENTS in training, but there is a clear downward trend as training progresses. If training continued for more episodes, the entanglement might decrease even further, particularly with the contiguous policy. It is important to note that the variance in the results is also influenced by the small number of agents (10) used in the averaging process. Given the environment’s complexity and the lack of high-performance simulators, it was not feasible to consider more agents within a reasonable time. This limitation will also apply to subsequent results, so it will not be reiterated below. 2) Born policies w/ softmax activation Because the softmax function generally has more controlled gradients and, crucially, adds greediness control to the policy, this part analyzes the performance of the same Born policies considered previously, but augmented with a softmax activation and parameter 𝛽=1 𝜏for controlling greediness, where 𝜏is the temperature. Since we are considering a small set of classical control environments, we used a linear annealing schedule for the temperature. The cumulative rewards obtained during training by the different Born policies using the UQC and Jerbi architectures are depicted in Figure 47. Figure 47: Cumulative rewards obtained by the Born policies with softmax activation in the Cartpole environment: (a) UQC with {1,2,4}qubits, and (b) Jerbi architecture. The action-projector-like policy is labeled global in the legend. As expected, the softmax activation improves the performance of the Born policies under both circuits. Still, the Jerbi architecture outperforms the UQC architecture, further stabilizing training. Figure 48 shows the entanglement during training. 109 CHAPTER 5. QUANTUM POLICY GRADIENTS Figure 48: Entanglement during training for the Born policies with softmax activation in the Cartpole environment: (a) UQC with {1,2,4}qubits, and (b) Jerbi architecture. The action-projector-like policy is labeled global in the legend. The results indicate that despite the softmax activation, the entanglement pattern during training for the Born policies remains roughly the same. For the Acrobot environment, the results are depicted in Figure 49. Figure 49: Cumulative rewards obtained by the Born policies with softmax activation in the Acrobot environment: (a) UQC with {1,2,4}qubits, and (b) Jerbi architecture. The action-projector-like policy is labeled global in the legend. Figures 49 (a) and (b) show the cumulative rewards obtained by the Born policies with softmax activation in the Acrobot environment using the UQC and Jerbi architectures, respectively. Unlike in the Cartpole environment, the softmax activation does not improve the performance of the Born policies in the Acrobot environment. This could be explained by the environment’s higher variance or by the linear annealing schedule for 𝜏. The environment’s more complex dynamics require more exploration. Therefore, a linear schedule may in fact be suboptimal. Figure 50 shows the entanglement during training. 110 5.4. NUMERICAL EXPERIMENTS Figure 50: Entanglement during training for the Born policies with softmax activation in the Acrobot environment: (a) UQC with {1,2,4}qubits, and (b) Jerbi architecture. The action-projector-like policy is labeled global in the legend. These results indicate that the entanglement pattern during training for the Born policies with softmax activation remains roughly the same as for the original Born policies in both environments. However, for the Jerbi circuit shown in Figure 50(b), the entanglement is even lower for the contiguous-like policy, which might be due simply to statistical noise from having fewer agents. 3) Softmax policy Here, we consider the Softmax policy. In this setting, the choice of the observable is crucial to the policy’s performance. Let us consider the following local and global observables for both environments, as described in Table 7. Table 7: Observables for the Softmax policy in different environments Environment Circuit Qubits Observables Cartpole UQC 1[𝑍0,−𝑍0] 2𝐿=[𝑍1,−𝑍1]𝐺=[𝑍0𝑍1,−𝑍0𝑍1] 4𝐿=[𝑍3,−𝑍3]𝐺=[𝑍0𝑍1𝑍2𝑍3,−𝑍0𝑍1𝑍2𝑍3] Jerbi 4𝐿=[𝑍3,−𝑍3]𝐺=[𝑍0𝑍1𝑍2𝑍3,−𝑍0𝑍1𝑍2𝑍3] Acrobot UQC 1[𝑍0, 𝑋0,−𝑍0] 2[𝑍0, 𝑍0𝑍1, 𝑍1] 4[𝑍0, 𝑍1𝑍2, 𝑍3] Jerbi 4[𝑍0, 𝑍1𝑍2, 𝑍3] The choice of local and global observables impacts the performance, entanglement, and trainability of the model. Here, trainability is not particularly restrictive because the model is small (up to four qubits and four layers of single-qubit parameterized gates). The cumulative reward and entanglement obtained during 111 CHAPTER 5. QUANTUM POLICY GRADIENTS training by the local Softmax policy using the UQC and Jerbi architectures in the Cartpole environment are depicted in Figure 51. Figure 51: Local softmax policy in the Cartpole environment: (a) cumulative reward and (b) entanglement during training. The UQC with {1,2,4}qubits and Jerbi architecture is considered. As seen in Figure 51(a), the local Softmax policy from the Jerbi architecture, even though it measures only a single qubit, achieves better performance in the Cartpole environment than the UQC, which performs significantly worse relative to the (1) Born and (2) Born w/ softmax activation policies. We expect more complex observables to improve the agent’s performance. Figure 51(b) shows a slight decreasing trend in entanglement for the Jerbi architecture in the Softmax formulation, although it might be due to statistical noise. For the Acrobot environment, the results are shown in Figure 52. Figure 52: Local softmax policy in the Acrobot environment: (a) cumulative reward and (b) entanglement during training. The UQC with {1,2,4}qubits and Jerbi architecture is considered. Figure 52(a) reveals a clear difference in performance between the UQC and Jerbi architectures in the Acrobot environment. The Jerbi architecture with the observables indicated in Table 7 is the only policy that achieves satisfactory performance. None of the UQC configurations come close to the Jerbi architecture. Given that for the Softmax policy, we also used the same linear annealing schedule, these results 112 6.2. BORN POLICIES observables (see Table 1). Subsection 6.2.1 begins with a case study of product states, followed by the general behavior for entangled states in Subsection 6.2.2. The variance as a function of the number of actions is investigated in Subsection 6.2.3. Subsection 6.2.4 then examines the Fisher Information spectrum associated with the policy. Finally, Subsection 6.2.5 provides numerical experiments that validate the theoretical results from Subsections 6.2.3 and 6.2.4. 6.2.1 The instructive case of product states Consider a scenario where a PQC-based Born policy is composed of a product state PQC without incorporating the agent’s state. Let the 𝑁-qubit PQC be |𝜓𝜃i= 𝑁−1 Ì 𝑖=0 𝑒−𝑖𝜃𝑖𝑃𝑖|0i, 𝜌𝜃=|𝜓𝜃ih𝜓𝜃|,(6.4) Assume 𝑃𝑖=𝑌for all 𝑖∈ {0,1, . . . , 𝑁 −1}and consider the task of learning the all-zero state. The cost function to be minimized is 𝐶(𝜃)=1−Tr𝜌𝜃𝑃0,(6.5) where 𝑃0=|0ih0|is the projector onto the all-zero state. The minimum cost corresponds to a probability of one for measuring the all-zero state, indicating that the entire state is concentrated in |0i⊗𝑁. Recall that |𝜓𝜃i= 𝑁−1 Ì 𝑖=0©« cos𝜃𝑖 2 sin𝜃𝑖 2ª®¬.(6.6) Then the probability of measuring the all-zero state is 𝑝0(𝜃)= 𝑁−1 Ö 𝑖=0 cos2(𝜃𝑖).(6.7) The function 𝑝0(𝜃)is a product of 𝑁factors, each within the interval [0,1]. If each 𝜃𝑖is randomly drawn (e.g., from a uniform distribution 𝜃𝑖∼𝑈[−𝜋, 𝜋]), then the average value of cos2(𝜃𝑖)is strictly less than 1 (in fact, it is 1/2if 𝜃𝑖is uniform on [−𝜋, 𝜋]). Therefore, uniform initialization typically leads to an exponential decrease in 𝑝0(𝜃)as 𝑁grows (see Figure 53(a)). For instance, if hcos2(𝜃𝑖)i =𝑐<1, then h𝑝0(𝜃)i =𝑁−1 Ö 𝑖=0 cos2(𝜃𝑖)≈𝑐𝑁, However, if 𝜃𝑖≈0(or 𝜃𝑖≈2𝑘𝜋 for integer 𝑘), then cos2(𝜃𝑖) ≈ 1, so 𝑝0(𝜃) may not decay as 𝑁 increases. Likewise, carefully chosen angles or circuit designs that keep cos2(𝜃𝑖)near 1 for all 𝑖may result in 𝑝0(𝜃)remaining large. This underscores the importance of parameter initialization in PQC-based policies. In [42], it was shown that this effect arises not only because of random initialization but also because a global projector is measured. The authors proposed modifying the cost function by including local contributions per qubit: 𝑂𝐿=1 𝑁 𝑁−1 Õ 𝑗=0|0ih0|𝑗⊗𝕀¯ 𝑗, 119 CHAPTER 6. TRAINABILITY ISSUES IN QUANTUM POLICY GRADIENTS where 𝕀¯ 𝑗is the identity on the other qubits. The cost function then becomes 𝐶(𝜃)=1−Tr𝜌𝜃𝑂𝐿=1−1 𝑁 𝑁−1 Õ 𝑖=0 cos2(𝜃𝑖),(6.8) which faithfully estimates the all-zero state while yielding polynomially vanishing quantities with 𝑁, as illustrated in Figure 53(b). This emphasizes the key influence of a suitably chosen cost function. Figure 53: (a) Variance of the probability of measuring the all-zero state under a global projector. (b) log plot for the variance of Tr[𝜌𝜃P], where Pis either the global or local projector as described above. The variance is plotted versus the number of qubits for 1000 randomly sampled parameters 𝜃∈𝑈(−𝜋, 𝜋). In a broader ML context, particularly for policy gradients, the log-likelihood is optimized rather than the direct probability considered above. That cost function behaves differently. For instance, if 𝐽(𝜃)=log Tr𝜌𝜃𝑃0,(6.9) the logarithm decomposes the product of cosines into a sum: 𝐽(𝜃)= 𝑁−1 Õ 𝑖=0 log cos2(𝜃𝑖).(6.10) Thus, the partial derivative with respect to 𝜃𝑖is 𝜕𝜃𝑖𝐽(𝜃)= 𝑁−1 Õ 𝑖=0 𝜕𝜃𝑖log cos2(𝜃𝑖) = 𝑁−1 Õ 𝑖=0−2 sin(𝜃𝑖) cos(𝜃𝑖)= 𝑁−1 Õ 𝑖=0−2 tan(𝜃𝑖).(6.11) which is no longer a product of 𝑁terms in [0,1]. If a parameter is shared across all gates (e.g., in the QAOA layers [66]), the partial derivative does depend on 𝑁. However, for the case 𝜃∈ℝ𝑁(i.e., unshared parameters), the partial derivative decouples: 𝜕𝜃𝑖𝐽(𝜃)=−2 tan(𝜃𝑖), 120 6.2. BORN POLICIES so the variance of this partial derivative is independent of 𝑁. Notably, with uniformly sampled 𝜃∼ 𝑈[−𝜋, 𝜋], the expected value of the partial derivative may still be undefined (due to 𝜃=±𝜋/2). When measuring the all-ones basis state 𝑝2𝑁(𝜃)instead, a similar expression involving arctan(𝜃𝑖)arises, which can be zero-mean in the same random initialization interval. Hence, parameter initialization is crucial; for example, 𝜃sampled from [𝜋 4,𝜋 4]might ensure bounded partial derivatives. Generally, when 𝜌𝜃is a product state, the probability of measuring |𝑎ifactors into individual qubit contributions, Tr𝜌𝜃𝑃𝑎= 𝑁−1 Ö 𝑖=0 Tr𝜌𝜃𝑖𝑃𝑎𝑖. The log-likelihood thus separates into a sum, 𝐽(𝜃)= 𝑁−1 Õ 𝑖=0 log Tr𝜌𝜃𝑖𝑃𝑎𝑖, potentially avoiding a BP since it turns it into a sum over 𝑁terms, and make vanishing quantities independent od the number of qubits and depedent of the initialization only. Consider next an arbitrary product state composed of 𝐿layers of single-qubit rotations, |𝜓(𝜃)i = 𝐿−1 Ö 𝑙=0 𝑁−1 Ì 𝑖=0 𝑒−𝑖 𝜃𝑖,𝑙 𝑃𝑖,𝑙 |0i, 𝜌𝜃=|𝜓(𝜃)ih𝜓(𝜃)|,(6.12) where 𝑃𝑖,𝑙 ∈ {𝑌}and 𝜃𝑖,𝑙 ∈ℝ. The probability of measuring a basis state 𝑃𝑎factors into individual qubits, but the partial derivative of the log probability with respect to 𝜃𝑖,𝑙 may depend on the number of qubits and layers, because each qubit’s probability is now a sum of 𝐿terms: Tr𝜌𝜃𝑖,𝑙 𝑃𝑎𝑖= 𝐿−1 Õ 𝑙=0 𝑎(𝜃𝑖,𝑙 ). Then 𝜕𝜃𝑖,𝑙 𝐽(𝜃)= 𝑁−1 Õ 𝑙=0 𝜕𝜃𝑖,𝑙 log𝐿−1 Õ 𝑙=0 𝑎(𝜃𝑖,𝑙 ). If parameters are not shared across gates, the partial derivative for each qubit decouples from 𝑁, but it can still scale with the number of layers. Specifically, 𝜕𝜃𝑖,𝑙 𝐽(𝜃)=𝜕𝜃𝑖,𝑙 Í𝐿−1 𝑙=0𝑎(𝜃𝑖,𝑙 ) Í𝐿−1 𝑙=0𝑎(𝜃𝑖,𝑙 )=𝜕𝜃𝑖,𝑙 𝑎(𝜃𝑖,𝑙 ) Í𝐿−1 𝑙=0𝑎(𝜃𝑖,𝑙 ). Hence, circuit depth matters alongside qubit count. In PQC-based RL, note that these examples fit a Born policy in the regime |𝐴|=2𝑁, implying no partition over the action space. The behavior changes if the action space is partitioned, as explored in subsequent sections. 121 CHAPTER 6. TRAINABILITY ISSUES IN QUANTUM POLICY GRADIENTS 6.2.2 Generalized behavior for entangled states In this subsection, we analyze the variance of the log-probability for entangled states. In particular, let us still consider the extreme scenario of a number of actions scaling exponentially with system size as |𝐴|=2𝑛, same as Subsection 6.2.1. Therefore, the measurements are still composed of global projectors into one of the 2𝑁possible basis states. Let 𝜌(𝜃)be an arbitrarily entangled PQC. Let 𝑃𝑎=|𝑎ih𝑎|be the projector into the 𝑎th basis state. In this scenario, the probability of measuring a basis state 𝑎is, in general, not decomposed by the product of individual qubit subsystems, Tr𝜌𝜃𝑃𝑎≠ 𝑁−1 Ö 𝑖=0 Tr𝜌𝜃𝑖𝑃𝑎𝑖(6.13) since the system is not separable. Indeed, the probability will be factored as the product of the probability associated with untangled subsystems 𝑆(𝑁). Let us consider the entangled quantum state illustrated in Figure 54, composed of a 𝑁=4PQC. In this setting the PQC even though composed of a four qubit Figure 54: Entangled PQC composed of two Bell states in a four qubit system. system it can be analyzed separately as two qubit subsystems 𝑆1(𝑁)and 𝑆2(𝑁)each one acting on two qubits. Thus, the probability of measuring a global projector 𝑃𝑎on all four qubits is factored as the product, Tr𝜌𝜃𝑃𝑎=Tr𝜌𝜃𝑃𝑆1 𝑎Tr𝜌𝜃𝑃𝑆2 𝑎(6.14) where 𝑃𝑆1 𝑎and 𝑃𝑆2 𝑎are the projectors into the 𝑎th basis state decomposed into the subsystems 𝑆1(𝑁) and 𝑆2(𝑁), respectively. Therefore, in entangled states the logarithm can still separate the product of probabilities but now instead of individual qubit contributions, the product is separated into the product of the probabilities of the set of unentangled subsystems {𝑆(𝑁)}, 𝐽(𝜃)=log Tr𝜌𝜃𝑃𝑎=Õ 𝑖∈{𝑆(𝑁)} log Tr𝜌𝜃𝑃𝑆𝑖 𝑎 (6.15) 122 6.2. BORN POLICIES The trainability of the entangled state is then analyzed by the variance of the log probability partial derivative and in this setting it boils down essentially to the size of the subsystem where the parameter is contained. Therefore, notice that, since we are measuring every qubit within the subsytem, it is still a global measurement. Thus, the probability of measuring a state within each subsystem will be exponentially small with the size of the subsystem. This drastically changes the behavior for the partial derivative. We have the logarithm of a probability that is vanishing exponentially with the number of qubits. Therefore, the partial derivative will go in the opposite direction. That is, it will increase with the number of qubits present in the subsystem. Thus, it seems that an exploding gradient is bound to happen instead of a vanishing gradient. Nevertheless, it still turns to be hard to train the model. Notice that the probability is getting exponentially small with the number of qubits. Therefore, even though the gradient increases, we still need eventually an exponential number of shots (or quantum circuit executions) to properly estimate the probability. Therefore, trainability will be guaranteed provided efficient estimation of probabilities. Let us stress that such behavior is expected because we are allowing global measurements within each subsystem. More generally, it is going to depend on the structure of gates and measurements. To generalize, let us consider the results from Cerezo et.al [42] in which the authors show that O(log 𝑁)depth presents a trainable region, resulting as well from the measurement of O(log 𝑁)qubits. This is guaranteed for circuits able of producing local 2-designs (See Definition 3.4.1). Meaning that efficient probability estimation will depend on both the number of qubits being measured as well as the depth of the circuit for efficient gradient signal propagation. Indeed, for PQC-based policies, this in turn depend on the number of actions |𝐴|of the environment we are trying to solve since these impact the locality of the measurement (see Table 1). To demonstrate the effect of |𝐴|=2𝑁in the context of generalized entangled states, let us consider three types of circuits: 1. Simplified 2-design ansatz illustrated in Figure 55(a). 2. Strongly entangling layers, depicted in Figure 55(b). 3. State generated from Pauli rotations sampled uniformly at random followed by randomly selected CZ gates, as illustrated in 55(c). Figure 55(d) illustrates the variance of the gradient 2-norm of the log probability for a set of randomly selected global projectors. The variance is illustrated as a function of the number of qubits for 𝑁layers of the blocks shown in their respective figures. Moreover, projectors were sampled uniformly at random from the set of 2𝑁available ones and the variance illustrated for an average of a thousand experiments. From Figure 55(d), it is evident that in each experiment, the variance of the log-probability increases with the number of qubits when global projectors are considered. This behavior is akin to what was described before. Probabilities are getting exponentially suppressed with the number of qubits 𝑁making the partial 123 CHAPTER 6. TRAINABILITY ISSUES IN QUANTUM POLICY GRADIENTS Figure 55: Variance of the log policy gradient for three distinct entangled states. (a) Simplified two design. (b) Strongly entangling layers. (c) Random states composed of Pauli rotations sampled uniformly at random followed by randomly selected CZ gates. (d) Variance as a function of the number of qubits for 𝑁layers of building blocks of each of the circuits (a)-(c). derivative of the log probability increase. The variance reaches extremely high levels as a function of 𝑁, indicating that although these circuits are prone to the exploding gradient phenomenon. This further leads us to conclude that an exponentially large number of quantum circuit executions is required to accurately estimate both the probability and its gradient. However, recall that in the context of RL, we will need to do a partitioning of possibly all 2𝑁basis states into the set of available actions |𝐴|. In such cases, a trainable region could be created depending on the locality of the projector, which in turn is heavily influenced by the type of Born policy implemented. In the following subsection, we examine the variance of the cost function for different Born policies as a function of the number of actions |𝐴|. Let us now proceed to the analysis of the variance of the log likelihood cost function for Born policies as a function of the number of actions |𝐴|. 6.2.3 Variance as a function of the number of actions This subsection analyzes the variance of the log-probability cost function for Born policies as a function of the environment’s available actions. In Subsection 6.2.2, it was observed that estimating policy probabilities can become exponentially hard when global measurements are performed on both product and entangled states with increasing qubit count. Consequently, the partial derivative of the log-probability would potentially “explode” because the measured probabilities are exponentially small. In practice, this behavior requires clarification, since different behavior arise when the action space is partitioned. Recall that Contiguous (Definition 5.1.2) and Parity-like (Definition 5.1.5) Born policies differ in how they partition measurement outcomes and thus induce different observable locality. The type of Born policy therefore has a strong impact on trainability, particularly as a function of the environment’s complexity (i.e., the number of actions |𝐴|). To establish theoretical bounds for the partial derivative variance for general classes of circuits, known results for local 2-design circuits are leveraged [42], since it is known that deep 124 6.2. BORN POLICIES PQCs form 2-designs [laroccaTheoryOverparametrizationQuantum2023.] We begin with an analytical upper bound on the log-probability’s partial-derivative variance, stated in Lemma 6.2.1. Throughout this discussion, let 𝑓(𝜋𝜃)=log 𝜋(𝑎|𝑠, 𝜃)for simplicity. Lemma 6.2.1. Consider a general 𝑁 -qubit Born policy 𝜋(𝑎|𝑠, 𝜃) (Definition 5.1.1) with |𝐴| actions. Then an upper bound for the variance of the log policy gradient is 𝕍𝜃𝜕𝜃log 𝜋(𝑎|𝑠, 𝜃)≤2𝜕𝜋𝜃𝑓(𝜋𝜃)2 ∞h𝕍𝜃𝜕𝜃𝜋𝜃+𝔼𝜃𝜕𝜃𝜋𝜃2i.(6.16) Proof. 𝕍𝜃𝜕𝜃log 𝜋(𝑎|𝑠, 𝜃)=𝕍𝜃𝜕𝜃𝑓(𝜋𝜃) =𝕍𝜃𝜕𝜋𝜃𝑓(𝜋𝜃)𝜕𝜃𝜋𝜃(A) ≤2𝕍𝜃𝜕𝜃𝜋𝜃𝜕𝜋𝜃𝑓(𝜋𝜃)2 ∞+2𝔼𝜃𝜕𝜃𝜋𝜃2𝕍𝜃𝜕𝜋𝜃𝑓(𝜋𝜃)(B) ≤2𝕍𝜃𝜕𝜃𝜋𝜃𝜕𝜋𝜃𝑓(𝜋𝜃)2 ∞+2𝔼𝜃𝜕𝜃𝜋𝜃2𝜕𝜋𝜃𝑓(𝜋𝜃)2 ∞(C) =2𝜕𝜋𝜃𝑓(𝜋𝜃)2 ∞h𝕍𝜃𝜕𝜃𝜋𝜃+𝔼𝜃𝜕𝜃𝜋𝜃2i,(D) where (A) applies the chain rule, (B) uses a variance-of-product bound 𝕍[𝑋𝑌] ≤ 2𝕍[𝑋]|𝑌|2 ∞+2𝔼[𝑋]2𝕍[𝑌][197], (C) bounds the variance of 𝜕𝜋𝜃𝑓(𝜋𝜃)by its supremum norm, and (D) collects terms. □ The upper bound depends crucially on 𝜕𝜋𝜃𝑓(𝜋𝜃)2 ∞, which in turn depends on the total number of actions |𝐴|and the observable used to estimate the policy. Assuming 1-design parameter blocks before and after the parameter 𝜃, one obtains 𝔼𝜃𝜕𝜃𝜋𝜃=0[42]. In RL, the log policy gradient is computed only for sampled actions, so 𝜋(𝑎|𝑠,𝜃)cannot be strictly zero. However, it can be extremely small. In practice, a minimal clipping parameter 𝑏is often adopted such that 𝜋min ∈ [𝑏, 1]. If 𝑏is exponentially small with respect to 𝑁, then log 𝜋(𝑎|𝑠,𝜃)may lead to large derivatives (see Subsection 6.2.2). The question becomes how small 𝑏can be while still ensuring effective probability estimation and avoiding exploding gradients. As shown next, the Born policy variant and the number of actions |𝐴|are critical factors. Lemma 6.2.2 provides an upper bound on the log-gradient variance for a parity-like Born policy. Lemma 6.2.2. (Variance for parity-like Born policy) Let 𝜋(𝑎|𝑠, 𝜃) be an 𝑁 -qubit parity-like Born policy (Definition 5.1.5) with |𝐴| actions. If each block in the parameterized quantum circuit forms a local 2-design, then the policy gradient variance vanishes exponentially with the number of qubits, 𝕍𝜃𝜕𝜃log 𝜋(𝑎|𝑠, 𝜃)∈ O1 𝛼𝑛, 𝛼 >1, provided |𝐴| ∈ O(poly(𝑁)) . Conversely, when |𝐴| exceeds polynomial growth in 𝑁 , the policy gradient variance scales as 𝕍𝜃𝜕𝜃log 𝜋(𝑎|𝑠, 𝜃)∈ O𝛽 𝛼𝑛, 𝛼, 𝛽 >1. 125 CHAPTER 6. TRAINABILITY ISSUES IN QUANTUM POLICY GRADIENTS and the upper bound can become loose. Particularly, if 𝛽>𝛼 , implying the variance increases with 𝑛 . Proof. A parity-like Born policy partitions 2𝑁basis states by measuring all 𝑁qubits (see Definition 5.1.5). If |𝐴| ∈ O(poly(𝑁)), we can assume a minimum probability 𝑏∈Ω1 poly(𝑁)[197], ensuring that each action probability is at least polynomially small. This is a reasonable assumption in RL for |𝐴|  2𝑁. The total number of features in an RL agent’s state, 𝑠𝑓, is typically large and 𝑠𝑓 |𝐴|for a discrete action space and several qubits are often required to encode the state of the agent. Traditionally, standard angle encoding schemes are considered in most literature [93, 48, 175, 96]. Therefore, 𝑁∼𝑠𝑓, which implies that |𝐴|  2𝑁and validates the poly(𝑁)clipping assumption. Under these conditions, the norm 𝜕𝜋𝜃𝑓(𝜋𝜃)2 ∞∈ O(poly(𝑁)), and if each circuit block is a local 2-design, then Var𝜕𝜃𝜋𝜃∈ O1 𝛼𝑛for some 𝛼>1[42]. Thus the variance vanishes exponentially in 𝑁, inducing a BP. Outside poly(𝑁)actions, 𝜋min can be exponentially small, Ω1 𝛽𝑛for 𝛽>1, causing 𝜕𝜋𝜃𝑓(𝜋𝜃)2 ∞to grow as O(𝛽𝑛). Consequently, 𝕍𝜃𝜕𝜃log 𝜋(𝑎|𝑠, 𝜃)∈ O𝛽 𝛼𝑛, which increases with 𝑁if 𝛽>𝛼. In this regime, the policy gradient exhibits exploding gradients, but also requires an exponentially large number of shots to estimate probabilities, making the policy hard to train. □ In contrast, the base case |𝐴|=2under a contiguous-like Born policy involves single-qubit measurements, yielding a very different trainability profile than the parity-like policy. Intuitively, contiguous-like policies become harder to train as |𝐴|grows, because larger |𝐴|typically implies a more global measurement. Hence, a trainability window exists should |𝐴|remain sufficiently small. In general, contiguous-like policy employs up to log(|𝐴|)-local measurements (see Definition 5.1.2); for example, if |𝐴|=𝑁, then at most log(𝑁)adjacent qubits are measured. Such log(𝑁)-local measurements are known to avoid BPs under certain conditions [162]. Lemma 6.2.3 provides a lower bound on the variance of the log-probability gradient for contiguous-like Born policies, as a function of the number of actions |𝐴|. Lemma 6.2.3. (Variance for Contiguous-like Born policy) Consider an 𝑁 -qubit contiguous-like Born policy 𝜋(𝑎|𝑠, 𝜃) with |𝐴| actions (Definition 5.1.1). If each circuit block forms a local 2-design, then 𝕍𝜃𝜕𝜃𝜋(𝑎|𝑠, 𝜃)∈Ω1 poly(𝑛) for |𝐴| ∈ O(𝑁) and circuit depth O(log(𝑁)) . Conversely, for |𝐴| ∈ O(𝑁) and depth O(poly(log(𝑁))) , the variance scales as 𝕍𝜃𝜕𝜃𝜋(𝑎|𝑠, 𝜃)∈Ω2−poly(log(𝑛)). The partial derivative of the log-probability likewise remains bounded, since probabilities do not vanish exponentially. Lemma 6.2.3 thus provides a lower bound on the policy gradient variance under local 2design assumptions. As long as |𝐴| ∈ O(𝑁)and the circuit depth is at most O(log(𝑁)), the variance 126 6.2. BORN POLICIES decreases at worst polynomially in 𝑁, and the required quantum measurements remain polynomially large. If the depth extends to O(poly(log(𝑁))), the variance decays faster than polynomially but not fully exponentially, reflecting partially global observables. A detailed derivation is deferred to Appendix A. The next section examines an alternative view of trainability by studying the Fisher information spectrum. 6.2.4 Analysis of the Fisher information spectrum In computational learning theory, the CFIM is used to assess how variations in model parameters affect the model’s output. In RL, the CFIM must account for states drawn from the policy-induced state distribution 𝑑𝜋 𝑠. For a parameterized policy 𝜋(𝑎|𝑠, 𝜃), the matrix is expressed as the expectation of the outer product of the log-likelihood gradient (see Section 4.4.1): I(𝜃)=𝔼𝑠∼𝑑𝜋 𝑠𝔼𝑎∼𝜋(·|𝑠,𝜃)h∇𝜃log 𝜋(𝑎|𝑠, 𝜃)∇𝜃log 𝜋(𝑎|𝑠, 𝜃)𝑇i.(6.17) The CFIM indicates how parameter changes influence the policy’s output distribution. Notably, the CFIM’s spectrum fundamentally characterizes BPs in PQC-based statistical models trained via log-likelihood objectives [5]. Although RL objectives also incorporate cumulative rewards (which the CFIM does not directly capture), the CFIM spectrum still helps to identify BP signatures—provided rewards are non-zero. In a BP, the CFIM eigenvalues concentrate exponentially near zero with the number of qubits 𝑁[5]. The expected value of a diagonal entry 𝑘in the CFIM can be written as 𝔼𝜃I𝑘𝑘 (𝜃)=𝔼𝜃h𝜕𝜃𝑘log 𝜋(𝑎|𝑠,𝜃)2i =𝕍𝜃h𝜕𝜃𝑘log 𝜋(𝑎|𝑠, 𝜃)i+𝔼𝜃𝜕𝜃𝑘log 𝜋(𝑎|𝑠, 𝜃)2 ,(6.18) which follows from the definition of variance. Hence, each diagonal component is bounded below by the variance of the log-likelihood gradient: 𝔼𝜃I𝑘𝑘 (𝜃)≥𝕍𝜃h𝜕𝜃𝑘log 𝜋(𝑎|𝑠,𝜃)i.(6.19) but it can also be assumed 1-design parameterized blocks to ensure 𝔼𝜃𝜕𝜃𝑘log 𝜋(𝑎|𝑠, 𝜃)2=0. Summing over all parameters 𝜃∈ℝ𝐾then implies 𝔼𝜃TrI(𝜃)≥ 𝐾−1 Õ 𝑘=0 𝕍𝜃h𝜕𝜃𝑘log 𝜋(𝑎|𝑠, 𝜃)i.(6.20) Thus, any lower bound on the partial-derivative variance (e.g. from Lemma 6.2.3) translates into a lower bound on the CFIM trace. In a BP each CFIM diagonal entry vanishes exponentially with 𝑁, also requiring an exponential number of measurement shots to estimate it accurately. By Lemma 6.2.3, a Contiguous-like Born policy with |𝐴| ∈ O(poly(𝑁)) has partial derivatives whose variance decays at most polylogarithmically in 𝑁. Consequently, the CFIM eigenvalues do not all vanish exponentially, and the CFIM spectrum does not reveal a BP. 127 CHAPTER 6. TRAINABILITY ISSUES IN QUANTUM POLICY GRADIENTS For a Parity-like Born policy with |𝐴| ∈ O(poly(𝑁)), the variance of the log-likelihood gradient shrinks exponentially with 𝑁. In turn, the CFIM eigenvalues also collapse exponentially, signaling a BP. In scenarios where the number of actions exceeds Poly(𝑁), not only do the required measurements for accurate policy estimation become prohibitively large, but the probabilities associated with actions remain exponentially small. This implies that, despite avoiding BPs, these scenarios are more likely to encounter exploding gradients rather than BPs, reflected in increasing CFIM entries and a less concentrated spectrum around zero. Hence, a non-vanishing CFIM spectrum in this large-action regime does not necessarily imply good trainability. Indeed, while the spectrum is less concentrated near zero, estimating the policy (and thus the gradient) demands exponentially more measurements. In summary, the CFIM spectrum can effectively characterize BPs for PQC-based policies when |𝐴| ∈ O(poly(𝑁)). Outside that range, the CFIM spectrum tends to be large (i.e. not concentrated near zero) but does not guarantee straightforward trainability, because exponentially many measurements are often required. The next section delves further into these trainability issues by examining numerical experiments. 6.2.5 Numerical experiments This subsection empirically investigates the trainability issues of Contiguous and Parity-like Born policies (as discussed in Lemma 6.2.3). Two primary tasks are considered: • Trainability with a simplified 2-design: Empirical validation of theoretical results on the variance of the log-likelihood gradient for Contiguous and Parity-like Born policies, presented in Lemmas 6.2.3 and 6.2.2. We consider a “simplified two-design” ansatz [42], see Figure 55(a) to explore how the variance of the log-likelihood gradient and the CFIM spectrum vary with both the policy type and the number of actions |𝐴|. • Multi-armed bandits: A synthetic multi-armed bandit environment is introduced to compare how these Born policies (Contiguous or Parity-like) distinguish the best arm through sampling and gradient-based updates as a function of the number of actions |𝐴|and having only access to a polynomial number of measurements. In the first task, although the selected ansatz does not precisely form a two-design, it is known to exhibit cost-function BPs [42], making it well-suited for simulation at larger qubit counts and depths. We choose a depth of O(𝑁2)in our experiments. Since large action-space RL benchmarks for PQC-based policies are scarce, we adopt the multi-armed bandit environment in the second task. This choice allows us to keep a consistent objective function while scaling the number of actions and the qubit count, thereby focusing on trainability. All simulations use Pennylane’s quantum simulator [21], with parameter-shift gradient estimation [172] and a polynomial number of measurements O(poly(𝑁)). Our code is available on GitHub at Trainability-issues-in-QPGs. 128 BIBLIOGRAPHY [59] M. de Oliveira and L. S. Barbosa. Quantum Bayesian Decision-Making* . 2020-10. doi: 10.4855 0/arXiv.2010.02088. arXiv: 2010.02088 [quant-ph]. (Visited on 2024-06-04) (cit. on p. 206). [60] F. Di Marcantonio et al. “Quantum Advantage Seeker with Kernels (QuASK): A Software Framework to Speed up the Research in Quantum Machine Learning”. In: Quantum Machine Intelligence 5.1 (2023-05), p. 20. issn: 2524-4914. doi: 10.1007/s42484-023-00107-2. (Visited on 202404-04) (cit. on p. 35). [61] C. Dimitrakakis and R. Ortner. Decision Making Under Uncertainty and Reinforcement Learning: Theory and Algorithms . Vol. 223. Intelligent Systems Reference Library. Cham: Springer International Publishing, 2022. isbn: 978-3-031-07612-1 978-3-031-07614-5. doi: 10.1007/978-3-0 31-07614-5. (Visited on 2024-05-31) (cit. on p. 206). [62] D. Dong et al. “Quantum Reinforcement Learning”. In: IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 38.5 (2008-10), pp. 1207–1220. issn: 1083-4419. doi: 10.11 09/TSMCB.2008.925743. arXiv: 0810.3828 [quant-ph]. (Visited on 2024-06-07) (cit. on p. 5). [63] Y. Du et al. “Expressive Power of Parametrized Quantum Circuits”. In: Physical Review Research 2.3 (2020-07), p. 033125. issn: 2643-1564. doi: 10.1103/PhysRevResearch.2.033125. (Visited on 2024-03-26) (cit. on pp. 3, 25). [64] V. Dunjko and H. J. Briegel. “Machine Learning & Artificial Intelligence in the Quantum Domain: A Review of Recent Progress”. In: Reports on Progress in Physics 81.7 (2018), p. 074001. (Visited on 2024-06-07) (cit. on pp. 1, 2, 5). [65] V. Dunjko, J. M. Taylor, and H. J. Briegel. “Quantum-Enhanced Machine Learning”. In: Physical Review Letters 117.13 (2016-09), p. 130501. issn: 0031-9007, 1079-7114. doi: 10 .1103 /PhysRevLett.117.130501. arXiv: 1610.08251 [quant-ph]. (Visited on 2024-06-05) (cit. on pp. 2, 5, 213, 222). [66] E. Farhi, J. Goldstone, and S. Gutmann. A Quantum Approximate Optimization Algorithm . 2014-11. doi: 10.48550/arXiv.1411.4028. arXiv: 1411.4028 [quant-ph]. (Visited on 2024-0328) (cit. on pp. 3, 21, 26, 120, 222). [67] E. Farhi and A. W. Harrow. Quantum Supremacy through the Quantum Approximate Optimization Algorithm . 2019-10. doi: 10.48550/arXiv.1602.07674. arXiv: 1602.07674 [quant-ph]. (Visited on 2024-03-28) (cit. on pp. 3, 21, 222). [68] E. Farhi and A. W. Harrow. Quantum Supremacy through the Quantum Approximate Optimization Algorithm . 2019-10. arXiv: 1602.07674. (Visited on 2024-11-05) (cit. on p. 166). [69] E. Farhi and H. Neven. Classification with Quantum Neural Networks on Near Term Processors . 2018-08. doi: 10.48550/arXiv.1802.06002. arXiv: 1802.06002 [quant-ph]. (Visited on 2024-03-28) (cit. on p. 28). 231 BIBLIOGRAPHY [70] A. Fawzi et al. “Discovering Faster Matrix Multiplication Algorithms with Reinforcement Learning”. In: Nature 610.7930 (2022-10), pp. 47–53. issn: 1476-4687. doi: 10.1038/s41586-022-05 172-4. (Visited on 2024-04-22) (cit. on p. 44). [71] R. P. Feynman. “Simulating Physics with Computers”. In: International Journal of Theoretical Physics 21.6 (1982-06), pp. 467–488. issn: 1572-9575. doi: 10.1007/BF02650179. (Visited on 2024-06-11) (cit. on p. 1). [72] T. Fösel et al. Quantum Circuit Optimization with Deep Reinforcement Learning . 2021-03. doi: 10.48550/arXiv.2103.07585. arXiv: 2103.07585 [quant-ph]. (Visited on 2024-0422) (cit. on p. 44). [73] T. Fösel et al. “Reinforcement Learning with Neural Networks for Quantum Feedback”. In: Physical Review X 8.3 (2018-09), p. 031084. doi: 10.1103/PhysRevX.8.031084. (Visited on 202404-22) (cit. on p. 44). [74] K. Fujii and T. Morimae. “Quantum Commuting Circuits and Complexity of Ising Partition Functions”. In: New Journal of Physics 19.3 (2017-03), p. 033003. issn: 1367-2630. doi: 10.108 8/1367-2630/aa5fdb. arXiv: 1311.2128 [quant-ph]. (Visited on 2025-01-06) (cit. on p. 163). [75] J. Gacon et al. “Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information”. In: Quantum 5 (2021-10), p. 567. issn: 2521-327X. doi: 10.22331/q-2021-1020-567. arXiv: 2103.09232 [quant-ph]. (Visited on 2024-04-04) (cit. on p. 38). [76] B. T. Gard et al. “Efficient Symmetry-Preserving State Preparation Circuits for the Variational Quantum Eigensolver Algorithm”. In: npj Quantum Information 6.1 (2020-01), pp. 1–9. issn: 2056-6387. doi: 10.1038/s41534-019-0240-1. (Visited on 2024-04-04) (cit. on p. 35). [77] I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning . Adaptive Computation and Machine Learning. Cambridge, Mass: The MIT press, 2016. isbn: 978-0-262-03561-3 (cit. on pp. 27, 36, 55, 100). [78] E. Grant et al. “An Initialization Strategy for Addressing Barren Plateaus in Parametrized Quantum Circuits”. In: Quantum 3 (2019-12), p. 214. doi: 10.22331/q-2019-12-09-214. (Visited on 2024-04-12) (cit. on p. 43). [79] A. Gretton et al. A Kernel Method for the Two-Sample Problem . 2008-05. doi: 10.48550/arXiv. 0805.2368. arXiv: 0805.2368 [cs]. (Visited on 2024-05-24) (cit. on p. 142). [80] L. K. Grover. A Fast Quantum Mechanical Algorithm for Database Search . 1996-11. doi: 10.4 8550/arXiv.quant-ph/9605043. arXiv: quant-ph/9605043. (Visited on 2024-06-04) (cit. on pp. 1, 211). [81] A. Hannun. An Introduction to Fisher Information . https://awni.github.io/intro-fisher-information/. (Visited on 2024-04-03) (cit. on p. 22). 232 BIBLIOGRAPHY [82] A. Harrow and J. Napp. “Low-Depth Gradient Measurements Can Improve Convergence in Variational Hybrid Quantum-Classical Algorithms”. In: Physical Review Letters 126.14 (2021-04), p. 140502. issn: 0031-9007, 1079-7114. doi: 10.1103/PhysRevLett.126.140502. arXiv: 1901.05374 [quant-ph]. (Visited on 2024-04-08) (cit. on p. 38). [83] A. W. Harrow, A. Hassidim, and S. Lloyd. “Quantum Algorithm for Solving Linear Systems of Equations”. In: Physical Review Letters 103.15 (2009-10), p. 150502. issn: 0031-9007, 10797114. doi: 10.1103/PhysRevLett.103.150502. arXiv: 0811.3171 [quant-ph]. (Visited on 2024-06-11) (cit. on p. 1). [84] T. Haug, K. Bharti, and M. S. Kim. “Capacity and Quantum Geometry of Parametrized Quantum Circuits”. In: PRX Quantum 2.4 (2021-10), p. 040309. issn: 2691-3399. doi: 10 . 1103 /PRXQuantum.2.040309. arXiv: 2102.01659 [quant-ph, stat]. (Visited on 2024-0403) (cit. on p. 34). [85] T. Haug and M. S. Kim. Generalization with Quantum Geometry for Learning Unitaries . 2023-03. arXiv: 2303.13462 [quant-ph, stat]. (Visited on 2023-03-27) (cit. on p. 147). [86] T. Haug and M. S. Kim. Optimal Training of Variational Quantum Algorithms without Barren Plateaus . 2021-06. arXiv: 2104 . 14543 [quant-ph, stat]. (Visited on 2023-09-11) (cit. on pp. 149, 156). [87] P. Hayden, D. W. Leung, and A. Winter. “Aspects of Generic Entanglement”. In: Communications in Mathematical Physics 265.1 (2006-07), pp. 95–117. issn: 0010-3616, 1432-0916. doi: 10.1 007/s00220-006-1535-6. arXiv: quant-ph/0407049. (Visited on 2024-03-26) (cit. on p. 20). [88] C. W. Helstrom. “Quantum Detection and Estimation Theory”. In: Journal of Statistical Physics 1.2 (1969-06), pp. 231–252. issn: 1572-9613. doi: 10.1007/BF01007479. (Visited on 202404-02) (cit. on p. 21). [89] Z. Holmes et al. “Connecting Ansatz Expressibility to Gradient Magnitudes and Barren Plateaus”. In: PRX Quantum 3.1 (2022-01), p. 010313. issn: 2691-3399. doi: 10.1103/PRXQuantum.3 .010313. arXiv: 2101.02138 [quant-ph, stat]. (Visited on 2024-03-26) (cit. on pp. 20, 195, 197). [90] K. Hornik. “Approximation Capabilities of Multilayer Feedforward Networks”. In: Neural Networks 4.2 (1991-01), pp. 251–257. issn: 0893-6080. doi: 10.1016/0893-6080(91)90009-T. (Visited on 2024-03-29) (cit. on p. 31). [91] J.-Y. Hsiao et al. Unentangled Quantum Reinforcement Learning Agents in the OpenAI Gym . 202203. doi: 10.48550/arXiv.2203.14348. arXiv: 2203.14348 [cond-mat, physics:quant-ph]. (Visited on 2024-06-11) (cit. on pp. 2, 6). 233 BIBLIOGRAPHY [92] M. Incudini et al. Automatic and Effective Discovery of Quantum Kernels . 2023-12. doi: 10.485 50/arXiv.2209.11144. arXiv: 2209.11144 [quant-ph]. (Visited on 2024-04-04) (cit. on p. 35). [93] S. Jerbi et al. “Parametrized Quantum Policies for Reinforcement Learning”. In: Advances in Neural Information Processing Systems . Vol. 34. Curran Associates, Inc., 2021, pp. 28362–28375. (Visited on 2023-03-20) (cit. on pp. 2, 6, 33, 96, 104, 113, 126, 152, 153, 155, 193). [94] S. Jerbi et al. “Quantum Enhancements for Deep Reinforcement Learning in Large Spaces”. In: PRX Quantum 2.1 (2021-02), p. 010328. issn: 2691-3399. doi: 10.1103/PRXQuantum.2.0 10328. (Visited on 2024-04-26) (cit. on pp. 6, 51). [95] S. Jerbi et al. “Quantum Machine Learning beyond Kernel Methods”. In: Nature Communications 14.1 (2023-01), p. 517. issn: 2041-1723. doi: 10 . 1038 / s41467 - 023 - 36159 - y. arXiv: 2110.13162 [quant-ph, stat]. (Visited on 2024-03-28) (cit. on pp. 31, 32). [96] S. Jerbi et al. Quantum Policy Gradient Algorithms . 2022-12. doi: 10.4230/LIPIcs.TQC.20 23.13. arXiv: 2212.09328 [quant-ph, stat]. (Visited on 2023-10-23) (cit. on pp. 6, 126, 213). [97] S. Jerbi et al. Shadows of Quantum Machine Learning . 2023-05. arXiv: 2306.00061 [quant-ph, stat]. (Visited on 2024-03-28) (cit. on p. 115). [98] S. Johri et al. Nearest Centroid Classification on a Trapped Ion Quantum Computer . 2020-12. arXiv: 2012.04145 [quant-ph]. (Visited on 2024-03-28) (cit. on p. 30). [99] R. Jozsa and A. Miyake. Matchgates and Classical Simulation of Quantum Circuits . 2008-11. doi: 10.48550/arXiv.0804.4050. arXiv: 0804.4050. (Visited on 2024-11-04) (cit. on pp. 26, 162). [100] S. M. Kakade. “A Natural Policy Gradient”. In: Advances in Neural Information Processing Systems . Vol. 14. MIT Press, 2001. (Visited on 2023-09-08) (cit. on pp. 3, 61, 64, 102, 144, 146). [101] S. M. Kakade. “On the Sample Complexity of Reinforcement Learning”. PhD thesis. 2003 (cit. on pp. 63, 64). [102] S. Kazi et al. Analyzing the Quantum Approximate Optimization Algorithm: Ansätze, Symmetries, and Lie Algebras . 2024-10. doi: 10 . 48550 / arXiv . 2410 . 05187. arXiv: 2410 . 05187. (Visited on 2024-11-10) (cit. on p. 166). [103] I. Kerenidis, J. Landman, and N. Mathur. Classical and Quantum Algorithms for Orthogonal Neural Networks . 2022-12. doi: 10.48550/arXiv.2106.07198. arXiv: 2106.07198 [quant-ph]. (Visited on 2024-03-28) (cit. on p. 30). [104] S. Kim et al. “Deepmellow: Removing the Need for a Target Network in Deep Q-learning”. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence . IJCAI’19. Macao, China: AAAI Press, 2019-08, pp. 2733–2739. isbn: 978-0-9992411-4-1. (Visited on 2024-05-29) (cit. on p. 205). 234 BIBLIOGRAPHY [105] D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization . 2017-01. doi: 10.48550 /arXiv.1412.6980. arXiv: 1412.6980 [cs]. (Visited on 2024-04-05) (cit. on p. 35). [106] M. J. Kochenderfer and T. A. Wheeler. Algorithms for Optimization . Cambridge: The MIT press, 2019. isbn: 978-0-262-03942-0 (cit. on p. 35). [107] V. Konda and J. Tsitsiklis. “Actor-Critic Algorithms”. In: Advances in Neural Information Processing Systems . Vol. 12. MIT Press, 1999. (Visited on 2024-05-03) (cit. on p. 60). [108] G. Kruse et al. “Variational Quantum Circuit Design for Quantum Reinforcement Learning on Continuous Environments”. In: Proceedings of the 16th International Conference on Agents and Artificial Intelligence . 2024, pp. 393–400. doi: 10.5220/0012353100003636. arXiv: 2312 .13798 [quant-ph]. (Visited on 2024-06-10) (cit. on p. 114). [109] J. M. Kübler et al. “An Adaptive Optimizer for Measurement-Frugal Variational Algorithms”. In: Quantum 4 (2020-05), p. 263. doi: 10.22331/q-2020-05-11-263. (Visited on 2024-04-04) (cit. on p. 35). [110] M. Larocca et al. “Diagnosing Barren Plateaus with Tools from Quantum Optimal Control”. In: Quantum 6 (2022-09), p. 824. issn: 2521-327X. doi: 10.22331/q-2022-09-29-824. arXiv: 2105.14377 [quant-ph]. (Visited on 2022-09-30) (cit. on pp. 113, 140). [111] M. Larocca et al. “Theory of Overparametrization in Quantum Neural Networks”. In: Nature Computational Science 3.6 (2023-06), pp. 542–551. issn: 2662-8457. doi: 10.1038/s43588-02 3-00467-6. (Visited on 2024-03-27) (cit. on pp. 35, 37, 43, 156, 157). [112] R. LaRose and B. Coyle. “Robust Data Encodings for Quantum Classifiers”. In: Physical Review A 102.3 (2020-09), p. 032420. issn: 2469-9926, 2469-9934. doi: 10.1103/PhysRevA.102.0 32420. arXiv: 2003.01695 [quant-ph]. (Visited on 2024-03-28) (cit. on p. 28). [113] E. L. Lehmann and G. Casella. Theory of Point Estimation . 2nd ed. Springer Texts in Statistics. New York: Springer, 1998. isbn: 978-0-387-98502-2 (cit. on pp. 22, 23). [114] L. Leone et al. On the Practical Usefulness of the Hardware Efficient Ansatz . 2022-11. doi: 10 .48550/arXiv.2211.01477. arXiv: 2211.01477 [quant-ph]. (Visited on 2023-05-11) (cit. on p. 41). [115] A. Letcher, S. Woerner, and C. Zoufal. “Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits”. In: Quantum 8 (2024-09), p. 1484. doi: 10.22331/q-2024-09-25-148 4. (Visited on 2025-01-02) (cit. on pp. 42, 140, 167, 169). [116] T. Liang et al. Fisher-Rao Metric, Geometry, and Complexity of Neural Networks . 2019-02. doi: 10.48550/arXiv.1711.01530. arXiv: 1711.01530 [cs, stat]. (Visited on 2024-0408) (cit. on p. 38). 235 BIBLIOGRAPHY [117] J. Liu et al. “Quantum Fisher Information Matrix and Multiparameter Estimation”. In: Journal of Physics A: Mathematical and Theoretical 53.2 (2020-01), p. 023001. issn: 1751-8113, 17518121. doi: 10.1088/1751-8121/ab5d4d. arXiv: 1907.08037 [quant-ph]. (Visited on 2024-04-02) (cit. on p. 22). [118] S. Lloyd, M. Mohseni, and P. Rebentrost. “Quantum Principal Component Analysis”. In: Nature Physics 10.9 (2014-09), pp. 631–633. issn: 1745-2481. doi: 10.1038/nphys3029. (Visited on 2024-06-11) (cit. on p. 1). [119] O. Lockwood and M. Si. Reinforcement Learning with Quantum Variational Circuits . 2020-08. doi: 10.48550/arXiv.2008.07524. arXiv: 2008.07524 [quant-ph, stat]. (Visited on 2024-06-07) (cit. on p. 5). [120] J. M. Lourenço. The NOVAthesis L A T EX Template User’s Manual . NOVA University Lisbon. 2021. url: https://github.com/joaomlourenco/novathesis/raw/main/template.pdf (cit. on p. ii). [121] G. H. Low, T. J. Yoder, and I. L. Chuang. “Quantum Inference on Bayesian Networks”. In: Physical Review A 89.6 (2014-06), p. 062315. issn: 1050-2947, 1094-1622. doi: 10.1103/PhysRevA.8 9.062315. arXiv: 1402.7359 [quant-ph]. (Visited on 2024-05-31) (cit. on pp. 206, 208, 210, 211, 224). [122] R. Manenti and M. Motta. Quantum Information Science . Oxford, New York: Oxford University Press, 2023-11. isbn: 978-0-19-878748-8 (cit. on pp. 15, 28). [123] D. J. Mankowitz et al. “Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning”. In: Nature 618.7964 (2023-06), pp. 257–263. issn: 1476-4687. doi: 10.1038/s41586-02306004-9. (Visited on 2024-04-22) (cit. on p. 44). [124] C. O. Marrero, M. Kieferová, and N. Wiebe. Entanglement Induced Barren Plateaus . 2021-03. doi: 10.48550/arXiv.2010.15968. arXiv: 2010.15968 [quant-ph]. (Visited on 2023-05-11) (cit. on p. 39). [125] S. C. Marshall, S. Aaronson, and V. Dunjko. Improved Separation between Quantum and Classical Computers for Sampling and Functional Tasks . 2024-10. arXiv: 2410.20935. (Visited on 202411-05) (cit. on pp. 25, 159, 160). [126] G. B. Mbeng, R. Fazio, and G. Santoro. Quantum Annealing: A Journey through Digitalization, Control, and Hybrid Quantum Variational Schemes . 2019-12. arXiv: 1906.08948 [quant-ph]. (Visited on 2024-04-04) (cit. on p. 35). [127] J. R. McClean et al. “Barren Plateaus in Quantum Neural Network Training Landscapes”. In: Nature Communications 9.1 (2018-11), p. 4812. issn: 2041-1723. doi: 10.1038/s41467-01 8-07090-4. (Visited on 2024-04-09) (cit. on pp. 3, 39, 40, 117). [128] E. Meckes. The Random Matrix Theory of the Classical Compact Groups . 2019-08. isbn: 978-1108-41952-9. doi: 10.1017/9781108303453 (cit. on pp. 19, 20). 236 BIBLIOGRAPHY [129] D. A. Meyer and N. R. Wallach. “Global Entanglement in Multiparticle Systems”. In: Journal of Mathematical Physics 43.9 (2002-09), pp. 4273–4278. issn: 0022-2488, 1089-7658. doi: 10.1 063/1.1497700. arXiv: quant-ph/0108104. (Visited on 2024-03-23) (cit. on p. 15). [130] J. J. Meyer. “Fisher Information in Noisy Intermediate-Scale Quantum Applications”. In: Quantum 5 (2021-09), p. 539. doi: 10.22331/q-2021-09-09-539. (Visited on 2023-03-27) (cit. on pp. 22, 23, 143–145, 147, 155). [131] N. Meyer et al. Quantum Natural Policy Gradients: Towards Sample-Efficient Reinforcement Learning . 2023-08. doi: 10.48550/arXiv.2304.13571. arXiv: 2304.13571 [quant-ph]. (Visited on 2023-10-23) (cit. on pp. 3, 6, 223). [132] N. Meyer et al. Quantum Policy Gradient Algorithm with Optimized Action Decoding . 2023-05. doi: 10.48550/arXiv.2212.06663. arXiv: 2212.06663 [quant-ph]. (Visited on 2023-05-29) (cit. on pp. 6, 77, 78). [133] F. Mezzadri. How to Generate Random Matrices from the Classical Compact Groups . 2007-02. doi: 10.48550/arXiv.math-ph/0609050. arXiv: math-ph/0609050. (Visited on 2024-03-26) (cit. on p. 19). [134] K. Mitarai et al. “Quantum Circuit Learning”. In: Physical Review A 98.3 (2018-09), p. 032309. issn: 2469-9926, 2469-9934. doi: 10.1103/PhysRevA.98.032309. arXiv: 1803.00745 [quant-ph]. (Visited on 2024-04-05) (cit. on pp. 36, 141). [135] V. Mnih et al. Asynchronous Methods for Deep Reinforcement Learning . 2016-06. doi: 10.4855 0/arXiv.1602.01783. arXiv: 1602.01783 [cs]. (Visited on 2024-05-03) (cit. on p. 60). [136] V. Mnih et al. “Human-Level Control through Deep Reinforcement Learning”. In: Nature 518.7540 (2015-02), pp. 529–533. issn: 1476-4687. doi: 10.1038/nature14236. (Visited on 2024-0430) (cit. on pp. 55, 56, 181, 195). [137] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning . Second edition. Adaptive Computation and Machine Learning. Cambridge, Massachusetts: The MIT Press, 2018. isbn: 978-0-262-03940-6 (cit. on p. 33). [138] A. Montanaro and L. Zhou. Quantum Speedups in Solving Near-Symmetric Optimization Problems by Low-Depth QAOA . 2024-11. doi: 10.48550/arXiv.2411.04979. arXiv: 2411.04979 [quant-ph]. (Visited on 2024-12-30) (cit. on p. 26). [139] M. Morales and C. Isbell. Grokking Deep Reinforcement Learning . Shelter Island: Manning, 2020. isbn: 978-1-61729-545-4 (cit. on pp. 55, 62). [140] T. Müller et al. Towards Multi-Agent Reinforcement Learning Using Quantum Boltzmann Machines . 2021-11. doi: 10.48550/arXiv.2109.10900. arXiv: 2109.10900 [cs]. (Visited on 202406-10) (cit. on p. 6). 237 BIBLIOGRAPHY [141] Y. Nakata and M. Murao. “Diagonal-Unitary 2-Designs and Their Implementations by Quantum Circuits”. In: International Journal of Quantum Information 11.07 (2013-10), p. 1350062. issn: 02197499, 1793-6918. doi: 10.1142/S0219749913500627. arXiv: 1206.4451 [quant-ph]. (Visited on 2025-01-07) (cit. on p. 167). [142] M. V. den Nest. Classical Simulation of Quantum Computation, the Gottesman-Knill Theorem, and Slightly Beyond . 2009-10. doi: 10 . 48550 / arXiv . 0811 . 0898. arXiv: 0811 . 0898 [quant-ph]. (Visited on 2024-12-30) (cit. on p. 24). [143] B. Neyshabur, R. R. Salakhutdinov, and N. Srebro. “Path-SGD: Path-Normalized Optimization in Deep Neural Networks”. In: Advances in Neural Information Processing Systems . Vol. 28. Curran Associates, Inc., 2015. (Visited on 2024-04-08) (cit. on p. 37). [144] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition . 10th. USA: Cambridge University Press, 2011. isbn: 978-1-107-00217-3 (cit. on pp. 13, 14, 24). [145] M. Y. Niu et al. “Universal Quantum Control through Deep Reinforcement Learning”. In: npj Quantum Information 5.1 (2019-04), pp. 1–8. issn: 2056-6387. doi: 10.1038/s41534-019-0141 -3. (Visited on 2023-10-24) (cit. on pp. 97, 143). [146] R. Orús. “Tensor Networks for Complex Quantum Systems”. In: Nature Reviews Physics 1.9 (201909), pp. 538–550. issn: 2522-5820. doi: 10 . 1038 / s42254 - 019 - 0086 - 7. (Visited on 2024-04-05) (cit. on p. 36). [147] G. D. Paparo et al. “Quantum Speedup for Active Learning Agents”. In: Physical Review X 4.3 (2014-07), p. 031002. issn: 2160-3308. doi: 10.1103/PhysRevX.4.031002. (Visited on 2024-06-07) (cit. on p. 5). [148] A. Paszke et al. PyTorch: An Imperative Style, High-Performance Deep Learning Library . 201912. doi: 10.48550/arXiv.1912.01703. arXiv: 1912.01703 [cs, stat]. (Visited on 2024-04-05) (cit. on p. 114). [149] A. Pellow-Jarman et al. “A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver”. In: Quantum Information Processing 20.6 (2021-06), p. 202. issn: 1570-0755, 1573-1332. doi: 10.1007/s1112802103140x. arXiv: 2106.08682 [quant-ph]. (Visited on 2024-04-04) (cit. on p. 35). [150] A. Pérez-Salinas et al. Data Re-Uploading for a Universal Quantum Classifier . 2020-06. doi: 10.4 8550/arXiv.1907.02085. arXiv: 1907.02085. (Visited on 2024-11-12) (cit. on p. 165). [151] A. Pérez-Salinas et al. “Data Re-Uploading for a Universal Quantum Classifier”. In: Quantum 4 (2020-02), p. 226. issn: 2521-327X. doi: 10.22331/q-2020-02-06-226. arXiv: 1907.02 085 [quant-ph]. (Visited on 2024-03-28) (cit. on p. 30). 238 BIBLIOGRAPHY [152] A. Pérez-Salinas et al. “One Qubit as a Universal Approximant”. In: Physical Review A 104.1 (202107), p. 012405. doi: 10.1103/PhysRevA.104.012405. (Visited on 2024-04-01) (cit. on pp. 33, 104, 113, 192, 198). [153] A. Peruzzo et al. “A Variational Eigenvalue Solver on a Photonic Quantum Processor”. In: Nature Communications 5.1 (2014-07), p. 4213. issn: 2041-1723. doi: 10.1038/ncomms5213. (Visited on 2024-03-27) (cit. on p. 21). [154] A. Pesah et al. “Absence of Barren Plateaus in Quantum Convolutional Neural Networks”. In: Physical Review X 11.4 (2021-10), p. 041011. doi: 10.1103/PhysRevX.11.041011. (Visited on 2023-05-11) (cit. on p. 43). [155] D. Petz and C. Ghinea. “Introduction to Quantum Fisher Information”. In: Quantum Probability and Related Topics . Vol. Volume 27. QP-PQ: Quantum Probability and White Noise Analysis. WORLD SCIENTIFIC, 2011-01, pp. 261–281. isbn: 978-981-4338-73-8. doi: 10.1142/978981433874 5_0015. (Visited on 2024-04-02) (cit. on pp. 22, 23). [156] J. Preskill. “Quantum Computing in the NISQ Era and Beyond”. In: Quantum 2 (2018-08), p. 79. doi: 10.22331/q-2018-08-06-79. (Visited on 2024-06-11) (cit. on p. 1). [157] R. Puig-i-Valls et al. Variational Quantum Simulation: A Case Study for Understanding Warm Starts . 2024-04. doi: 10.48550/arXiv.2404.10044. arXiv: 2404.10044 [quant-ph, stat]. (Visited on 2024-05-24) (cit. on pp. 141, 156). [158] M. Ragone et al. A Unified Theory of Barren Plateaus for Deep Parametrized Quantum Circuits . 2023-09. arXiv: 2309.09342 [quant-ph]. (Visited on 2024-01-12) (cit. on pp. 41, 42). [159] J. Rajakumar, J. D. Watson, and Y.-K. Liu. Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth . 2024-10. doi: 10.48550/arXiv.2403.14607. arXiv: 2403.1 4607 [quant-ph]. (Visited on 2025-01-06) (cit. on p. 164). [160] P. Rebentrost, M. Mohseni, and S. Lloyd. “Quantum Support Vector Machine for Big Data Classification”. In: Physical Review Letters 113.13 (2014-09), p. 130503. issn: 0031-9007, 1079-7114. doi: 10.1103/PhysRevLett.113.130503. arXiv: 1307.0471 [quant-ph]. (Visited on 2024-03-28) (cit. on pp. 1, 30). [161] P. Ronagh. The Problem of Dynamic Programming on a Quantum Computer . 2021-07. doi: 10 .48550/arXiv.1906.02229. arXiv: 1906.02229 [quant-ph]. (Visited on 2024-06-07) (cit. on p. 5). [162] M. S. Rudolph et al. Trainability Barriers and Opportunities in Quantum Generative Modeling . 2023-05. arXiv: 2305.02881 [hep-ex, physics:quant-ph, stat]. (Visited on 202308-10) (cit. on pp. 41, 126, 142). [163] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach (4th Edition) . Pearson, 2020. isbn: 978-0-13-461099-3. (Visited on 2023-10-23) (cit. on pp. 208, 209). 239 BIBLIOGRAPHY [164] S. H. Sack et al. “Avoiding Barren Plateaus Using Classical Shadows”. In: PRX Quantum 3.2 (2022-06), p. 020365. issn: 2691-3399. doi: 10 . 1103 / PRXQuantum . 3 . 020365. arXiv: 2201.08194 [quant-ph]. (Visited on 2024-04-12) (cit. on p. 43). [165] J. Schrittwieser et al. “Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model”. In: Nature 588.7839 (2020-12), pp. 604–609. issn: 1476-4687. doi: 10.1038/s41586-02003051-4. (Visited on 2024-04-22) (cit. on pp. 44, 48). [166] M. Schuld. Supervised Quantum Machine Learning Models Are Kernel Methods . 2021-04. doi: 10.48550/arXiv.2101.11020. arXiv: 2101.11020 [quant-ph, stat]. (Visited on 2024-03-28) (cit. on pp. 1, 29). [167] M. Schuld and N. Killoran. “Quantum Machine Learning in Feature Hilbert Spaces”. In: Physical Review Letters 122.4 (2019-02), p. 040504. doi: 10.1103/PhysRevLett.122.040504. (Visited on 2024-03-28) (cit. on p. 29). [168] M. Schuld and F. Petruccione. Machine Learning with Quantum Computers . Second edition. Cham, Switzerland: Springer, 2021. isbn: 978-3-030-83098-4 (cit. on pp. 12, 16, 18, 27–30, 33, 38, 39). [169] M. Schuld, R. Sweke, and J. J. Meyer. The Effect of Data Encoding on the Expressive Power of Variational Quantum Machine Learning Models . 2021-03. doi: 10.48550/arXiv.2008.0860 5. arXiv: 2008.08605. (Visited on 2024-11-12) (cit. on p. 165). [170] M. Schuld, R. Sweke, and J. J. Meyer. “The Effect of Data Encoding on the Expressive Power of Variational Quantum Machine Learning Models”. In: Physical Review A 103.3 (2021-03), p. 032430. issn: 2469-9926, 2469-9934. doi: 10.1103/PhysRevA.103.032430. arXiv: 2008.08605 [quant-ph, stat]. (Visited on 2023-05-12) (cit. on pp. 1, 30–33). [171] M. Schuld et al. “Circuit-Centric Quantum Classifiers”. In: Physical Review A 101.3 (2020-03), p. 032308. issn: 2469-9926, 2469-9934. doi: 10.1103/PhysRevA.101.032308. arXiv: 1804.00633 [quant-ph]. (Visited on 2024-03-28) (cit. on pp. 28, 71, 72, 137). [172] M. Schuld et al. “Evaluating Analytic Gradients on Quantum Hardware”. In: Physical Review A 99.3 (2019-03), p. 032331. issn: 2469-9926, 2469-9934. doi: 10.1103/PhysRevA.99.032331. arXiv: 1811.11184 [quant-ph]. (Visited on 2023-10-24) (cit. on pp. 36, 128). [173] J. Schulman et al. Proximal Policy Optimization Algorithms . 2017-08. doi: 10.48550/arXiv.1 707.06347. arXiv: 1707.06347 [cs]. (Visited on 2023-10-23) (cit. on pp. 60, 62, 114, 142). [174] J. Schulman et al. Trust Region Policy Optimization . 2017-04. doi: 10.48550/arXiv.1502.0 5477. arXiv: 1502.05477 [cs]. (Visited on 2023-10-23) (cit. on pp. 61, 63, 157). [175] A. Sequeira, L. P. Santos, and L. S. Barbosa. “Policy Gradients Using Variational Quantum Circuits”. In: Quantum Machine Intelligence 5.1 (2023-04), p. 18. issn: 2524-4914. doi: 10.1007 /s42484-023-00101-8. (Visited on 2023-05-11) (cit. on pp. 2, 96, 100, 126). 240 The lower bound on the variance of the policy gradient can thus be further simplified to: 𝕍𝜃𝜕𝜃log 𝜋𝜃≥𝔼𝜃(𝜕𝜃𝜋𝜃)2𝔼𝜃1 𝜋2 𝜃−3 2𝕍𝜃𝜕𝜃𝜋𝜃1 𝜋2 𝜃max ≥𝔼𝜃𝜕𝜃𝜋𝜃2 −𝕍𝜃𝜕𝜃𝜋𝜃2𝔼𝜃1 𝜋𝜃2 −𝕍𝜃1 𝜋𝜃2−3 2𝕍𝜃𝜕𝜃𝜋𝜃1 𝜋𝜃2 max (A) =𝕍𝜃𝜕𝜃𝜋𝜃2 𝕍𝜃1 𝜋𝜃2 −𝕍𝜃𝜕𝜃𝜋𝜃2 𝔼𝜃1 𝜋𝜃2 +3 2𝕍𝜃𝜕𝜃𝜋𝜃1 𝜋𝜃2 max(B) ≥𝕍𝜃𝜕𝜃𝜋𝜃2 𝕍𝜃1 𝜋𝜃2 −3𝕍𝜃𝜕𝜃𝜋𝜃2 𝔼𝜃1 𝜋𝜃2 (C) =𝕍𝜃𝜕𝜃𝜋𝜃2𝕍𝜃1 𝜋𝜃2 −3𝔼𝜃1 𝜋𝜃2 | {z } (𝑎) (D) where (A) is obtained from the lower bound of the expectation value of the product of two non-negative random variables, (B) from the assumption that either parameterized block before/after 𝜃forms a 1design and thus 𝔼𝜃[𝜕𝜃𝜋𝜃]=0and reorganizing terms and (C) from the upper bound on the expectation value and joining terms. Since the variance is non-negative it implies that (𝑎) ≥ 0. Therefore the variance will be lower bounded depending on the number of actions and corresponding globality of the observable. For |𝐴| ∈ O(𝑛), 𝕍𝜃𝜕𝜃𝜋𝜃2 ∈Ω(1 poly(𝑛))for O(log(𝑛))depth. It decays polynomially with the number of qubits since we are measuring log(𝑛)(adjacent) qubits [42]. Moreover, (𝑎) ≤ poly(𝑛). Thus, the overall variance deacay at most polynomially with the number of qubits. When the number of actions |𝐴| ∈ O(poly(𝑛)), 𝕍𝜃𝜕𝜃𝜋𝜃2 ∈Ω(2−poly(log(𝑛))). It decays faster than polynomially but slower than exponentially since we are measuring log(poly(𝑛))qubits [42]. In this case (𝑎) ≤ 2poly(log(𝑛))since we have |𝐴| ∈ poly(𝑛). Therefore the overall variance decay at most polylogarithmically with the number of qubits. Thus, completing the proof. □ 247 Appendix B Environment characteristics Environment State Action Reward function Horizon Termination criteria Cartpole 4 features 2 actions 𝐴={0,1} +1 per time step 200 time steps Reach horizon or out of bounds Acrobot 4 features 3 actions 𝐴={0,1,2} -1 + height 500 time steps Reach goal or horizon Table 11: Characterization of the environments considered in the numerical experiments. 248 Appendix C Natural policy gradients - hyperparameters Environment Policy Layers Observables Batch Size CartPole Born 4 {𝑃0, 𝑃1}10 Softmax 4 {𝑃0, 𝑃1}10 Acrobot Born 5 {𝑃0,3, 𝑃1, 𝑃2}10 Softmax 5 {𝑃0,3, 𝑃1, 𝑃2}10 Table 12: Characterization of the PQC’s considered in the numerical experiments. 𝑃𝑖indicates the projector in the computational basis in decimal. For the Cartpole environment a single-qubit was measured and the probability of each basis state associated to an action. In the Acrobot environment, the action assignmment was made using 𝑖𝑛𝑡 (𝑏)mod 3=𝑎for a particular basis state 𝑏. 249 Appendix D PQC-based DQN - hyperparameters 250 Hyperparameter CartPole-v0 Acrobot-v1 Qubits (n) 4 4 Layers 5 5 𝛾0.99 0.99 Trainable Input Scaling Yes, No Yes, No Trainable Output Scaling Yes, No Yes, No Learning Rate of Parameters 𝜃0.001 0.001 Learning Rate of Input Scaling Parameters 0.1 0.1 Learning Rate of Output Scaling Parameters 0.1 0.1 Batch Size 16 32 Decaying Schedule of 𝜖-Greedy Policy Exponential Exponential 𝜖init 1 1 𝜖dec 0.99 0.99 𝜖min 0.01 0.01 Update Model 1 5 Update Target Model 1 250 Size of Replay Buffer 10000 50000 Data Re-uploading Yes, No Yes, No Input Scaling Initialization Initialized as 1s Initialized as 1s Output Scaling Initialization Initialized as 1s Initialized as 1s Rotational Parameters Initialization Uniformly sampled between 0 and 𝜋 Uniformly sampled between 0 and 𝜋 ˜𝑤Initialization - - ˜ 𝑏Initialization - - Observables (𝑍0𝑍1, 𝑍2𝑍3) (𝑍0, 𝑍1𝑍2, 𝑍3) Table 13: PQC-based DQN hyperparameters for the numerical experiments of Section 9.5.1. 251 APPENDIX D. PQC-BASED DQN - HYPERPARAMETERS Parameter CartPole-v0 Acrobot-v1 Qubits (n) 4 4 Layers 5 5 𝛾0.99 0.99 Trainable Input Scaling Yes Yes Trainable Output Scaling Yes Yes Learning Rate of Parameters 𝜃0.001 0.001 Learning Rate of Input Scaling Parameters 0.1 0.1 Learning Rate of Output Scaling Parameters 0.1 0.1 Batch Size 16 32 Decaying Schedule of 𝜖-Greedy Policy Exponential Exponential 𝜖init 1 1 𝜖dec 0.99 0.99 𝜖min 0.01 0.01 Update Model 1 5 Update Target Model 1, 500, 1000, 2500 100, 1000, 2500, 5000 Size of Replay Buffer 10000 50000 Data Re-uploading Yes Yes Input Scaling Initialization Initialized as 1s Initialized as 1s Output Scaling Initialization Initialized as 1s Initialized as 1s 𝜃Initialization Uniformly sampled between 0 and 𝜋 Uniformly sampled between 0 and 𝜋 ˜𝑤Initialization - - ˜ 𝑏Initialization - - Observables (𝑍0𝑍1, 𝑍2𝑍3) (𝑍0, 𝑍1𝑍2, 𝑍3) Table 14: Complexity comparison between classical and quantum rejection sampling algorithms. 𝑁is the number of variables, 𝑀is the number of parents of any variable, and 𝑃(𝑒)is the probability of the evidence taking value 𝑒. 252 Parameter CartPole-v0 Acrobot-v1 Qubits (n) 1, 2, 4 1, 2, 4 Layers 5 5 𝛾0.99 0.99 Trainable Input Scaling Yes Yes Trainable Output Scaling Yes Yes Learning Rate of Parameters 𝜃0.001 0.001 Learning Rate of Input Scaling Parameters 0.001 0.001 Learning Rate of Output Scaling Parameters 0.1 0.1 Batch Size 16 32 Decaying Schedule of 𝜖-Greedy Policy Exponential Exponential 𝜖init 1 1 𝜖dec 0.99 0.99 𝜖min 0.01 0.01 Update Model 1 5 Update Target Model 1, 500, 1000, 2500 100, 1000, 2500, 5000 Size of Replay Buffer 10000 50000 Data Re-uploading Yes Yes Input Scaling Initialization - - Output Scaling Initialization Initialized as 1s Initialized as 1s 𝜃Initialization - - ˜𝑤Initialization Gaussian Distribution (mean=0, std=0.01) Gaussian Distribution (mean=0, std=0.01) ˜ 𝑏Initialization Initialized as 0s Initialized as 0s Observables (𝑍0𝑍1, 𝑍2𝑍3) (𝑍0, 𝑍1𝑍2, 𝑍3) Table 15: Hyperparameters of Models for Figure 91 253 APPENDIX D. PQC-BASED DQN - HYPERPARAMETERS Parameter CartPole-v0 Acrobot-v1 Qubits (n) 2, 4, 6, 8, 10, 12 2, 4, 6, 8, 10, 12 Layers 5 5 𝛾0.99 0.99 Trainable Input Scaling Yes Yes Trainable Output Scaling Yes Yes Learning Rate of Parameters 𝜃0.001 0.001 Learning Rate of Input Scaling Parameters 0.001 0.001 Learning Rate of Output Scaling Parameters 0.1 0.1 Batch Size 16 32 Decaying Schedule of 𝜖-Greedy Policy Exponential Exponential 𝜖init 1 1 𝜖dec 0.99 0.99 𝜖min 0.01 0.01 Update Model 1 5 Update Target Model 1, 500, 1000, 2500 100, 1000, 2500, 5000 Size of Replay Buffer 10000 50000 Data Re-uploading Yes Yes Input Scaling Initialization - - Output Scaling Initialization Initialized as 1s Initialized as 1s 𝜃Initialization - - ˜𝑤Initialization Gaussian Distribution (mean=0, std=0.01) Gaussian Distribution (mean=0, std=0.01) ˜ 𝑏Initialization Initialized as 0s Initialized as 0s Observables (𝑍0. . . 𝑍𝑛/2−1, 𝑍𝑛/2. . . 𝑍𝑛) (𝑍0, 𝑍1. . . 𝑍𝑛−1, 𝑍𝑛) Table 16: Hyperparameters of Models for Figure 93 254 Appendix E Quantum belief update Lemma E.0.1. Let 𝜌=|𝜓 final ih𝜓 final | be the quantum state after the amplitude amplification operator. The probability of measuring the state 𝑠0 is given by, h𝑠0|𝜌|𝑠0i=1 𝜂𝑃(𝑜|𝑠0, 𝑎)Õ 𝑠 𝑏(𝑠)𝑃(𝑠0|𝑠, 𝑎)(E.1) which is an equivalent belief update rule. Proof. 𝜌=|𝜓final ih𝜓final | =1 𝜂Õ 𝑠,𝑎0,𝑜0,𝑟 Õ 𝑠★∈S p𝑏(𝑠★)Õ 𝑠0∈S p𝑃(𝑠0|𝑠★, 𝑎)p𝑃(𝑜|𝑠0, 𝑎)Õ 𝑟0∈R p𝑃(𝑟0|𝑠★, 𝑎) h𝑠𝑎0𝑜0𝑟|𝑠★𝑎𝑠0𝑜𝑟0i! Õ 𝑠★∈S p𝑏(𝑠★)Õ 𝑠0∈S p𝑃(𝑠0|𝑠★, 𝑎)p𝑃(𝑜|𝑠0, 𝑎)Õ 𝑟0∈R p𝑃(𝑟0|𝑠★, 𝑎) h𝑠★𝑎𝑠0𝑜𝑟0|𝑠𝑎0𝑜0𝑟i! =1 𝜂Õ 𝑠,𝑎0,𝑜0,𝑟 Õ 𝑠★∈S p𝑏(𝑠★)Õ 𝑠0∈S p𝑃(𝑠0|𝑠★, 𝑎)p𝑃(𝑜|𝑠0, 𝑎)Õ 𝑟0∈R p𝑃(𝑟0|𝑠★, 𝑎)𝛿𝑠𝑠★𝛿𝑎𝑎0𝛿𝑜𝑜0𝛿𝑟𝑟0|𝑠0i! Õ 𝑠★∈S p𝑏(𝑠★)Õ 𝑠0∈S p𝑃(𝑠0|𝑠★, 𝑎)p𝑃(𝑜|𝑠0, 𝑎)Õ 𝑟0∈R p𝑃(𝑟0|𝑠★, 𝑎)𝛿𝑠𝑠★𝛿𝑎𝑎0𝛿𝑜𝑜0𝛿𝑟𝑟0h𝑠0|! =1 𝜂Õ 𝑠∈S 𝑏(𝑠)Õ 𝑟∈R Õ 𝑠0∈S p𝑃(𝑠0|𝑠, 𝑎)p𝑃(𝑜|𝑠0, 𝑎)p𝑃(𝑟|𝑠, 𝑎)|𝑠0i! Õ 𝑠0∈S p𝑃(𝑠0|𝑠, 𝑎)p𝑃(𝑜|𝑠0, 𝑎)p𝑃(𝑟|𝑠, 𝑎)h𝑠0|! 255 APPENDIX E. QUANTUM BELIEF UPDATE Then, the probability of measuring state 𝑆𝑡+1with value 𝑠0is computed as follows: h𝑠0|𝜌|𝑠0i=1 𝜂Õ 𝑠∈S 𝑏(𝑠)Õ 𝑟∈R Õ 𝑠★∈S p𝑃(𝑠★|𝑠, 𝑎)p𝑃(𝑜|𝑠★, 𝑎)p𝑃(𝑟|𝑠, 𝑎)𝑠0|𝑠★! Õ 𝑠★∈S p𝑃(𝑠★|𝑠, 𝑎)p𝑃(𝑜|𝑠★, 𝑎)p𝑃(𝑟|𝑠, 𝑎)𝑠★|𝑠0! =1 𝜂Õ 𝑠∈S 𝑏(𝑠)Õ 𝑟∈R Õ 𝑠★∈S p𝑃(𝑠★|𝑠, 𝑎)p𝑃(𝑜|𝑠★, 𝑎)p𝑃(𝑟|𝑠, 𝑎)𝛿𝑠0𝑠★! Õ 𝑠★∈S p𝑃(𝑠★|𝑠, 𝑎)p𝑃(𝑜|𝑠★, 𝑎)p𝑃(𝑟|𝑠, 𝑎)𝛿𝑠★𝑠0! =1 𝜂Õ 𝑠∈S 𝑏(𝑠)Õ 𝑟∈R 𝑃(𝑠0|𝑠, 𝑎)𝑃(𝑜|𝑠0, 𝑎)𝑃(𝑟|𝑠, 𝑎) =1 𝜂𝑃(𝑜|𝑠0, 𝑎)Õ 𝑠∈S 𝑃(𝑠0|𝑠, 𝑎)𝑏(𝑠)Õ 𝑟∈R 𝑃(𝑟|𝑠, 𝑎) =1 𝜂𝑃(𝑜|𝑠0, 𝑎)Õ 𝑠∈S 𝑃(𝑠0|𝑠, 𝑎)𝑏(𝑠) □ 256