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

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 New

Abstract | References | Similar Articles | Additional Information

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