Classical methods control quantum computations with near linear effort
Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
Cryptography and Security
Summary
Verifying quantum computations using classical computers is challenging because quantum processes are complex and hard to check. The authors show a new method that lets a classical computer verify the result of a quantum computation efficiently, using resources that grow almost linearly with the size of the quantum task. They build on existing tests that check quantum states and adapt multi-prover techniques into a single-prover system, making it more practical. This approach relies on a well-known cryptographic assumption to ensure security and accuracy.
What this means in practice
- •For quantum computing engineers: Design efficient protocols to verify quantum computations with minimal classical resources for delegation scenarios.
- •For cryptography software developers: Implement secure classical verification methods for quantum cryptographic protocols based on the LWE assumption.
Authors
Finn Holler, Anand Natarajan
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(\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.