Differentiable Quantum Computing for Large-scale Linear Control

Authors: connor  clayton
jiaqi  leng
gengzhi  yang
yi-ling  qiao
ming c lin
xiaodi  wu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 19:29:42

Abstract: As industrial models and designs grow increasingly complex, the demand for optimal control of large-scale dynamical systems has significantly increased. However, traditional methods for optimal control incur significant overhead as problem dimensions grow. In this paper, we introduce an end-to-end quantum algorithm for linear-quadratic control with provable speedups. Our algorithm, based on a policy gradient method, incorporates a novel quantum subroutine for solving the matrix Lyapunov equation. Specifically, we build a *quantum-assisted differentiable simulator* for efficient gradient estimation that is more accurate and robust than classical methods relying on stochastic approximation. Compared to the classical approaches, our method achieves a *super-quadratic* speedup. To the best of our knowledge, this is the first end-to-end quantum application to linear control problems with provable quantum advantage.

Main paper: 
 introduction: 
 Over the past few decades, the growing complexity of modern engineering designs has made the control of large-scale dynamical systems a crucial task across various application fields, such as power grid management [56] , swarm robotics [16, 18] , sensor networks [21] , and airline scheduling [57] . These challenges often involve high-dimensional solution spaces with tens of thousands of degrees of freedom, presenting a significant obstacle for traditional optimal control methods.The emergence of quantum computing has expanded the potential for designing efficient algorithms in numerical optimization and machine learning [1, 36, 62] . By leveraging the principles of quantum mechanics, such as superposition and entanglement, quantum computers excel at efficient data processing, making them promising for accelerating solutions to large-scale computational challenges [31] .Although there has been some progress in quantum algorithms for some specific optimal control problems arising in quantum sciences [37, 39] , a viable pathway for accelerating general large-scale optimal control problems remains unclear. A conventional approach to optimal control involves solving the Algebraic Riccati Equation (ARE, see Section 1.1 for details), which is a nonlinear matrix equation. This problem has been less explored in the field of quantum computing for two reasons. First, most proposed quantum algorithms for algebraic and differential equations focus on linear and vector-valued problems, and extending them to nonlinear matrix equations is highly challenging. Second, while efficient quantum algorithms exist for certain weakly nonlinear problems [41] , they are not powerful enough to handle the nonlinearity present in the Algebraic Riccati Equation. A breakthrough in this direction calls for novel ideas in algorithm design.Inspired by the recent advances in differentiable physics [37, 46, 53] and reinforcement learning [19, 45] , we develop an end-to-end quantum algorithm that solves a fundamental optimal control problem called the linear-quadratic regulator (LQR). Given its widely applicable mathematical formulation, LQR has been extensively researched and serves as a standard case study for various computing and learning algorithms [25] ; moreover, LQR is of significant practical relevance as many real-world optimal control problems can be formulated to address through linearization techniques. Our quantum algorithm is proven to output an ε-approximate optimal solution in time O nε -1. 5 1 , where n is the dimension of the state vector and ε is an error tolerance parameter. The algorithm involves two major components: a quantum differentiable simulator and a quantum-accessible classical data structure. This hybrid quantum-classical framework enables us to employ a policy gradient method that exhibits a fast convergence rate for the LQR problem. Since almost all known classical methods for the LQR problem heavily rely on subroutines such as matrix factorization and matrix inversion [6, 32, 34, 35] , which require at least O(n 3 ) overhead in the problem dimension n, our new linear-time quantum algorithm, with super-quadratic speedup, offers significant promise for large-scale applications.Notation. We use R and C to denote the set of real and complex numbers, respectively. I denotes an identity operator with an appropriate dimension. For two real vectors u, v ∈ R n , the Euclidean inner product ⟨u, v⟩ = u T v, and the norm of a vector u is ∥u∥ = √ u T u. Given a symmetric/Hermitian matrix M , we denote λ max (M ) (or λ min (M )) as the maximal/minimal eigenvalue of M . The spectral norm of a matrix M ∈ R m×n is denoted by ∥M ∥ = sup ∥v∥=1 ∥M v∥. The Frobenius norm of a matrix M ∈ R m×n is denoted by ∥M ∥ F = i,j |M i,j | 2 = Tr M T M . We say ξ ∼ D if the random variable ξ ∈ R n is distributed according to D.We focus on the infinite-horizon continuous-time linear-quadratic regulator (LQR) problem:EQUATIONsubject to ẋ = Ax + Bu, x(0) ∼ D, (1b) where x(t) : [0, ∞] → R n is the state vector, u(t) : [0, ∞] → R m is the control input. A and B are constant matrices of appropriate dimensions; Q and R are positive definite matrices. Definition 1. For a square matrix M ∈ R n×n , we say M is Hurwitz if every eigenvalue of M has a strictly negative real part. Definition 2. For a controllable pair (A, B), the set of stabilizing feedback gains is given byEQUATION)Given a controllable pair (A, B), the optimal controller u(t) of problem (1) can be expressed as a linear function of the state vector x(t), namely u(t) = -K * x(t), (3) where the matrix K * is the optimal linear feedback gain. An analytical form of the optimal feedback gain is given by K * = R -1 B ⊤ P * , where P * is the unique positive solution to the Algebraic Riccati Equation (ARE),EQUATION)For large-scale control problems where the control input is much smaller than the state vector (i.e., m ≪ n), it is often desired to compute the optimal feedback gain matrix K * without explicitly solving for P * . To this end, we can rewrite the LQR objective function J(x, u) as a function solely depending on K by leveraging the linearity of the optimal controller u(t) = -Kx(t). With standard algebraic manipulation, it turns out thatEQUATIONwhereEQUATIONand Σ 0 := E ξ∼D [ξξ ⊤ ]. Given this reformulation, the search for the optimal feedback gain K * reduces to minimizing the unconstrained objective function f (K).In practice, the matrices A, B, Q, R often possess sparsity structures that can be leveraged by quantum computers. We make the assumptions on the efficient quantum access model.Assumption 1 (Sparse-access matrices). We assume A, B, Q, and R are s-sparse, i.e., there are at most s non-zero entries in each row/column. For M ∈ {A, B, Q, R}, we assume access to an efficient procedure2 that loads the matrix into quantum data:EQUATIONwhere r i,k is the index of the k-th non-zero entry of the i-th row of M , c ℓ,j is the index of the ℓ-th non-zero entry of the j-th column of M , and M ij is a fixed-length binary description of the (i, j)-th entry of M .With quantum access to the problem data, we aim to determine the optimal linear feedback gain K * so that the objective function f (K) is minimized, as summarized in the following problem statement:Problem 1. Assume (A, B) is a controllable pair and Q, R are positive-definite. Given quantum access to A, B, Q, R in the sense of Assumption 1, we want to compute an εapproximate solution K such that ∥K -K * ∥ F ≤ ε, where ε > 0 is prefixed.In this paper, we propose an end-to-end quantum algorithm for solving LQR problems that exhibits the desired quantum advantage in the large-scale setting (i.e., in the parameter regime m ≪ n). A detailed comparison between ours and various other methods is given in Table 1 . Compared with state-of-the-art classical methods, our algorithm achieves a super-quadratic speedup in terms of the state vector dimension n. To the best of our knowledge, this is the first end-to-end quantum application to linear control problems with provable speedup.Time/Gate Complexity Schur method [35, 48] O(n 3 ) Newton-Kleinman method [32, 47] O(n 3 ) (Model-based) policy gradient [45] O(n 3 • poly(ε -1 ))O(nε -1.5 ) (Theorem 7) Table 1 : Asymptotic cost of different methods for LQR.Our algorithm is based on a novel policy gradient strategy to find globally optimal solutions for linear-quadratic control problems. A brief overview of the policy gradient method for LQR is available in Section 3.2. In each iteration cycle, our algorithm executes a fast, quantum-assisted differentiable simulator to obtain robust gradient estimates, as detailed in Theorem 31. The gradient estimates are then utilized by a classical computer to update the control policy K.As illustrated in Figure 1 , with the back-and-forth iterations between the quantum simulator and a classical computer, the control policy K converges to the optimal policy K * at a linear rate, leading to an end-to-end resolution of the LQR problem.Our quantum algorithm design can be regarded as a novel realization of the hybrid quantum-classical computing paradigm, where collaboration between classical and quantum computers significantly reduces the burden on the quantum side. Moreover, we provide explicit constructions of the quantum simulator and analyze the convergence rate of the policy gradient based on our end-to-end model. These desirable attributes make our proposed design more practical and relevant in the early fault-tolerant era [29] . Notably, we propose a new quantum algorithm for solving the Lyapunov equation, a fundamental task in optimal control theory [25] .Based on an integral representation of the solution and a rich toolbox of methods for quantum numerical linear algebra, our algorithm can produce a quantum representation of the solution matrix in a cost that is polylogarithmic in the matrix dimension n (see Theorem 4), leading to an exponential speedup over existing classical methods [51] . Moreover, since the matrix Lyapunov equation is fundamental to many control problems, we foresee that our quantum algorithm may play an important role in finding speedups for other tasks.The fast quantum algorithm for the Lyapunov equation enables us to develop a quantum gradient estimation subroutine in near-optimal cost, as detailed in Theorem 31. Compared with the conventional gradient estimation techniques based on stochastic approximation (e.g., one-and two-point gradient estimators [45] ), our quantum gradient estimation benefits from the explicit exploitation of the analytical form of the gradient. Numerical experiments suggest that our gradient estimation is robust and often leads to faster convergence in practice, as demonstrated in Section 5.3. 
related work: 
 We survey related work on model-based and model-free linear-quadratic control, differentiable physics, and quantum reinforcement learning in this section.Model-based linear-quadratic control. Model-based optimal control [17, 50] refers to the scenario where historical measurement data explicitly gives (or estimates) the problem description. In this case, the optimal linear feedback gain K * can be computed by solving the algebraic Riccati equation (ARE), as detailed in Section 1.1. Commonly used numerical methods for ARE include factorization methods (e.g., Schur method [35, 48] ) and iterative methods (e.g., Newton-Kleinman method [20, 32, 47] ). These methods require computing matrix factorization or matrix inverse, which in general leads to a O(n 3 ) run time (assuming m ≤ n). Some methods for ARE can achieve O(n) runtime under strong assumptions such as the solution P * is of low rank [8] . It is also possible to solve LQR by reformulating it as a semidefinite programming (SDP) problem [14] . We do not dive into the SPD approach as it does not demonstrate superior asymptotic scaling compared to other direct methods.Model-free linear-quadratic control. LQR can be regarded as a continuous-time analog of the discrete Markov Decision Process (MDP) model and many techniques from reinforcement learning (RL) can be introduced to learn the optimal feedback gain (i.e., control policy), such as policy gradient [19, 45] , natural gradient [25] , and policy iteration [10] .These RL-based methods are particularly useful when we have access to the observed costs but the system model can not be directly constructed.Differentiable physics and quantum computing. The differentiable programming paradigm has been applied to many dynamical systems for learning [46] and control [53] .Those gradient-based methods can be used in reinforcement learning [61] , inverse problems [27] , optimization [5] , design [60] , etc. People have developed differentiable pipelines for various dynamics including fluids [59] , rigid body [49] , soft body [26] , and other hybrid systems [52] . Recently, [37] have derived a differentiable analog quantum computing pipeline for quantum optimization and control. In this work, we will focus on using differentiable quantum computing to accelerate a widely studied classical problem -linear control synthesis.Recently, quantum-accelerated reinforcement learning has attracted significant attention as it demonstrates the potential for computational speedup [43] . It has been shown that quantum computers can be used to compute policy gradients given coherent access to a Markov Decision tree model [15, 28] . Some works also discuss the quantum policy iteration method for RL, see [12, 58] . It is worth noting that the existing works are usually based on a strong quantum access model and it remains unclear what the cost of constructing such models is in an end-to-end sense. 
introduction to quantum computing: 
 All quantum states of a quantum system form a Hilbert space, which is isomorphic to C N . We may assume N = 2 n and n is a non-negative integer. An element |ψ⟩ in this Hilbert space is then noted as a N -dimensional quantum state, whereEQUATION)wherev i ∈ C, i ∈ {0, 1, • • • , N -1}. Also, we often use ⟨ψ| to denote the conjugate transpose of |ψ⟩. For any c ̸ = 0, c|ψ⟩ and |ψ⟩ refer to the same state, thus without loss of generality, ∥|ψ⟩∥ = 1 always holds. Specifically, a one qubit system corresponds to the aforementioned Hilbert space with n = 1.EQUATIONis a quantum state in the space that consists m subspaces.The evolution of a quantum state can be described by a unitary operator U , meaningEQUATION)We often note these operations as gates on the quantum circuit. One important type of unitary operators are the Pauli operators, namelyEQUATION)They form a basis of all the linear operators acting on C 2 .For the quantum measurement, given a quantum observable H, we can do the measurement of a quantum state |ψ⟩. Specifically, after the measurement on |ψ⟩, the state collapses to Pm|ψ⟩ √ pm , and we get an outcome λ m with probability p m = ⟨ψ|P m |ψ⟩, whereEQUATION)is the spectral decomposition of H.For all stabilizing feedback gains K ∈ S K , the gradient of the objective function f (K) as defined in (5) has the following closed-form expression [38, 40] :EQUATIONwhere P (K) is given in (6) , and X(K) is determined byEQUATION)The (direct) policy gradient method for LQR minimizes the objective f (K) via the vanilla gradient update rule K ← K -s∇f (K), where s > 0 is a fixed step size. Given sufficiently small s, it has been shown that the policy gradient method converges at a linear rate [45, Theorem 2] . In practice, however, the policy gradient is often estimated through stochastic approximation, such as one-and two-point estimation [45] . While these zeroth-order gradient estimation methods are less demanding in terms of computational cost, they tend to be sensitive to random perturbations and slow to converge.In this paper, we propose a fast quantum algorithm that outputs a robust estimate of the gradient in O(n) time (assuming m ≪ n, see Theorem 31) . Leveraging the quantum gradient estimation subroutine, we recover the linear convergence rate using robust gradient descent, as detailed in Proposition 34.To perform policy gradient in the training process, the linear feedback gain K is stored in a quantum-accessible data structure as proposed in [30] . This data structure allows intermediate updates on K and efficient quantum queries to K as a block-encoded matrix. This data structure is a purely classical representation of K, and quantum access to this data structure (e.g., through qRAM [23] ) is required to build the block-encoding of K. In the literature, this data structure is also known as classical-write, quantum-read qRAM [7, 54] .Definition 3 (Block-encoding). Suppose that M is an p-qubit operator, α, ε ∈ R + and r ∈ N, then we say that the (p + r)-qubit unitary U M is an (α, r, ε)-block-encoding of M , ifEQUATION)In this paper, the growth of ancilla qubits (space complexity) is dominated by the number of elementary gates (gate complexity). Therefore, when referring to a specific block-encoding, we often omit the number of ancilla qubits (i.e., the parameter r) for simplicity.Lemma 1. Let K ∈ R m×n . There exists a data structure to store K with the following properties: (1) the size of the data structure is O mn log 2 (mn) , ( 2) the time to store a new entry (i, j, Ki,j ) is O log 2 (mn) , and (3) for any ε > 0, a quantum algorithm can implement a (∥K∥ F , ⌈log 2 n⌉ + 2, ε)-block-encoding of K in time O (poly log(n, 1/ε)). There also exists an analogous data structure for K⊤ .Proof. We use the data structure as described in [30, Theorem 5.1] . To construct the block-encoding, we utilize [22, Lemma 50] .Quantum computers can simulate certain linear ordinary differential equations (ODEs) exponentially faster than classical computers [3, 4, 9, 22, 33] . In this paper, we present a quantum simulation subroutine based on quantum linear system solvers (QLSS) [9, 33] , as described below. While this approach may not be optimal in terms of state preparation cost compared to quantum singular value transformation [22] or linear combination of Hamiltonian simulation [3, 4] , it allows us to incorporate the Hurwitz stability of the system. More details and the proof of Theorem 2 can be found in Appendix C. Note that the dependence on t in the above result can be further improved using a standard padding technique, but for simplicity, we do not discuss this minor improvement, as it does not affect our main end-to-end result. We also notice a technique called quantum eigenvalue transformation (QEVT), recently proposed by Low and Su [42] . While this method cannot be directly applied to Hurwitz-stable systems, it may be enhanced to provide a simulation algorithm with a similar cost, as discussed in Appendix D.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: The full set of technical assumptions is provided in the introduction section (see "Problem Formulation"). A complete proof of our main theoretical results can be found in the main paper and the appendices. Guidelines: • The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
quantum algorithm for the lyapunov equation: 
 The (continuous-time) Lyapunov equation is a linear matrix equation of the following form,EQUATION)Since this equation is linear in terms of the matrix X, it is possible to derive a vectorization form of ( 16) and solve it using a quantum linear system algorithm [11, 24] . In this paper, we propose a new quantum algorithm for solving the Lyapunov equation based on an integral representation formula. Our algorithm directly prepares a block-encoded solution matrix X * . Compared to the previous approach, our method leads to an exponentially faster quantum objective function evaluation algorithm (see Theorem 5) and a new quantum gradient estimation subroutine (see Theorem 6).Given a positive-definite Q, there exists a unique positive-definite X * satisfying ( 16) if and only if A is Hurwitz. The unique positive solution is given byEQUATION)The integral formula (17) suggests that the solution to the Lyapunov equation can be computed using a numerical integration technique. For a finite τ > 0, we defineEQUATION)For any arbitrary ε > 0, we find that a τ = O(log(1/ε)) is sufficient to ensure an ε-approximate solution. We denote κ := ∥X * ∥/λ min (Ω).Lemma 3 (Numerical integration). For any ε > 0, we haveEQUATION)Proof. Note that ∥X * -X τ ∥ = ∞ τ e At Ωe A ⊤ t dt ≤ ∞ τ ∥Ω∥∥e At ∥∥e A ⊤ t ∥ dt, where ∥e At ∥ (or ∥e A ⊤ t ∥) is upper bounded by ∥X * ∥λmin(X * ) e -t/κ (see [44, Lemma 12] ). It follows that ∥X * -X τ ∥ ≤ ∥Ω∥∥X * ∥κ λmin(X * ) e -τ /κ . Therefore, an integration time as given in (19) guarantees that ∥X * -X τ ∥ ≤ ε.The matrix X τ can be approximated by a trapezoidal rule with (K + 1) quadrature node points, namely,EQUATIONwherew k = (2-1 k=0,K )τ 2K, t k = kτ K , and F (t) := e At Ωe A ⊤ t . The summation in (20) can be computed on a quantum computer by performing linear combinations of block-encoded matrices, which we will explain shortly. Definition 4 (Select oracle). Let A ∈ R n×n be a Hurwitz matrix. Given an integer K > 0 and two positive scalars τ, ε > 0, we define the following unitary (named as the select oracle):EQUATION)where for each k = 0, . . . , K, U k is a (ζt k , ε)-block-encoding of e At k with t k = kτ /K. Here, ζ denotes some parameter that only depends on A.Now, we consider two select oracles:EQUATION)where for each k = 0, . . . , K, U k (or V k ) denotes a block-encoding of e At k (or e A ⊤ t k ) with normalization factor ζt k . Let O Ω be a (η, 0)-block-encoding of Ω, and we find thatEQUATIONwhereW k := U k O Ω V k is a (ηζ 2 t 2 k , 2ζηε)-block-encoding of the matrix F (t k ). Denoting λ k := w k k 2 , then it is clear that K k=0 λ k W k is a block-encoding of X τ .Thus we can implement a block-encoded X τ on a quantum computer using a technique known as linear combination of unitaries (LCU) [22, Lemma 52] . The rigorous complexity of this quantum algorithm is given in the following theorem, for which a complete proof is provided in Appendix E. Theorem 4. Suppose that A ∈ R n×n is Hurwitz and Ω ∈ R n×n is positive-definite. Let O A be an (α, 0)-block-encoding of A and O Ω be an (η, 0)-block-encoding of Ω. Then, we can implement a (γ, ε)-block-encoding of X * , the unique solution to the Lyapunov equation ( 16), using a single query to O Ω , O α 2 η ε queries to controlled O A and its inverse, and O α 2 η ε queries to other additional elementary gates. Here γ = O(α 2 η).As a direct consequence of Theorem 4, we can evaluate the objective function value f (K) for a given K ∈ S K in a cost that is logarithmic in the dimension parameter n. This result demonstrates an exponential quantum advantage for the objective function evaluation task, as any known classical algorithm for this task requires at least matrix multiplication time. Theorem 5. Assume that we have efficient procedures (as described in Assumption 1) to access the problem data A, B, Q, R in O(poly log(n)) time. Let K ∈ S K be a stabilizing policy stored in a quantum-accessible data structure. We can estimate the objective function f (K) up to multiplicative error θ in cost O 1 θ 2 . Proof. Given a K ∈ S K , we can evaluate the objective function f (K) via the formula f (K) = Tr[P (K)Σ 0 ]. Here, without loss of generality, we assume Σ 0 = I. P (K) has a closed-form representation as in (6) , which corresponds to the unique positive solution to the Lyapunov equationEQUATION)We denote A = A -BK, and Ω = Q + K ⊤ RK. By Lemma 11 and Remark 1, we can block-encode A with normalization factor s(∥K∥ F + 1) and Ω with normalization factor s(∥K∥ 2 F +1), both in cost O(poly log(n, s)). Suppose that f (K) = a, it follows from Lemma 8 that ∥K∥ F ≤ O(a). Therefore, by Theorem 4, we can implement a (γ, ε)-block-encoding ofP (K) in cost Õ a 3 ρ κ 5 ε, where γ ≤ O(a 4 ρ 2 κ 3 ). Note that P (K) is a Hermitian matrix, and λ min (P (K)) ≥ λ min (Q), by invoking Theorem 25, we can estimatef (K) = Tr[P (K)] up to a multiplicative error θ in cost O a 3 ρ θ γ 3 κ 5 ε ≤ O a 13 ρ 6 κ 10 θ 2. Here, the error parameter must be chosen so that ε ≤ O(θ 2 /γ 2 ).5 Quantum Policy Gradient for Large-Scale ControlQuestion: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: All information needed to reproduce the main experiment results of the paper is disclosed in the "Numerical Experiments" section. The code for the experiment is attached in the supplementary material. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. Justification: The paper reports error bars to reflect the statistical significance of the experiments, see the "Numerical Experiments" section and Figure 2 .Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
quantum gradient estimation: 
 Definition 5. Given any K ∈ S K , we call G ∈ R m×n a θ-robust estimate of ∇f (K) if it approximates the gradient ∇f (K) up to a multiplicative error θ, i.e.,EQUATION)Here, we utilize the close-form expression of the policy gradient ∇f (K), as shown in (13) , to construct a quantum algorithm for gradient estimation. The complete theorem statement and the proof are in Appendix G.A, B, Q, R in O(poly log(n)) time. Let K ∈ S K be a stabilizing policy stored in a quantum-accessible data structure. Provided that ∥K -K * ∥ > ε and m ≪ n, we can compute a θ-robust estimate of ∇f (K) in cost O n θ 1.5 ε 1.5 .Our main quantum algorithm for LQR is summarized in Algorithm 1.Inputs: A, B, Q, R (problem data), K0 ∈ SK (initial guess), σ > 0 (step size/learning rate), θ (robustness parameter), N (number of iterations) Output: an approximate solution KN for k ∈ {0, 1, . . . , N -1} do Compute a θ-robust estimate of ∇f (K k ), denoted as G k , using Theorem 6.Update the quantum-accessible data structure using the rule:K k+1 = K k -σG k . end forWe can prove that the iterates in Algorithm 1 converges to the optimal control policy K * at a linear rate (Proposition 34). It follows that our algorithm can find an ε-approximate optimal policy with an end-to-end cost O n ε 1.5 . Theorem 7 (Informal version of Theorem 35) . Assume that we have efficient procedures (as described in Assumption 1) to access the problem data A, B, Q, R in O(poly log(n)) time. Let K 0 ∈ S K be a stabilizing policy and assume that m ≪ n. Then, Algorithm 1 outputs an ε-approximate solution to Problem 1 in cost O n ε 1.5 .Correctness. We conduct a numerical experiment to showcase the correctness of our quantum policy gradient algorithm. Following a similar setup as in [45] , a mass-springdamper system with g = 4 masses is used for constructing our LQR problem. The state Following the mass-spring-damper setup in [45] , our policy gradient descent algorithm converges much faster than [45] .(a) J -J * (b) f (K) -f (K * ) (c) runtimex = [p ⊤ , v ⊤ ] ⊤ ∈ R 2g contains positions and velocities, with dynamic and input matrices,EQUATION)where 0, I are g × g zero and identity matrices, e i is the ith unit vector, and matrix T has 2 on the main diagonal and -1 on the first super-and sub-diagonal. In Figure 2 , we run our method against the classical model-free gradient-based method [45] . It shows that our model-based policy gradient converges much faster to the ground truth ARE solution K * . In the benchmark example [45] , ours converges within 750 iterations, while the classical method takes 2 × 10 4 iterations (orders of magnitude longer). In Figure 2 (c), we increase the system size by scaling g from 4 to 64. Both methods run on a classical simulator with Intel i9-10980XE CPU. Our method runs much faster than [45] by nearly 3 orders of magnitude.The code for both methods can be seen at https://github.com/YilingQiao/diff_lqr. Additional numerical results can be found in Appendix I. 
conclusion and future work: 
 In this paper, we propose the first quantum algorithm for solving linear-quadratic control problems that achieves end-to-end quantum speedups. Our quantum algorithm utilizes an exponentially faster quantum linear dynamics simulator combined with a policy gradient method. Compared to classical approaches relying on matrix factorization and iterations, our method achieves super-quadratic speedup in the large-scale regime (i.e., m ≪ n). Moreover, the hybrid quantum-classical algorithm design makes our algorithm a promising candidate for practical quantum advantage in the near horizon. We also provide numerical evidence to demonstrate the robustness and favorable convergence behavior of our method.Limitations and Future Work. Accelerating optimal control and reinforcement learning using quantum computers remains an emerging research topic. Our work has focused on the theoretical aspects of quantum advantage for LQR, a classic optimal control problem of fundamental importance in both theory and practice. However, for special cases [17] ,we have no guarantee that our quantum algorithm still applies, since Lemma 33 may not hold. In the future, we aim to explore both the practical utility of quantum computing for such tasks and its potential for handling more complex optimal control scenarios, such as non-quadratic and nonlinear problems. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The paper provides sufficient descriptive information on the computer resources, see the "Numerical Experiments" section.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A LQR theory Definition 6. Given a positive number a > 0, we define the sublevel set S K (a) := {K ∈ R m×n : f (K) ≤ a}. We have the following useful bound on K. Lemma 8. Over the sublevel set S K (a) of the LQR objective function f (K), we haveEQUATION)EQUATION)where the constantEQUATION)Proof. See [45, Lemma 16] .Lemma 9. For any K ∈ S K (a), we haveEQUATION)where ν is the same as in (28) .Proof. By [45, Lemma 2], we havef (K) -f (K * ) = Tr (K -K * ) ⊤ R(K -K * )X(K) ≥ λ min (R)λ min (X(K))∥K -K * ∥ 2 F .Combining the above result with Lemma 8, we end up with (29) .Lemma 10 (PL condition). Fix a > 0. For any K ∈ S K (a), we haveEQUATION)where µ f > 0 is a constant that only depends on the problem data and a.Proof. See [45, Remark 2] .Lemma 11. Assume that we have efficient procedures (as described in Assumption 1) to access the problem data A, B, Q, R in O(poly log(n)) time. For a fixed a > 0, suppose that K ∈ S K is a stabilizing policy stored in a quantum-accessible data structure. Then, we can implement 1. a (s(∥K∥ F + 1), ε)-block-encoding of A -BK in cost O(poly log(n, s/ε)), 2. a (s(∥K∥ 2 F + 1), ε)-block-encoding of Q + K ⊤ RK in cost O(+ 1), ε)-block-encoding of Q + K ⊤ RK in cost O(poly log(n, s/ε)).Remark 1. We observe that the block-encodings of A -BK and Q + K ⊤ RK can be implemented with high precisions, i.e., in cost O(poly log(1/ε)). To simplify our technical arguments, we assume these block-encodings can be implemented with no error, i.e., we can implement a (s(∥K∥ F +1), 0)-block-encoding of A-BK (or a (s(∥K∥ 2 F +1), 0)-block-encoding of Q + K ⊤ RK in cost O(poly log(n, s)).Lemma 12 (Modified from [42] , Lemma 11) . Let C be a matrix such that C/α C is blockencoded by O C with some normalization factor α C . Then we can implement a (O(α EQUATIONM -1 ), ε 2 + α 2 M -1 α-ε1α M -1 ε 1 )-block-encoding for M -1 using O(κ M log(1/ε 2 )) (33) queries to U M .Proof. From the lemma above we know we can implement a (α M -1 , ε 2 )-block-encoding as ŨM -1 for (M + Λ/α), where αM -1 = O(α M -1 ). To analyze the error,EQUATION)The first quantum algorithm for solving linear differential equations was proposed by [9] . Since this work was done, several refinements have been made. Among these, [33] significantly loosen the requirement of performing the algorithm. We notice that this whole algorithm can be written in the form of block-encoding. Basically, for a linear differential equation du dt = Au, (35) upon appropriate discretization method and the method of line, one may construct a big matrix A s.t.EQUATION)Then it is easy to see that the matrix inverseEQUATIONEQUATION) Suppose A -1 is block-encoded in some U A -1 , we have (⟨k| ⊗ I)((⟨0 a | ⊗ I)U A -1 (|0 a ⟩ ⊗ I))(|0⟩ ⊗ I) = (⟨k0 a | ⊗ I)U A -1 (|0 a+ℓ ⟩ ⊗ I).(39) Here ℓ satisfy 2 ℓ = T /h, where T is the simulation time and h is the step size. Then it is obvious that U A -1 is also a block-encoding of e khA .Lemma 14 (Modified from [33] ). If we have a block-encoding U L that block-encodes L defined asEQUATION)EQUATION)EQUATION)which means that ((X ⊗ I s-1 ⊗ I a ⊗ I)U L -1) is a block-encoding of e T A with its normalization factor as α L -1 and error being at most ε.Proof. The proof of the correctness of L can be found in [33] .Now we turn to construct the block-encoding for L.Lemma 15. Assume we can query the (α A , 0)-block-encoding U A that encodes A and hα A = O(1), then we can construct a (O(k 1.5 ), k 1/2 ϵ)-block-encoding for L defined in (40) using O(k log(1/ϵ)) queries of U A and same queries to additional elementary gates.Proof. First we need to block-encode M 1 . We will use the ADD operator defined asEQUATION)and the controlled-rotation U R asEQUATION)Notice thatEQUATION)Post-select on the second register and the ancilla qubits of U A , we haveEQUATION)If we apply the operator on a state, namely  k-1 j=0 U R |(j + 1) mod k⟩⟨j| ⊗ I ⊗ U A   |t⟩|0⟩|ψ⟩ = 1 α A (t + 1)|(t + 1) mod k⟩|0⟩A|ψ⟩+|⊥⟩.(47) So we can apply one more multi-controlled-X gate to flip the flag register for the control register being |0⟩, then the whole thing becomes a (α A h, 0)-block-encoding for M 1 , using just one query to U A . We can then easily generate the block-encoding of I -M 1 by LCU, with a 1 + α A h normalization factor. By the analysis in [33] , we know ∥I -M 1 ∥∥(I -M 1 ) -1 ∥ ≤ 2k. Using Lemma 12, we can implement a (O(k), ϵ 1 )-block-encoding of (I -M 1 ) -1 using O(k log(1/ε 1 )) queries to the block-encoding of I -M 1 thus the same queries to U A .For the block-encoding of M 2 , since it is sparse, we may directly implement it through the sparse input model. We may just assume the normalization factor to be √ k and there is no error. Then we can implement a (O(k 3/2 ), √ kε 1 )-block-encoding of (I -M 1 ) -1 M 2 using O(k log(1/ε 1 )) queries to U A and other additional gates.For the block-encoding for N , we can see the normalization factor would be the same scaling as M 2 (I -M 1 ) -1 , thus we implemented a (O(k 3/2 ), O( √ kε 1 ))-block-encoding of N . Now if we use QSVT to perform the matrix inverse, just as described in Theorem 13, we can implement an (αL -1 , ε 2 + α 2 L -1 α L -ε1α L -1 √ kε 1 )-block-encoding U L -1 that encodes L -1 in cost O(κ L log(1/ε 2 )) queries to U L , i.e. O(κ L log(1/ε 2 )k log(1/ε 1 )) queries to U A .In order to perform the inverse of L, we need to know the condition number of L.Lemma 16 (Modified from [33] , Theorem 3 & 4) . Suppose E is the solution operator block-encoded by U L -1 that approximates e AT and m is the number of steps. LetEQUATION)whereEQUATION)EQUATION)EQUATION)Proof. The proof can be seen at [ Proof. Firstly notice that m = O(α A T ) and k = O log(T α A ρ/δ) log log(T α A ρ/δ) . For a given accuracy ε, we need δ ≤ ε, which could be given by lettingEQUATION)Choose ε 1 = O(ε/T 2 ) and ε 2 = ε/2, from the discussion above we know we can implement an (α L -1 , ε)-block-encoding of e T A . Since α L -1 = O(mρ(1 + δ)), the queries we need is O(α A ρT • poly log(1/ε)).Remark 2. If we directly use the theorem above to prepare the state |e AT |ψ⟩⟩ for some input state |ψ⟩, the dependence on T would be T 2 , which does not match the optimal scaling. This is actually due to our usage of QSVT to block-encode matrices inverses. If we adopt the common technique of padding in the quantum linear system solver, we can easily improve the current scaling into T 3/2 . However, for simplicity, we do not implement these standard improvements in this work, as they does not affect our end-to-end complexity result.Here we exploit a technique known as quantum eigenvalue transformation (QEVT) by Low and Su [42] to simulate linear dynamics ẋ = Ax. The algorithm (QEVT) requires that the dynamics is stable under A + A ⊤ ≤ 0, which is stronger than A is Hurwitz stable.Notice that A + A ⊤ ≤ 0 is the stability under the common 2-norm, and A satisfying the Lyapunov equation AX + XA ⊤ ≤ 0 (16) indicates the stability under the inner product induced by the matrix X. We hence follow [42] , use a sequence of polynomial functions (known as the Faber polynomials) to approximate the time-evolution operator e At .Lemma 18 (Faber truncation of matrix exponentials, [42, Lemma 27] ). Suppose we have a matrix A where its numerical range W(A) := {⟨ψ|A|ψ⟩ ∥|ψ⟩∥ = 1} is enclosed by a Faber region E with associated conformal maps Φ : E c → D c , Ψ : D c → E c and Faber polynomials F s (z). Given t > 0, let e tz = ∞ j=0 β j F j (z) be the Faber expansion of the complex exponential function e tz . Assume that E is convex and symmetric with respect to the real axis, lying on the left half of the complex plane, then for sufficiently large s, e Ats-1 k=0EQUATION)where c is a constant determined by the conformal maps.By Lemma 18, given any ε > 0, it suffices to choose s ∼ O(t log 1 ε ) such that e Ats-1 k=0EQUATION)Definition 7. For some matrix A of size N × N with its normalization factor α A , denote the identity matrix of size N × N as I N , andEQUATIONas the lower shift matrix of size N × N . We then defineEQUATION)andEQUATION)Note that the conformal map Ψ has its Laurent expansion, and so are Ψ ′ (ω) and ωΨ(ω -1 ). Furthermore, Ψ ′ (ω) and ωΨ(ω -1 ) only contains terms with non-negative exponents. Thus Ψ(L -1 N ) and Ψ ′ (L -1 N ) are well-defined even though L -1 N is not invertible itself.With the matrices PAD(A) and PAD(B), we can compute the matrix PAD(A) -1 PAD(B), sayEQUATION)Note that this matrix has (2s) × (2s) blocks, and each block of size N × N .Definition 8. For a matrix A whose numerical range is enclosed by a Faber region E with associated conformal maps Φ : E c → D c , Ψ : D c → E c and Faber polynomials F s (z), consider some Faber expansion till s-th order, we then defineEQUATION)as an upper bound on the derivative of Faber polynomials.We are able to have a (ξ, ε)-block-encoding to (PAD(A)) -1 using O(ξ log 1 ε ) queries to the block-encoding of A and O(1) additional elementary gates. Here ξ ∼ O(ρs).Proof. Since we know that PAD(A) can be block-encoded with an O(1) normalization factor with arbitrary precision using a single query to the block-encoding of A and a polylogarithmic number of elementary gates, and ∥(PAD(A)) -1 ∥ = O(sρ), the rest of the proof is done by Lemma 12. Proof. First, we observe thatEQUATION)The X is the quantum Pauli-X gate. Here the circuit has 3 registers, the first one only has one qubit, the second has log 2 s qubits, and the third one matches the size of A.By [42, Theorem 9] , we can implement a block-encoding of PAD(A) using a single query to the block-encoded matrix A/α A . Also, given a constantEQUATION)we know that ∥PAD(A) -1 ∥ = O(ρs). By Lemma 19, we can construct a (ξ, ε)-block-encoding of PAD(A) -1 using O(ξ log(1/ϵ)) queries to the block-encoding of A/α A .Also, assume we can implement a block-encoding of PAD(B) with a O(1) normalization factor. Combining these two block-encodings together, we obtain a (ξ ′ , ε)-block-encoding of PAD(A) -1 PAD(B), where ξ ′ ≤ O(ρs). Then, by (62) , the block-encoding we implemented turns out to be a (ξ ′ ∥β∥, ∥β∥ε)-block-encoding of s-1 k=0 β k F k (A/α A ).Lemma 22 (Select oracle). Suppose that A is Hurwitz, and O A is an (α, 0)-block-encoding of A. Let K be a positive integer and τ, ε > 0 are two real-valued scalars. The select oracle as defined in Definition 4 can be implemented usingEQUATION)queries to controlled O A , and O αρτ K log(K) • poly log 1 ε queries to other additional elementary gates.Proof. Firstly, t k here attains t k = kτ K . By Theorem 17, for each k = 0, . . . , K, we can implement a (ζt k , ε)-block-encoding of e At k using O(αρt k • poly log(1/ε)) queries to O A . We denote this block-encoding as U k . Notice that the select oracle select(A, ε) can be represented byEQUATION)where each unitary operator[(I -|k⟩⟨k|) ⊗ I + |k⟩⟨k| ⊗ U k ] in this product is a k-controlled version of U k that can be implemented with O(αρt k log(K) • poly log(1/ε))queries to the controlled O A and other additional gates. Therefore, the overall query complexity isEQUATION)where the last step follows fromK k=0 t k = K k=0 kτ K = (K+1)τ 2 .In the following proof, we will need a state preparation oracleEQUATIONwhereλ k = w k k 2 , ∥λ∥ 1 = K k=0 |λ k | and w k = (2-1 k=0,K )τ 2K. Since λ k can be expressed as a smooth function of k for k ∈ {0, 1, • • • , K}, this state preparation oracle can be implemented in O(poly log(K)) cost. Now, we are ready to prove Theorem 4.Proof. The global error of the trapezoidal rule (see (20) ) is proportional toEQUATION)where|F ′′ (ξ)| = A 2 F (ξ) + 2AF (ξ)A ⊤ + F (ξ)(A ⊤ ) 2 ≤ 4∥A∥ 2 ∥Ω∥.Therefore, to achieve precision ε 1 , the total number of quadrature points isEQUATION)Now, we consider the following two select oracles, as defined in Definition 4:EQUATION)whereEQUATION)whereW k := U k U Ω V k is a (ηζ 2 t 2 k , 2ζt k ηε 2 )-block-encoding of the matrix F (t k ). Let O λ be the state preparation oracle defined in (68). By the LCU technique [22, Lemma 52] , we can implement a (γ,K k=0 2|w k |ηζt k ε 2 )-block-encoding (where γ := K k=0 |w k |ζ 2 t 2 k η) of K k=0w k e At k Ωe A ⊤ t k using a single query to select(A, ε 2 ), select(A ⊤ , ε 2 ), U Ω , O λ and its inverse.EQUATIONEQUATION)Given a positive scalar ε > 0, and set the integration timeEQUATION)Note thatEQUATIONEQUATION)where δ > 0 is a constant positive number. By Lemma 3 and the error analysis above, we implement a (γ, ε)-block-encoding of X * , withEQUATION)It follows that the overall cost of this block-encoding isO α 2 ρκ 5/2 η 1/2 ε 1/2 (79)queries to O A and same queries to other additional elementary gates.Here we show how to estimate the trace of a positive definite block-encoded matrix. The main result is in Theorem 25.Let U H be an (α, m, ε H )-block-encoding of a positive-definite Hermitian matrix H ∈ C n×n and let ε ∈ (0, Proof. Define λ min := λ min /α, such that λ min I ⪯ H/α ⪯ I. We first find a polynomial approximation of f (x) :=x 36 over x ∈ [ λ min , 1] using [22, Corollary 66 ]. To use this corollary, let x 0 := 1, r := 1 -λ min , δ := λ min , and observe that f(x 0 + x) = 1 6 √ 1 + x = 1 6 ∞ ℓ=0 1/2 ℓ x ℓ whenever |x| ≤ r + δ = 1. Also note that 1 6 ∞ ℓ=0 1/2 ℓ ≤ 1 3 =: B.Then there is an efficiently computable polynomialP 0 ∈ C[x] of degree d = O 1 λmin log(1/ε) such that ∥f (x) -P 0 (x)∥ ≤ ε 2 for x ∈ [ λ min , 1] and ∥P 0 (x)∥ ≤ ε 2 + B ≤ 1 2 for x ∈ [-1, 1]. It follows that defining P (x) := Re (P 0 (x)) gives |f (x) -P (x)| [ λmin,1] ≤ ε 2 and |P (x)| [-1,1] ≤ 1 2 .Next, we use [22, Theorem 56] to construct construct a unitary V that is a (1, m + 2, ε/2)encoding of P (H/α) with the desired complexity, using the promise that ε H is sufficientlyEQUATIONwhere λ H ∈ R n is the vector of eigenvalues of H.Lemma 24. Let µ > 0. Let A be an n-by-n Hermitian matrix such that 0 ⪯ A ⪯ I and let V be a (1, m, µ/3)-block-encoding of √ A. Then there exists U A such that(⟨0| ⊗ I) U A |0 . . . 0⟩ 2 -Tr(A)n ≤ µ that uses 1 query to V and O(log n) additional gates.Proof. Our proof is similar to the proof of [55, Lemma 13] . The idea is to first prepare the maximally entangled state n i=1 |i⟩|i⟩/ √ n (which requires O(log n) gates) and then apply the map √ A to the first register. We can assume without loss of generality that µ ≤ 1, otherwise the statement is trivial.By combining (86) and (89) and using the triangle inequality, we get EQUATIONLemma 26. Given K ∈ S K (a) and ∥K -EQUATION)where the constant c = 2µ f νλ min (R)/a.Proof. This lemma follows directly from Lemma 9 and Lemma 10.Lemma 27 (Block-encoded ∇f (K)). Assume that we have efficient procedures (as described in Assumption 1) to access the problem data A, B, Q, R in O(poly log(n)) time. Let K ∈ S K (a) be a stabilizing policy stored in a quantum-accessible data structure. Given anyε b > 0, we can implement a (γ ∇ , ε b )-block-encoding of ∇f (K) in cost O a 6 ρ 3 κ 11 ε b , where γ ∇ ≤ O(a 6 ρ 4 κ 6 ).Proof. We know that for the function f (K) defined in (5) , the gradient has a closed-form expression: ∇f (K) = 2(RK -B ⊤ P (K))X(K). As shown in the proof of Theorem 5, we can implement a (γ P , ε)-block-encoding of P (K) in cost O a 3 ρ κ 5 ε , where γ P ≤ O(a 4 ρ 2 κ 3 ).Similarly, since X(K) is the solution to the Lyapunov equation (assumingEQUATIONwe can implement a (γX , ε)-block-encoding of X(K) in cost O a 2 ρ κ 5 ε, where γ X ≤ O(a 2 ρ 2 κ 3 ). Based on our assumptions on the input procedures and the usage of quantum data structure, we can implement a (s∥K∥ F , 0)-block-encoding of RK and a (sγ P , sε)-block-encoding of B ⊤ P (K). It follows that a (γ ∇ , ε b )-block-encoding of ∇f (K) can be implemented in cost O a 3 ρ κ 5 ε, whereEQUATIONand ε b ≤ O((a + γ P + γ X γ P )ε). To achieve the desired precision, we pass the error parameter ε → ε/(2(a + γ P + γ X γ P )) to the asymptotic cost.Definition 9. For a matrix G of size m × n, we could always write is asEQUATIONwhere G i is a column vector of size m × 1. Define |G vec ⟩ asEQUATION)Lemma 28 (Matrix Vectorization). Let U G be a (γ ∇ , ε)-block-encoding of (∇f (K))⊤ , and we denoteEQUATION)where r is the number of ancilla qubits required. Then, we can prepare a quantum state |G vec ⟩ with Ω(1) success probability usingO γ ∇ √ m ∥G∥ Fqueries to U G and its inverse.Proof. First, from Lemma 27 we know that we have U ⊤ G that encodes ∇f (K) ⊤ . Notice that ∇f (K) is of size m × n, soEQUATIONwhere r 1 , r 2 , r 3 are the indexes for registers, where the r 1 register has log 2 (m) qubits and the r 3 register has log 2 (n) qubits(We can always assume m and n are the power of 2). The state |⊥⟩ contains the state satisfyEQUATION)By leveraging amplitude amplification, we can get the state |G vec ⟩ using O( γ ∇ √ m ∥G∥ F ) queries to the block-encoding U ⊤ G . Lemma 29 (Gradient entry estimation). Denote the state preparation in Lemma 28 for |G vec ⟩ as U Gvec , we are able to get the classical G with ∥G -|G vec ⟩∥ ≤ ε r (100) using O γ ∇ ∥G∥ F m 3/2 n ε r (101) queries to U G and O γ ∇ ∥G∥ F m 3/EQUATION)Lemma 30 (Gradient norm estimation). Suppose we have the block-encoding U G defined in Lemma 27 , whereEQUATION)then we are able to estimate ∥G∥ F up an additive error ε a usingO γ ∇ √ m∥G∥ F ε 2 a + 2∥G∥ F ε a (105)queries to U G and its inverse and alsoO γ ∇ √ m∥G∥ F ε 2 a +2∥G∥ F εa elementary gates.Proof. We still need the computation we did in equation 98, sayEQUATIONAccording to [55, Lemma 9] , we can get the estimation to∥G∥ F γ ∇ √ m 2with multiplicative errorµ using O( γ ∇ √ m µ∥G∥ F ) queries to U ⊤ G .Note our estimator to ∥G∥ F as a est , the goal we want to achieve isEQUATION)Consider our estimation to the amplitude asEQUATION)This in turn gives us the estimation in 107. And this estimation requiresO γ ∇ √ m∥G∥ F ε 2 a + 2∥G∥ F ε a (109)queries to U G and its inverse. The gate complexity also follows from [55, Lemma 9] .Theorem 31 (Quantum gradient estimation). Assume that we have efficient procedures (as described in Assumption 1) to access the problem data A, B, Q, R in O(poly log(n)) time. Let K ∈ S K (a) be a stabilizing policy stored in a quantum-accessible data structure. Provided that ∥K -EQUATION)Proof. We need an estimation to ∇f (K) up to a multiplicative error θ. This requires a few steps as below:Block-Encoding. From Lemma 27, we know we are able to construct a (γ ∇ , ε b )-blockencoding to ∇f (K) usingEQUATIONelementary gates. And we also have the estimation that γ ∇ ≤ O(a 6 ρ 4 κ 6 ).Entry Retrieving. The next step is to retrieve the entries in the estimation to ∇f (K). We firstly use the technique introduced in Lemma 28 to get a state of the estimation to |G vec ⟩, and this step requiresO γ ∇ √ m ∥G∥ F (112)queries. Now we can use Lemma 29 to get the entries in |G vec ⟩ up to an additive error ϵ r , usingO γ ∇ ∥G∥ F m 3/2 n ε r (113)queries to U G .Norm Estimation. The final step is to estimate the norm of G. Lemma 30 tells us that we can achieve an additive error ε a to ∥G∥ F usingO γ ∇ √ m∥G∥ F ε 2 a + 2∥G∥ F ε a (114)queries to U ⊤ G . The rest of the theorem is just to assemble all these steps. Note the requirement isEQUATION)and according to Lemma 26, ∥∇f (K)∥ F ≥ cϵ before convergence.Denote the entries retrieved in the Entry Retrieving step form a matrix G where ∥G∥ F = 1, the norm estimated in the Norm Estimation step as a est , our estimator is then a est G. ChooseEQUATIONwe then know that ∥G -∇f (K)∥ ≤ cθε 3 , ∇f (K) ≥ cε, thenEQUATION)Thus it is clear to seeEQUATION)And the total gate complexity should be O a 12 ρ 7 κ 11.5 m 1.5 n θ 1.5 ε 1.5 .(119)Lemma 32. Given any K ∈ S K , let G be a θ-robust estimate of ∇f (K). Then, we haveEQUATION)Proof. It is straightforward to verify thatEQUATIONEQUATION)Lemma 33 (Descent lemma). Given K ∈ S K (a), and let G be a θ-robust estimate of ∇f (K).Then, there exists a positive σ m such that for all σ ∈ [0, σ m ], we haveEQUATION)where µ, σ m only depends on A, B, R, Q, and a, and µ > σ m .Proof. This lemma is a direct consequence of Lemma 32 (with θ < 1/2) and [45, Proposition 6] .Proposition 34. For any initial stabilizing feedback gain K 0 ∈ S K , we denote a := f (K 0 ). Then, there exists constants µ > σ m > 0, depending only on A, B, Q, R, and a, such that for any fixed σ ∈ [0, σ m ], the iterates of Algorithm 1 satisfyEQUATIONEQUATION)where b is an absolute constant that is independent of k.Proof. The first part (124a) is a direct corollary of Lemma 33. By Lemma 9 and (124a), we haveEQUATIONwhere the last step follows from [45, Lamma 2] and b = λ max (RX(K 0 )).Theorem 35 (Quantum policy gradient for LQR). Assume that we have efficient procedures (as described in Assumption 1) to access the problem data A, B, Q, R in O(poly log(n)) time. Let K 0 ∈ S K be a stabilizing policy. Then, Algorithm 1 outputs an ε-approximate solution to Problem 1 in costEQUATION)Proof. Notice that with lemma 33, we need log 1 ε iterations. By Theorem 31, the quantum gradient estimation subroutine requires O m 1.5 n ε 1.5 elementary gates.We perform another experiment on a practical problem that can be formulated as LQR. Here, we consider the aircraft flight control problem, specifically for pitch angle control. We adopt a linearized model of the aircraft around a steady flight condition. For a small aircraft, the pitch dynamics can be represented by the following state variables: pitch angle θ (rad) and pitch rate q (rad/s). The control input is elevator deflection angle δ (rad). The state-space model can be represented as ẋ = Ax + Bu, where x = [θ, q] ⊤ , u = [δ]. We set A = [[0, 1], [0, -0.5]] ⊤ , B = [0, 1] ⊤ , Q = [[10, 0], [0, 1]] ⊤ ,We conducted further numerical experiments to understand how the optimality scales with problem size in Figure Figure 4 . Here, we scale the number of masses in a spring-mass system from 2 to 4, and the problem dimension scales accordingly from 2 to 8. We measure the optimality by the relative error found in both our method and the classical method. The relative errors are (J -J * )/j * and (f (K) -f (K * ))/f (K * ). As the dimension scales up, the relative errors increase, while our method consistently outperforms the classical optimization method. We scale the size of a mass-spring system and our method consistently gets smaller relative error compared to [45] .NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.The O(•) notation suppresses the condition number dependence and polylogarithmic factors in n and ε.This input model is sometimes referred to as the sparse-input oracle model in the literature. It is a standard assumption in many applications, see[2,13,22] for details. 


Decision: The paper considers the problem of finding an optimal controller for the continuous LQR control problem. They take a gradient descent approach to the problem which is known to have linear convergence from prior work. The main contribution of the paper is to provide a quantum algorithm for the estimation of the gradient which can run in time linear in the matrix dimension (as opposed to a classical algorithm which requires a cube of the dimension). 

Overall the paper provides a first foray of quantum algorithms into the fundamental problem of LQR control showing a quadratic speedup under their assumptions. While I do not have enough expertise to evaluate the quantum assumptions, the reviewers all found the paper to be reasonable. I recommend accept.

Reviews: review: paper_summary: paper_summary: This paper studies the problem of applying quantum computing to linear quadratic regulator (LQR) control. The approach is based on an efficient quantum estimation of the policy gradient. When the dimension n of the state space is large, the proposed approach can achieve orders of magnitude improvement on the time complexity to find the optimal controller compared to existing policy gradient methods.
strength_weakness: strength_weakness: Since this work proposes a model-based approach and assumes access to the exact model, including A, B, Q, and R (Algorithm 1), I wonder why the authors compare with the model-free approach in [44], which does not assume knowledge of the model and uses two-point gradient estimation. I don’t think this is a fair comparison.

Besides, I do not understand why the application of the proposed quantum approach is limited to the classic LQR problem. If the real contribution is the first quantum approach to solve the Lyapunov equation (11) efficiently, I think the proposed method can be applied to other important problems like stability analysis. I hope the authors can clarify the most general statement of the main contribution or what limits the application to LQR.
questions: questions: Besides my comments in the weakness part, I also hope the authors can clarify if the proposed method is robust to estimation errors in A and B if we estimate them from samples (see [Dean, Sarah, et al., 2020]).

[Dean, Sarah, et al., 2020] Dean, Sarah, et al. "On the sample complexity of the linear quadratic regulator." Foundations of Computational Mathematics 20.4 (2020): 633-679.
limitations: limitations: I do not see any potential negative societal impact of this work.
paper_summary: paper_summary: This proposes an end-to-end solution to the quantum-assisted LQR problem. Based on a policy gradient method, the proposed algorithm incorporates a quantum subroutine for solving the matrix Lyapunov equation, achieving a super-quadratic speedup.
strength_weakness: strength_weakness: 1. While the paper highlights the theoretical advantages of the quantum algorithm, implementing these algorithms on current quantum hardware might pose significant challenges. Today's quantum computers suffer from noise and have a limited number of qubits, which could affect the actual performance and reliability of the algorithm.

2. Although the paper claims a super-quadratic speedup, it's important to verify whether this speedup is practically achievable. Especially in large-scale industrial models, the real-world complexity and scalability of the algorithm are critical issues.

3. This paper is not always well written. For example, in Line 520, "The evolution of a quantum state can always described by a unitary operator".
questions: questions: 1. How does the proposed quantum algorithm account for the current limitations of quantum hardware, such as noise and the limited number of qubits? 
2. The paper introduces a novel quantum subroutine for solving the matrix Lyapunov equation. Could you elaborate on the specific technical innovations that this subroutine brings compared to existing quantum algorithms? What are the key theoretical breakthroughs that enable the claimed super-quadratic speedup?
limitations: limitations: The limitations of this work have been adequately discussed.
paper_summary: paper_summary: The paper "Differentiable Quantum Computing for Large-scale Linear Control" introduces a quantum algorithm for linear-quadratic control problems, offering provable speedups. It utilizes a policy gradient method enhanced with a novel quantum subroutine for solving the matrix Lyapunov equation, leading to more accurate and robust gradient estimation than classical methods. The proposed algorithm achieves a super-quadratic speedup, making it the first end-to-end quantum application to linear control problems with demonstrable quantum advantages.
strength_weakness: strength_weakness: The experiments are insufficient. The proposed method has only been applied to simple abstract problems, but it would be beneficial to conduct experiments on practical problems in the form of LQR.
questions: questions: 1. How does the proposed quantum algorithm handle cases where the sparsity assumptions on matrices A,B,Q,R do not hold?

2. Can the authors provide detailed runtime performance comparisons between the proposed quantum algorithm and state-of-the-art classical algorithms?

3. Comparison with Other Methods: How does the proposed method's stability and convergence rate compare with other existing quantum and classical approaches for solving linear-quadratic control problems?
limitations: limitations: The primary limitation of the proposed method is its dependency on the availability of quantum resources and the sparsity assumptions for the matrices involved.
paper_summary: paper_summary: This paper introduces an end-to-end quantum algorithm for linear quadratic control problem. The proposed quantum-assisted differentiable simulator is suitable for large-scale dynamical systems where the dimension of system state is huge. Sample complexity is also provided when apply quantum computation in such problem. Simulated results support its theory.
strength_weakness: strength_weakness: This work only considers linear-quadratic control problem.
questions: questions: What are the optimality plot such as the plots shown in Figure 2(a) and 2(b) for Figure 2(c) when you increase the system dimension?
limitations: limitations: NA

Comments: title: Thanks for your kind response.
Thank you for the responses.
Thanks for your comment!
comment: Thank you for your thoughtful feedback and for taking the time to review our work. We sincrely appreciate your willingness to reconsider the score!
The author's response has somewhat addressed my concerns and questions. I will increase my score accordingly.
Thank you for your thoughtful review and for recognizing the theoretical contributions of our work. We appreciate your insights on the practical realization and scalability of our proposed methods. Your feedback has been important in refining our approach.
Thank you for your detailed rebuttal and for addressing the concerns raised. I appreciate the insights provided, particularly regarding the theoretical contributions and potential robustness of your proposed quantum algorithm.

Your work establishes a good theoretical foundation, and the practical realization and scalability of these methods in real-world scenarios are important aspects to consider moving forward. I will maintain my current assessment of the submission.