{"id":"arxiv/2609.38060","url":"https://arxiv.org/abs/2609.38060","tags":["quant-ph","cs.CR"],"score":0,"title":"Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games","domain":"quant-ph","source":"arxiv","authors":["Finn Holler","Anand Natarajan"],"reviews":0,"subject":"quant-ph","summary":"Computational self-testing gives a classical verifier command over the quantum register of a single computationally bounded prover. We use this framework to construct the first argument system for BQP with quasilinear total resource requirements in the circuit model. Our argument system is based on the learning with errors (LWE) assumption and requires total resources of $O(\\mathrm{poly}(λ, \\log g)\\cdot g)$ for delegating a circuit with $g$ gates, where $λ$ is the LWE security parameter. This is achieved by constructing a new computational self-test for certifying the prover's quantum state…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}