Differentiable Quantum Computing for Large-scale Linear Control

We thank the reviewer for recognizing the novelty and computational advantage of the proposed quantum application.

Due 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.

We 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^*$.

The 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).

We 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.

We appreciate the reviewer recognizing the super-quadratic speedup achieved in this paper as a significant advancement in quantum computing for control problems.

Regarding 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. 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 $\dot{x} =Ax+Bu$, where $x = [\theta, q]^T$, $u = [\delta]$. We set $A=[[0, 1], [0, -0.5]]^T$, $B=[0, 1]^T$, $Q=[[10, 0], [0, 1]]^T$, and $R=[0.1]$. The plot of our optimization curve is available in the uploaded PDF (see Figure 1). Clearly, our method converges faster than the classical method.

Regarding 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.

Since 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.

Regarding 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).

We 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.

[1] Wang and Wossnig (2018). A quantum algorithm for simulating non-sparse Hamiltonians. arXiv:1803.08273

[2] Liu and Lin (2023). Dense outputs from quantum simulations. arXiv:2307.14441

We appreciate the reviewer recognizing our work as the first end-to-end quantum application to linear control problems with a provable quantum advantage.

One 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:

1. 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.
2. 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.
3. 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.

The 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.

We 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.

[1] Gilyén et al. (2018). Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetic. arXiv:1806.01838

[2] An et al. (2023). Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost. arXiv:2303.01029

[3] Fang et al. (2022). Time-marching based quantum solvers for time-dependent linear differential equations. arXiv:2208.06941

[4] Low and Su. (2024). Quantum eigenvalue processing. arXiv:2401.06240

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.

In 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.

We 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),

$X^* = \int^\infty_0 e^{\mathcal{A}t} \Omega e^{\mathcal{A}^T t},$

which 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.

Regarding 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.

We 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.