⚛️ quantum physics

Towards Surrogate Based Dequantization of Quantum Reinforcement Learning

This paper extends surrogate-based dequantization to reinforcement learning by establishing finite sample guarantees for classical kernelized Fitted Q-Iteration that match the performance of quantum Q-learning under specific conditions regarding data encoding, kernel design, and problem structure.

Original authors: Pablo Rodriguez-Grasa, Sofiene Jerbi, Mikel Sanz, Ryan Sweke

Published 2026-09-16

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Pablo Rodriguez-Grasa, Sofiene Jerbi, Mikel Sanz, Ryan Sweke

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the rapidly evolving world of computing, two powerful fields have recently begun to collide: the science of learning from experience and the physics of quantum mechanics. For decades, researchers have dreamed of using quantum computers to solve problems that are too difficult for traditional machines, particularly in the realm of artificial intelligence. One specific area of interest is reinforcement learning, a method where an agent learns to make decisions by interacting with an environment, receiving rewards for good choices and penalties for bad ones. To handle complex tasks, modern versions of this learning often use mathematical models called parameterized quantum circuits. These are like intricate, adjustable circuits built from quantum bits that can process information in ways classical computers cannot. The hope has been that these quantum models could learn faster or better than any classical method, offering a massive speed advantage. However, a critical question has remained unanswered: is this advantage real, or is it an illusion that a clever classical computer could simply replicate?

A team of researchers has now taken a significant step toward answering this question by developing a new way to test whether quantum learning methods can truly outperform classical ones. Instead of trying to simulate the quantum machine directly, which is often impossible for large systems, they built a classical "surrogate" model. Think of this surrogate as a stand-in that mimics the behavior of the quantum circuit using standard mathematics, specifically a technique known as kernel ridge regression. This method allows the classical computer to operate within a specific mathematical space that captures the same structural biases as the quantum model, effectively asking, "If we build a classical machine that thinks exactly like the quantum one, can it do just as well?"

The researchers focused on a simplified but realistic scenario where the learning agent has access to a vast library of past experiences, allowing it to sample data uniformly from all possible situations. In this setting, they proved that under specific, well-defined conditions, their classical surrogate can match the performance of the quantum algorithm with high probability. They demonstrated that if the mathematical structure of the problem aligns correctly with the learning method, and if the data is processed efficiently, the classical approach requires only a reasonable amount of time and data to reach the same level of skill as the quantum version. This finding effectively rules out the possibility of an exponential speed advantage for quantum reinforcement learning in this specific context, suggesting that the quantum machine offers no magical shortcut when the problem is well-structured.

The study did not claim that quantum computers are useless for learning, but rather clarified the boundaries of their power. The researchers identified three key conditions that must be met for this classical mimicry to work. First, the mathematical weights used in the model must decrease in a predictable, polynomial pattern, ensuring the problem isn't too complex to solve. Second, the way the data is encoded into the model must allow for efficient calculation, a feat the team showed is possible using a specific mathematical structure known as a tensor network. Third, and perhaps most importantly, the learning targets must align well with the model's inherent biases; if the problem's solution fits naturally within the model's structure, the classical method succeeds. When these conditions are met, the classical algorithm can produce a policy that is nearly as good as the best possible quantum solution, using resources that grow polynomially rather than exponentially.

This work provides a rigorous framework for understanding when quantum advantages might exist and when they do not. By establishing that a classical algorithm can provably match the performance of a quantum one under these conditions, the researchers have narrowed the search for genuine quantum speedups. They have shown that for many practical reinforcement learning problems, the promise of quantum acceleration may be limited to specific, unstructured cases or may require conditions that are difficult to verify in advance. The study also offers a practical tool: the classical algorithm they developed can serve as a powerful heuristic for solving reinforcement learning problems even when the strict theoretical conditions are not fully met. In essence, the researchers have mapped out the terrain, showing that while quantum computers may still hold secrets, the path to a universal advantage in learning is far more constrained than previously hoped, and classical methods, guided by the right mathematical insights, can often walk that path just as effectively.

Technical Summary: Towards Surrogate Based Dequantization of Quantum Reinforcement Learning

Problem Statement

The paper addresses the open question of whether variational quantum algorithms (VQAs) for reinforcement learning (RL), specifically Quantum Q-learning, can provide a provable exponential advantage over classical approaches for problems of practical relevance. While Quantum Q-learning replaces the classical neural network in Deep Q-learning with a Parameterized Quantum Circuit (PQC) as a function approximator, its theoretical foundations remain largely unexplored. The authors aim to determine if such quantum approaches can be "dequantized"—that is, matched in performance by efficient classical algorithms with only polynomial overhead.

To provide rigorous insights, the authors focus on a simplified setting: Reinforcement Learning with a Uniform Generative Model. In this regime, the agent has access to uniformly random state-action samples, modeling the scenario of sampling from a large experience replay buffer after sufficient exploration. This assumption isolates the statistical components of the analysis, treating the problem as a sequence of supervised regression tasks.

Methodology

The authors employ a surrogate-based dequantization approach. Rather than simulating the quantum circuit directly (simulation-based dequantization), they identify a classical model class that shares the same inductive bias as the PQC model.

PQC Structural Analysis:
- The paper analyzes PQC models used in Quantum Q-learning, defined as $f_\theta(s, a) = \langle 0|U^\dagger(s, \theta)V^\dagger(a)OV(a)U(s, \theta)|0\rangle$ .
- Under specific Hamiltonian data-encoding strategies, these models are shown to be linear models with respect to a feature map $\phi_\mathcal{D}$ defined by the data-encoding strategy.
- Consequently, the set of functions expressible by the PQC lies within a Reproducing Kernel Hilbert Space (RKHS) associated with a specific kernel derived from the PQC structure (a "PQC-inspired kernel").
The Dequantization Algorithm:
- The proposed classical algorithm replaces the stochastic gradient descent optimization of the PQC with Kernel Ridge Regression (KRR) within the identified PQC-RKHS.
- The algorithm utilizes Fitted Q-Iteration (FQI). In each iteration, it samples i.i.d. state-action pairs, computes Bellman targets ( $y_i = r_i + \gamma \max_a \hat{Q}_k(s'_i, a)$ ), and solves a regularized regression problem using the PQC-inspired kernel $K(\mathcal{D}, w)$ .
- A reweighting vector $w$ is chosen to define the specific kernel $K(\mathcal{D}, w)$ , ensuring the RKHS contains all functions expressible by the PQC.
Efficiency Mechanisms:
- To ensure the kernel evaluation is computationally tractable (avoiding the exponential dimension of the feature space), the authors assume the weight vector $w$ is induced from a symmetric Matrix Product State (MPS) with polynomial bond dimension. This allows the kernel to be evaluated exactly and efficiently via tensor network contractions.

Key Contributions

Surrogate-Based Dequantization for RL: This work extends the surrogate-based dequantization program, previously established for supervised learning, to the domain of reinforcement learning.
Finite Sample Guarantees: The authors provide rigorous finite sample guarantees for Kernelized Fitted Q-Iteration (FQI) using PQC-inspired kernels. They establish conditions under which this classical algorithm outputs a policy $\epsilon$ -close to the optimal policy achievable within the PQC model class.
Sufficient Conditions for Dequantization: The paper identifies a set of explicit, interpretable sufficient conditions under which Quantum Q-learning can be efficiently dequantized in the uniform sampling setting. These conditions include:
- Polynomial Eigenvalue Decay: The weights defining the kernel must decay polynomially (Assumption 7.5).
- Efficient Kernel Evaluation: The weights must be induced from a symmetric MPS with polynomial bond dimension to allow efficient tensor network evaluation.
- Alignment: The Bellman targets encountered during learning must be well-aligned with the kernel's inductive bias (specifically, the RKHS norm of the Bellman targets must be polynomially bounded).
- Problem Structure: The data-encoding strategy must satisfy bounds on the number of encoding Hamiltonians and their eigenvalues, and the transition density must be bounded relative to the uniform distribution.

Results

Under the stated assumptions (uniform sampling, polynomial decay of weights, efficient kernel evaluation, and alignment of Bellman targets), the authors prove that Algorithm 1 (FQI with PQC-inspired KRR) is an efficient PAC (Probably Approximately Correct) learner.

Sample Complexity: The number of samples $m$ required to achieve an $\epsilon$ -optimal policy with probability $1-\delta$ scales polynomially with the problem size ( $d_\mathcal{S}, |\mathcal{A}|$ ), the inverse accuracy ( $1/\epsilon$ ), and the inverse confidence ( $1/\delta$ ).
Time Complexity: The algorithm runs in polynomial time per iteration, provided the kernel is evaluated via tensor network contractions.
Dequantization Guarantee: Consequently, whenever these conditions are met, the classical algorithm outputs a policy that is $\epsilon$ -close to the best possible policy achievable by the Quantum Q-learning algorithm. This implies that no exponential quantum advantage is possible via Quantum Q-learning in this simplified setting under these conditions.

Significance and Claims

The paper claims that its results provide rigorous dequantization guarantees for Quantum Q-learning in the simplified uniform sampling regime. By establishing that classical kernel methods can match the performance of PQC-based quantum algorithms under specific structural conditions, the work sharpens the understanding of where quantum speedups are and are not possible.

The authors emphasize that while the analysis is conducted in a simplified setting (uniform generative model), the results serve two purposes:

They rule out exponential advantages for Quantum Q-learning in this specific regime when the identified sufficient conditions are met.
They motivate the use of kernelized Fitted Q-Iteration as a practical dequantization heuristic in standard settings, even when the strict sufficient conditions cannot be verified.

The work acknowledges that the alignment condition (Condition 5 in Theorem 7.8) is problem-dependent and difficult to verify a priori, noting that in practice, heuristics would be required to choose the reweighting vector $w$ . The paper does not claim to solve the general dequantization problem for all RL settings or all PQC architectures, but rather provides a foundational theoretical step and a set of conditions for a specific, simplified, yet analytically tractable regime.