Preprint · v2cs.LG quant-phpeer-reviewed · accepted

Polynomial-time classical simulation of variational quantum kernels with bounded entanglement

  1. Elena MarchettiaORCID(corresponding)
  2. Daniel FriedrichbORCID
  3. Priya IyercORCID
  1. aICFO — The Institute of Photonic Sciences, Castelldefels, Spain
  2. bDepartment of Physics, ETH Zürich, Switzerland
  3. cIBM Research — Zürich, Rüschlikon, Switzerland
DOI
10.12345/tauhub.2026.0001
Permalink
tauhub.com/p/tauhub.2026.0001
Submitted
2 Apr 2026
Published
9 Apr 2026
Accepted
21 Apr 2026
Licence
CC-BY-4.0 (paper) · MIT (code) · CC0 (data)

Abstract

Variational quantum kernels (VQKs) have been proposed as a route to quantum advantage in supervised learning, but the conditions under which they offer a genuine separation from classical methods remain unsettled. We give a polynomial-time classical algorithm that approximately simulates a broad family of VQKs whose feature maps generate states of entanglement entropy bounded by O(log n). Our construction combines a tensor-network contraction scheme with a sampling oracle reminiscent of recent dequantization results for low-rank linear algebra.

On the experimental side, we benchmark our simulator against published VQK implementations on three standard datasets (Iris, MNIST-4, and a synthetic two-spiral problem). The classically-simulated kernel matches the reported quantum-hardware accuracy within experimental error on all three, suggesting that observed performance in those settings is not attributable to quantum advantage. We do not rule out advantage in regimes where the entanglement bound is violated; characterising that boundary is left to future work.

All code, datasets, and the full set of simulator artefacts (including intermediate tensor decompositions) are openly available under CC-BY-4.0 and MIT, respectively.

1. Introduction (excerpt)

The promise of variational quantum kernels rests on a hopeful pair of claims. First, that a sufficiently expressive quantum feature map can encode classical data in a Hilbert-space geometry that no polynomial-time classical algorithm can reproduce. Second, that the kernel matrix induced by inner products in that Hilbert space carries useful classification structure for problems of practical interest. Neither claim is settled, but the second has tended to receive most of the experimental attention while the first is assumed and not tested.

In this paper we attack the first claim head-on, in the restricted but practically common regime of feature maps whose intermediate states never depart from the area-law manifold. We show that for entanglement entropy growing no faster than O(log n) — a constraint satisfied by every published hardware-realisable VQK we are aware of — there is a tensor-network simulator that reproduces inner products up to additive error ε in time polynomial in n, 1/ε, and the bond dimension implied by the entanglement bound.

Full body, methods, results, and references in the canonical PDF — attached on the right column of the production paper page (not built out in this preview).

Key contributions

Open peer review · 2 signed

Signed · recommended: accept with minor revisions

Sara Lindqvist, KTH Royal Institute of Technology, Stockholm, Sweden

ORCID 0000-0002-7711-2890 · submitted 14 Apr 2026

Summary
A clean and important negative result. The authors provide a polynomial-time classical simulator that reproduces a broad family of VQK feature maps under a stated entanglement bound, and they back it up with side-by-side empirical replication on three standard benchmarks. The work is careful about what it does *not* claim (it does not foreclose quantum advantage outside the area-law manifold), and the writing reflects that.
Strengths
  • The entanglement-bounded regime is the regime where most published hardware VQKs actually live. The result has real bite.
  • The empirical section is reproducible: the simulator, datasets, and full intermediate artefacts are all open under permissive licences.
  • The discussion of limitations is unusually honest for the subfield. The authors are explicit that their result is a sufficient condition for classical simulability, not a necessary one.
Weaknesses
  • Theorem 3.2 assumes O(log n) entanglement entropy uniformly across the feature map. Real hardware experiments may transiently exceed this during state preparation even when the final state respects the bound. A short discussion of whether the simulator survives mid-circuit excursions would strengthen the paper.
  • The MNIST-4 benchmark uses a four-class subset of MNIST which is not the standard MNIST. The reported accuracies should be compared against a fair classical baseline on the same four-class subset, not against the published 10-class MNIST numbers.
Claims vs. evidence
The theoretical claim (Theorem 3.2) is supported by a clear constructive proof; I checked the bond-dimension accounting in §3.4 carefully and it is correct. The empirical claim is supported within the stated benchmarks but should be hedged to those benchmarks until a broader sweep is done.
Recommendation
Accept with minor revisions. The required changes are limited to (a) clarifying the entanglement assumption's robustness to mid-circuit excursions and (b) reporting the fair four-class MNIST baseline. Both are small and the authors clearly have the data to do them.

Signed · pseudonymous · recommended: accept

Reviewer δ-1

ORCID 0000-0001-5302-8214 · submitted 16 Apr 2026

Summary
This paper sits in a tradition of dequantization results (Tang 2019 et seq.) and extends that line to variational kernel methods. The contribution is incremental in technique — the tensor-network-plus-sampling combination is by now a standard hammer — but new and useful in scope. Acceptance is the right call.
Strengths
  • The choice to release intermediate tensor decompositions, not just final code, is exactly the right level of openness for this kind of result. Anyone wanting to attack the proof has the artefacts to do it with.
  • Theorem 3.2 is stated in a way that makes the boundary of the simulability claim immediately obvious. That clarity is what makes the result useful to the broader community.
Weaknesses
  • The paper does not discuss noise. Real hardware VQK runs are noisy, and the entanglement entropy of a noisy state can be quite different from that of the ideal state the circuit is designed to produce. The paper's result applies to the ideal state. The practical question of whether noisy hardware ever escapes the simulability boundary deserves at least a paragraph.
Claims vs. evidence
Theoretical claims supported. Empirical claims supported within the three benchmarks tested. I would not extrapolate beyond that without further evidence.
Recommendation
Accept. The minor revisions suggested by R1 are reasonable; I would not require the noise discussion as a condition for acceptance but I would encourage the authors to add it.

Author response (excerpt)

We thank both reviewers for their careful and constructive evaluation. We agree with both points raised by R1 and have added (i) §3.5 discussing the robustness of Theorem 3.2 to mid-circuit excursions and (ii) Table 4 reporting the four-class MNIST baseline. On R2's noise point: we have added a new §6.2 making explicit that our result is an ideal-state result and outlining the (open) question of how robust the simulability boundary is under realistic noise channels.

Community discussion · 14 threads · 47 comments

“The four-class MNIST baseline now in Table 4 (post-revision) is the one I was looking for. With that result the headline message is unambiguous: under the stated entanglement bound, the published VQK numbers on this benchmark are explained by the classical simulator, not by the quantum hardware. Useful and important.”

— Tomás Reyes, Universidade de Lisboa

Full threaded discussion not built out in this preview — see the project plan §7.3.

Funding, code, and data

This is a fictional exemplar paper used as a UX preview. Do not cite. See the landing page for context.