Trainability issues in quantum policy gradients

PAPER • OPEN ACCESS Trainability issues in quantum policy gradients To cite this article: André Sequeira et al 2024 Mach. Learn.: Sci. Technol. 5 035037 View the article online for updates and enhancements. You may also like Simulation-based inference on virtual brain models of disorders Meysam Hashemi, Abolfazl Ziaeemehr, Marmaduke M Woodman et al. - Quantum support vector data description for anomaly detection Hyeondo Oh and Daniel K Park - OmniJet-: the first cross-task foundation model for particle physics Joschka Birk, Anna Hallin and Gregor Kasieczka - This content was downloaded from IP address 2.80.236.195 on 01/09/2025 at 21:50 Mach. Learn.: Sci. Technol. 5(2024) 035037 https://doi.org/10.1088/2632-2153/ad6830 OPEN ACCESS RECEIVED 17 April 2024 REVISED 20 June 2024 ACCEPTED FOR PUBLICATION 26 July 2024 PUBLISHED 6 August 2024 Original Content from this work may be used under the terms of the Creative Commons Attribution 4.0 licence. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI. PAPER Trainability issues in quantum policy gradients André Sequeira1,2,3,∗, Luis Paulo Santos1,2,3and Luis Soares Barbosa1,2,3 1Department of Informatics, University of Minho, Braga, Portugal 2High Assurance Software Laboratory, INESC TEC, Braga, Portugal 3Quantum Linear-optical computation group, International Nanotechnology Laboratory, Braga, Portugal ∗Author to whom any correspondence should be addressed. E-mail: [email protected] Keywords: quantum policy gradients, barren plateaus, quantum reinforcement learning Abstract This research explores the trainability of Parameterized Quantum Circuit-based policies in Reinforcement Learning, an area that has recently seen a surge in empirical exploration. While some studies suggest improved sample complexity using quantum gradient estimation, the efficient trainability of these policies remains an open question. Our findings reveal significant challenges, including standard Barren Plateaus with exponentially small gradients and gradient explosion. These phenomena depend on the type of basis-state partitioning and the mapping of these partitions onto actions. For a polynomial number of actions, a trainable window can be ensured with a polynomial number of measurements if a contiguous-like partitioning of basis-states is employed. These results are empirically validated in a multi-armed bandit environment. 1. Introduction Variational Quantum Algorithms (VQAs), emerging as a cornerstone in the Noisy Intermediate Scale Quantum (NISQ) era, present a novel approach to overcoming the limitations inherent in quantum computing, such as restricted qubit availability and noise related constraints on circuit depth. Initially proposed as universal computation models [4], VQAs operate through a synergy of quantum and classical mechanisms. They utilize a Parameterized Quantum Circuit (PQC) where the parameters are fine-tuned via a classical optimization routine to achieve the global optimum of a specified objective function [5]. Despite the theoretical allure of VQAs, their practical efficiency is often hampered by the so-called barren plateau (BP) phenomenon, a critical challenge in quantum optimization [13]. This phenomenon, characterized by the exponential suppression of the gradients’ magnitude with an increasing number of qubits, requires an exponentially large number of measurements to allow the algorithm to effectively navigate through the optimization landscape. The BP phenomenon pose a significant hurdle, not only in gradient-based but also in gradient-free optimization approaches, where cost concentration emerges as a parallel challenge [2]. Understanding and mitigating the occurrence of BPs in specific VQAs is thus vital for harnessing any potential quantum advantage. Several factors contribute to the emergence of BPs, including deep and random quantum circuits [13], PQCs adhering to a volume law in entanglement entropy [12] etc. The work of Cerezo et al [6] particularly highlights the dependence of the BP phenomenon on the locality of the cost function, showing that local losses measured on a logarithmic number of qubits can retain trainability in shallow circuits [16]. Further complicating the picture, conventional machine learning cost functions like the mean squared error, negative log likelihood, and KL-divergence have been shown to lead to BPs [21]. BPs are typically characterized by the scaling of the variance of partial derivatives of the cost function, which diminishes exponentially with the number of qubits [13]. This scaling results in gradients increasingly concentrating around zero, making optimization exceedingly difficult. Another approach to characterize a BP is through the study of cost concentration [2], where cost differences between randomly selected points in the landscape show an exponential concentration with increasing qubits. In addition, the Fisher Information Matrix (FIM) spectrum, as explored in the work of Abbas et al [1], offers valuable insights into the flatness of the loss © 2024 The Author(s). Published by IOP Publishing Ltd Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al landscape in the presence of BPs, with the eigenvalues of the FIM becoming exponentially small as the number of qubits increases. Recent studies have expanded the application of VQAs to Reinforcement Learning (RL), showing promising results [10,19,20]. Notably, the work of Jerbi et al [11] demonstrated a quadratic optimization improvement in policy-based RL agents using PQC-based policies over classical agents. However, the trainability of these quantum policies, particularly in the face of BPs, remains an open question. In this context, our study aims to provide a deeper understanding of the trainability issues associated with PQC-based policies in RL, focusing on cost-function dependent BPs and their implications. We explore the challenges faced by specific variations of previously proposed Raw Policies [10,14], and investigate their performance under various conditions. Our findings contribute to the ongoing research on optimizing PQC-based agents in quantum RL, addressing critical questions on the interplay between policy types, number of qubits, action-space size, and the presence of BPs and other trainability issues such as exploding gradients. This research not only advances our understanding of quantum RL but also sets the stage for future investigations into other types of PQC-based policies [10,19], thereby unlocking the full potential of quantum computing in machine learning applications. 1.1. Related work Recent advancements have been documented concerning the application of VQAs to RL. There has been considerable empirical evidence supporting the efficacy of VQAs in diverse benchmark environments, encompassing both value-based [8,20] and policy-based [10,19] RL paradigms. A significant contribution in this field was made by Jerbi et al [11], who demonstrated a quadratic improvement in gradient estimation for optimizing policy-based RL agents using PQC-based policies compared to purely classical agents. In another notable work, Cherrat et al [9] introduced quantum neural network architectures featuring orthogonal and compound layers for policy and value functions, notably devoid of BPs in the context of financial hedging. At the same time, Meyer et al [14] posited that a global parity-based policy could provide more information to the agent and a more conducive optimization landscape. This proposition challenges the previously held belief that global measurements lead to flatter landscapes, implying further issues on trainability. The emerging divergence in these findings entails the need for further research to fully understand the impact of the BP phenomenon within RL, especially in the context of generalized PQC-based policies, as it may significantly influence optimization efficiency provided by gradient estimation. This investigation centers on analyzing cost-function dependent barren plateaus within the framework of policy-based RL, utilizing both local and global projector-based observables in conjunction with PQC-based policies. The primary objective of this study is to delineate variance limits for the gradient of the REINFORCE policy-dependent objective function [23], especially under the assumption of a PQC-based policy. We re-examine two previously introduced policies, redefined here for enhanced clarity: (1) The Contiguous-like Born policy, as referenced in [10], derived from categorizing basis states into a contiguous set proportional to the action-space size, and (2) The Parity-like Born policy, detailed in [14], formulated through a recursive parity function applied to measured basis states. 1.2. Contributions Our findings highlight that both contiguous and parity-like Born policies can potentially face extreme challenges in terms of trainability. On one side, the policy might encounter standard BPs characterized by exponentially vanishing gradients, while on the other, it may face issues of gradient explosion. These phenomena are heavily influenced by the locality of the observables employed that depend on the action-space size. For nqubit policies estimated through O(poly(n)) measurements, the contiguous-like Born policy exhibits a trainable region at logarithmic depth O(log(n)), assuming the action-space is of O(n)size. For a O(poly(n)number of actions, the policy enters a transition region where the locality of the observables increase but it is still possible to train under polynomially large number of measurements. Conversely, under the same conditions, the Parity-like Born policy is untrainable, suffering from a BP. Beyond polynomiallysized action spaces, no policy can be trained using a polynomial number of measurements since the probability of measuring basis states becomes exponentially suppressed with the number of qubits. In such a scenario, the gradient behavior shifts towards exploding gradients due to the exponentially small probabilities. The trainability of PQC-based policies was further analyzed by inspecting the FIM spectrum. It was observed that, under polynomially sized actions spaces, the FIM spectrum indeed reveals a BP for the Parity-like Born policy, as FIM entries shrink exponentially with increasing qubits, resulting in a spectrum highly concentrated at zero, therefore characterizing a flat landscape. Outside polynomial action spaces, the FIM spectrum becomes less informative about BPs due to the exponentially small probabilities that induce large FIM entries, causing a shift in the spectrum with more eigenvalues concentrated away from zero. 2 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al Empirical validation of these results was achieved by examining the scaling of the variance of the log likelihood gradient, using the simplified two-design ansatz [6] for the PQC-based policy. Furthermore, the effect of the observables’ global nature on a PQC-based agent’s trainability was explored in the context of learning to select the optimal arm in a simulated multi-armed bandit environment. The observations confirmed that for a PQC-based agent with a polynomial number of actions, the contiguous-like Born policy is capable of learning the optimal arm, unlike the parity-like policy. However, when extending beyond a polynomial number of actions, both policies were unable to learn the optimal arm, in line with our theoretical predictions. The rest of the document is organized as follows: section 2introduces the policy gradient framework in RL and the intricacies behind PQC-based policies such as gradient estimation. Section 3establishes novel results forming the core of this work. It provides clear lower bounds for the policy gradient’s variance. Section 4resorts to numerical experiments as an empirical validation of the theoretical predictions in section 3. Finally, section 5concludes the work and outlines future research directions. 2. Quantum policy gradients Policy Gradient algorithms are designed to optimize a parameterized policy π(a|s,θ) = P{at=a|st=s,θt=θ}, where θ∈Rkdenotes the parameter vector with dimension k,s,a, and trepresent the state, action and the time step, respectively. The essence of this approach is to enable optimal action selection without relying on a value function, with the primary aim of maximizing a performance measure J(θ). This is achieved by applying gradient ascent to J(θ)as follows: θi+1=θi+η∇θiJ(θi)(1) where ηis the learning rate. For discrete and small action spaces, a Softmax-Policy is commonly used to balance exploration and exploitation. The Monte-Carlo policy gradient, known as REINFORCE, estimates the gradient from samples across Ntrajectories of length T, or the horizon, under the parameterized policy. A known limitation of REINFORCE is the high variance of its gradient estimation due to the stochastic nature of sampling trajectories. This variance can negatively affect performance in complex settings. Introducing a baseline denoted by b(st), such as the average return, can reduce the variance without having to increase the number of samples N. The baseline is subtracted from the returned value to stabilize the optimization process, as shown in equation (2) ∇θJ(θ) = 1 N N−1 X i=0 T−1 X t=0 (Gt(τi)−b(sti))∇θlogπ(ati|sti,θ)(2) where Gt(τi)is the cumulative discounted return at time step tin trajectory τi. Throughout the rest of the paper, the baseline b(st)is considered as the average return across all trajectories b(st) = 1 N N−1 X i=0 Gt(τi).(3) In this work, we consider PQC-generated policies i.e. policies generated from PQCs. Specifically we consider two variants of the raw policies proposed in the literature and redefined here for enhanced clarity: (1)The Contiguous-like Born policy [10] and (2) Parity-like Born policy [14]. For completion, the Softmax-based PQC policy [10,19] is also defined but addressing its trainability is outside of the scope of this work. Let us start with the most general definition of a Born policy. 2.1. Born policy Definition 2.1. Let s∈ S be a state embedded in an n-qubit parameterized quantum state, |ψ(s,θ)⟩, where θ∈Rk. The probability associated to a given action a∈Ais given by: π(a|s,θ) = ⟨Pa⟩s,θ =⟨ψ(s,θ)|Pa|ψ(s,θ)⟩(4) where Pa=Pv∈Va|v⟩⟨v|is the projector into partition Va⊆Vwhere V={v0,v1,...,v2n−1}is the set of eigenstates of an observable O= 2n−1 X i=0 λi|vi⟩⟨vi|.(5) Moreover, Sa∈AVa=Vand Va∩Va′=∅, for all a=a′. 3 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al Figure 1. Partitions considered for the base case of |A|=2. (a) and (b) Illustrates a Contiguous-like and parity-like partitioning, respectively, of all 2nbasis states. (c) Action-projector-like partitioning considering just two basis states. Definition 2.1 introduces the most general definition of a Born policy. However, there could be partitions that do not take into account every eigenstate of a given observable, as described above. In these scenarios, the probability associated to a given action would not be normalized as before since Pa∈APa=I. Moreover, since the goal of this work is the study of cost-function dependent BPs in quantum policy gradients, different partitions Va, and the associated globality of the measurement should be further clarified. Figure 1illustrates different partitions considered throughout this work for |A|=2, which constitutes the base case in RL. 2.1.1. Contiguous-like Born policy Consider the action space A={a0,a1}. The simplest partitioning that fits definition 2.1, would be to separate all basis states in half i.e. Va0={|0⟩,|1⟩,|2⟩...|2n−1 2⟩} and Va1={|2n 2⟩...|2n−1⟩}. Such partitioning is illustrated in figure 1(a). In this case, even though every n-bit bitstring is considered to build the policy, a careful analysis of the partitioning indicates that it does not correspond to a global measurement. It is possible to assign a bitstring to its respective set by just measuring the first bit. If the bit is in state |0⟩(respectively, |1⟩) it corresponds to the set Va0(respectively, Va1). Thus, such assignment corresponds to a 1-local measurement, indeed. In general, for an arbitrary number of actions |A|⩽2nif we assign each bitstring to |A|contiguous sets, then the measurement will actually be (log|A|)-local, since to assign each bitstring log|A|bits are required to distinguish between the sets. As an example. let the the number of qubits be n=3. The total number of bitstrings is 23=8 , corresponding to the set {000,001,010,011,100,101,110,111}. Suppose |A|=4 with partition set V=V0∪V1∪V2∪V3. The number of bits needed to distinguish between sets is log2(4) = 2. Thus, the first 2 bits of each bitstring are considered to assign it to one of the 4 sets. Let abe represented in its binary expansion. Then, the partitioning will be given by V={000,001} ∪ {010,011} ∪ {100,101} ∪{110,111} ∪ {110,111}. and the measurement will be 2-local. 2.1.2. Parity-like Born policy Notice that for the base case |A|=2, the contiguous-like Born policy loses expressivity since the measurement becomes 1-local. We can actually devise a more expressive assignment by considering a parity function, as illustrated in figure 1(b). The 2nbitstrings in a n-qubit PQC can be considered assigning each of them by the parity of the bitstring (number of 1’s). Thus, the policy is represented as: π(a|s,θ) = ⊕b=a X b∈{0,1}n ⟨ψ(s,θ)|b⟩⟨b|ψ(s,θ)⟩.(6) Such an assignment constitutes a global measurement and the authors of [14] 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, provided a CNOT cascade prior to the measurement, as highlighted in [14]. For |A|>2, the authors designed a partitioning based on a recursive parity function which they conjecture to be optimal in the sense of extracted information and globality. Let m=log|A|be the number of recursive calls and bbe a n-bit bitstring measured through sampling a PQC. Then, the partition can be defined recursively as, C(m) [a]2=(b| n−1 M i=m bi=a0∧b∈ C(m−1) am···a2(a1⊕a0))(7) 4 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al Table 1. Summary of the locality of the measurement for the different partitions considered in this work. Born policy Locality of measurement Contiguous-like log|A|—local Parity-like n-local Action-projector-like n-local where [a]2=am...a0is the binary expansion of action a. Since for computing the parity, each of the nbits is necessary, a parity-based policy will be composed of a global measurement (or n-local) for |A|=2 as base case. Thus, it will always be global independently of the number of actions. 2.1.3. Action-projector-like Born policy There can also be partitions that do not take into account every eigenstate of a given observable. For instance, for the base case |A|=2, we could assign the all-zero state to action a0,⟨Pa0⟩s,θ =|⟨0|ψ(s,θ)⟩|2and the all-ones state to action a1,⟨Pa1⟩s,θ =|⟨1|ψ(s,θ)⟩|2, and discard all other basis states, as illustrated in figure 1(c). In this case, the probability would need to be further normalized: π(a|s,θ) = ⟨Pa⟩s,θ Pa′∈A⟨Pa′⟩s,θ .(8) For |A|=2nit makes sense to assign each eigenstate to an action. In such case, the measurement would be n-local. Table 1summarizes the locality of the measurement for the different partitions considered in this work. The locality is expressed as a function of |A|. 2.2. Softmax policy Definition 2.2. Let s∈ S be a state embedded in an n-qubit parameterized quantum state, |ψ(s,θ)⟩, where θ∈Rk. Let Oabe an arbitrary observable composed by the sum of mlocal/global terms Oa=Pm−1 i=0⟨Oi⟩ representing the numerical preference of action a∈ A and βan hyperparameter. The probability associated to a given action afor a softmax policy is given by: π(a|s,θ) = eβ⟨Oa⟩s,θ Pa′eβ⟨Oa′⟩s,θ (9) where βis often referred as the inverse temperature hyperparameter that is responsible for the control of the policies greediness. That is, the softmax policy allows for greater control compared to the Born policy , since βcan control the degree in which we select what we think to be the best action or explore other actions. The higher the βthe more greedy the policy is [10]. 2.3. Gradient estimation The policy gradient (equation (2)) is in its essence classical with the exception of the log policy gradient in which the gradient w.r.t the PQC must be computed. In that regard, the log policy gradient must be expressed as the gradient of the expectation value of an observable and the parameter-shift rule [17] can be applied to compute the gradient using quantum hardware. Let ⟨O⟩θbe the parameterized expectation value of the observable O. The parameter-shift rule is a hardware-friendly technique to compute the partial derivative of ⟨O⟩θw.r.t θ. Explicitly, it states the equality ∂⟨O⟩θ ∂θl =1 2sinα[⟨O⟩θ+αel− ⟨O⟩θ−αel](10) where elindicates that the parameter θlis being shifted by α. The partial derivative can be obtained using two expectation value estimates, each requiring a number of quantum circuit evaluations. Thus, for θ∈Rk, the gradient can be estimated using 2ktotal quantum circuit evaluations. The gradient accuracy is maximized at α=π 4, since 1 sinαis minimized at this point. For arbitrary functions of expectation values like the log policy gradient, the gradient can be obtained via the standard chain rule. For the Born policy the chain rule gives the following expression for the log policy gradient partial derivatives ∂θllogπ(a|s,θ) = ∂θllog⟨Pa⟩s,θ =∂θl⟨Pa⟩s,θ ⟨Pa⟩s,θ (11) which results clearly in a unbounded gradient expression. The full REINFORCE algorithm with PQC-based policies explored in this work is outlined in algorithm 1. 5 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al Algorithm 1: PQC-based REINFORCE with Baseline. Input: PQC-based policy πθwith θ∈Rk. Learning rate ηand horizon T Output: Updated parameters θ∗ /∗Loop until the stopping condition is met ∗/ 1 while True do /∗Generate trajectories following the policy πθ ∗/ 2for i=0...N−1do 3 Generate τi={(s0,a0,r0),...,(sT−1,aT−1,rT−1)}under PQC-based policy 4 Compute gradient with baseline, ∇θJ(θ)as in equation (2) using the parameter-shift rule (equation (10)) /∗Update parameters via gradient ascent ∗/ 5θ=θ+η∇θJ(θ) 3. Trainability issues in Born policies This section presents new findings that form the cornerstone of this study, addressing the trainability of the quantum policy gradient algorithm as outlined in algorithm 1. We focus on Contiguous and Parity-like PQC-based Born policies defined in definition 2.1. A key aspect of this investigation is the analysis of the variance of the log policy gradient for these policies, considering the impact of the number of qubits and actions, which subsequently influences the globality of associated observables, as detailed in table 1. The analysis proceeds as follows: 1. Analysis of Product States (section 3.1): We begin with an examination of product states as an instructive case, discussing the behavior and characteristics of the log policy gradient variance in this simplified scenario. 2. Consideration of Entangled States (section 3.2): We extend the analysis to include entangled states, comparing and contrasting the findings with those from the product states to highlight the effects of entanglement on trainability. 3. Unified Variance Analysis (section 3.3): We conduct a unified analysis of variance as a function of the number of actions, providing a comprehensive overview of how the variance scales with an increasing number of actions and its implications for the trainability of PQC-based policies. By systematically analyzing these cases, we aim to provide a thorough understanding of the factors influencing the trainability of quantum policy gradient algorithms and offer insights into optimizing PQC-based policies for practical applications. Since the variance of the log policy partial derivative is desired, we start with a simplification of the REINFORCE policy gradient objective, expressed in equation (2), to an expression that depends only on the variance of the policy. This approach allows for an accurate study of trainability as a function of different PQC-based policies. In the following, we consider the trivial upper bound in terms of relevant quantities in RL to rephrase the variance expression as a function of the policy. Lemma 3.1. Let π(a|s,θ)be a n-qubit PQC-based policy with θ∈Rk. Let T be the trajectories horizon, Rmax be the maximum reward and γthe trajectories discount factor. Then, the policy gradient variance w.r.t variational parameters θis upper bounded by Vθ[∂θvπ(s)] ⩽R2 maxT4 (1−γ)4Vθ[∂θlogπ(a|s,θ)] (12) Proof. Vθ[∂θvπ(s)] = Vθ"1 N N−1 X i=0 T−1 X t=0 Gt(τi)∂θlogπai t|si t,θ# =1 N2Vθ"N−1 X i=0 T−1 X t=0 Gt(τi)∂θlogπai t|si t,θ# ⩽1 N2 N−1 X i=0 T−1 X t=0qG2 tVθ∂θlogπai t|si t,θ!2 (A) =G2 t N2 N−1 X i=0 T−1 X t=0qVθ∂θlogπai t|si t,θ!2 (B) 6 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al ⩽G2 tT2Vθ[∂θlogπ(a|s,θ)] (C) =R2 maxT4 (1−γ)4Vθ[∂θlogπ(a|s,θ)] (D) where: (A) Follows from the variance of the sum of random variables VPiXi⩽PipV[Xi]2. (B) Follows from variance of a constant atimes a random variable X(V[aX] = a2V[X]). (C) Considers the upper bound on Nand T. (D) Considers the trivial upper bound on the return (see appendix A), following the independence of θ. Lemma 3.1 indicates that the variance of the log policy objective function increases with relevant quantities in RL. Specifically, the variance increases with the reachable maximum reward, the horizon and the discount factor. At this stage trainability of PQC-based agents can be evaluated through the scaling of the variance of the log policy gradient Vθ[∂θlogπ(a|s,θ)] as a function on the number of qubits. To that end, let us start by analyzing the behavior of the gradients in the context of product states and build from there towards general entangled quantum states. 3.1. The instructive case of product states We begin by examining the straightforward scenario of a product state. In [6], the authors explored a simple n-qubit parameterized model described by the unitary V(θ) = Nn−1 i=0e−iθiσx. They focused on the global observable OG=1− |0⟩⟨0|to prepare the all-zero state. Although this PQC corresponds to a single layer of parameterized Pauli rotations forming a separable state, it was shown to suffer from BPs. The global observable results in a cost function CG(θ) = 1−Qn−1 i=0cos2(θi), whose variance decays exponentially with the number of qubits due to its global nature. The authors then suggested the local observable composed by individual qubit contributions OL=1−Pn−1 j=0|0⟩⟨0|j⊗I ¯ jwith cost function CL(θ) = 1−1 nPn−1 i=0cos(θ)2. This modification ensures that the variance of the cost function decays polynomially with the number of qubits, thus avoiding BPs. Such finding emphasizes the critical role of a well-crafted cost function. In the broader context of machine learning, and policy gradients specifically, the log-likelihood is often preferred over direct probability as considered before. Such cost-function leads to different behavior. For an arbitrary product state |ψ⟩, the probability of the all-zero state is given by: |⟨0⟩ψ|2= n−1 Y i=0 |⟨0i⟩ψ|2.(13) The decomposition into individual qubit contributions enables a product state to avoid BPs since the log likelihood cost-function separates the product into a sum of individual qubit contributions. To apply this reasoning to the REINFORCE cost function in RL, where the focus is on the log policy gradient, consider a Born policy with |A|=2nand a global projector |a⟩⟨a|for action a. The policy is expressed as π(a|s,θ) = |⟨a⟩ψ(s,θ)|2. If the parameterized state is a product state, the probability can be decomposed into individual qubit contributions as follows: π(a|s,θ) = |⟨a⟩ψ(s,θ)|2= n−1 Y i=0 |⟨ai⟩ψ(s,θ)|2(14) where airepresents the individual qubit projector |ai⟩⟨ai| ⊗ Iˆ ion the ith qubit, applying the identity operation to the other qubits. Considering the variance of the log policy gradient: Vθ[∂θlogπ(a|s,θ)] = Vθ"∂θlog n−1 Y i=0 |⟨ai⟩ψ(s,θ)|2# =Vθ"n−1 X i=0 ∂θlog|⟨ai⟩ψ(s,θ)|2# = n−1 X i=0 Vθ∂θlog|⟨ai⟩ψ(s,θ)|2(A) where (A) follows from the linearity and independence of the observables [22]. The variance of the log policy gradient becomes the sum of the variances of the log probabilities of each individual qubit. Notice that since we have a product state, the partial derivative would in fact not depend on the number of qubits, provided that different parameters are part of the circuit. Only in the scenarion where the parameters are shared across 7 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al Figure 2. Variance and expectation value of the gradient of log-probability cost-function. (a) Variance for the all-zero state with parameterized state of individual qubit y-rotations. (b) Random product state composed of Pauli rotations sampled uniformly at random. (c) Expectation value for randomly sampled projectors in the random product state in (b). Figure 3. 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 the circuits (a)–(c). qubits the partial derivative will sum those terms and increase with the number of qubits, as illustrated in figure 2(a). Such behavior is propelled by the nature of a product state, where the probability of each individual qubit is independent of the other qubits. In figure 2(c) the expectation value of the partial derivative of log probability of the all-zero state is illustrated for the random product state illustrated in figure 2(b) where the parameters are shared per layer. That is θi,l=θlfor all number of layers l. Indeed, the variance increases with both the number of qubits and layers, as expected. 3.2. Generalized behavior for entangled states In this subsection, we analyze the variance of the log-probability for entangled states. In particular, we focus on the extreme case where |A|=2n, involving global projectors similar to the product states discussed in section 3.1. It is known that such measurements are susceptible to BPs [6] since the probability of each basis state in this scenario depends on a subset of qubits characterized by the entangled state, derived from an n-qubit global projector, assuming a PQC constituted by local two-design parameterized blocks. In figure 3(d) the variance of the log probability is illustrated as a function of the number of qubits for three distinct entangled quantum states: (1) Simplified 2-design ansatz illustrated in figure 3(a). (2) Strongly entangling layers, depicted in figure 3(b). (3) State generated from Pauli rotations sampled uniformly at random followed by randomly selected CZ gates, as illustrated in figure 3(c). nlayers of the blocks shown in their respective figures are employed. Moreover, projectors were sampled uniformly at random from the set of 2navailable ones and the variance illustrated for an average of a thousand experiments. From figure 3(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 that observed in product states. However, the variance reaches extremely high levels as a function of n, indicating that although these circuits avoid BP, they are prone to exploding gradients. This phenomenon arises because the probabilities diminish exponentially with an increase in the number of qubits, leading to two major issues: (1) The log-probability gradient becomes exponentially large due to the vanishing probabilities. (2) An exponentially large number of quantum circuit executions is required to accurately estimate both the probability and its gradient. As the number of qubits grows, measuring the eigenstate of interest becomes increasingly challenging due to the exponentially concentrated probabilities [16]. However, recall that in the context of RL, we will need to do a partitioning of possibly all 2nbasis states into the set of available actions 8 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al Figure 9. Eigenvalue distribution for the FIM as a function of the number of qubits for the parity-like Born policy in the extreme cases of |A|=2 and |A|=2n. Figure 10. Eigenvalue distribution for the FIM as a function of the number of qubits for the contiguous-like Born policy in the extreme cases of |A|=2 and |A|=2n. for increasing qubits, but with a noticeably lower density compared to the parity-like case shown in figure 9(a). 4.2. Multi armed bandits This section discusses trainability in the context of PQC-based policies, particularly what quantum systems with a substantial number of qubits, and evaluates their effectiveness in learning optimal actions in a reward-based context akin to RL. We consider a multi-armed bandit environment featuring a simple linear reward function: for each arm a, the deterministic reward R(a) is given by R(a) = 2a. This setup allows us to scrutinize the learning capabilities of PQC-based policies with respect to the number of available actions. The PQC-based policy architecture we examine comprises a single layer of σzand σysingle-qubit rotations, followed by an all-to-all CZ entanglement pattern. For these experiments, we use 16 qubits (n=16) to gauge the impact of PQC depth on trainability in the scenario we have a contiguous or a parity-like policy. We analyze two scenarios: (1) a bandit environment with |A|=narms, which results in a contiguous-like policy that is log(n)-local, and (2) a bandit environment with |A|=2n−4arms, leading to a contiguous-like policy involving measurements over a polynomial number of qubits. The performance of contiguous-like policies considered in those scenarios is compared with the global parity-like policy with the same number of qubits. Each scenario incorporates a polynomial number of measurements. Gradient estimation is conducted using parameter-shift rules. We assess the performance of the PQC-based agent by tracking the probability of choosing the best arm over a fixed number of episodes. An episode in this bandit environment involves performing a single action, collecting the associated reward, and using this information to update the PQC-based policy parameters via gradient-based methods. We conduct 100 episodes, comprising 100 action-steps, and average the probability of selecting the best arm over 50 different trials with randomly selected parameters. Figure 11 presents the outcomes when |A|=narms. In subfigures 11(a) and (b), the probability of choosing the best arm is depicted for contiguous-like and parity-like policies, respectively. The contiguous-like policy generally 15 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al Figure 11. Experimental results for the Multi armed bandit environment with |A|=nactions. In (a) and (b) the probability of selecting the best arm is illustrated for the contiguous-like and parity-like policies, respectively. (c) Illustrates the variance of the log policy gradient for both policies. Figure 12. Experimental results for the Multi armed bandit environment with |A|=2n−4actions. In (a) and (b) the probability of selecting the best arm is illustrated for the contiguous-like and parity-like policies, respectively. (c) illustrates the variance of the log policy gradient for both policies. achieves a selection probability above 0.8 for the best arm, with some instances reaching a deterministic policy (probability of 1). The parity-like policy, however, struggles to exceed a 0.5 selection probability throughout training. This disparity can be attributed to the differing localities of each policy. Since |A|=n, the contiguous-like policy involves log(n)-local measurements, contrasting with the parity-like policy’s n-local approach. The effect of these differing observables on trainability is further illuminated by examining the variance of the log policy gradient, as shown in figure 11(c). While the variance remains relatively low for both policies, it is notably smaller and close to zero for the parity-like policy. Figure 12 depicts results for the bandit environment with |A|=2n−4arms. Subfigures 12(a) and (b) depict the probability of selecting the best arm over a series of episodes for both contiguous-like and parity-like policies. In this scenario, neither policy demonstrates the ability to learn the optimal arm effectively, with probabilities of selecting the best arm consistently below one percent. This outcome is explained by examining the employed observables. The parity-like policy is always globally measured, but now, with more arms, the probabilities associated with each arm are significantly reduced. Furthermore, the contiguous-like policy, which previously measured log(n)qubits, engages in a measurement over a polylog number of qubits. Despite not experiencing exponential decay in variance, the large number of qubits and actions places the contiguous-like policy in a BP, akin to the parity-like policy. This is further evidenced by the variance of the gradient, as shown in figure 12(c). The variance for both policies is minimal, indicating an inability to learn the optimal policy. Thus, a polynomial number of measurements, as utilized in these experiments, proves insufficient for learning the optimal policy in such complex settings. 5. Conclusion In conclusion, our research provides pivotal insights into the trainability of PQC-based policies in the realm of policy-based RL. A significant aspect of our findings concerns the trainability challenges faced by two specific types of policies: the Contiguous-like and Parity-like Born policies. These challenges manifest in two 16 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al distinct forms: the occurrence of standard BPs characterized by exponentially diminishing gradients, and the potential for gradient explosion. The nature and extent of these challenges are influenced by two key factors: the specific type of Born policy used, and the interplay between the number of qubits and the action-space size. Notably, our study reveals that with nqubits, when a polynomial number of measurements (O(poly(n))) is considered, the Contiguous-like Born policy demonstrates trainable regions at a logarithmic depth (O(log(n))), provided that the action-space remains within polynomial bounds (O(poly(n))). This observation is crucial as it delineates a specific scenario where this policy remains effective and trainable. In contrast, under similar conditions, the Parity-like Born policy consistently exhibits a BP, indicating its inherent limitations in certain settings. Furthermore, we noticed a striking shift in gradient behavior for actions beyond polynomial size. In these instances, the gradients transition from diminishing to exploding, attributed to exceedingly low probabilities. This shift renders the polynomial number of measurements inadequate for differentiating actions, thus presenting a significant challenge to the practical application of these policies. We would like to emphasize that part of the gradient behavior observed throughout this work is due to classical post-processing. Recall that in section 3.1 we analyzed the variance for the trivial scenario of product states. We concluded that product states would not lead to trainability issues in policy gradient optimization. This is given by the logarithm post-processing of the probability of basis states, which separates the product of individual qubit contributions into a sum. However, for entangled states, the product factorization is no longer true, and indeed, as the number of qubits increases, the probabilities potentially become exponentially small. The logarithm post-processing, in turn, makes the gradient explode. Thus, the classical-post processing indeed impacts what we observe. We highlight that such behavior is also expected to manifest in the classical policy gradient algorithm. Indeed, for very small probabilities, the gradient would also explode. This is one reason advanced policy gradient algorithms such as PPO [18] are much more stable to train. The crucial difference compared with PQC-based policies stems from the fact that the probabilities derived from quantum systems will eventually concentrate given more expressivity and depth of the circuit [16], leading to other sorts of optimization problems that we do not know to be as severe in the classical setting. In addition, we would also like to stress that the trainability analysis presented in this work neglected the effect of the reward. Indeed, it was assumed the presence of a maximum reward to simplify the policy gradient REINFORCE objective expressed in equation (2) to an expression dependent only on the policy. Nevertheless, in practice, there are problems such as the sparsity of the reward. For instance, environments where the reward is assigned only at a goal state and no reward in the middle. In such scenarios, small or even null rewards would lead to vanishing gradients and, indeed, hide the behavior of the quantum system. For that matter, we did not consider these cases. In [7], the authors showed that the BP phenomenon results from a curse of dimensionality and that the cases where one can impose trainability guarantees also lead to classically simulable models. We suspect that this is most likely the case for PQC-based policies since we are still considering hardware-efficient ansatze, and under the measurement conditions outlined through this work, it would fall under the same category explored in [7]. However, it raises the question of whether there are other types of ansatze that strike a perfect balance between trainability and non-efficient classical simulation, combined with specific PQC-based optimization that could be used to circumvent this issue. There are several other promising directions for future work. For instance, one should address the trainability issues associated with softmax policies [10,19], where the freedom to measure the expectation values of |A|different observables presents an intriguing avenue for exploration since more sophisticated results in the trainability of PQCs [15] can be considered. Data availability statement The data that support the findings of this study are openly available at the following URL/DOI: https://github.com/andre-sequeira10/Trainability-issues-in-QPGs. Acknowledgments This work is financed by National Funds through the Portuguese funding agency, FCT - Fundaç˜ ao para a Ciˆ encia e a Tecnologia, within project UIDB/50014/2020 (DOI 10.54499/UIDB/50014/2020). This work is financed by National Funds through FCT - Fundaç˜ ao para a Ciˆ encia 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). 17 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al Appendix A. Upper bound on the return Let Rmax be the maximum possible reward at any time step. Thus, the return is upper bounded by: G(τ) = T−1 X t=0 γtrt+1⩽Rmax T−1 X t=0 γt=Rmax γT−1 γ−1.(20) This enables the following upper bound on the return per time step T−1 X t=0 Gt(τ)⩽Rmax T−1 X t=0 γT−t−1 (γ−1)⩽Rmax T (γ−1)2.(21) Appendix B. Proof of lemma 3.3 Lemma 3.3. Consider a n-qubit contiguous-like Born policy π(a|s,θ)with |A|actions as in definition 2.1. Then, if each block in the parameterized quantum circuit forms a local 2-design, the policy gradient variance is given by Vθ[∂θlogπ(a|s,θ)] ∈Ω1 poly(n)(16) for |A|∈O(n)and depth O(log(n)). On the other hand, the policy gradient variance scales as Vθ[∂θlogπ(a|s,θ)] ∈Ω2−poly(log(n))(17) for |A|∈O(n)and depth O(polylog(n)). Proof. Let us start with the expansion of the standard expression of the variance. For the sake of simplicity let πθ=π(a|s,θ)and the partial derivative ∂θlogπθ=∂θπθ πθ Vθ[∂θlogπθ] = Eθ"∂θπθ πθ2#−Eθ∂θπθ πθ2 ⩾Eθh(∂θπθ)2iEθ1 π2 θ−Vθh(∂θπθ)2iVθ1 π2 θ−Eθ∂θπθ πθ2 (A) ⩾Eθh(∂θπθ)2iEθ1 π2 θ−Vθh(∂θπθ)2iVθ1 π2 θ−Vθ[∂θπθ]Vθ1 πθ(B) =Eθh(∂θπθ)2iEθ1 π2 θ−Vθh(∂θπθ)2iVθ1 π2 θ+Vθ[∂θπθ]Vθ1 πθ | {z } (a) where (A) is obtained from the lower bound of the expectation value of the product of two non-negative random variables Eθ[XY]⩾Eθ[X]Eθ[Y]−Vθ[X]Vθ[Y]and (B) from the upper bound of the variance of the product of two random variables via Cauchy-Schwarz Vθ[XY]⩽pVθ[X]Vθ[Y][21]. The variance is lower bounded taking the upper bound of (a) that can be simplified to: (a)⩽ 2Vθ[∂θπθ]∂θπθ 2 max +2Eθ[∂θπθ]Vθ[∂θπθ]! 1 π2 θmax +Vθ[∂θπθ]Vθ1 πθ(A) ⩽1 2Vθ[∂θπθ] 1 π2 θmax +Vθ[∂θπθ]Vθ1 πθ(B) ⩽3 2Vθ[∂θπθ] 1 π2 θmax (C) where (A) is obtained from the upper bound of the variance pf the product of two random variables, (B) from the assumption that either parameterized block before/after θforms a 1-design and thus Eθ[∂θπθ] = 0 and (C) from the upper bound on the variance Vθ[1 πθ]⩽|1 π2 θ |max. 18 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al The lower bound on the variance of the policy gradient can thus be further simplified to: Vθ[∂θlogπθ]⩾Eθh(∂θπθ)2iEθ1 π2 θ−3 2Vθ[∂θπθ] 1 π2 θmax ⩾Eθ[∂θπθ]2−Vθ[∂θπθ]2 Eθ1 πθ2 −Vθ1 πθ2!−3 2Vθ[∂θπθ] 1 πθ 2 max (A) =Vθ[∂θπθ]2Vθ1 πθ2 − Vθ[∂θπθ]2Eθ1 πθ2 +3 2Vθ[∂θπθ] 1 πθ 2 max!(B) ⩾Vθ[∂θπθ]2Vθ1 πθ2 −3Vθ[∂θπθ]2Eθ1 πθ2 (C) =Vθ[∂θπθ]2 Vθ1 πθ2 −3Eθ1 πθ2! | {z } (a) (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 1-design and thus Eθ[∂θπθ] = 0 and reorganizing terms and (C) from the upper bound on the expectation value and joining terms. Since the variance is non-negative it implies that (a)⩾0. Therefore the variance will be lower bounded depending on the number of actions and corresponding globality of the observable. For |A|∈O(n), Vθ[∂θπθ]2∈Ω( 1 poly(n) 2)for O(log(n)) depth. It decays polynomially with the number of qubits since we are measuring log(n)(adjacent) qubits [6]. Moreover, (a)⩽poly(n)2. Thus, the overall variance deacay at most polynomially with the number of qubits. When the number of actions |A|∈O(poly(n)),Vθ[∂θπθ]2∈ Ω(2−poly(log(n))2). It decays faster than polynomially but slower than exponentially since we are measuring log(poly(n)) qubits [6]. In this case (a)⩽2poly(log(n))2since we have |A| ∈ poly(n). Therefore the overall variance decay at most polylogarithmically with the number of qubits. Thus, completing the proof. ORCID iD André Sequeira https://orcid.org/0000-0002-6659-9277 References [1] Abbas A, Sutter D, Zoufal C, Lucchi A, Figalli A and Woerner S 2021 The power of quantum neural networks Nat. Comput. Sci. 1403–9 [2] Arrasmith A, Cerezo M, Czarnik P, Cincio L and Coles P J 2021 Effect of barren plateaus on gradient-free optimization Quantum 5558 [3] Bergholm V et al 2022 PennyLane: automatic differentiation of hybrid quantum-classical computations (arXiv:1811.04968v4 [quant-ph]) [4] Biamonte J 2021 Universal variational quantum computation Phys. Rev. A103 L030401 [5] Cerezo M et al 2021 Variational quantum algorithms Nat. Rev. Phys. 3625–44 [6] Cerezo M, Sone A, Volkoff T, Cincio L and Coles P J 2021 Cost function dependent barren plateaus in shallow parametrized quantum circuits Nat. Commun. 12 1791 [7] Cerezo M et al 2024 Does provable absence of barren plateaus imply classical simulability? or, why we need to rethink variational quantum computing (arXiv:2312.09121 [quant-ph]) [8] Chen S Y C, Huck Yang C-H, Qi J, Chen P-Y, Ma X and Goan H-S 2020 Variational quantum circuits for deep reinforcement learning IEEE Access 8141007–24 [9] Cherrat E A et al 2023 Quantum deep hedging (arXiv:2303.16585 [quant-ph]) [10] Jerbi S, Gyurik C, Marshall S, Briegel H J and Dunjko V 2021 Variational quantum policies for reinforcement learning (arXiv:2103.05577) [11] Jerbi S, Cornelissen A, Ozols M¯ aris and Dunjko V 2022 Quantum policy gradient algorithms (arXiv:2212.09328 [quant-ph]) [12] Leone L, Oliviero S F E, Cincio L and Cerezo M 2022 On the practical usefulness of the hardware efficient ansatz Phys. Rev. Lett. 128 050402 [13] McClean J R, Boixo S, Smelyanskiy V N, Babbush R and Neven H 2018 Barren plateaus in quantum neural network training landscapes Nat. Commun. 94812 [14] Meyer N, Scherer D D, Plinge A, Mutschler C and Hartmann M J 2023 Quantum policy gradient algorithm with optimized action decoding (arXiv:2212.06663 [quant-ph]) [15] Ragone M, Bakalov B N, Sauvage F’eric, Kemper A F, Ortiz Marrero C, Larocca M and Cerezo M 2023 A unified theory of barren plateaus for deep parametrized quantum circuits (arXiv:2309.09342 [quant-ph]) [16] Rudolph M S, Lerch S, Thanasilp S, Kiss O, Vallecorsa S, Grossi M and Holmes Z 2023 Trainability barriers and opportunities in quantum generative modeling [17] Schuld M, Bergholm V, Gogolin C, Izaac J and Killoran N 2019 Evaluating analytic gradients on quantum hardware Phys. Rev. A 99 032331 19 Mach. Learn.: Sci. Technol. 5(2024) 035037 A Sequeira et al [18] Schulman J, Wolski F, Dhariwal P, Radford A and Klimov O 2017 Proximal policy optimization algorithms (arXiv:1707.06347 [cs.LG]) [19] Sequeira A, Paulo Santos L and Soares Barbosa L 2023 Policy gradients using variational quantum circuits Quantum Mach. Intell. 518 [20] Skolik A, Jerbi S and Dunjko V 2022 Quantum agents in the gym: a variational quantum algorithm for deep q-learning Quantum 6720 [21] Thanasilp S, Wang S, Nghiem N A, Coles P J and Cerezo M 2021 Subtleties in the trainability of quantum machine learning models (arXiv:2110.14753 [quant-ph]) [22] Uvarov A V and Biamonte J D 2021 On barren plateaus and cost function locality in variational quantum algorithms J. Phys. A: Math. Theor. 54 245301 [23] Williams R J 1992 Simple statistical gradient-following algorithms for connectionist reinforcement learning Mach. Learn. 8229–56 20