Towards Surrogate Based Dequantization of Quantum Reinforcement Learning
quant-ph, cs.LG
Submitted: 2026-09-14
Updated: 2026-09-14
License: http://creativecommons.org/licenses/by/4.0/
The gist: In recent years, the utility of parameterized quantum circuits as function approximators has been widely studied.
Terminology
Abstract
In recent years, the utility of parameterized quantum circuits as function approximators has been widely studied. In the context of reinforcement learning, this approach has led to variational quantum algorithms such as quantum Q-learning. While these methods show promising empirical results, and can provide provable advantages for artificial problems, it remains unclear whether they can provide a provable quantum advantage over classical approaches for problems of practical relevance. A natural way to investigate this question is through the lens of dequantization: The construction of efficient classical algorithms capable of matching the performance of quantum variational methods. Building on recent kernel-based dequantization results for supervised learning, we take steps towards extending this surrogate-based dequantization program to reinforcement learning. Specifically, we study the simplified setting of reinforcement learning with a uniform generative model in which uniformly random state-action samples are available, which models the regime of sampling from a large experience replay buffer after sufficient exploration. Within this setting, we provide finite sample guarantees for classical kernelized Fitted Q-Iteration, with classical kernels designed to match the inductive bias of particular parameterized quantum circuits. Using these results, we then provide a set of sufficient conditions, on the data-encoding strategy of a parameterized quantum circuit, the corresponding classical kernel, and the problem structure, under which kernelized Fitted Q-Iteration provides a meaningful dequantization of quantum Q-learning, in this simplified setting. Apart from providing rigorous dequantization guarantees when these conditions are met, these results also motivate the use of kernelized fitted Q-iteration as a dequantization heuristic when these sufficient conditions cannot be verified.
Sources
- Classically Approximating Variational Quantum Machine Learning with Random Fourier Features
- On Dequantization of Supervised Quantum Machine Learning via Random Fourier Features
- The Born Ultimatum: Conditions for Classical Surrogation of Quantum Generative Models with Correlators
- Prospects for quantum advantage in machine learning from the representability of functions
- Efficient 2D Tensor Network Simulation of Quantum Systems
- Differentiable matrix product states for simulating variational quantum computational chemistry
- Quantum circuit simulation with a local time-dependent variational principle
- Tensor network surrogate models for variational quantum computation
- Classical simulations of noisy variational quantum circuits
- Efficient quantum-enhanced classical simulation for patches of quantum landscapes
- Classically estimating observables of noiseless quantum circuits
- Simulating quantum circuits with arbitrary local noise using Pauli Propagation
- Pauli Propagation: A Computational Framework for Simulating Quantum Systems
- Framework for learning agents in quantum environments
- A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
- Quantum deep Q learning with distributed prioritized experience replay
- A quantum-classical reinforcement learning model to play Atari games
- A Survey on Quantum Reinforcement Learning
- Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model
- Constrained and Vanishing Expressivity of Quantum Fourier Models
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity