A Caltech Library Service

Verifying quantum computations at scale: A cryptographic leash on quantum devices

Vidick, Thomas (2020) Verifying quantum computations at scale: A cryptographic leash on quantum devices. Bulletin of the American Mathematical Society, 57 (1). pp. 39-76. ISSN 0273-0979. doi:10.1090/bull/1678.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Rapid technological advances point to a near future where engineered devices based on the laws of quantum mechanics are able to implement computations that can no longer be emulated on a classical computer. Once that stage is reached, will it be possible to verify the results of the quantum device? Recently, Mahadev introduced a solution to the following problem: Is it possible to delegate a quantum computation to a quantum device in a way that the final outcome of the computation can be verified on a classical computer, given that the device may be faulty or adversarial and given only the ability to generate classical instructions and obtain classical readout information in return? Mahadev's solution combines the framework of interactive proof systems from complexity theory with an ingenious use of classical cryptographic techniques to tie a "cryptographic leash'' around the quantum device. In these notes I give a self-contained introduction to her elegant solution, explaining the required concepts from complexity, quantum computing, and cryptography, and how they are brought together in Mahadev's protocol for classical verification of quantum computations.

Item Type:Article
Related URLs:
URLURL TypeDescription
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2019 American Mathematical Society. Received by editor(s): February 6, 2019. Published electronically: October 9, 2019. I am indebted to Urmila Mahadev for numerous conversations that helped clarify her work. I thank Victor Albert, Alexandru Georghiu, Urmila Mahadev, and Oded Regev for comments on earlier versions of these notes.
Issue or Number:1
Classification Code:2010 Mathematics Subject Classification. Primary 68Q12.
Record Number:CaltechAUTHORS:20200316-150528835
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101930
Deposited By: George Porter
Deposited On:17 Mar 2020 14:58
Last Modified:16 Nov 2021 18:07

Repository Staff Only: item control page