Anand Natarajan

Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games

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 er...