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
DOI:
https://doi.org/10.1090/bull/1678
Published electronically:
October 9, 2019
MathSciNet review:
4037407
Full-text PDF Free Access
View in AMS MathViewer
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.
- 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 https://doi.org/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 https://doi.org/10.1007/978-3-642-00457-5_28
- 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
- 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 https://doi.org/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 https://doi.org/10.1016/0022-0000%2888%2990005-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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/BF02650179
- Joseph F. Fitzsimons, Michal Hajdušek, and Tomoyuki Morimae, Post hoc verification of quantum computation, Phys. Rev. Lett. 120 (2018), no. 4, 040501, 5. MR 3758139, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/978-3-642-29011-4_41
- Chris Peikert, A decade of lattice cryptography, Found. Trends Theor. Comput. Sci. 10 (2014), no. 4, i—iii, 283–424. MR 3494162, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/978-3-662-49896-5_18
- 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 https://doi.org/10.1109/FOCS.2017.61
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:
vidick@cms.caltech.edu
Received by editor(s):
February 6, 2019
Published electronically:
October 9, 2019
Article copyright:
© Copyright 2019
American Mathematical Society