aiqbench analysis
This research establishes a classical verification protocol for BQP computations using quasilinear resources, effectively delegating quantum circuit execution to a bounded prover while maintaining constant robustness against verification errors. By adapting nonlocal game compilers to single-prover settings under the LWE assumption, the work bridges theoretical cryptography with practical quantum delegation frameworks.
Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
arXiv:2609.38060v1 Announce Type: new 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}(\lambda, \log g)\cdot g)$ for delegating a circuit with $g$ gates, where $\lambda$ 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 $\sigma_X, \sigma_Y, \sigma_Z, (\sigma_Y-\sigma_X)/\sqrt{2}$ and $(\sigma_Y+\sigma_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.
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}(\lambda, \log g)\cdot g)$ for delegating a circuit with $g$ gates, where $\lambda$ 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 $\sigma_X, \sigma_Y, \sigma_Z, (\sigma_Y-\sigma_X)/\sqrt{2}$ and $(\sigma_Y+\sigma_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.
Quantum Physics (quant-ph); Cryptography and Security (cs.CR)
arXiv:2609.38060 [quant-ph]
(or arXiv:2609.38060v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2609.38060 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 287 words
