Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



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

Author: Thomas Vidick
Journal: Bull. Amer. Math. Soc. 57 (2020), 39-76
MSC (2010): Primary 68Q12
Published electronically: October 9, 2019
MathSciNet review: 4037407
Full-text PDF Free Access
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information


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.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 68Q12

Retrieve articles in all journals with MSC (2010): 68Q12

Additional Information

Thomas Vidick
Affiliation: California Institute of Technology, Pasadena, California 91106
MR Author ID: 845076

Received by editor(s): February 6, 2019
Published electronically: October 9, 2019
Article copyright: © Copyright 2019 American Mathematical Society