Differentiable Quantum Computing for Large-scale Linear Control

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.

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.

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?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

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.

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

Questions

1. How does the proposed quantum algorithm handle cases where the sparsity assumptions on matrices A,B,Q,R do not hold? 2. Can the authors provide detailed runtime performance comparisons between the proposed quantum algorithm and state-of-the-art classical algorithms? 3. Comparison with Other Methods: How does the proposed method's stability and convergence rate compare with other existing quantum and classical approaches for solving linear-quadratic control problems?

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

2

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.

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.

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. 2. This paper also provides numerical evidence to demonstrate the robustness and favorable convergence behavior of the method. 3. 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. 2. Although the paper claims a super-quadratic speedup, it's important to verify whether this speedup is practically achievable. Especially in large-scale industrial models, the real-world complexity and scalability of the algorithm are critical issues. 3. This paper is not always well written. For example, in Line 520, "The evolution of a quantum state can always described by a unitary operator".

Questions

1. How does the proposed quantum algorithm account for the current limitations of quantum hardware, such as noise and the limited number of qubits? 2. The paper introduces a novel quantum subroutine for solving the matrix Lyapunov equation. Could you elaborate on the specific technical innovations that this subroutine brings compared to existing quantum algorithms? What are the key theoretical breakthroughs that enable the claimed super-quadratic speedup?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitations of this work have been adequately discussed.

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.

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. Besides, I do not understand why the application of the proposed quantum approach is limited to the classic LQR problem. If the real contribution is the first quantum approach to solve the Lyapunov equation (11) efficiently, I think the proposed method can be applied to other important problems like stability analysis. I hope the authors can clarify the most general statement of the main contribution or what limits the application to LQR.

Questions

Besides my comments in the weakness part, I also hope the authors can clarify if the proposed method is robust to estimation errors in A and B if we estimate them from samples (see [Dean, Sarah, et al., 2020]). [Dean, Sarah, et al., 2020] Dean, Sarah, et al. "On the sample complexity of the linear quadratic regulator." Foundations of Computational Mathematics 20.4 (2020): 633-679.

Rating

5

Confidence

2

Soundness

2

Presentation

3

Contribution

3

Limitations

I do not see any potential negative societal impact of this work.

Thank you for the responses.

The author's response has somewhat addressed my concerns and questions. I will increase my score accordingly.