Theory of Computing
-------------------
Title : Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources
Authors : Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick
Volume : 20
Number : 3
Pages : 1-87
URL : https://theoryofcomputing.org/articles/v020a003
Abstract
--------
The problem of reliably certifying the outcome of a computation
performed by a quantum device is rapidly gaining relevance. We present
two protocols for a classical verifier to verifiably delegate a
quantum computation to two non-communicating but entangled quantum
provers, with statistical soundness. Our protocols have near-optimal
complexity in terms of the total resources employed by the verifier
and the honest provers, with the total number of operations of each
party, including the number of entangled pairs of qubits required of
the honest provers, scaling as $O(g\log g)$ for delegating a circuit
of size $g$. This is in contrast to previous protocols, whose overhead
in terms of resources employed, while polynomial, is far beyond what
is feasible in practice. Our first protocol requires a number of
rounds that is linear in the depth of the circuit being delegated, and
is blind, meaning neither prover can learn the circuit or its input.
The second protocol is not blind, but requires only a constant number
of rounds of interaction.
Our main technical innovation is an efficient rigidity theorem that
allows a verifier to test that two entangled provers perform
measurements specified by an arbitrary $m$-qubit tensor product of
single-qubit Clifford observables on their respective halves of $m$
shared EPR pairs, with a robustness that is independent of $m$. Our
two-prover classical-verifier delegation protocols are obtained by
combining this rigidity theorem with a single-prover quantum-verifier
protocol for the verifiable delegation of a quantum computation,
introduced by Broadbent (Theory of Computing, 2018).
-------------------
A conference version of this paper appeared in the
Proceedings of the 48th Ann. Internat. Conf. on Theory
and Appl. of Cryptographic Techniques (EUROCRYPT 2019).