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, Post hoc verification of quantum computation, Phys. Rev. Lett. 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