How to Verify a Quantum Computation

by Anne Broadbent

Theory of Computing, Volume 14(11), pp. 1-37, 2018

Bibliography with links to cited articles

[1]   Scott Aaronson and Alex Arkhipov: The computational complexity of linear optics. Theory of Computing, 9(4):143–252, 2013. Preliminary version in STOC’11. [doi:10.4086/toc.2013.v009a004, arXiv:1011.3245]

[2]   Scott Aaronson and Alex Arkhipov: BosonSampling is far from uniform. Quantum Inf. Comput., 14(15-16):1383–1423, 2014. [arXiv:1309.7460, ECCC:TR13-135]

[3]   Dorit Aharonov, Michael Ben-Or, and Elad Eban: Interactive proofs for quantum computations. In Proc. 1st Symp. Innovations in Computer Science (ICS’10), pp. 453–469, 2010. [arXiv:1704.04487]

[4]   Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev: Interactive proofs for quantum computations, 2017. [arXiv:1704.04487]

[5]   Dorit Aharonov, Vaughan Jones, and Zeph Landau: A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica, 55(3):395–421, 2009. Preliminary version in STOC’06. [doi:10.1007/s00453-008-9168-0, arXiv:quant-ph/0511096]

[6]   Dorit Aharonov and Umesh Vazirani: Is Quantum Mechanics falsifiable? A computational perspective on the foundations of Quantum Mechanics. In Computability: Turing, Gödel, Church, and Beyond, pp. 329–349. MIT Press, 2013. [arXiv:1206.3686]

[7]   Andris Ambainis, Michele Mosca, Alain Tapp, and Ronald de Wolf: Private quantum channels. In Proc. 41st FOCS, pp. 547–553. IEEE Comp. Soc. Press, 2000. [doi:10.1109/SFCS.2000.892142, arXiv:quant-ph/0003101]

[8]   László Babai: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM Press, 1985. [doi:10.1145/22145.22192]

[9]   Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp: Authentication of quantum messages. In Proc. 43rd FOCS, pp. 449–458. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181969, arXiv:quant-ph/0205128]

[10]   Stefanie Barz, Joseph F. Fitzsimons, Elham Kashefi, and Philip Walther: Experimental verification of quantum computation. Nature Physics, 9(11):727–731, 2013. [doi:10.1038/nphys2763, arXiv:1309.0005]

[11]   Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith: Secure multiparty quantum computation with (only) a strict honest majority. In Proc. 47th FOCS, pp. 249–260. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.68, arXiv:0801.1544]

[12]   P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan: A new universal and fault-tolerant quantum basis. Inform. Process. Lett., 75(3):101–107, 2000. [doi:10.1016/S0020-0190(00)00084-3, arXiv:quant-ph/9906054]

[13]   Gilles Brassard, David Chaum, and Claude Crépeau: Minimum disclosure proofs of knowledge. J. Comput. System Sci., 37(2):156–189, 1988. [doi:10.1016/0022-0000(88)90005-0]

[14]   Anne Broadbent: Delegating private quantum computations. Canad. J. Physics, 93(9):941–946, 2015. [doi:10.1139/cjp-2015-0030, arXiv:1506.01328]

[15]   Anne Broadbent, Joseph F. Fitzsimons, and Elham Kashefi: Universal blind quantum computation. In Proc. 50th FOCS, pp. 517–526. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.36, arXiv:0807.4154]

[16]   Anne Broadbent, Gus Gutoski, and Douglas Stebila: Quantum one-time programs. In Proc. 33rd Ann. Intern. Cryptology Conf. (CRYPTO’13), pp. 344–360, 2013. [doi:10.1007/978-3-642-40084-1_20, arXiv:1211.1080]

[17]   Anne Broadbent and Stacey Jeffery: Quantum homomorphic encryption for circuits of low T-gate complexity. In Proc. 35th Ann. Intern. Cryptology Conf. (CRYPTO’15), pp. 609–629, 2015. [doi:10.1007/978-3-662-48000-7_30, arXiv:1412.8766]

[18]   Andrew M. Childs, Debbie W. Leung, and Michael A. Nielsen: Unified derivations of measurement-based schemes for quantum computation. Phys. Rev. A, 71(3):032318, 2005. [doi:10.1103/PhysRevA.71.032318, arXiv:quant-ph/0404132]

[19]   Andrea Coladangelo, Alex Grilo, Stacey Jeffery, and Thomas Vidick: Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources, 2017. [arXiv:1708.07359]

[20]   Anne Condon and Richard E. Ladner: Interactive proof systems with polynomially bounded strategies. J. Comput. System Sci., 50(3):506–518, 1995. Preliminary version in SCT’92. [doi:10.1109/SCT.1992.215403]

[21]   Ivan B. Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner: Cryptography in the bounded-quantum-storage model. SIAM J. Comput., 37(6):1865–1890, 2008. Preliminary version in FOCS’05. [doi:10.1137/060651343, arXiv:quant-ph/0508222]

[22]   Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine: Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A, 80(1):012304, 2009. [doi:10.1103/PhysRevA.80.012304, arXiv:quant-ph/0606161]

[23]   Vedran Dunjko, Joseph F. Fitzsimons, Christopher Portmann, and Renato Renner: Composable security of delegated quantum computation. In 20th Internat. Conf. on the Theory and Appl. of Cryptology and Information Security (ASIACRYPT’14), pp. 406–425, 2014. [doi:10.1007/978-3-662-45608-8_22, arXiv:1301.3662]

[24]   Richard P. Feynman: Simulating physics with computers. Internat. J. Theoretical Physics, 21(6-7):467–488, 1982. [doi:10.1007/BF02650179]

[25]   Kent A. G. Fisher, Anne Broadbent, Lynden K. Shalm, Zhennya Yan, Jonathan Lavoie, Robert Prevedel, Thomas Jennewein, and Kevin J. Resch: Quantum computing on encrypted data. Nature Communications, 5:3074, 2014. [doi:10.1038/ncomms4074, arXiv:1309.2586]

[26]   Joseph F. Fitzsimons and Michal Hajdušek: Post hoc verification of quantum computation, 2015. [arXiv:1512.04375]

[27]   Joseph F. Fitzsimons and Elham Kashefi: Unconditionally verifiable blind computation, 2012. [arXiv:1203.5217]

[28]   Joseph F. Fitzsimons and Elham Kashefi: Unconditionally verifiable blind quantum computation. Phys. Rev. A, 96(1):012303, 2017. [doi:10.1103/PhysRevA.96.012303]

[29]   Zhengting Gan and Robert J. Harrison: Calibrating quantum chemistry: A multi-teraflop, parallel-vector, full-configuration interaction program for the Cray-X1. In 18th Ann. Conf. on Supercomputing (SC’05), pp. 22–22, 2005. [doi:10.1109/SC.2005.17]

[30]   Christian Gogolin, Martin Kliesch, Leandro Aolita, and Jens Eisert: Boson-Sampling in the light of sample complexity, 2013. [arXiv:1306.3995]

[31]   Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum: Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27:1–27:64, 2015. Preliminary version in STOC’08. [doi:10.1145/2699436, ECCC:TR17-108]

[32]   Shafi Goldwasser, Silvio Micali, and Charles Rackoff: The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186–208, 1989. Preliminary version in STOC’85. [doi:10.1137/0218012]

[33]   Daniel Gottesman and Isaac L. Chuang: Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402(6760):390–393, 1999. [doi:10.1038/46503, arXiv:quant-ph/9908010]

[34]   Masahito Hayashi and Michal Hajdušek: Self-guaranteed measurement-based quantum computation, 2016. [arXiv:1603.02195]

[35]   Masahito Hayashi and Tomoyuki Morimae: Verifiable measurement-only blind quantum computing with stabilizer testing. Phys. Rev. Lett., 115(22):220502, 2015. [doi:10.1103/PhysRevLett.115.220502, arXiv:1505.07535]

[36]   Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous: QIP = PSPACE. Comm. ACM, 53(12):102–109, 2010. Preliminary version in STOC’10. [doi:10.1145/1859204.1859231, arXiv:0907.4737]

[37]   Theodoros Kapourniotis, Vedran Dunjko, and Elham Kashefi: On optimising quantum communications in verifiable quantum computing. In Asian Quantum Info. Sci. Conf. (AQIS’15), pp. 23–25, 2015. [arXiv:1506.06943]

[38]   Elham Kashefi and Petros Wallden: Optimised resource construction for verifiable quantum computation. J. Physics A, 50(14):145306, 2017. [doi:10.1088/1751-8121/aa5dac, arXiv:1510.07408]

[39]   Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick: Using entanglement in quantum multi-prover interactive proofs. Comput. Complexity, 18(2):273–307, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0275-3, arXiv:0711.3715]

[40]   Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan: Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Preliminary version in FOCS’90. [doi:10.1145/146585.146605]

[41]   Michael A. Nielsen and Issac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000. [doi:10.1017/CBO9780511976667]

[42]    Ben W. Reichardt, Falk Unger, and Umesh Vazirani: Classical command of quantum systems. Nature, 496(7446):456–460, 2013. Preliminary version in ITCS’13. [doi:10.1038/nature12035, arXiv:1209.0448, arXiv:1209.0449]

[43]   Adi Shamir: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90. [doi:10.1145/146585.146609]

[44]   Peter W. Shor and John Preskill: Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett., 85(2):441–444, 2000. [doi:10.1103/physrevlett.85.441, arXiv:quant-ph/0003004]

[45]   Nicolò Spagnolo, Chiara Vitelli, Marco Bentivegna, Daniel J Brod, Andrea Crespi, Fulvio Flamini, Sandro Giacomini, Giorgio Milani, Roberta Ramponi, Paolo Mataloni, Roberto Osellame, Ernesto F. Galvão, and Fabio Sciarrino: Experimental validation of photonic boson sampling. Nature Photonics, 8(8):615–620, 2014. [doi:10.1038/nphoton.2014.135, arXiv:1311.1622]

[46]   John Watrous: PSPACE has constant-round quantum interactive proof systems. Theoret. Comput. Sci., 292(3):575–588, 2003. Preliminary version in FOCS’99. [doi:10.1016/S0304-3975(01)00375-9, arXiv:cs/9901015]

[47]   Xinlan Zhou, Debbie W. Leung, and Isaac L. Chuang: Methodology for quantum logic gate construction. Phys. Rev. A, 62(5):052316, 2000. [doi:10.1103/PhysRevA.62.052316, arXiv:quant-ph/0002039]