Polynomial-time classical simulation of variational quantum kernels with bounded entanglement
- Elena Marchettia(corresponding)
- Daniel Friedrichb
- Priya Iyerc
- aICFO — The Institute of Photonic Sciences, Castelldefels, Spain
- bDepartment of Physics, ETH Zürich, Switzerland
- cIBM Research — Zürich, Rüschlikon, Switzerland
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.
Full abstract continues on the paper page.