Interactive Proofs for $\mathsf{BQP}$ via Self-Tested Graph States
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]