Verifying quantum computations at scale: A cryptographic leash on quantum devices

Vidick, Thomas

doi:10.1090/bull/1678

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