Interactive Proofs for $\mathsf{BQP}$ via Self-Tested Graph States

by Matthew McKague

Theory of Computing, Volume 12(3), pp. 1-42, 2016

Bibliography with links to cited articles

[1]   Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani: Device-independent security of quantum cryptography against collective attacks. Physical Review Letters, 98(23):230501, 2007. [doi:10.1103/PhysRevLett.98.230501, arXiv:quant-ph/0702152]

[2]   Dorit Aharonov, Michael Ben-Or, and Elad Eban: Interactive proofs for quantum computations. In Innovations in Computer Science (ICS’10), pp. 453–469. Tsinghua Univ. Press, 2010. Available at ICS’10 website. [arXiv:0810.5375]

[3]   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. MIT Press, 2013. [arXiv:1206.3686]

[4]   Charles-Edwourd Bardyn, Timothy C. H. Liew, Serge Massar, Matthew McKague, and Valerio Scarani: Device-independent state estimation based on Bell’s inequalities. Physical Review A, 80(6):062327, 2009. [doi:10.1103/PhysRevA.80.062327, arXiv:0907.2170]

[5]   Anne Broadbent, Joseph 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]

[6]   Boris S. Cirel’son: Quantum generalizations of Bell’s inequality. Letters in Mathematical Physics, 4(2):93–100, 1980. [doi:10.1007/BF00417500]

[7]   Reinhard Diestel: Graph Theory. Volume 173 of Graduate Texts in Mathematics. Springer, 2010.

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

[9]   Daniel Gottesman: Stabilizer Codes and Quantum Error Correction. Ph. D. thesis, Caltech, 1997. [arXiv:quant-ph/9705052]

[10]   Carsten Lund, Lance Fortnow, Howard J. 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]

[11]   Frédéric Magniez, Dominic Mayers, Michele Mosca, and Harold Ollivier: Self-testing of quantum circuits. In 33rd International Colloquium on Automata, Languages and Programming (ICALP’06), volume 4051 of LNCS, pp. 72–83. Springer, 2006. [doi:10.1007/11786986_8, arXiv:quant-ph/0512111v1]

[12]   Dominic Mayers and Andrew Chi-Chih Yao: Quantum cryptography with imperfect apparatus. In Proc. 39th FOCS, pp. 503–509. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743501, arXiv:quant-ph/9809039]

[13]   Dominic Mayers and Andrew Chi-Chih Yao: Self testing quantum apparatus. Quantum Inf. Comput., 4(4):273–286, 2004. ACM DL. [arXiv:quant-ph/0307205]

[14]   Matthew McKague: Quantum Information Processing with Adversarial Devices. Ph. D. thesis, University of Waterloo, 2010. [arXiv:1006.2352]

[15]   Matthew McKague: Self-testing graph states. In 6th Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC’11), volume 6745 of LNCS, pp. 104–120. Springer, 2011. [doi:10.1007/978-3-642-54429-3_7, arXiv:1010.1989]

[16]   Matthew McKague: Interactive proofs with efficient quantum prover for recursive Fourier sampling. Chicago J. Theor. Comput. Sci., 2012(6):1–10, 2012. [doi:10.4086/cjtcs.2012.006, arXiv:1012.5699]

[17]   Matthew McKague and Michele Mosca: Generalized self-testing and the security of the 6-state protocol. In 5th Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC’10), volume 6519 of LNCS, pp. 113–130. Springer, 2010. [doi:10.1007/978-3-642-18073-6_10, arXiv:1006.0150]

[18]   Matthew McKague, Tzyh Haur Yang, and Valerio Scarani: Robust self-testing of the singlet. Journal of Physics A, 45(45):455304, 2012. [doi:10.1088/1751-8113/45/45/455304, arXiv:1203.2976]

[19]   Mehdi Mhalla and Simon Perdrix: Graph states, pivot minor, and universality of (X,Z)-measurements. Internat. J. Unconventional Comput., 9(1-2):153–171, 2013. [arXiv:1202.6551]

[20]   Carl A. Miller and Yaoyun Shi: Optimal robust quantum self-testing by binary nonlocal XOR games. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, (TQC’13), volume 22 of LIPIcs, pp. 254–262, 2013. [doi:10.4230/LIPIcs.TQC.2013.254, arXiv:1207.1819]

[21]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge Univ. Press, 2000.

[22]   Stefano Pironio, Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, and Valerio Scarani: Device-independent quantum key distribution secure against collective attacks. New Journal of Physics, 11(4):045021, 2009. [doi:10.1088/1367-2630/11/4/045021, arXiv:0903.4460]

[23]   Stefano Pironio, Antonio Acín, Serge Massar, Antoine Boyer de la Giroday, Dzmitry N. Matsukevich, Peter Maunz, Steven Olmschenk, David Hayes, L. Luo, T.A. Manning, and Christopher Monroe: Random numbers certified by Bell’s theorem. Nature, 464(7291):1021–1024, 2010. [doi:10.1038/nature09008, arXiv:0911.3427]

[24]   Robert Raussendorf and Hans J. Briegel: A one-way quantum computer. Physical Review Letters, 86(22):5188–5191, 2001. [doi:10.1103/PhysRevLett.86.5188, arXiv:quant-ph/0010033]

[25]   Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel: Measurement-based quantum computation on cluster states. Physical Review A, 68(2):022312, 2003. [doi:10.1103/PhysRevA.68.022312, arXiv:quant-ph/0301052]

[26]   Ben W. Reichardt, Falk Unger, and Umesh Vazirani: Classical command of quantum systems. Nature, 496(7446):456–460, 2013. [doi:10.1038/nature12035]

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

[28]   Wim van Dam, Frédéric Magniez, Michele Mosca, and Miklos Santha: Self-testing of universal and fault-tolerant sets of quantum gates. SIAM J. Comput., 37(2):611–629, 2007. Preliminary version in STOC’00. [doi:10.1137/S0097539702404377, arXiv:quant-ph/9904108]