Skip to Main Content

Bulletin of the American Mathematical Society

The Bulletin publishes expository articles on contemporary mathematical research, written in a way that gives insight to mathematicians who may not be experts in the particular topic. The Bulletin also publishes reviews of selected books in mathematics and short articles in the Mathematical Perspectives section, both by invitation only.

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

The 2020 MCQ for Bulletin of the American Mathematical Society is 0.84.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Verifying quantum computations at scale: A cryptographic leash on quantum devices
HTML articles powered by AMS MathViewer

by Thomas Vidick HTML | PDF
Bull. Amer. Math. Soc. 57 (2020), 39-76 Request permission


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.

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
  • Email:
  • Received by editor(s): February 6, 2019
  • Published electronically: October 9, 2019
  • © Copyright 2019 American Mathematical Society
  • Journal: Bull. Amer. Math. Soc. 57 (2020), 39-76
  • MSC (2010): Primary 68Q12
  • DOI:
  • MathSciNet review: 4037407