Differentiable Quantum Computing for Large-scale Linear Control
Authors: Connor Clayton
Jiaqi Leng
Gengzhi Yang
Yi-Ling Qiao
Ming Lin
Xiaodi Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: quantum computing
quantum algorithms
optimal control
differentiable physics
reinforcement learning
Primary area: learning_theory

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.

Differentiable Quantum Computing for Large-scale Linear Control
Connor Clayton*.4: Jiaqi Leng 1,3,5
Gengzhi Yang*..3
Yi-Ling Qiao Ming Lin2.4 Xiaodi Wul.1.2
Joint Center for Quantum Information and Computer Science, University of Maryland Department of Computer Science, University of Maryland $ DDepartment Mathematics, University of Maryland
'Center for Machine Learning, University of Maryland
Departmentt of Mathematics and Simons Institute for the Theory of Computing, UC Berkeley
Equual Contribution
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 problem dimensions grow. In this paper, we introduce end-to-end quantum algorithm for linear-quadratic control with provable speedups. Our algorithm, based on policy gradient method, incorporates novel quantum subroutine for solving the matrix Lyapunov equation. Specifically, build conntmm-assisted differentiable simalator for efficient gradient estimation that more accurate and robust than classical methods relying stochastic approxination. Compared to the classical approaches, 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.
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 power grid management 58 swarm robotics [6. [8 sensor networks [11] and airline scheduling 57 These challenges often involve high-dimensional solution spaces with tens of thousands of degrees of freedom, presenting significant obstacle for traditional optimal control methods.
The emergence of quantum computing has expanded the potential for designing efficient algorithms numerical optimization and machine learning [ 36 (
By leveraging
the principles of quantum mechanies, such 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 quantum algorithms for some specific optimal control problems arising in quantum sciences 37 3g a viable pathway for accelerating general largo-scale optimal control problems remains unclear. conventional approach to optimal control involves solving the Algebraic Riccati Equation (ARE, see (Sectinn 1.1 for details), which is a nonlinear matrix equation. This problem has been less explored in the
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

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 A11, 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.
and reinforcement 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 rescarched and serves as a standard case study for varions computing and learning algorithrss [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 e-approximate optimal solution in time O (nE-1.5) I where n. is the dimension of the state vector and & an error tolerance parameter. The algorithm involves two major components: quantum differentiable simulator and quantum- quantum-accessible classical data structure. This hybrid quantum- claassical framework enables us to employ a policy gradient method that exhibits 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 M 32 3 35, which require at least ((n²) overhead in the problem dimension n, our new linear-time quantum algorithm, with super-quadrafic speodup, offers significant promise for large-scale applications.
Inspired by the recent advances in differentiable physics 37
46
58
learning 19 55
Notation. We use R and C to denote the of real and complex numbers, respectively, II denotes an identity operator with appropriate dimension. For two real vectors u, E R", the Euclidean inner product vu. = wf v, and the norm of a vector u |||||| = Vu'u. Given a symmetric/ symmetric/Hermmitan Heemmitaa matrix M, we denote Amax(M (or Amin (M)) as the maximal/ maximaal/minmall minimal eigenvalue of M. The spectral norm of matrix M E Ruxn is denoted by || = sup ==1 [|M The Frobenius norm of a matrix M E RRxx is denoted by || Ei, |M,j 2 Mr] We say & DD if the random variable RR" is
distributed according to D.
1.1 Problem Formulation
We focus the infinite- continuous-tin linear-quadratic regulator (LQR) problem:
min J J [T, (1)(()=( + -u += (1)Ru(()) di RTM
(1a)
subject to è = Ax + Bu, x(0)) D,
(1b)
where a(I): [0, xc| + R" is the state vector, u(l): [0, oc] + Rm 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 E IRax,, we say M is Hurwitz if every eigenvalue of M has strictly negative real part.
Definition 2. For a controllable pair (A, the set of stabilizing feedback gains is given by Sx = (K E m= A BK is Hurwitz).
(2)
Given controllable pair (4, B), the optimal controller ult) of problem 1 can be expressed as a linear function of the state vector x(t), namely
u(t) =K'x(t),
where the matrix K is the optimal linear feedback gain. An analytical form of the optimal feedback gain is given by K* = R -B" T Pa; where pa is the unique positive solution to the Algebraic Riccati Equation (ARE),
A + PA+ B
(4)
'The Ö(-) notation suppresses the condition number dependence and polylogarithmic factors in and E.
2

---

For large-scale control problems where the control imput is much smaller than the state vector (i.e., m < n), is often desired to compute the optimal feedback gain matrix K without explicitly solving for P To this end, we can rewrite the LQQ objective function [ar u) as function solely depending on K by leveraging the linearity of the optimal controller u(t) = - Kx(()). With standard algebraic manipulation, it turns out that
(T((P()EE)) K E Sk: 00
u(z, =()))
(5)
otherwise,
where
( P(K) = 1000=[((440 c(A--B)) (Q + KJ RK) c(A-BK)e dt,
(6)
and Eg = == Given this reformulation, the search for the optimal leedback 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 (Sparse-access matrices). We assume A, B, Q, and R are s-sparse, i.e., there are most non-zero entrics in cach row /cooummmn. For M {, Q, R), assume access to an efficient procedurd
P that loads the matrix into quantum data:
i> k)) + rs,k),
(e)b)) (ec)) 10)b))0) + M²)
where rik is the index of the k-th non-zero entry of the i-th row of M. Ctj is the index of the b-th non-zero entry of the j-th column of M, and My 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 that the objective function f(K) is minimized, as summarized in the following problem statement:
Problem Assume (A,B) is a controllable pair and Q, R are positive-defiiit. Given quantum access to A, Q, R in the sense of Assumption 1 we want to compute an
approximate solution K such that |K- K' S E, where ε > 0 is prefixed.
1.2 Main Contributions
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.c., in the parameter regime m < n). A detailed comparison between ours and various other methods is given in Table Compared with stato-of-the-art classical methods, our algorithm achieves super-quadratic speedup in terms 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.
Methods
Time GGate Complexity
Schur method 35
O(n3)
method 32
47
(n²))
(Model-based) policy gradient
45
On poly(e
Ours
Ö 1.5) Theorem 7
Table 1: Asymptotic cost of different methods for LQR.
Our algorithm is based on novel policy gradient strategy to find globally optimal solutions
for -unaar-quadratic control problems. A bricf overview of the policy gradient method for
LQR is available in Section 3.2 In cach iteration cycle, our algorithm executes fast,
"This input model is sometimes referred to as the sparse-input oracle model in the literature. It is standard assumption in many applications, see
| 22 for details.
3

---

mmantum-assisted differentiable simulator to obtain robust gradient estimates, 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 & linear rate, leading 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 quan- tum computers significantly reduces the burden on the quantum side. Morcover, 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 proposed design practical and relevant in the early fault-tolerant era. 20
Notably, propose tum algorithm for solving the Lya- punov equation, 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 quantum representation of the solution matrix in a cost that polylogarithmic in the matrix dimension (see Theorem 4), leading to an eaponential speedup over existing classical methods [5]]. Moreover, since the matrix Lyapunov equation fundamental to many control problems, we foresee that our quantum algorithm may play an important role in finding speedups for other tasks.
quan-
LOR Policy Gradient
Vf(k)
fundamental
Control
Objective Function
brasient-based
Policy
Differentiable Quantum
Optimizer
Computing
K
f(K)
Classical Module
Quantum Module
Figure 1: Differentiable quantum computing for linear control.
The fast quantum algorithm for the Lyapunov equation enables gradient estimation subroutine in near-optimal cost, as detailed in Theorem 31 Compared with the conventional gradient estimation techniques based stochastic approximation (e.g., one- and two-point gradient ostimators 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
develop quantum
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. Tn 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- Kleinmann method |20 32 47 These methods require computing
matrix factorization or matrix inverse, which general leads to O(n²) run time (assuming m < n). Some methods for ARE can achieve O(n) runtime under strong assumptions such as the solution pa is of low rank [8. It is also possible to solve LQR by reformulating it as semidefinite programming (SDP) problem [1]] 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-Lime analog of the discrete Markov Decision Process (MDP) model and many techniques from reinforcement learning (RI.) can be introduced to learn the optimal feedback gain (i.e. control policy), such as policy gradient [g 45 natural gradient 26 and policy iteration [0]

---

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 20 and control b3
Those gradient-based methods can be used in reinforcement learning [61,, inverse prob- lems 27,, optimization [] design 600 etc. People have developed differentiable pipelines for various dynamics including fluids [99, rigid body F., soft body 26,, and other hybrid systems Recently, Br have derived differentiable analog quantum computing pipcline for quantum optimization and control. In this work, we will focus on using differentiable quantum computing accelerate a widely studied classical problem linear control synthesis.
Quantum reinforcement learning. Recently, quantum-acceelrateel reinforcement Iearn- ing has attracted significant attention it demonstrates the potential for computational speodup A3 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 what the cost of constructing such models is in an end-lo-end sense.
strong quantum access model and it remains unclear
Preliminaries
3.1 Introduction to Quantum Computing
All quantum states of a quantum system form a Hilbert space, which is isomorphic to CNV We may assume N = 2" and is non-negative integer. An clement (t) in this Hilbert space is then noted as N-dimensional quantum stale, where
v0
21
(0)
(8)
UN--J
where E C, 1, - Also, often use (vi to denote the conjugale transpose of [bb. For any e + 0, c/v) 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
Given m quantum states (11)), [12)) ... |im) from m quantum systems, then (+) | (1/2) @ ... @ (mm)
(9)
is quantum state in the space that consists m subspaces.
The evolution of quantum state can be described by unitary operator U, meaning
U = U0 =
(10)
We often note these operations as gates on the quantum circuit. One important type of unitary operators are the Pauli operators, namely
1
0 -1
Y
=
(11)
They form a basis of all the linear operators acting on C².
For the quantum measurement, given a quantum observable H, we can do the measurement of a quantum state (r)). Specifically, after the measurement (8²), the state collapses to Pm and we get an outcome Am with probability Pm = (vbl Pm (2), where ypm
H = Σ
Am Pm
(12)
is the spectral decomposition of H.
5

---

3.2 Policy Gradient for LQR
For all stabilizing leedback gains K Sk, the gradient of the objective function ((K) as defined in (5) has the following closed-form expression BS 40
Vf(K) = 2(RK - B ((K))
(13)
where P(K) is given in 6 and ( is determined by
X(K) / oo 11- (A-BK)" dt.
(14)
The (direct) policy gradient method for LQR minimizes the objective f(K) via the vanilla gradient update rule K + K - {V)(K), where s > fixed step size. Given sufficiently small 8, it has been shown that the policy gradient method converges at a linear rate [b Theorem 2]. In practice, however, the policy gradient often estimated through stochastic approximation, such one- and two-point estimation 45 While these zeroth-order gradient estimation methods are less demanding in terms computational cost, they tend to be sensitive to random perturbations and slow to converge.
In this paper, we propose fast quantum algorithm that outputs a robust estimate of the gradient in ((n) time (assuming m < nt see Theorem 31). Leveraging the quantun gradient estimation subroutine, recover the linear convergence rate using robust gradient descent, as detailed in Proposition 34
3.3 Quantum Data Structure
To perform policy gradient in the training process, the linear feedback gain K is stored in puantum-aczessible data structure proposed in [30] This data structure allows intermediate updates on K and efficient quantum queries to K as a elocked 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 build the block-encoding of K. In the literature, this data structure is also known as classical-urite, quantum-read qRAM 7 54
Definition 3 (Block-encoding). Suppose that M is an p-qubit operator, 0,E R and r E N, then we say that the (p + r)-qubit unitary UM is an (a, (,,r,e)-bloon -l-ooooc-nnooiing of M,
|| - ((() & 1) & D)Il S.
(15)
In this paper, the growth of ancilla qubits (space complexity) is dominated by the number of elementary gales (gale 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 Let K E Rmxx, There exisls a data structure to slore K with the following properties: (1) the size of the data structure is O (mnlog) (onllog(m))) (mn)), (2) the time to store new entry (i,j, Rig) is
(men), and (3) for any E > O, a quantum algorithom can implement a ([| [[, [log2 n. + -locedin of K in time O (poly log(n, 1/E)). There also erists an analogous data structure for RT.
Proof. We use the data structure described in 30 Theorem 5.1]. To construct the block-encoding, we utilize 22 Lemma 50).
3.4 Quantum Simulation of Linear Dynamics
Quantum computers can simulate certain lincar ordinary differential equations (ODEs) exponentially faster than classical computers 3
4
9
22, 33 In this paper, we present
quantum simulation subroutine based on quantum linear system solvers (QLSS) g 33 as described below. While this approach may not. be optimal in terms of state preparation ion cost compared to quantum singular value transformation 22 or linear combination of Hamiltonian simulation g 4, it allows to incorporate the Hurwitz stability of the system.

---

Theorem 2 (Informal version of Theorem 17). Suppose that A E R is a Hurwitz matriz, and Oд an (a, O)-block-encoding of A. For an arbitrory > 0, we can implement (çt,E)- block-encoding of edt using O (apt poly log(1/E)) queries to O and O (apt poly log(1/E)) queries to additional gates. Here, the normalization factor Ç = O(ap), and the constant p solely determined by A.
More details and the proof of Theoremm 2 can be found in Appendix C dependence on 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 technique called quantum eigenvalue transformation (QEVT), recently proposed by Low and Su [4]] While this method cannot be directly applied Hurwitz-stable systems, may be enhanced to provide a simulation algorithm with similar cost, as discussed in Appendix D
Note that the
4 Quantum Algorithm for the Lyapunov Equation
The (continuous-time) Lyapunov equation is linear matrix equation of the following form,
4X+XA =
(16)
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 [T 24 In this paper, 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 (sec Thcorem and new quantum gradient estimation subroutine (see Theorem 6)
4.1 Representation
Given a positive-defiite Q, there exists a unique positive-defiitt X satisfying 16 and only if A is Hurwitz. The unique positive solution is given by
X = {o Al A dt.
(17)
The integral formula (17) suggests that the solution to the Lyapunov equation can be computed using numerical integration technique. For finite >> 0, define
X, = L/ A' dt.
(18)
For any arbitrary e > 0, we find that a (log(1//e) is sufficient to ensure an e-approximate
solution. We denote = |X* //mmi//mmn (22).
Lemma (Numerical integration). For any 0, we have ||X -x--xx X+Il |l E, provided that
||||||| x=||||
1og
(19)
E EXmin (X*) )
Proof. Note that ||x X, 1 eALRe dt $ 1 ||] * dt, where ||e
(or TeA""1)) upper bounded by |X" t/18 (see Lemma 12]). follows that XX=]
||X -x, - ||||||**| eT/// Therofore, an intogration time as given (19) guarantees
Ax-n(X-) that ||X" X, E.

---

4.2 Algorithm Complexity Analysis
The matrix X, can be approximated by trapezoidal rule with (K 1) quadrature node points, namely,
X
Σ k=U
wh whe
Σ wk wr (1x),
(20)
where Wi = (2-1R=o.k)r fx = kT and == e The summation in (20) can be 2K
K
computed quantum computer by performing lincar combinations of block-encoded matrices, which we will explain shortly.
Definition 4 (Select oracle). Let A RR=x" be Hurwitz matrix. Given an integer K and two positive scalars T, > O, we define the following unitary (named as the select oracle):
scloct(A, = Σ |&XM| & Uk.
(21)
where for each == 0,...... K, UR is (cl,, e-bllock-encoding of ese with la KT K. Here, [ denotes some parameter that only depends on A.
Now, consider two select oracles:
K Σ k=
select(A,8) =
[xXk| & Uk, select ,6)
Σ k=0
|&Xk| @ Vas
(22)
where for each k= = O,..., ......,, K, Us (or Vi)) denotes a block-encoding of eAti (or e e (x) with normalization factor Çtx. Let On be (n, 0) blobeeck-nnnodingg of 52, and find that
K
(e) @ On)sclect(A (AT ,E)
Σ R=
[k)( & Wt.
(23)
where Wi = V& a (nc block--oocnnn of the matrix I (tx). Denoting A = wgk2, then it is clear that Σ du We is block-encoding of X,. Thus can implement 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 Raxn is Hurwitz and Ω E Rax= is mnsitive-dffinés Let O be an (a, eecooiig of A and On be an (n. 0) booc---nnnnodnn of Ω. Then, we can imple- of X*, the unique solution to the Lyapunou equation (16) using
ment (a.z)))look-encnne a single query On, Ô (?) queries controlled O and its inverse, and (a (a²
queries to other additional elementary gates. Here 7 (()2)).
4.3 Objective Function Evaluation
As direct consequence of Thcorem 4 we evaluate the objective function value f(K) for a given K E SK in a cost that is logarithmic the dimension parameter n. This result demonstrates exponential quantum advantage for the objective function evaluation task, as any known classical algorithm for this lask requires at least. matrix multiplication time.
Theorem 5. Assume that we have efficient procedures (as described in Assumption 1l to access the problem data A, B, Q, R in Oppoly log(n)) time. Let K E SK be stabilizing policy stored in maanuum-accessile dala structure. We can estimate the objective function J(K) up to multiplicativve error in cost Ö (
Proof. Given K E SK, can evaluate the objective function f(K) via the formula.
f(K) = Tr(P(K)Eo]- Here, without loss of generality, we assume Σg T. P(K) has a closed-form representation as in (6) which corresponds the unique positive solution to the Lyapunov equation
(A BK) P+ P(A BK) - (Q K RK) = 0.
(24)
8

---

We denote A = A - BK, and === - Q 1Q+K* K RK. By Lemma 11 and Remark we can block-encode with normalization factor s(I]K]]
and 52 with normalizatinn factor <[]| +1), both in cost Oppoly log(n, Supposee that f(K) = a, it follows from Lemma that | I ((a). Therefore, by Theorem 4 we can implement (y, (y,e)=-book-encodiin of
P(K) in cost Ô aa dV'Vv where Y O(a)p2n)). Note that P(K) Hermitian matrix,
and Amin (P(K)) (min(Q) by invoking Theorem 25
we estimate f(K) Tr Tr[P(K) up d=0p"r='0)
to a multiplicative error f in cost Ö a'p (
S O
"0 Here, the error parameter
must be chosen so that S (0(22/7))
Quantum Policy Gradient for Large-Scale Control
5.1 Quantum Gradient Estimation
Definition 5. Given any K E Sk, we call G E R=x" 0-robust estimate of Vf(K) if it approximates the gradient (K() up a multiplicative error 0, i.e,
||G Vf(K)]lr s (KV]((K)le-
(25)
Here, we utilize the close-form expression of the policy gradient Vf(K), shown in (13) to construct a quantum algorithm for gradient estimation. The complete theorem statement and the proof are in Appendix G.
Theorem (Informal version of Theorem 31p. Assume we have efficient procedures (as described in Assumption 1 to access A, Q, in ((polylo((n) time. Let K E SK be stabilizing policy stored in quontum-accessible data structure. Provided that || K and m < n, can compute O-robust. estimate of (((K) in cost ① (g13515)
5.2 Quantum Policy Gradient
Our main quantum algorithm for LQR is summarized in Algorithm
Algorithm 1 Quantum policy gradient
Inputs: A, B, Q, R (problem data), Ko E SK (initial guess), 0 (step size/learning rate), (robustness parameter), N (uumber of iterations)
Output: an approximate solution KN
for & E (0, 10. 1} do Compute 0-robust estimate of V (KK)), denoted as Gs, using Theorem 6 Update the quantum-acoessibee data structure using the rule: K4+1 = Kt oGr. end for
We prove that the iterates in Algorithm converges to the optimal control policy K at a linear rate (Proposition 34). It tollows that our algorithm can find an e-approximate optimal policy with an end-to-end cost Ö (fTss.
Theorem 7 (Informal version of Thcorem 35). Assume that we have efficient procedures (as described in |Assumption 1) to access the problem data A, B, Q, R in Oppoly log(n)) time. Then, Algorilim ] oulputs an
Let Ko E Sk be slabilizing policy and assume that
e e-approzimate solution to Problem 1 in cost Ö g1.8
5.3 Numerical Experiments
ness. We conduct numerical experiment to showcase the correctness of our quantum policy gradient algorithm. Following similar setup as in 45, a mass-spring- damper system with g = 4 masses is used for constructing LQR problem. The state

---

10a
classical
10a
10
10
10a
1
10'
Time
10
10-
classical
classical
10
ours
10-
ours
10a
250
500
750
250
500
750
10
20
BoF
50
60
(a) J J
(b) f(K) f(K)
(c) runtime
Figure 2: Numerical Results on Convergence. Following the mass-spring-damper setup
in
45
our policy gradient descent algorithm converges much faster than 45
p 2 J
2o contains positions and velocities, with dynamic and imput matrices,
I -T -T..B.
[ Q
0
A
Q 1
100ele] R = 4e2e2
(26)
where 0 are g x g zero and identity matrices, e, is the ith unit vector, and matrix has 2 on the main diagonal and -1 the first super- and sub-diagonal. In Figure 2 run our mothod against the classical model-frce gradient-based method 25 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 x 10a iterations (orders of magnilude longer). In Figure (c); we increase the system size by scaling 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:/ ////gtthuu..... www.tu..coom.iliiii........ wom/YilingQiao//aiiiiiccci 1qr
Additional numerical results can be found in Appendix
6 Conclusion and Future Work
In this paper, we propose the first quantum algorithm for solving linear- uhear-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.c., m < n). Morcover, 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 TQQ,, 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 [emma 33 may not hold. In the future, we aim to explore both the practical utility of quantuu computing for such tasks and its potential for handling more complex optimal control scenarios, such as non-quadratic and nonlinear problems.
Acknowledgment
We thank Kaiqing Zhang for the helpful discussions and the anonymous reviewers for their helpful feedback. This work was supported in part by the U.S. Department of Energy Office of Science, National Quantum Information Science Rescarch Centers, Quantum Systems Accelerator, Air Force Office of Scientific Research (Award##A9550221110000) the U.S. National Science Foundation Career Grant (CCF-1942837), Sloan research fellowship, Meta Research PhD Fellowship, National Science Foundation Graduate Research Fellowship (Grant No. DGE 2236417), the Simons Quantum Postdoctoral Fellowship, Simons Investigator award (Grant. No. 825053), and Dr. Barry Mersky Captial One E-Nnovate Endowed Professorships.
10

---

References
[1] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J Egger, Bruce G Elmegreen, al. Quantum optimization: Potential, challenges, and the path forward, 2023.
arXiv:2312.02277
[2] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and sta- tistical zero knowledge. In Proceedings of the thirty-fffth annual ACM symposium on Theory of computing, pages 20-29, 2003.
3] Dong An, Andrew M Childs, and Lin Lin. Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all paramnterss 2023. arXiv:2312.0300
[4] Dong An, Jin-Peng Liu, and Lin Lin. Linear combination of Hamiltonian simulation for nomunitary dynamics with optimal state preparation cost. Physical Review Letters, 131(15):150603, 2023.
[5] Rika Antonova, Jingyun Yang, Krishna Murthy Jatavallabhula, and Jeannette Bohg. Rethinking optimization with differentiable simulation from a global perspective. In Proceedings of The 6th Conference on Robot Learning. PMLR, 2023.
[6] William F Arnold and Alan Laub. Generalized eigenproblem algorithms and software for algebraic Riccati equations. Proceedings of the IEEE, (2(12):1746-1723 1984.
7 Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F Zuluaga. Quantum interior point methods for semidefinite optimization. Quantum, 7:1110, 2023.
(8) Peter Benner, Zvonimir Bujanovic, Patrick Kurschner, and Jens Saak. A numerical comparison of different solvers for large-scale, continuous-timn algebraic Riccati equations and lar problems. SIAM Journal on Scientific Computing, 42(2):A957 A996, 2020.
Dominic W Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematicnl and Theoretical, 47(10):10533) 2014.
[10] Steven J Bradtke, B Erik Ydstie, and Andrew G Barto. Adaptive linear quadratic control using policy iteration. In Proceedings of 1994 American Control Conference-ACCC9), volume 3, pages 3475 3479. IEEE, 1994.
[11] Shantanav Chakraborty, András Gilyén, and Stacey Jeffory. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation, 2018.
ar arx:v 110:01804.0993
[12] El Amine Cherrat, lordanis Kerenidis, and Anupam Prakash. Quantum reinforcement learning via policy iteration. Quantum Machine Intelligence, 5(2):30, 2023.
[13] Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal Computing, 46(6))1920-1195 1950, 2017.
[14] Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. In International Conference on Machine Learning, pages 1029-1033 PMLR, 2018
[15] Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi. Near-optinal quantum al- gorithms for multivariate mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 33 43, 2022.
[16 Nikolaus Correll. Parameter estimation and optimal control of swarm-robotic systems: A case study in distributed task allocation. In 2008 IEEE International Conference on Robotics and Automation, pages 3302 3307. IEEE, 2008
[17] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Rechi, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mothematics, 20(4):633 679, 2020.
11

---

[18] Karthik Elamvazhuthi and Spring Berman. Optimal control of stochastic coverage strategies for robotic swarms. In 2015 ieee international conference on robotics and aulomalion, (iera), pages 1822-1829) IEFE, 2015.
[19] Maryam Fazel, Rong Ge, Sham Kakade, and Mchran Mcsbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International conference on machine learning, pages 1467-1476. PMLR, 2018.
[20] Franziska Feitzinger, Timo Hylla, and L'kkehard W Sachs. Inexact Kleinmau-Newton method for Riccati equations. SIAM Journal on Matriz Analysis and Applications, 31 31(2):272-288 2009.
[21] Greg Foderaro, Pingping Zhu, Hongchuan Wei, Thomas Wettergren, and Silvia Ferrari. Distributed optimal control of sensor networks for dynamic target tracking. IEEE Trunsactions on Control of Network Systems, 5(1):142 153, 2016.
[22] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51sl Annual ACM SIGACT Symposium on Theory of Compuling, pages 193 204, 2019.
[23] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical review letters, 100(16):160501, 2008.
[24] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009.
[25] Bin Hu, Kaiqing Zhang, Na Li, Mehran Mesbahi, Maryam Fazel, and Tamer Başar. Toward a theoretical foundation of policy optimization for learning control policies. Annual Review of Control, Robotics, and Autonomous Systems, 6:123-153 2023.
[26] Yuamming Hu, Luke Anderson, Tau-Mao Li, Qi Sun, Nathan Carr, Jonathan Ragan- Kelley, and Frédo Durand. DiffTaichi: Diflerentiable programming for physical simula- tion. In ICLR, 2020.
[27] Krishna Murthy Jatavallabhula, Miles Macklin, Florian Golemo, Vikram Voleti, Linda Petrini, Martin Weiss, Breandan Considine, Jerome Parent-Levesque, Kevin Xie, Kenny Erleben, Liam Paull, Florian Shkurti, Derek Nowrouzezahrai, and Sanja Fidler. gradsim: Differentiable simulation for system identification and visuomotor control. International Conference on Learning Representations (ICLR), 2021.
[28] Sofiene Jerbi, Arjan Cornelissen, Māris Ozols, and Vedran Dunjko. Quantum policy gradient algorithms, 2022. arXiv:2212.09325
[29] Amara Katabarwa, Katerina Gratsea, Athena Caesura, and Peter D Johnson. Early fault-tolerant quantum computing, 2023. ar 2r11v22311.14814
[30] lordanis Kerenidis and Anupam Prakash. Quantum recommendation systems, 2016.
ArXiv:1603.08
[31] Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al. Evi- dence for the utility of quantum computing before fault tolerance. Nature, 618(7955):500 505, 2023.
[32] David Kleinman. On an iterative technique for Riccati equation computations. IEEE Transactions on Automatic Control, 13(1):114 115, 1968.
[33] Hari Krovi. Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7:913, 2023.
[34] Peter Lancaster and Leiba Rodman. Algebricc Riccati equations. Clarendon press, 1995.
(35] Alan Laub. A Schur method for solving algebraic Riccati equations. IFFE Transactions automatic control, 24(6):913 921, 1979.
12

---

[36] Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu. Quantum Hamiltonian Descent, 2023. arXiv:2303.0147
[37] Jiaqi Leng, Yuxiang Peng, Yi-Ling Qiao, Ming Lin, and Xiaodi Wu. Differentiable analog quantum computing for optimization and control. Advances in Newral Information Processing Systems, 35:4707-4722 2022.
[38] William Levine and Michael Athans. On the determination of the optimal constant output feedback gains for linear multivariable systems. IEEE Transactions on Automolic control, :541):44 48, 1970.
[39] Xiantao Li and Chunhao Wang. Efficient quantum algorithms for quantum optimal control. In International Conference on Machine Learning, pages 19982-19994. PMLR, 2023.
[40] Fu Lin, Makan Fardad, and Mihailo R Jovanovic. Augmented lagrangian approach to design of structured optimal state feedback gains. IEEE Transactions on Automatic Control, 56(12):2923 2929, 2011.
[41] Jin-Peng Liu, Herman Oie Kolden, Hari K Krovi, Nuno F Loureiro, Konstantina Trivisa, and Andrew M Childs. Efficient, quantum algorithm for dissipative nonlinear differential equations. Proceedings of the National Academy of Sciences, 118(35):e00260051 2021.
[42] Guang Hao Low and Yuan Su. Quantum eigenvalue processing, 2024. arXiv:2401.062400
[43] Nico Meyer, Christian Ufrecht, Maniraman Periyasamy, Danicl Scherer, Axel Plinge, and Christopher Mutschler. A survey on quantum reinforcement learning, 2022.
ar Xrxivv221 03464
[44] Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, and Mihailo R. Jovanović. Convergence and sample complexity of gradient methods for the model-free linear- quadratic regulator problem, 2019. arXiv:1912.11899
[45] Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, and Mihailo R Jovanović. Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem. IEEE Transactions on Automatic Control, (5):24433 2450, 2021.
[46] Miguel Angel Zamora Mora, Momchil Peychev, Schoon Ha, Martin Vechev, and Stelian Coros. Pods: Policy optimization via differentiable simulation. In International Confer- ence on Machine Learning, pages 7805 7817. PMLR, 2021.
[47] Kirsten Morris and Carmeliza Navasca. Iterative solution of algebraic Riccati equations for damped systems. In Proceedings of the 45th IEEE Conference Decision and Control, pages 2436-2440. IEEE, 2006.
[48] Kirsten A Morris. Introduction to feedback control. Academic Press, Inc., 2000.
[49] Yi-Ling Qiao, Junbang Liang, Vladlen Koltun, and Ming C. Lin. Efficient differentiable simulation of articulated bodies. In ICML, 2021.
[50] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018
[51] Valeria Simoncini. Computational methods for lincar matrix equations. SIAM Review, 58(3):377-441, 2016.
[52] Sanghyun Son, Yi-Ling Qiao, Jason Sewall, and Ming C. Lin. Differentiable hybrid traffic simulation. ACM Transactions on Graphics (TOG), 2022.
[33] Hyung Ju Suh, Max Simchowitz, Kaiqing Zhang, and Russ Tedrake. Do iifferentiable simulators give better policy gradients? In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 20668 20696. PMLR, 2022.
13

---

[54] Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games, 2019. arXiv:1904.00 03180
[55] Joran Van Apeldooru, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 403-414 414. IEEE, 2017.
[56] R. Vinifa and A Kavitha. Lincar quadratic regulator based current control of grid connected inverter for renewable energy applications. In 2016 International Conference on Energy Efficient Technologies for Sustainability (ICEETS), pages 106 111. IEEE, 2016.
[57] Xin Wen, Xuting Sun, Yige Sun, and Xiaohang Yue. Airline crew scheduling: Models and algorithms. Transportation research part E: logistics and transportation review, 149:102304, 2021.
[58] Simon Wiedemann, Daniel Hein, Steffen Udluft, and Christian Mendl. Quantum policy iteration via amplitude estimation and grover search towards quantum advantage for reinforcement learning, 2022. arXXvv2206.0441 04414144111
[59] Zhou Xian, Bo Zhu, Zhenjia Xu, Hsiao- Yu Tung, Antonio Torralba, Katerina Fragkiadaki, and Chuang Gan. Fluidlab: A differentiable environment for benchmarking complex fluid manipulation. In International Conference on Learning Representations, 2023.
[60] Jie Xu, Tao Chen, Lara Zlokapa, Michael Foshey, Wojeiech Matusik, Shinjiro Sueda, and Pulkit Agrawal. An End-to- End Differentiable Framework for Contact- Aware Robot Design. In Proceedings of Robotics: Science and Systems, Virtual, July 2021.
[61] Jie Xu, Viktor Makoviychuk, Yashraj Narang, Fabio Ramos, Wojeiech Matusik, Animesh Garg, and Miles Macklin. Accelerated policy learning with parallel differentiable simulation. In International Conference on Learning Representations, 2021.
62 Yao Zhang and Qiang Ni. Recent advances in quantum machine learning. Quantum Engineering, 2(1):e34, 2020.
14

---

Appendices
A LQR theory
Definition 6. Given a positive number a > O, we define the sublevel sct SK (a) = {K Rmxx f(K) S a). We have the following useful bound on K.
Lemma 8. Over the sublevel set Sy (a) of the LQR objective function f(K), we have
(x(x(K) ]]] & a/Amin(44 (Q),
(27a)
v/a I Amiu (X(K))
(27b)
| F 2 a/ V Vmmin (R),
(27c)
where the constant
1
|| (miu(Q)
Bl12 v Amia (R)
(28)
4
Proof. See 45 Lemma 16].
Lemma 9. For any K E (x(a), we have
K K
(((K))(((())
(29)
2 Vdmin (R)
where the same as in
Proof. By 45 Lemma 2]. we have
[(K)- Tr [K KT)TR( - - (*)((K)) Combining the above result with Lemma 8 end up with (29)
2 Amiu Amin (X(K)) K
Lemma 10 (PL condition). Fir > 0. For any K E Sx (a), we have
[VS(K) 2 (ps( {(K))),
(30)
where By > 0 is conslant that only depends on the problem dala and a.
Proof. See
45 Remark 2].
B Implementation of block-encoded matrices
Lemma 11. Assume that we have efficient procedures (as described in Assumption 1) to access the problem data A, B, Q, R in (poly log(n)) time. For a fixed a > 0, suppose that K Sk is stabilizing policy stored in quandum-accessille data structure. Then, implement
1. (s(1 K F + 1),e) - -blcc-ee-e-n-kkiiingg of A - -BK in cost Oppoly log(n, s/e));
2. (s(1 K| 2 + (ea.)))booc-eeoolii of Q KTR.K in cost O(poly log(n.s/e)) s/e)).
Proof. By 22 Lemma 48). we can implement a (s, blos)-block- of A (or B, Q, in cost (poly s/E)). Also, due to [22] Lemma 50), we can implement a {| F) block-encoding of K in cost Oppoly log(n, 1/=)). Therefore, by [22] Lemma 52, 53]. (s(I] 1), blocc-cocckn of A BK can be implement in cost O(poly log(n, s/E)). Similarly, can implement (s([ K + block-boook- of Q + K RK in cost Opooy log(n,
Remark 1.
We observe that the block-encodings of A BK and Q + KT RK can be implemented with high precisions, i.e,, in cost Oppoly log(1/s)). To simplify our technical arguments, we assume these block-encodings can be implemented with no error, i.e., we can implement (<[ + (loc))))ook-enooooe of A- BK (or (s[I) +1), en-cocinggnnodiing of Q KJ RK in cost Oppoly log(n,
15

---

C Matrix exponential based on quantum linear system solver
C.1 Block-encoding for matrix inverse
Lemma 12 (Modified from A2 Lemma 11). Let C be matriz such that C/ac block-
encoded by Oc with some normalization factor ac- Then we can implement a (O(ac-1) block-encoding of C-1 using
O(ko log(1/e))
(31)
queries to Oc. Here Ke is the condition number of C.
Suppose we have an blooe))boock-nncodiigg UM that block-encodes M. Denote
a:O)Umm () M A,
(32)
we have ||||| I s. Then we can see UM as an (ax bllock-encoding of M + A/a. So with the lemma above, have the thcorem below:
Theorem 13. Suppose we have an (a,ε1)-blodd) encoding UM that block-encodes M, then we can implement a (O(am-1), + a-tiau-1 (ili))-boo--eeeee encoding for M using
a2
"M
O(nas log(1 (152))
(33)
queries UM.
Proof. From the lemma above we know we can implement a (ăM-1, 62)
as bloc-cccoookk haa----e--lccchccceeooo
-M for (M + A/a), where a = O(aw-1). To analyze the error,
llă || S E2 + II(M + A/aa) M E + (I
1//0)-1100 -M--11
E2 + 1 100 = 62
Σ ((-M ((-M |MM-
a aM- E1.
<
| S a E1aM-1
n=1
(34)
C.2 Introduction to quantum linear system solver
The first quantum algorithm for solving linear differential equations proposed by g Since this work was done, several refinements have been made. Among these, [3 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 Au,
(35)
dt
upon appropriate discretization method and the method of line, one may construct a big matrix A s.t.
O()
(()))
u(h)
u 2(hh)
A
(36)
(TT)
Then it is easy to see that the matrix inverse A -1 satisfies
(ik) @ A)A- ((o) @ u(0) u w(kh) e kh v()).
(37)
Because u(0) is arbitrarily chosen, we conclude
((k) A)A - & T) khA
(38)
Suppose 1 block-encoded in some U we have
((k) @ (((()) T)UA-1(09) 6 ()) /) = ((k0 s Here & satisfy 2f = hh, where T is the simulation time and h is the step size. Then it is obvious that U is also block-encee bloc--encoding of khA
60 T).
(39)
16

---

C.3 Matrix exponential construction
Lemma 14 (Modified from defined as
33
we have block-encoding Ur, that L
L=I-M, N,
m
2m
N Σ
+ 1xi 60 M2 - Mi)
Σ
1
Ah
(40)
Mi
Σ
li + 1X61 &
j+1'
==
k
M
Σ
==
then the (, -ll---booo--eooliiie Ut.1 that block-encodes L- satisfies
|al ((r0%) @ T)UL :10ate) 6 1) AA Sc
(41)
for anyy 2 m 1. Let 20-1 m. thus
ag 110 2 1) ((X @ 1--1 2 La 0 1)U, =) (10 8 1) E
(42)
which means that ((X & ---1 & I @ 1-1) is a block-encoding of TA with its normalization factor ag-1 and error being at most
Proof. The proof of the correctness of T, can be found in 33
Now turn to construct the block-encoding for L.
Lemma 15. Assume we query the (o O)-block-encodlee UA that encodes A and has O(),, then we construct a (O(KL.5), - b-occcc--nnnoiiigg for L, defined in (40)
using (k log(1/e)) queries of UA and same queries to addilional elementary gales.
Proof. First need to block-encode MI. We will use the ADD operator defined as
ADD E1(+1) mod kXil.
(43)
and the controled-rotatioon Un as
URli+ 1)10) lj + 1)
j+1 0) + V ( 132 11
(44)
Notice that
(Un @ (ADD & 187)
bi bYloIQUAl
(45)
Σ UR(l++1 mod kXJ 8 1) & UA.
Post-select on the second register and the ancilla qubits of UA, we have
k-1
(I 2 (0) 2 (0))
Un(li+1 +1 mod kXil & 1) 2 UA (1) 0))
(46)
A/as j j+1
-Σ 11+1)
mod
17

---

If we apply the operator on a state, namely
1 Σ Un(((+11 mod kXil kXil 1) UUA 10)0)10) a)( (1 (1+1) mod 11
(47)
So we can apply more multi-contrrlled-X. gate to flip the flag register for the control register being [0), then the whole thing becomes a (axh, O)-block-encoding for Mi, using just query to UA. We can then easily generate the block-encoding of M1 by LCU, with
1 + agh normalization factor. By the analysis in [3 we know || - Mil [I - M1)-1 S
2k. Using Lemma 12, can implement
(1(k))e))-boon elodk-ngn of (I M1) using
(( queries to the block-encode encokinn
M1 thus the same queries to UA-
For the block-encoding of M2, since it is sparse, we may directly implement it through the sparse imput model. We may just assume the normalization factor to be vk and there is no error. Then we can implement a (O(K3/2), v bllok---eooddngg of (I M1) M2 using ((llog()/))) queries to UA and other additional gates.
For the block-encoding for N, we can see the normalization factor would be the same scaling as M2 - M1)1, thus we implemented a (O(1./3), (-lVeea))bboockccccoo
N.
Now we use QSVT to perform the matrix inverse, just as described in Theorem 13 we can implement an (ag-1,,2 + σo o1-e1ag- vke bbeek-bbooc--enooddnng UL-1 that encodes I.1 in cost OKL log(1/s2)) queries to Uz, ie. OKz log(1 log(1/1)) queries to UA-
a²
In order perform the inverse of L, we need know the condition mumber of L. Lemma 16 (Modified from 38
Theorem & 4). Suppose E is the solution operalor Wock-encoded by UL-1 that appronimates eAT and m is the numbee of steps. Let
(k - 1)! me²
CA.
(48)
8
where
sup || ||exp(Att) S CCA.
(49)
we have
E AT 6 0 +))
(50)
and
Kr. S 0 100mm/Caa111 + 5)).
(51)
Proof. The proof can be seen at
33 Theorem 4].
Let matrix A be a Hurwitz matrix with sup, ll exp(tA)ll bounded by some constant p, and O is (a., (looo))-bbkkeee -occdiic--nn of A. Then construct a (CT, blockk encoding of AT using
Theorem 17.
ō (asspT poly log (
(52)
queries to O and same queries to other additional elementary gates. Here (= O(aAp).
Proof. Firstly notice that m = Oa and == we noed & E, which could be given by letting
log(TexApd) log log(T
) For given accuracy 6,
af
E2 + aj 110
vkz S..
(53)
Choose é = Ō()/T2) and E2 s/2, from the discussion above we know we can implement an (el---,))bloock-eeeddd of TA Since a- = O(mp(1 + 6)), the queries we need is Ö(aApT poly log(1/s)).
18

---

Remark 2. If we directly use the theorem above to prepare the state le |e^T) for some imput state (4), the dependence on T would be 7 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 padding the quantum linear system solver, we can easily improve the current scaling into 78/2. However, for simplicity, we do not implement these standard improvements this work, as they does not affect our end-to-end complexity result.
D Quantum eigenvalue transformation for linear differential equations
Here we exploit a technique known as quantum eigenvalue transformation (QEVT) by Low and Su 42 to simulate linear dynamics è Ar. The algorithm (QEVT) requires that the dynamics is stable under A + A $ 0, which is stronger than A is Hurwitz stable.
Notice that A+ T Lyapunov equation AX + XA" < (16) indicates the stability under the inner product induced by the mairix X. We hence lollow 42 use sequence of polynomial functions (known as the Faber polynomials) to approximate the time-evolution operator ett
is the stabilitt under the common 2-norm, and A satisfying the
Lemma 18 (Faber truncation of matrix exponentials, 42 Lemma 27]). Suppose we have matriz A where its namerical range W(A) == ((b))
|| = is enclosed by a Faber region & with associated conformal maps - W : + and Faber polynomials F,(z). Given t > O, let e = Li= (z) be the Faber expansion of the compler exponential function etz Assume that & is convez and symmetric with respect to the real ozis, lying the left half of the complex plane, then for sufficiently large s,
5-1
((
E3,1((A)
(54)
K=0
where c is constant determined by the conformal maps.
By Lemma 18 given any > 0, it suffices to choose s ~ O(tlog( such that
(A) S..
(55)
Definition 7. For some matrix A of size N x N with its normalization factor aa, denote the identity matrix of size N x N as IN, and
0
1
0
1
0
NN
1
0
(56)
NxN
as the lower shift matrix of size N N. We then define
A
PAD(A) : -0 & ( 2 IN LN &
aA
(57)
+|1X0| @ OYN 1| @ (N) + |1|1| @ (IN - LN) 8 IN.
and
PAD(B) joXo| & V V'( IN [XX IN & IN.
(58)
Note that the conformal map V has its Laurent expansion, and so are ('(w) and (W Furthermore, ('(w) and () only contains terms with non-negative exponents. Thus v (L and ('(Lz)) are well-defined even though L is not invertible itself.
19

---

With the matrices (AD(A) and PAD(B), we can compute the matrix (AD(A) PAD(A)-PAD(()) (B) say
0
((A) (A)
Fo(
PAD(A)=\PA((B)-
F
Fn-2 A
Fn.
Fo
(59)
TT
F F3-2
0
A
2
Fo
1
( A
(2)
Fo I I
Note that this matrix has (2s) x (2s) blocks, and each block of size N x N.
Definition 8. For a matrix whose numerical range enclosed by Faber region & with associated conformal maps +: - + DD, V De + E and Faber polynomials F,(2), consider some Faber expansion till s-th order, we then define
FJ
P J=
(60)
as an upper bound on the derivative of Faber polynomials. Lemma 19. We are able to have a (E, -bllock- to (PAD(A)) using O log (+)) queries to the block-encoding of A and ((1) additional elementary gates, Here (ps).
Proof. Since we know that PAD(A) can be block-encoded with an O(1) normalization factor with arbitrary precision using single query to the block-encoding of A and polylogarithmic number of elementary gates, and ((PAD(A)) = O(sp), the rest of the proof is done by Lemma 12
Theorem 20 (Modified version of Theorem 10. 42 Let matrir A have its numerical range W(A) = {(b) A w) ||]b)||]| 1} enclosed by Faber region with associated conformal maps : E D= v DE E and Faber polynomials F,(2). Let p(z) 5 be the Faber expansion of degree-(s 1) polynomial p and O₂10) = Di 1aln-1 1- /1 be the oracle preparing the coefficients. Then, can construct (E' [[@lle) of
using
o
0 ps log (2)
(61)
queries to OA, query to Og and Ō(1) additional gate. Here, g' < O(ps).
Proof. First, we observe that
3r |
(00 ② I) (PAD(A) & 80 (10)
0) Σ
Fo(//os) (62)
The X is the quantum Pauli-X gate. Here the circuit has 3 registers, the first one only has one qubit, the second has loga qubits, and the third one matches the size of A.
By 42 Theorem 9], implement block-encoding of PAD(A) using single query to the block-encoded matrix A/a Also, given a constant
F fax j
PZ
max j=l...
(63)
we know that [P=) O(p)). By Lemma 19 we can construct a (5, (bockebloc-- of PAD(A)-1 using O log(1/e)) queries to the block-encoding of A/a
20

---

Also, assume we can implement block-encoding of PAD(B) with ((1) normalization factor. Combining these two block-encodings together. we obtain a (...e))bock-encooeee of PAD(A))IPAD(B), where ç S (ps). Then, by (62) the block-encoding we implemented turns out to be (5'1)81I, [lokll))bbookkcccodinng of Lk=0 (A/a(A
Theorem 21 (Block-encoding of matrix exponential). Suppose that A E Rmxn is Hurwitz matriz, and O^ a (ax (a..)))boo--enoodiig encoding of A. Then we can implement a (Ct, (St,,))-lock, encoding of At using
o (a log (
(64)
queries to OA, one query a state preparation oracle Og and Õ(1) additional gate. Here Ç = O(a poly log(1/c)).
Proof. First we use
Lemma 18 to ("a(A/aa)), then we know the polynomial should be of ei in order to have a e accuracy. Then leverage Theorem 20 we need
degree Ol log
o (p
queries to Oд to construct a block-encoding the polynomial. Since the Faber polynomial expansion of e converges absolutely, without loss of generality, we assume || is (l)). Choosing E and E2 2 we have a (Ct, bloock---oc--kn of
log
et
L
E Proof of Theorem 4
Lemma 22 (Select oracie). Suppose that A is Hurwitz, and Oa is an (a, -)-block-ennodding of A. Let K be positive integer and T, > are two real-valued scalars. The select oracle as defined in Definition 4 can be implemented using
(app log(K) poly log 1
(65)
queries to controlled Os, and Ö (aprk log(K)) poly (og( queries to other additional elementary gates.
Proof. Firstly, tx here attains ts kr By Theorem 17 for each t: 0,... K, can K implement a (et..s))-lockkencoddin of Ax using Olaptx poly log(1/s)) queries to OΛ. We denote this block-encoding as Up. Notice that the select oracle (Ale e) be represented by
K
select (A, = II
(II [k)(()) @ I |&X&| @ Uz]
(66)
k=
where each unitary operator [[1- [x)x+]) @ 1+ [k)(|| @ U&] in this product is a k-controlled version of Uk that can be implemented with Öappt log(K) poll log(1/s)) queries to the controlled OA and other additional gates. Therefore, the overall query complexity is
((
(apT app
K E4 log(K): poly log ( k=
S Sō
<0(0pt (appk log(K). poly log ! )
(67)
where the last step follows from Ek 4 = ΣK kT
(K+
K=
In the following proof, we will need a state preparation oracle
K
Ox
(68)
km
21

---

where X w | ΣE ~ A and wn. (2-1==0k)r Since A can be expressed as
smooth function of for & E [0,1, K). this state preparation oracle can be implemented in (ppoly log(K)) cost.
Now, ready to prove Theorem 4
Proof.
The global error of the trapezoidal rule (see (20)
proportional
F"
(9)
(69)
K2
where
(9) = (() + 2AF(S)A + & 4||A||
Thercfore, to achieve precision E the total number of quadrature points is
3/2 (=00?))
=
(70)
2//
Now, we consider the following two select oracles, as defined in Deñnition 4
K
k
select = 1KX1| @ Us. select(A .82) =
Σ
|XX & Va.
(71)
k=
where Up (or Vi) is (Stx, bloy---oo--enodiii of ets (or eA eATu) for 0 < k K. Recall that On is a (n, ho--block-encodeee Q it turns out that
select(A,e)) & Os)seloct(A .0) Σ RXK @ W.
(72)
where We = U is 2 2[tarra)-block-encooing of the matrix $ (tx).
Let Ox be the state preparation oracle defined in (68) By the LCU technique 22 Lemma
52], we can implement a (7, Ek= 2/wx (nlfk=a)-blockkeeneee
(where 7 = Σ ww ls 22
of Ek=o Me using single query to (ieet(A,e)) select(AT, 52),, Uo. Ox and its inverse.
Notice that
T KT
Wwl th $
>
O(72), O(7).
(73)
K KK K
k=
thus
2 wk MTt4E2 O (72(CE))
(74)
k=0
Given positive scalar E > 0, and set the integration time
3/| 3||X111 ||
k log
(75)
[ >mmin (x*)
Note that.
Φ "poly
[oog
2)
(76)
8
then if we choose
E1
Eg = O(E2+6).
(77)
3
where constant positive number. By Lemma and the error analysis above, we implement a
of X*, with
K
Wk 22t = 0(a3p313m))
(78)
22

---

It follows that the overall cost of this block-encoding is
a
(79)
E1/2
queries OA and same queries other additional elementary gates.
F Quantum trace estimation
Here we show how to estimate the trace a positive definite block-encoded matrix. The main result is in Theorem 25
Lemma 23. Let UH be an (a, --m.mm..bbocc-eeee HE C" and let e (0, }11 Let Amin > 0 be known lower bound on the smallest eigenvalue
of a positive-deftnits Hermitian matriz
of H. Provided that ε S Amine lug(1/E)
sufficienlly small (where e >> 0 is a given number))
applications of Un and UH, a single application of controlled-Uni and O [mm+1)) log(1/E) other one-
construct (1, -bb-b.eeenoooceennddiing of 36
Hia using O
Auman log((/E))
Amen
and twoo-uuii gates. The description of this block-encoding circuit can be computed classically in time O (poly log_1)
Proof. Define Amia == Amia/a, such that Amint 3 H/a I. We first find polynomial approximation of f(x) == V over [Amin: 1] using 22 Corollary 66). To use this corollary, Ee= (2/2)x²
let 2g 1, 1 Aminy d == Amin; and observe that f(xo +x) 1
whenever |x| S 8 1. Also note that Σ (1/3) S 1 = B. Then there an efficiently computable polynomial Po E C[x] of degree d o (og(11))) such that (=) Po(x)l S for [Amin. 1] and [x) S B S 2 for x [-1, It follows that defining P(x) Re (Po(x)) gives (f()) P(x))
Auiin
Xmmn.1] S and |P(x)) S 1
Next, we use [22 Theorem 56] to construct construct a unitary V that is a (1,m+ + e, e/2)- encoding of P(H/a) with the desired complexity, using the promise that εн is sufficiently
small to satisfy 4d /EH//// s s/4. V is then a (1,m + 2, block-eenodien
V
H/a since 36
11/a (10 & I)V(10) 8m+2 @1)
36
H/a P(H1/)) P(H/a) @m) @ T)V(10) 8m+2
36
(80)
(lg(H/a) - P(H/a)ll + [[diag(((Am/aa) diag diag(P(Nn/aa))
max 9(\x/a) P(A/a)) 2 =,, X.EA
where dy E Fn is the vector of eigenvalues of H.
Lemma 24. Let μ > 0. Let A be n-by-n Hermition matriz such that 0 < A I and let V. be (1. block-encoding of VA. Then there erists ÚA such that [(00 & 1o 0/||2 T((A) s that uses 1 query to V and O n) additional gates.
Proof. Our proof is similar to the proof of 55 Lemma 13). The idea to first prepare the maximally entangled state E /)) /n (which requires Oloog n) gates) and then apply the map V the first register. We can assume without loss of generality that. μ S 1, otherwise the statement is trivial.
23

---

Note that ( Rm @ ( 8mh @ is a 1/3-approxiimatin of VA by definition. We interested in the probability p of measuring 0pm in the first register after applying V.
2 b
((0) @m
[)O mm
Vo
(81)
i) = Tr (o.Vo
It remains to show that p is a good approximation of Tr(A)/n. For this, we show 1i% ~ A. Note that for all matrices B, B with ||||||
- 1, we have
B - B = (Bt Bt
B$ - -) -B)(B- B)|
< ( BtB
+ BBBB -B)B-Bi]- + -| (B
(82)
< BB 31 |B|| + B B B- B + +|| B' - -B
< B - B| +
B
Using equation
(81)
along with equation
(82)
(lotting B VA and = Vo), we see
Tr(A)
p
Tr ( volv))
A 1o Vo
+
1 3 S μ.
(83)
Theorem 25. Let Un be an -lom))))oooc--ecooinng of Hermilion molrix H E Cax where Uh can implemented using Th elementary gales. Suppose H and let Amin > be a known lower bound on the smallest eigenvalue of H. Then, with probubilily at least 4/5, we can estimate Tr(H) to within multiplicative error E (0, 1] in cost
a 3/2TH log 0Xinin
)
O
(84)
0x 3/2
provided that E S 00(
mia 92 logla (8/mi))
Proof. Our proof is similar to the proof of [55] Corollary 10). Let A H/a 36
and note that
since H/a y Amin /aa we have
Tr(A)
Tr(H/a)
Amin
(85)
n
36n
36a
Let U. be (1, mmmm++2 2, 0mmin/ /216a / clock-nnodingg of VA constructed via Lemma 23 Using
Lemma 24 we can construct a unitary circuit V such that
||(00| & rv o)|²
Tr(A)
0Amin
0
Tr(A)
Tr(A)
(86)
n
72x
2
n
2n
Therefore we have
||:0| o ni .0/l///// (A(
Tr(A)
Tr(A)
Amin Pminn
>
(87)
n
2n
2n
72x
as well as
[(0] & r)vio...0) 0/|
Tr(A)
Tr(A)
TT((A)
(88)
2n
2n
Using the amplitude estimation technique of b5 Lemma 9] with Pmni Amin /72 and f 0/3 gives us P that with probability at least 4/3 satisfies
i - |[00| 1)voo....))
.//|/| < [100]] @ 1)Vio...0// /)/² S Tr(A)
(89)
2
24

---

By combining 86 and (89) and using the triangle inequality, we get
Tr(A)
P S 0 Tr(A)
(90)
n
Therefore, 36anp is a multiplicative 0-approximation of Tr(H).
It remains to show that the complexity statement holds. The construction of ÜA via Lemma 23 uses O[Th x log(a/0Amiin) elementary gates from the applications of Un, UH and controlled-UH, and O((m 1) Amin log(a/OAmin)) other one- and two-qubit gates. The construction of V requires additional Ollog n) gates. The amplitude estimation step requires ( (1 a Amin/0) uses of V and Vt, and ((Va///mi l/0) additional gates. So the overall complexity is
o
(
y Va//mmn
aTH log
(m + 1)e
a
+ log ))
log
(91)
0
Amnin
0mmin
Amin
0 0mmin
Noting that Th m and Th 2 log n for any non-trivial UH gives the stated bound.
G Quantum gradient estimation
Lemma 26. Given K (x( and || K |F > E, we have
|V CE,
(92)
where the constant um
(R))aa (R)aa.
Proof. This lemma follows directly from Lemma and Lemma 10
Lemma 27 (Block-encoded {(K)). Assume that we have efficient procedures (as described in Assumption 7) to access the problem data A, B, B,Q, Q,Q,R R in Opooy log(n)) time. Let e
SK (a) be a stabilizing policy stored in quantum-accesstie Eb 0, we implement (vv,,E))-lookk block--ncoding of (K(K in cost Ö (aapp p²
data structure. Given any
Kll
where
cb
TV s (aapp^x))
Proof. We know that for the function f(K) defined 55) the gradient has a closod-form expression: Vs(K) 2(RK B B (KK) As shown in the proof of Theorem we can
implement (xe.e))block-encodugg of P(K) in cost δ (a'py
K
where 7/P - =0(atp2
Similarly, since X(K) is the solution to the Lyapunov equation (assuming En = I)
- BK)x X(A - BK)T =1=0,
(93)
can implement (7x, block-encooin of X(K) in cost 0 a'pp
N where xx S
Öaa²p² p²x²). Based on our assumptions on the input procedures and the usage quantum data structure, we can implement (s|l ||] -)-bllok--nnodiing of RK and (87P, -lookk encoding of TT P(K). It follows that (rV (o.)-blokk-ooe block-encoding of V ((K) can be implemented
in cost δ (a3py/ k
where
1 TV = six (Tp + [[]])) S ((())))))))))) 2
(94)
and ε < xOOaa (p To achieve the desired precision, we pass the error parameter e/(2(a + 7P +xx7P)) to the asymptotic cost.
25

---

Definition 9. For a matrix G of size m x we could always write is as
G
[G1
G2
Gn),
(95)
where G₃ a column vector size m x 1. Define [Gvee] as
G1
G2
(vveo
/||G|F
(96)
G
Lemma 28 (Matrix Vectorization). Let UG be (vv, (TV.:))-lock-encollle of (VI(K)) and we denote
G = ==-00 ()U)( I);
(97)
where r is the wumber of ancilla qubils required. Then, uee con prepore a quandum slate (Gvee) with (11) success probability using Ö (TEY T
queries UG and its inverse.
Proof. First, from Lemma we know that we have UJ that encodes Vf(K) Notice that f((K) is of size m n,
1" 2 (U
i0y & (1)))
71) & (10 s (G 1)) +11)
(98)
vV v
t=0
|
E 1i)" s (10))²* s (G 10)) +111
|
where T1, 73 the indexes for registers, where the register has (m)) qubits and the r3 register has log2(n) qubits We can always assume m and n are the power of 2). The state [1] contains the state satisfy
(I" & 10 & |-] =0
(99)
By leveraging amplitude amplification, we can get the state (Gvec) using O D(20 to the block-encoding U.-
|
queries
Lemma 29 (Gradient entry estimation). Denote the state preporation in Lemma 28 for (Gvec) as UG... we are able to get the classical & with
|| |Gveo S Er
(100)
using
δ vV 3/2 | Er
(101)
queries UG and Ō
3/2 dr
additional elementary gates.
Proof. Theorem 2] indicates that get using Ó man queries to the oracle that
prepares (Gvec) and δ m2
additional elementary gates. Since each Ua... requires
δ TV vv |
(102)
queries, we know the total cost should be
m
δ AV
(103)
G
26

---

Lemma 30 (Gradient norm estimation). Suppose we have the block-encoding Ug defined in Lemma 27 where
G (v( @ ()) & T). then we are able to eslimate || up an additive error Sa using
(104)
7V m m G
(105)
E + 2 2|| PEa
queries to UG and its inverse and also Ö
19 /m |Gl|=) 22
elementary gates.
Proof. We still need the computation we did in equation 98 say
m-1
@ (U?
1t) @ (10*))²² @ 12)
(106)
|G||e E [1)" @ (10*))²² @ (G r
(1].
v
| F
According to 55 Lemma 9], we get the estimation to
G Tv v
with multiplicative error
using O 0 achieve is
queries to Ug. Note our estimator to ||G|| as Gest the goal we want to
Oestt - || S Ea-
(107)
2
set μl 22+22a have
Consider estimation to the amplitude
|G
1
Cest ||G|1211 7V
(laest -11G|1/ |aest + +|[G][=|)
7V
m
1
(ea (laest
|G| rl 2||+)])))))
<
(ea + 28 (||])
(108)
||]|| F
2
Sp
TV v m
This in turn gives us the estimation in 107 And this estimation requires
yv m
G
o
(109)
G|
queries to Ua and its inverse. The gale complexity also follows from
55 Lemma 9).
Theorem 31 (Qantuun gradient estimation). Assume that we have efficient procedures (as described in Assumption 10 to access the problem data A, B, Q, R in Opoly log(n)) time. Let K E (a) be a stabilizing policy stored in a quantum accessible data structure. Provided that |K- K*] E, we can compute 0-robust estimate of f((K) in cost
(
m 1.5
(110)
gl.
Proof. We need an estimation to f((K) up to a multiplicative error 0. This requires a few steps as below:
Block-Encoding From Lemma 27 encoding to (K( using
know we are able to construct (obook)-block-
Rll
δ
(111)
Eb
elementary gates. And we also have the estimation that yv < ((appk))))
27

---

Entry Retrieving. The next step is to retrieve the entries in the estimation to Vf(K), We firstly use the technique introduced in Lemma 28 get a state of the estimation to [vee)) and this step requires
TV vvym ||||
(112)
queries. Now we use Lemma 29 to get the entries in (Gvee) up to additive error cr, using
TV 3/22
(113)
G
queries to UG-
Norm Estimation. The final step is to estimate the norm of G. Lemma 30 tells us that we can achieve an additive error Eo to ||G|] using
vv m G
(114)
2 + 2 G PEa
queries Ug.
The rest the theorem is just to assemble all these steps. Note the requirement is
- V]())( s (K)(()
(115)
and according Lemma 26
[F]()) 2 cc before convergence.
Denote the entries retricved in the Entry Retrieving step form a matrix G where ||]]| = 1, the norm estimated in the Norm Estimation step aest, estimator is then aest Choose
cse
dls
C6
Ea
6, 3 +
(116)
3
3
we then know that ||G VS(K)]| S
de
VS(K) 2 0 then
3
dle
< S [f(K)]lr++ ds
O()) S
[Vf(K)]
(117)
Thus is clear to see
1eest [(()]|
0 - [101++++[0))
x a - = + |111-- -
+ G-VJ(K)
(118)
C+E
S ca + || + S E (I)
3 Err + ED
< [K]](
And the total gate complexity should be
δ a a2 2 m.
(119)
f1.5g155
H Convergence analysis
Lemma 32. Given any K Sk, let G be 8-robust estimate of (K).. Then, we have
()(K) 2 ())])
(120)
|| < (1+ (1+))
28

---

Proof. It is straightforward to verify that
(G, (G,VS(K) = (G - // (/(K))
(V/K)]
2 -
(121)
[G|| = || V/(K) + V 5 < V/(K) +
(122)
$ ((+
Lemma 33 (Descent lemma). Given K Sk(a), and let G be 8-robust estimate of (.K(K).
Then, there ewists a positive om such that for all a E [0, om), we have
f(K [G)- f(K)) (1 a/p) (F(K) f(K)))
(123)
where po om only depends on A, B, R, Q, and a, and μ > 0m.
Proof. This lemma is a direct consequence Lemma 32 (with 1/2) and 45 Proposition 6).
Proposition 34. For any initial stabilizing feedback gain Kn E SK. we denote == (Ka).
Then, there erists constonts μ o. 0, depending only A, Q,Q, R, and a, such that for any fixed a E oml, the iterotes of Alloorthm 1 satisfy
f(Kx) - f(k') S (1 (1-01/000 a/1)* (f(Ko)-f(K))) f(K))) |K K b/11-//4)\|1 K' where b is an absolute constant that is independent of k.
(124a)
(124b)
The first part 124a] direct corollary of Lemma 33 have
Proof.
By Lemma 9 and (124a)
||
1 < V V R)
a
(S(K)) [(K*))
(125)
(1 0 0/1)² (f(Kg) - f(K()) S b(1 // l//)///K K"
(126)
where the last step follows from 45 Lamma 2] and Amax (R.X (Ko)).
Theorem 35 (Quantum policy gradient for LQR). Assume that we have efficient procedures (as described in Assumplion 10 to access the problem dala A, B, Q, R in Oppoly log(n)) time. Let Kg E SK be a stabilizing policy. Then, Algorithm 1 outputs an e-approzimate solution to Problem 1 in cost
m mm
(127)
cl.5
Proof. Notice that with lemma
33
need log (t)
iterations. By Theorem 31 the quantum
gradient estimation subroutine requires ① 1.5
elementary gates.
I Extended numerical experiments
L.1 Aircraft Control Problem
We perform another experiment Here, we consider the aircraft flight control problem, specifically for pitch angle control. We adopt a linearized model of the aircraft around steady flight condition. For a small aircraft, the pitch dynamics can be represented by the following state variables: pitch angle 0 (rad) and pitch rate q (rad/s). The control input is elevator deflection angle 8 (rad). The state-space model can be represented
practical problem that can be formulated as LQR.
[6]. We set A [[0, 1], [0, - B = [0, 1] Q [10,00 00. T] and R = [0.1]. The plot of our optimization curve available the Figure Figure 3 Our method converges faster than the classical method.
& Ar Bu, where
[0.q]
29

---

10
10
100
10-1
classical
classical
10-1
ours
ours
20
40
0
20
40
(a) J-
(b) f(K) f(K*)
Figure 3: Numerical Results on Convergence. In the aircraft control problem, our policy gradient descent algorithm converges much faster than classic method 45
1.2 Relative Errors
We conducted further numerical experiments to undersland how the optimality scales with problem size in Figure Figure 4] Here, we scale the number of masses in 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"" and (f(K) f(K*))/ ((K))) As the dimension scales up, the relative errors increase, while our method consistently outperforms the classical optimization method.
10-2
10
10-4
classical
10-4
classical ours
ours
10
10-6
2
3
2
3
4
(a) Relative J- error
(b) Relative f(K) - S(K)) error
Figure 4: Relative Error. We scale the size of mass-spring system and our method consistently gets smaller relative error compared to [5]
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract accurately reflect the paper's technical contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or /or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations.
No or NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect
how much the results can be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations and future work of this work are discussed in the last section of the main paper.
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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-led system might not be used reliably to provide closed captions for online lect because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algo- rithms and how they scale with dataset size.
applicable, the auth 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
31

---

Question: For each theoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
Answer: [Yes]
Justification: The full set technical assumptions is provided in the introduction section (see "Problem Formulation"). A complete proof of our main thcoretical 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 thcorems, 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 appendix or supplemental material. Thoorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or /or conclusions of the paper (regardless of whether the code and data are provided 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 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 reprodueíble is important, regardless of whether the code and data are provided or not.
the contribution a dataset and/or model, the authors should describe the steps (aken to make their results reproducible verifiable.
Depending the contribution, reproducibility ways. For example, the contribution is a novel architecture, describing the architecture fully might suffice, or 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 replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
be accomplished in various
While NeurIPS docs not require relcasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) Tf the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should doscribe the architecture clcarly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
32

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e-g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code for the experiment is attached in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips
onsalicyyllyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NewrIPS code and data submis- sion guidelines for more details.
The authors should provide instructions on data access and preparation, in- cluding how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and basclines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental BeatinggDetaill
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All the training and test details are provided in the "Numerical Experiments" section. The source code for the experiment is attached in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental sctting should be presented the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
33

---

The paper reports error bars to reflect the statistical significance of the experiments, see the "Numerical Experiments" section and Figure 2.
Justification:
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, 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/ter ttett split, initialization, random drawing of some parameter, 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 (c.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mcan.
It is OK to report 1-sigma error bars, but should state it The authors should preferably report a 2-sigma error bar than state that they have a 96% C1, if the hypothesis of Normality of errors is verified.
For asymmetric distributions, the authors should be careful not 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 calculatod and reference the corresponding figures or tables in the text.
8. 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 well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:://barrrpp.ccppppp/////ccad
Answer:
[Yes]
Justification: The rescarch conducted in the paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
34

---

The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses the societal impacts of the work performed in the "Conclusion and Future Work" section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profils, surveillance) fairness consid- erations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational rescarch and not tied particular applications, let alone deployments. However, if there is direct path to any negalive applications, the authors should point it out. For example, it legilimate to point out that an improvement of generative models could be used to generate deepfakes for disinformation On the other hand, it not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
the quality
The authors should consider possible harms that could arise when the technology being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negalive societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper mainly focuses on the theoretical foundation of computer algorithms and poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
35

---

Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The source code of the numerical experiments provided in the supplementary material with appropriate documentation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/coo /wt////oo/oooo/ee as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text instructions given to participants and screenshols, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor rescarch with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
36

---

According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which rescarch is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between insti- tutions 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 the institution conducting the review.
37


Reviews:
[{"review_id": "3BETg1Nm86", "reviewer": "Reviewer_oizh", "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.", "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]).\n\n[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": "I do not see any potential negative societal impact of this work.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "I am not familiar with quantum computing. Since the LQR sample complexity has received much attention recently, this work should be interesting for the learning theory community if the claim about time complexity improvement is correct.", "weaknesses": "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.\n\nBesides, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for confirming that our work is of interest to the learning theory community, given that the technical part is sound. In what follows, we address the concerns regarding the weaknesses and technical details mentioned in the review.\n\nIn Table 1, the “(Model-based) policy gradient [44]” item summarizes the convergence results proven in [Theorem 1, 44]. This result is proven under the assumption of a “known model,” indicating that the policy gradient can be computed explicitly. It focuses on the convergence rate of an exact gradient descent method and is parallel to the “model-free” approach discussed later in the same paper.  Given context in [44], since our algorithm adopts a similar policy gradient idea with quantum-assisted gradient estimation, we believe that it is a fair comparison to mention the (model-based) policy gradient result in Table 1. We apologize for the confusion and will provide expanded elaboration in the camera-ready version.\n\nWe agree with the reviewer that our quantum subroutine for the matrix Lyapunov equation is of *independent interest* and its **application need NOT be limited to the LQR problem**. Our quantum algorithm is based on the integral formula (12),\n\n$$X^* = \\int^\\infty_0 e^{\\mathcal{A}t} \\Omega e^{\\mathcal{A}^T t},$$\n\nwhich holds only when the matrix $\\mathcal{A}$ is Hurwitz stable. If our quantum algorithm does not produce a correct solution to the Lyapunov equation in a designated time, we may conclude that the matrix $\\mathcal{A}$ is non-stable. However, the output of our quantum algorithm is a “block-encoded matrix,” a quantum circuit that cannot be efficiently simulated by classical means. This means that checking if the output “solution” satisfies the Lyapunov equation is quite non-trivial and requires additional algorithmic design, as opposed to the classical case where we can do simple matrix multiplication. For the sake of conciseness and self-consistency of this paper, we mainly focus on the end-to-end solution of the LQR problem. We will clarify our main technical contribution by discussing the potential applications of our quantum subroutine in the camera-ready version and leave the technical details for future work.\n\nRegarding the estimation error on $A$ and $B$: if the matrix $A$ and $B$ are estimated using the independent data collection scheme (as indicated in [Dean, Sarah, et al., 2020]) and these estimates allow efficient quantum input procedures (as described in Assumption 1 in our manuscript), we believe that our method is robust to the estimation error. This is because the relative error in the LQR objective function can be characterized similarly to how it is presented in Proposition 1.2 in the reference paper [Dean, Sarah, et al., 2020]. We thank the reviewer for making this insightful and interesting observation.  We will cite this paper in the camera-ready version. \n\nWe sincerely thank the reviewer for the detailed review. We plan to address the reviewer’s questions in the camera-ready version by clarifying the comparison in Table 1 and elaborating on the scope of potential applications. If the reviewer finds this additional information helpful, we would be grateful if they could consider an increased preliminary rating for this submission.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lA12c7k2LN", "reviewer": "Reviewer_v7Mi", "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.", "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? \n2. 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": "The limitations of this work have been adequately discussed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. To the best of my knowledge, this is the first end-to-end quantum application to linear control problems with provable quantum advantage.\n\n2. This paper also provides numerical evidence to demonstrate the robustness and favorable convergence behavior of the method.\n\n3. This paper is clearly written.", "weaknesses": "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.\n\n2. 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.\n\n3. 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\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer recognizing our work as the first end-to-end quantum application to linear control problems with a provable quantum advantage.\n\nOne main concern in the review is related to the performance and reliability of the proposed quantum algorithm on noisy quantum hardware. The primary objective of this work is to establish the theoretical advantage of our algorithm, and the core subroutine (i.e., solving the matrix Lyapunov equation) requires a fault-tolerant quantum computer. That being said, our method still has reasonable potential for implementation on early fault-tolerant devices. In particular, the following aspects of our algorithm make it particularly robust given **mild noise** and a **limited number of logical qubits**:\n\n1. The **hybrid quantum-classical nature** of our algorithm *mitigates noise* by limiting the runtime of each quantum processing routine via interspersed classical routines, which is advantageous on quantum devices with fewer qubits and shorter qubit coherence times.\n2. The classical optimizer in our algorithm utilizes a **stochastic gradient descent (SGD)** algorithm, which *in principle converges for any unbiased gradient estimator*. The unbiasedness is a reasonable assumption given the independent nature of quantum noise. Therefore, it is expected that our algorithm is resistant to (sufficiently low amounts of) independent noise in gate execution and/or memory.\n3. Our algorithm is truly **end-to-end** in the sense that the input and output are both classical data, which is often not the case for other proposed quantum algorithms for optimal control and RL. For example, most cited works in the “Quantum reinforcement learning” part under Section 2 do not support a comparable classical output.\n\n\nThe second question concerns the key theoretical innovation in the novel quantum subroutine for solving the matrix Lyapunov equation. This quantum subroutine is **exponentially faster** than its classical counterpart and is the key ingredient in achieving *super-quadratic quantum speedup*. The high-level idea of the quantum subroutine is to use the linear combination of unitaries (LCU) technique to compute the integral formula (12). To do so, we need an efficient implementation of the block-encoded operator $\\exp(\\mathcal{A}t)$, where $\\mathcal{A}$ is Hurwitz. Note that no explicit upper bound on the largest singular value of $\\mathcal{A}$ is known. Most existing quantum algorithms for this task (i.e., to compute $\\exp(\\mathcal{A}t)$) cannot be applied in our case, either because they have stronger assumptions on the matrix $\\mathcal{A}$ (Quantum Singular Value Transformation (QSVT) [1] and Linear Combination of Hamiltonian Simulations (LCHS) [2]) or because they have worse asymptotic scaling (Taylor series expansion leads to an exponentially small success rate, and the so-called time-marching strategy [3] has super-linear scaling in $t$ (more precisely, $t^2$). Instead, we employ some ideas from Quantum EigenValue Transformation (QEVT) [4], a recent breakthrough in quantum algorithms, to construct this block-encoded operator with favorable asymptotic scaling (linear in $t$ and polylogarithmic in $1/\\epsilon$). It is worth noting that our construction is not identical to the one in [4], as they do not have an explicit block-encoding form in the original paper.\n\nWe sincerely thank the reviewer for the detailed review. We plan to address the reviewer’s questions in the camera-ready version of this paper by further elaborating on our technical novelty and near-term feasibility. If the reviewer finds this additional information helpful, we kindly request consideration for an increased preliminary rating for this submission.\n\n[1] Gilyén et al. (2018). Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetic. [arXiv:1806.01838](https://arxiv.org/abs/1806.01838)\n\n[2] An et al. (2023). Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost. [arXiv:2303.01029](https://arxiv.org/abs/2303.01029)\n\n[3] Fang et al. (2022). Time-marching based quantum solvers for time-dependent linear differential equations. [arXiv:2208.06941](https://arxiv.org/abs/2208.06941)\n\n[4] Low and Su. (2024). Quantum eigenvalue processing. [arXiv:2401.06240](https://arxiv.org/abs/2401.06240)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KZ69Txlovw", "reviewer": "Reviewer_dSDS", "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.", "questions": "1. How does the proposed quantum algorithm handle cases where the sparsity assumptions on matrices A,B,Q,R do not hold?\n\n2. Can the authors provide detailed runtime performance comparisons between the proposed quantum algorithm and state-of-the-art classical algorithms?\n\n3. 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": "The primary limitation of the proposed method is its dependency on the availability of quantum resources and the sparsity assumptions for the matrices involved.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Quantum Speedup: The algorithm achieves a super-quadratic speedup over classical methods, which is a significant advancement in the field of quantum computing for control problems.\n\nInnovative Approach: It introduces a novel quantum-assisted differentiable simulator, enhancing the accuracy and robustness of gradient estimation.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer recognizing the super-quadratic speedup achieved in this paper as a significant advancement in quantum computing for control problems. \n\nRegarding the reviewer’s comment on the insufficient experiments as a main weakness of this paper, while the key contribution of this work is on the analytical formulation and theoretical advances, we conducted several experiments in the original submission. \n We perform another experiment on a practical problem that can be formulated as LQR, see Figure 1 in the uploaded PDF. 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 $\\theta$ (rad) and pitch rate $q$ (rad/s). The control input is elevator deflection angle $\\delta$ (rad). The state-space model can be represented as\n$\\dot{x} =Ax+Bu$, where $x = [\\theta, q]^T$, $u = [\\delta]$.\nWe set $A=[[0, 1], [0, -0.5]]^T$, $B=[0, 1]^T$, $Q=[[10, 0], [0, 1]]^T$, and $R=[0.1]$.\nThe plot of our optimization curve is available in the uploaded PDF (see Figure 1). Clearly, our method *converges faster than the classical method*.\n\n\nRegarding the question on the sparsity assumption, *the sparsity assumptions are standard* across quantum algorithms research and are *necessary to efficiently load classical data into quantum registers*. Since our primary objective of this work is to establish the theoretical advantage of the proposed quantum algorithm, the sparsity assumptions are reasonable and at par with other works in this field. In practice, even when the sparsity assumptions do not hold, it is still possible to extend our algorithmic design to other types of quantum input models that allow dense data (e.g., [1, 2]). We will add this information to justify our sparse matrix input model and leave the adaptation of other input models in future work. \n\n\nSince the proposed quantum algorithm utilizes advanced subroutines such as linear combination of unitaries (LCU), a detailed runtime analysis would require developing a customized compiler to estimate the gate count, which is clearly beyond the scope of the current paper. The **asymptotic analysis in the paper asserts a super-quadratic speedup against SOTA classical** algorithms, which paves the way toward a comprehensive resource analysis in future research. \n\n\nRegarding the comparison with other methods: to our best knowledge, this paper is the **first to prove the robust convergence to the LQR solution in the literature of quantum computation**. We achieve a linear convergence rate, which is comparable with the classical SOTA, while our quantum advantage comes from the fact that we can **solve the matrix Lyapunov equation exponentially faster than any classical means**. Since our algorithm uses analytical gradient estimation, it **demonstrates stability in the SGD iterations** and achieves **faster convergence compared to classical model-free methods**, as illustrated in our numerical experiments (see figure 2 in the main paper).\n\nWe sincerely thank the reviewer for the detailed review. We plan to address the reviewer’s questions in the camera-ready version by elaborating on the technical assumptions and adding a numerical experiment with a practical background. If the reviewer finds this additional information helpful, we kindly request consideration for an increased preliminary rating for this submission.\n\n[1] Wang and Wossnig (2018). A quantum algorithm for simulating non-sparse Hamiltonians. [arXiv:1803.08273](https://arxiv.org/abs/1803.08273)\n\n[2] Liu and Lin (2023). Dense outputs from quantum simulations. [arXiv:2307.14441](https://arxiv.org/abs/2307.14441)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LrC3eVsIKW", "reviewer": "Reviewer_7tHw", "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.", "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": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The quantum application to linear-quadratic problem seems new and provides a lot computation benefit.", "weaknesses": "This work only considers linear-quadratic control problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the novelty and computational advantage of the proposed quantum application.\n\nDue to the page limit, we only consider the classic LQR problem in this paper. Nevertheless, our approach can be readily generalized to other optimal control problems, such as distributed LQR and nonlinear control problems. We plan to investigate these applications in future work. \n\nWe conducted further numerical experiments to understand how the optimality scales with problem size, see Figure 2 in the uploaded PDF file. Here, we scale the number of masses $g$ 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 $f(K)$ error is $|f(K) - f(K^*)| / f(K^*)$ and relative $J$ error is $|J - J^*| / J^*$.\n\nThe results are reported in the following table. As the dimension scales up, the relative errors increase, while our method consistently outperforms the classical optimization method. The plot has been added to the uploaded PDF file (see Figure 2).\n\n\n| problem dimension      | 2g = 2          | 2g = 6          | 2g = 8          |\n|---------------|------------------|------------------|------------------|\n| relative fK classical | 0.01177443       | 0.01369893       | 0.01562343       |\n| relative fK quantum   | 3.08486486e-08   | 3.54893993e-08   | 4.01301499e-08   |\n| relative J classical  | 0.01636588       | 0.01905698       | 0.02174809       |\n| relative J quantum    | 1.13132601e-07   | 1.28453806e-07   | 1.43775011e-07   |\n\nWe sincerely thank the reviewer for the detailed review. We plan to address the reviewer’s questions in the camera-ready version by elaborating on the possible generalization of the proposed methodology and including the new numerical experiments. If the reviewer finds this additional information helpful, we kindly request consideration for an increased preliminary rating for this submission.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their invaluable comments on our submission. We are particularly grateful for the reviewers' recognition of the novelty of our paper as the *first end-to-end quantum application to optimal control* (Reviewers v7Mi, 7tHw), the acknowledgment of the *super-quadratic speedup* over classical methods as a significant advancement (Reviewer dSDS), and the overall *interest our work generates within the broader learning theory community* (Reviewer oizh).

In this message, we would like to address a few questions raised by the reviewers regarding the technical contributions, algorithm applicability, and numerical experiments. 

The proposed algorithm is truly **end-to-end**, with classical input and classical output, and achieves a **super-quadratic speedup** against SOTA classical methods for the LQR problem. Both aspects make it a significant result in quantum computing. Most existing quantum algorithms for classical optimization and control problems either return a quantum state as output, requiring an exponential overhead to convert to classically readable data, or only achieve a quadratic speedup by leveraging a Grover-type quantum algorithm. In contrast, our super-quadratic speedup comes from an exponentially faster quantum subroutine for solving the matrix Lyapunov equation. To the best of our knowledge, this matrix Lyapunov equation solver is a novel quantum algorithm and is of independent interest. As Reviewer oizh mentioned, this subroutine can be applied to other problems, such as stability analysis. The key technical difficulty behind this new quantum subroutine is that it requires efficiently computing the matrix exponential of a Hurwitz matrix, for which most existing quantum algorithms are not directly applicable. We employ ideas from a recent result known as Quantum EigenValue Transformation (QEVT) to resolve this difficulty. 

Since the primary goal of this paper is to investigate the theoretical advantage of the proposed quantum algorithm, we adopt the sparse-matrix input model, which is considered one of **the most standard input models for quantum algorithm design**. The hybrid quantum-classical nature of our algorithm limits the runtime of each quantum processing routine by interspersing classical routines, which is advantageous on near- and mid-term quantum devices with fewer qubits and shorter qubit coherence times. While estimating the actual gate count is beyond the scope of this paper, the hybrid quantum-classical approach makes our algorithm more feasible than many other algorithms without a classical component. 
Additionally, we add two more numerical experiments to show the scalability and practical relevance of our approach. We observe that (1) our method **converges faster** than classical methods in an **aircraft flight control** problem, and (2) our method **consistently outperforms classical methods** as the **problem dimension increases**. The figures are included in the uploaded PDF file. We will add these results in the camera-ready version of this submission. 

We appreciate the reviewers' informative feedback and look forward to further discussions on specific technical or conceptual questions. If this additional information proves helpful, we would be thankful if the reviewers could consider a higher preliminary rating for our submission.

Meta-review: 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.
Decision: Accept (poster)