Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
Researchers give a classical verifier a quasilinear-cost argument system for BQP under LWE.
The paper constructs the first circuit-model argument system for BQP with total resources O(poly(λ, log g)·g) for a g-gate circuit, under learning with errors. A new computational self-test certifies a single bounded prover's quantum state and dequantizes Broadbent's 2018 verification protocol. It enables verifiable remote preparation of tensor-product single-qubit Clifford observable states with constant robustness. The single-prover result applies the Kalai et al. STOC 2023 compiler to a modified Coladangelo et al. multi-prover self-test.
- First quasilinear-resource classical argument system for BQP circuits.
- Security rests on the learning-with-errors assumption.
- Remote state preparation has robustness independent of qubit count.
- Single-prover result uses the Kalai et al. nonlocal-game compiler.
Full article189 words · extracted from arxiv.org · click to collapse
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 and using it to dequantize the efficient verification protocol of Broadbent (ToC 2018). Specifically, this self-test enables the verifiable, random remote state preparation of tensor product states of the single-qubit Clifford observables $σ_X, σ_Y, σ_Z, (σ_Y-σ_X)/\sqrt{2}$ and $(σ_Y+σ_X)/\sqrt{2}$, with constant robustness: the verification error is independent of the number of prepared qubits. This approach was first proposed by Coladangelo et al. (ToC 2024) in the multi-prover setting. We replicate their result in the single-prover setting by applying the compiler proposed by Kalai et al. (STOC 2023)---which turns any nonlocal game into a single-prover argument system---to a modified version of their self-test.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.38060