Verifying quantum computations at scale: A cryptographic leash on quantum devices
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.
Cite this item
Vidick, T. (2020). Verifying quantum computations at scale: A cryptographic leash on quantum devices. Bulletin of the American Mathematical Society, 57(1), Article 1678. https://doi.org/10.1090/BULL/1678
Click Copy to copy the citation, or select the text manually.
2-s2.0-85083285899
California Institute of Technology
2020
57
1
1678
1
38
REVIEWED
OTHER