Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
Abstract
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(poly(λ, log g)· 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)/√2 and (σY+σX)/√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.
Related
- Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
- Saving resources through repeat-until-success positive-operator-valued-measure measurements in quantum computation
- Modular optical fault-tolerant quantum computation via an interface between verified resources and online logical operations
- Total Ordering of Resources: A Quantum-Classical Separation
- Warm-Start Quantum Computation: Spectral-Weight Resources for Energy Readout and State Preparation
BibTeX
@misc{holler2026classical,
title = {{Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games}},
author = {Finn Holler and Anand Natarajan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38060},
eprint = {2609.38060},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38060},
}
RIS
TY - UNPB
TI - Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
AU - Finn Holler
AU - Anand Natarajan
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38060
UR - https://arxiv.org/abs/2609.38060
AB - 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(poly(λ, log g)· 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)/√2 and (σ_Y+σ_X)/√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.
ER -