Towards Surrogate Based Dequantization of Quantum Reinforcement Learning
Pablo Rodriguez-Grasa, Sofiene Jerbi, Mikel Sanz, Ryan Sweke
quant-ph · cs.LG
Quick verdict
First dequantization guarantees for quantum Q-learning via kernel FQI under uniform sampling; rigorous but strongly conditioned, no experiments.
Summary
This theory paper extends surrogate-based dequantization from supervised quantum machine learning to reinforcement learning, targeting quantum Q-learning, where parameterized quantum circuits (PQCs) approximate the action-value function. The authors study a simplified setting with a uniform generative model providing uniformly random state-action samples — motivated as sampling from a large experience replay buffer after sufficient exploration. They propose classical Fitted Q-Iteration (FQI) with kernel ridge regression using PQC-inspired kernels whose RKHS contains all PQC-expressible functions, and prove finite-sample guarantees (Theorem 7.8): with m = Õ(poly(d_S, |A|, 1/ε, 1/δ)) samples and K = O(log(1/ε)) iterations, the greedy policy is ε-optimal, under conditions including Bellman closure of the RKHS, bounded transition density (polynomial p_max), polynomial decay of kernel weights, efficient kernel evaluation via symmetric matrix product states, and polynomially bounded RKHS norm of all encountered Bellman targets (G_K). These yield relative-to-best dequantization — the classical solution is within ε of the best PQC policy — ruling out exponential quantum advantage in this setting. Main limitations: the uniform-sampling setting and the Bellman-closure assumption are restrictive; the alignment condition on Bellman targets is unverifiable a priori and strictly stronger than in supervised dequantization; policies are evaluated under a uniform state-action loss rather than return; and no experiments support the proposed heuristic use of the algorithm.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Kernelized Fitted Q-Iteration with PQC-inspired kernels admits finite-sample guarantees: m = Õ(poly(d_S, |A|, 1/ε, 1/δ)) samples and K = O(log(1/ε)) iterations suffice for an ε-optimal policy (Theorem 7.8).
- Under the stated sufficient conditions, Algorithm 1 is a relative-to-best dequantization of quantum Q-learning in the uniform generative model setting, ruling out exponential quantum advantage there.
- The sufficient conditions are: Bellman target realizability/closure, bounded transition density, polynomial decay of kernel weights, efficient kernel evaluation via polynomial-bond-dimension symmetric matrix product states, and polynomial RKHS norm of all encountered Bellman targets.
- The alignment requirement is strictly stronger than in supervised dequantization because it must hold uniformly over the whole FQI trajectory of Bellman iterates, not just one fixed target (Remark 8.2).
Strengths
First rigorous dequantization treatment of quantum Q-learning
Section 1 notes no prior work addressed whether quantum Q-learning can be dequantized; Theorem 7.8 delivers finite-sample guarantees for kernelized FQI with PQC kernels, stated by the authors as potentially of independent interest.
Transparent assumption architecture
Section 7.1 gives every assumption paired Justification and Role paragraphs; Remark 7.7 explicitly states they are sufficient, not necessary; Appendix H sketches relaxing Assumption 7.1 at the cost of an extra approximation error.
Honest scope and tension analysis
Model class grounded in prior quantum Q-learning practice
Detailed, checkable proof chain
Weaknesses
Bellman closure effectively presupposes classical learnability
Narrow and idealized setting
Alignment condition unverifiable a priori
No empirical validation
Polynomiality is parameter-sensitive
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper (arXiv:2609.16266) asks whether quantum Q-learning — where a parameterized quantum circuit (PQC) replaces the DQN network as the Q-function approximator (Section 3.1.3) — can be dequantized: matched by an efficient classical algorithm. The authors extend the surrogate-based program of Refs [7-10] from supervised learning to RL. They deliberately narrow the setting to RL with a uniform generative model (Assumption 5.1): i.i.d. uniformly random state-action pairs, motivated as sampling a large experience replay buffer after sufficient exploration. The central deliverables are (i) finite-sample guarantees for classical Fitted Q-Iteration (FQI) with kernel ridge regression using PQC-inspired kernels (Theorem 7.8), and (ii) a list of sufficient conditions under which this yields relative-to-best dequantization (Section 8): the classical policy is ε-close, under the uniform loss of Definition 3.1, to the best policy achievable by the PQC class — ruling out exponential quantum advantage in this setting. Claims are carefully scoped ("towards", "simplified setting"), with a clean reduction from Question 6.2 (PAC learning of the RKHS optimum) to Question 6.1 (dequantization).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does 'dequantization' of a quantum algorithm mean in this paper?
It means constructing a purely classical algorithm that provably matches the performance of the quantum algorithm with at most polynomial overhead in time and samples. Here, classical kernel-based Fitted Q-Iteration is shown — under explicit conditions — to match the best policy achievable by quantum Q-learning that uses a parameterized quantum circuit as its Q-function approximator.
Does this paper prove quantum reinforcement learning has no advantage?
No. Results hold only in a simplified setting where the learner receives uniformly random state-action samples (an idealized replay buffer) and under restrictive conditions, such as the kernel's Hilbert space being closed under the Bellman operator and polynomial decay of kernel weights. Outside these conditions the paper makes no claims, and the authors note quantum Q-learning may still succeed as a heuristic.
Is there code or experimental data for this paper?
No. The paper is purely theoretical: it specifies Algorithm 1 (kernelized Fitted Q-Iteration with PQC-inspired kernels) and proves sample and time complexity bounds, but reports no experiments and releases no code. Because the algorithm is fully specified, third parties could run small-scale numerical comparisons against quantum Q-learning simulators.
What is the main theorem (Theorem 7.8) in plain terms?
If Bellman targets stay inside the kernel's Hilbert space, transition densities are bounded, kernel weights decay polynomially, the kernel can be evaluated efficiently (e.g., via matrix product states), and the targets remain aligned with the kernel spectrum, then a polynomial number of samples and O(log(1/ε)) iterations suffice for the classical algorithm to output — with high probability — a policy that is ε-optimal.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Extracted text has omitted sections (parts of Sections 2.2, 5.1-5.4, the end of Section 8, and portions of Appendices C, E, F, H); judgments rely on the available text.
- Figures 1-2 render as base64 LaTeX blobs; their content is inferred from captions only.
- Observation C.1 (sub-Gaussian noise definition) and the statements of Lemmas C.2-C.3 lie partially outside the extracted text, so those lemmas could not be proof-level verified.
- Appendix H (relaxation of Assumption 7.1) is not available in the extraction; the relaxation claim is taken from the main-text discussion.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.