Abstract
Reinforcement learning (RL) relies heavily on policy iteration, where the evaluation step requires solving large linear systems of equations (LSE). As state spaces grow, these systems become computationally prohibitive for classical solvers. This paper presents VarQPI, a variational quantum algorithm that leverages Noisy Intermediate-Scale Quantum (NISQ) devices to perform policy evaluation. A key contribution is the "warm-start" technique (WS-VarQPI), which reuses optimized circuit parameters from previous iterations to accelerate convergence. Experimental results on the FrozenLake environment demonstrate that WS-VarQPI reduces training steps by approximately 30% and successfully scales to 256-dimensional problems using minimal qubits.
Introduction
The core bottleneck in reinforcement learning is policy evaluation, which involves determining the value of state-action pairs by solving a massive LSE. While classical iterative methods provide approximations, they struggle with high-dimensional environments. Quantum algorithms like HHL offer theoretical exponential speedups but require fault-tolerant hardware far beyond current capabilities. VarQPI addresses this by utilizing variational quantum linear solvers (VQLS) suitable for the current NISQ era.
Methodology
VarQPI replaces the classical LSE solver with a parameterized quantum circuit (ansatz) to prepare a state representing the solution to the Bellman equations. The algorithm alternates between quantum evaluation and classical improvement using efficient $\ell_\infty$-tomography to extract optimal actions.
The primary innovation, Warm-Start VarQPI (WS-VarQPI), exploits the incremental nature of policy iteration. Since the policy typically changes only slightly between steps, the solution to the LSE in one iteration serves as an excellent starting point for the next. By "warm-starting" the quantum circuit with parameters from the previous step, the authors significantly accelerate convergence.
Experimental Results
The algorithm was benchmarked on the FrozenLake grid-world environment, scaling from $4 \times 4$ (64-dimensional LSE) to $8 \times 8$ (256-dimensional LSE) grids.
Quantum-Friendly Environments
A crucial insight of this work is that RL environments naturally produce sparse and well-conditioned matrices. These properties are essential for quantum linear solvers to provide a practical advantage, suggesting that RL is an ideal application for quantum computing.
The Warm-Start Advantage
WS-VarQPI achieved a 30% reduction in training steps compared to random initialization. As shown in the loss curves below, warm-starting significantly lowers the initial loss in subsequent iterations, allowing the solver to reach target accuracy much faster.
Practical Precision and Scalability
The researchers found that the theoretical precision required for these solvers is much lower in practice than mathematical bounds suggest. Error thresholds could be set several orders of magnitude higher while still finding the optimal policy, drastically reducing training time. Furthermore, empirical results suggest that the condition number of the LSE grows only logarithmically with the state space size, supporting long-term scalability.
Conclusion and Future Work
VarQPI demonstrates the feasibility of quantum-enhanced RL on near-term devices. However, challenges remain, including the classical bottleneck of unitary decomposition (SVD) and the potential impact of real-world hardware noise. Future research will explore extending this approach to model-free RL scenarios where environment dynamics are unknown.
Summary updated