## 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

## Abstract:

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

- Scott Aaronson and Andris Ambainis,
*Forrelation: a problem that optimally separates quantum from classical computing*, SIAM J. Comput.**47**(2018), no.Â 3, 982â€“1038. MR**3818333**, DOI 10.1137/15M1050902 - Dorit Aharonov, Micahel Ben-Or, and Elad Eban,
*Interactive Proofs For Quantum Computations*, arXiv:0810.5375 (2008). - Dorit Aharonov and Ayal Green,
*A quantum inspired proof of ${P}^{\# {p}}\subseteq {IP}$*, arXiv:1710.09078 (2017). - Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan,
*Simultaneous hardcore bits and cryptography against memory attacks*, Theory of cryptography, Lecture Notes in Comput. Sci., vol. 5444, Springer, Berlin, 2009, pp.Â 474â€“495. MR**2546214**, DOI 10.1007/978-3-642-00457-5_{2}8 - LĂˇszlĂł Babai,
*Trading group theory for randomness*, Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, ACM, 1985, pp. 421â€“429. - Francisco Barahona,
*On the computational complexity of Ising spin glass models*, J. Phys. A**15**(1982), no.Â 10, 3241â€“3253. MR**684591**, DOI 10.1088/0305-4470/15/10/028 - Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S Zibrov, Manuel Endres, Markus Greiner, et al.,
*Probing many-body dynamics on a 51-atom quantum simulator*, Nature**551**(2017), no. 7682, 579. - Manuel Blum,
*Coin flipping by telephone: a protocol for solving impossible problems*, ACM SIGACT News**15**(1983), no. 1, 23â€“27. - Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick,
*Certifiable randomness from a single quantum device*, arXiv:1804.00640 (2018). - Zvika Brakerski and Vinod Vaikuntanathan,
*Efficient fully homomorphic encryption from (standard) $\mathsf {LWE}$*, SIAM J. Comput.**43**(2014), no.Â 2, 831â€“871. MR**3504684**, DOI 10.1137/120868669 - Gilles Brassard, David Chaum, and Claude CrĂ©peau,
*Minimum disclosure proofs of knowledge*, J. Comput. System Sci.**37**(1988), no.Â 2, 156â€“189. Twenty-Seventh Annual IEEE Symposium on the Foundations of Computer Science (Toronto, ON, 1986). MR**979117**, DOI 10.1016/0022-0000(88)90005-0 - Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi,
*Universal blind quantum computation*, 2009 50th Annual IEEE Symposium on Foundations of Computer Scienceâ€”FOCS 2009, IEEE Computer Soc., Los Alamitos, CA, 2009, pp.Â 517â€“526. MR**2648431**, DOI 10.1109/FOCS.2009.36 - Ran Canetti and Marc Fischlin,
*Universally composable commitments*, Annual International Cryptology Conference, Springer, 2001, pp. 19â€“40. - Toby Cubitt and Ashley Montanaro,
*Complexity classification of local Hamiltonian problems*, SIAM J. Comput.**45**(2016), no.Â 2, 268â€“316. MR**3477325**, DOI 10.1137/140998287 - Richard P. Feynman,
*Simulating physics with computers*, Internat. J. Theoret. Phys.**21**(1981/82), no.Â 6-7, 467â€“488. Physics of computation, Part II (Dedham, Mass., 1981). MR**658311**, DOI 10.1007/BF02650179 - Joseph F. Fitzsimons, Michal HajduĹˇek, and Tomoyuki Morimae,
, Phys. Rev. Lett.*Post hoc*verification of quantum computation**120**(2018), no.Â 4, 040501, 5. MR**3758139**, DOI 10.1103/PhysRevLett.120.040501 - Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi,
*Verification of quantum computation: an overview of existing approaches*, Theory Comput. Syst.**63**(2019), no.Â 4, 715â€“808. MR**3942255**, DOI 10.1007/s00224-018-9872-3 - Shafi Goldwasser, Silvio Micali, and Charles Rackoff,
*The knowledge complexity of interactive proof systems*, SIAM J. Comput.**18**(1989), no.Â 1, 186â€“208. MR**978174**, DOI 10.1137/0218012 - Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee,
*Attribute-based encryption for circuits*, J. ACM**62**(2015), no.Â 6, Art. 45, 33. MR**3437230**, DOI 10.1145/2824233 - Rishab Goyal, Venkata Koppula, and Brent Waters,
*Lockable obfuscation*, 58th Annual IEEE Symposium on Foundations of Computer Scienceâ€”FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp.Â 612â€“621. MR**3734265**, DOI 10.1109/FOCS.2017.62 - Rishab Goyal, Venkata Koppula, and Brent Waters,
*Collusion resistant traitor tracing from learning with errors*, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 660â€“670. - Joe Kilian,
*A note on efficient zero-knowledge proofs and arguments*, Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, ACM, 1992, pp. 723â€“732. - Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan,
*Algebraic methods for interactive proof systems*, J. Assoc. Comput. Mach.**39**(1992), no.Â 4, 859â€“868. MR**1187215**, DOI 10.1145/146585.146605 - Urmila Mahadev,
*Classical verification of quantum computations*, 59th Annual IEEE Symposium on Foundations of Computer Scienceâ€”FOCS 2018, IEEE Computer Soc., Los Alamitos, CA, 2018, pp.Â 259â€“267. MR**3899595**, DOI 10.1109/FOCS.2018.00033 - Daniele Micciancio and Chris Peikert,
*Trapdoors for lattices: simpler, tighter, faster, smaller*, Advances in cryptologyâ€”EUROCRYPT 2012, Lecture Notes in Comput. Sci., vol. 7237, Springer, Heidelberg, 2012, pp.Â 700â€“718. MR**2972927**, DOI 10.1007/978-3-642-29011-4_{4}1 - Chris Peikert,
*A decade of lattice cryptography*, Found. Trends Theor. Comput. Sci.**10**(2014), no.Â 4, iâ€”iii, 283â€“424. MR**3494162**, DOI 10.1561/0400000074 - Ran Raz and Avishay Tal,
*Oracle separation of BQP and PH*, Electronic Colloquium on Computational Complexity (ECCC), vol. 25, 2018, p. 107. - Oded Regev,
*On lattices, learning with errors, random linear codes, and cryptography*, J. ACM**56**(2009), no.Â 6, Art. 34, 40. MR**2572935**, DOI 10.1145/1568318.1568324 - Ben W Reichardt, Falk Unger, and Umesh Vazirani,
*Classical command of quantum systems*, Nature**496**(2013), no. 7446, 456. - Adi Shamir,
*IP = PSPACE*, J. Assoc. Comput. Mach.**39**(1992), no.Â 4, 869â€“877. MR**1187216**, DOI 10.1145/146585.146609 - Dominique Unruh,
*Computationally binding quantum commitments*, Advances in cryptologyâ€”EUROCRYPT 2016. Part II, Lecture Notes in Comput. Sci., vol. 9666, Springer, Berlin, 2016, pp.Â 497â€“527. MR**3516412**, DOI 10.1007/978-3-662-49896-5_{1}8 - Daniel Wichs and Giorgos Zirdelis,
*Obfuscating compute-and-compare programs under LWE*, 58th Annual IEEE Symposium on Foundations of Computer Scienceâ€”FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp.Â 600â€“611. MR**3734264**, DOI 10.1109/FOCS.2017.61

## Additional Information

**Thomas Vidick**- Affiliation: California Institute of Technology, Pasadena, California 91106
- MR Author ID: 845076
- Email: vidick@cms.caltech.edu
- 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: https://doi.org/10.1090/bull/1678
- MathSciNet review: 4037407