A Caltech Library Service

Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources

Coladangelo, Andrea and Grilo, Alex B. and Jeffery, Stacey and Vidick, Thomas (2019) Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources. In: Advances in Cryptology - EUROCRYPT 2019. Lecture Notes in Computer Science. No.11478. Springer , Cham, pp. 247-277. ISBN 978-3-030-17658-7.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper ReadCube access
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2019 International Association for Cryptologic Research. First Online: 24 April 2019. We thank Anne Broadbent for useful discussions in the early stages of this work. All authors acknowledge the IQIM, an NSF Physics Frontiers Center at the California Institute of Technology, where this research was initiated. AC is supported by AFOSR YIP award number FA9550-16-1-0495. AG is supported by ERC Consolidator Grant 615307-QPROGRESS and was previously supported by ERC QCC when AG was a member of IRIF (CNRS/Université Paris Diderot). SJ is supported by an NWO WISE Grant. TV is supported by NSF CAREER Grant CCF-1553477, MURI Grant FA9550-18-1-0161, AFOSR YIP award number FA9550-16-1-0495, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
European Research Council (ERC)615307
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Gordon and Betty Moore FoundationGBMF-12500028
Series Name:Lecture Notes in Computer Science
Issue or Number:11478
Record Number:CaltechAUTHORS:20190320-123759874
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93993
Deposited By: Tony Diaz
Deposited On:20 Mar 2019 19:45
Last Modified:16 Nov 2021 17:02

Repository Staff Only: item control page