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

[2]   Dorit Aharonov, Itai Arad, and Thomas Vidick: Guest Column: The Quantum PCP Conjecture. SIGACT News, 44(2):47–79, 2013. [doi:10.1145/2491533.2491549]

[3]   Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev: Interactive proofs for quantum computations. 2017. Preliminary version in ICS’10, see arXiv:0810.5375. [arXiv:1704.04487]

[4]   Dorit Aharonov and Tomer Naveh: Quantum NP - a survey, 2002. [arXiv:quant-ph/0210077]

[5]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Preliminary version in FOCS’92. [doi:10.1145/278298.278306]

[6]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]

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

[8]   László Babai, Lance Fortnow, and Carsten Lund: Nondeterministic exponential time has two-prover interactive protocols. Comput. Complexity, 1(1):3–40, 1991. Preliminary version in FOCS’90. [doi:10.1007/BF01200056]

[9]   Jonathan Barrett: Nonsequential positive-operator-valued measurements on entangled mixed states do not always violate a Bell inequality. Phys. Rev. A, 65(4):042302, 2002. [doi:10.1103/PhysRevA.65.042302, arXiv:quant-ph/0107045]

[10]   John S. Bell: On the Einstein Podolsky Rosen paradox. Physics Physique Fizika, 1(3):195–200, 1964. [doi:10.1103/PhysicsPhysiqueFizika.1.195]

[11]   Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson: Multi-prover interactive proofs: How to remove intractability assumptions. In Proc. 20th STOC, pp. 113–131. ACM Press, 1988. [doi:10.1145/62212.62223]

[12]   Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters: Mixed-state entanglement and quantum error correction. Phys. Rev. A, 54(5):3824–3851, 1996. [doi:10.1103/PhysRevA.54.3824, arXiv:quant-ph/9604024]

[13]   Jacob D. Biamonte and Peter J. Love: Realizable Hamiltonians for universal adiabatic quantum computers. Phys. Rev. A, 78(1):012352, 2008. [doi:10.1103/PhysRevA.78.012352, arXiv:0704.1287]

[14]   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]

[15]   Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous: Zero-knowledge proof systems for QMA. In Proc. 57th FOCS, pp. 31–40. IEEE Comp. Soc. Press, 2016. [doi:10.1109/FOCS.2016.13, arXiv:1604.02804]

[16]   Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas Winter: On the quantum chromatic number of a graph. Electronic J. Combinatorics, 14:R81, 2007. [arXiv:quant-ph/0608016]

[17]   John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880–884, 1969. [doi:10.1103/PhysRevLett.23.880]

[18]   Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous: Consequences and limits of nonlocal strategies. In Proc. 19th IEEE Conf. on Computational Complexity (CCC’04), pp. 236–249. IEEE Comp. Soc. Press, 2004. [doi:10.1109/CCC.2004.1313847, arXiv:quant-ph/0404076]

[19]   Richard Cleve and Rajat Mittal: Characterization of binary constraint system games. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), pp. 320–331. Springer, 2014. [doi:10.1007/978-3-662-43948-7_27, arXiv:1209.2729]

[20]   Roger Colbeck: Quantum And Relativistic Protocols For Secure Multi-Party Computation. Ph. D. thesis, University of Cambridge, 2006. [arXiv:0911.3814]

[21]   Stephen A. Cook: The complexity of theorem-proving procedures. In Proc. 3rd STOC, pp. 151–158. ACM Press, 1971. [doi:10.1145/800157.805047]

[22]   Toby S. Cubitt and Ashley Montanaro: Complexity classification of local Hamiltonian problems. SIAM J. Comput., 45(2):268–316, 2016. Preliminary version in FOCS’14. [doi:10.1137/140998287, arXiv:1311.3161]

[23]   Irit Dinur: The PCP theorem by gap amplification. J. ACM, 54(3):12:1–12:44, 2007. Preliminary version in STOC’06. [doi:10.1145/1236457.1236459]

[24]   Uri Feige and László Lovász: Two-prover one-round proof systems: their power and their problems. In Proc. 24th STOC, pp. 733–744. ACM Press, 1992. [doi:10.1145/129712.129783]

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

[26]   Joseph F. Fitzsimons and Thomas Vidick: A multiprover interactive proof system for the local Hamiltonian problem. In Proc. 6th Innovations in Theoretical Computer Science Conf. (ITCS’15), pp. 103–112. ACM Press, 2015. [doi:10.1145/2688073.2688094, arXiv:1409.0260]

[27]   Lance Fortnow, John Rompel, and Michael Sipser: On the power of multi-prover interactive protocols. Theoret. Comput. Sci., 134(2):545–557, 1994. Preliminary version in SCT’88. [doi:10.1016/0304-3975(94)90251-8]

[28]   Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin: Quantum Hamiltonian complexity. Foundations and Trends in Theoretical Computer Science, 10(3):159–282, 2014. [doi:10.1561/0400000066, arXiv:1401.3916]

[29]   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]

[30]   Daniel Gottesman: Stabilizer Codes and Quantum Error Correction. Ph. D. thesis, California Institute of Technology, 1997. [arXiv:quant-ph/9705052]

[31]   Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto: Oracularization and two-prover one-round interactive proofs against nonlocal strategies. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09), pp. 217–228. IEEE Comp. Soc. Press, 2009. [doi:10.1109/CCC.2009.22, arXiv:0810.0693]

[32]   Tsuyoshi Ito and Thomas Vidick: A multi-prover interactive proof for NEXP sound against entangled provers. In Proc. 53th FOCS, pp. 243–252. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.11, arXiv:1207.0550]

[33]   Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous: QIP = PSPACE. J. ACM, 58(6):30:1–30:XX, 2011. Preliminary version in STOC’10. [doi:10.1145/2049697.2049704, arXiv:0907.4737]

[34]   Zhengfeng Ji: Binary constraint system games and locally commutative reductions, 2013. [arXiv:1310.3794]

[35]   Zhengfeng Ji: Classical verification of quantum proofs. In Proc. 48th STOC, pp. 885–898. ACM Press, 2016. [doi:10.1145/2897518.2897634, arXiv:1505.07432]

[36]   Zhengfeng Ji: Compression of quantum multi-prover interactive proofs. In Proc. 49th STOC, pp. 289–302. ACM Press, 2017. [doi:10.1145/3055399.3055441, arXiv:1610.03133]

[37]   Camille Jordan: Essai sur la géométrie à n dimensions. Bull. de la Soc. Math. de France, 3:103–174, 1875. [doi:10.24033/bsmf.90]

[38]   Richard M. Karp: Reducibility among combinatorial problems. In Proc. Symp. Complexity of Computer Computations, pp. 85–103. Springer, 1972. [doi:10.1007/978-1-4684-2001-2_9]

[39]   Julia Kempe, Alexei Kitaev, and Oded Regev: The complexity of the local Hamiltonian problem. SIAM J. Comput., 35(5):1070–1097, 2006. Preliminary version in FSTTCS’04. [doi:10.1137/S0097539704445226, arXiv:quant-ph/0406180]

[40]   Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick: Entangled games are hard to approximate. SIAM J. Comput., 40(3):848–877, 2011. Preliminary version in FOCS’08. [doi:10.1137/090751293, arXiv:0704.2903]

[41]   Alexei Y. Kitaev: Lecture given in Hebrew University, Jerusalem, Israel, 1999.

[42]   Alexei Y. Kitaev, Alexander H. Shen, and Mikhail. N. Vyalyi: Classical and Quantum Computation. American Mathematical Society, 2002.

[43]   Alexei Y. Kitaev and John Watrous: Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proc. 32nd STOC, pp. 608–617. ACM Press, 2000. [doi:10.1145/335305.335387]

[44]   Hirotada Kobayashi and Keiji Matsumoto: Quantum multi-prover interactive proof systems with limited prior entanglement. J. Comput. System Sci., 66(3):429–450, 2003. Preliminary version in ISAAC’02. [doi:10.1016/S0022-0000(03)00035-7, arXiv:cs/0102013]

[45]   Simon B. Kochen and Ernst Specker: The problem of hidden variables in quantum mechanics. J. Math. Mech., 17(1):59–87, 1967. JSTOR.

[46]   Raymond Laflamme, Cesar Miquel, Juan Pablo Paz, and Wojciech Hubert Zurek: Perfect quantum error correcting code. Phys. Rev. Lett., 77(1):198–201, 1996. [doi:10.1103/PhysRevLett.77.198, arXiv:quant-ph/9602019]

[47]   Leonid Levin: Universal search problems. Problems of Information Transmission, 9(3):115–116, 1973.

[48]   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]

[49]   Dominic Mayers and Andrew Yao: Quantum cryptography with imperfect apparatus. In Proc. 39th FOCS, p. 503. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743501]

[50]    Matthew McKague: Self-testing graph states. In Proc. 6th Conf. Quantum Computation, Communication, and Cryptography (TQC’11), pp. 104–120. Springer, 2014. [doi:10.1007/978-3-642-54429-3_7, arXiv:1010.1989]

[51]   Matthew McKague: Interactive proofs for BQP via self-tested graph states. Theory of Computing, 12(3):1–42, 2016. [doi:10.4086/toc.2016.v012a003, arXiv:1309.5675]

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

[53]   Nathaniel David Mermin: Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett., 65(27):3373–3376, 1990. [doi:10.1103/PhysRevLett.65.3373]

[54]   Carl A. Miller and Yaoyun Shi: Optimal robust self-testing by binary nonlocal XOR games. In Proc. 8th Conf. Quantum Computation, Communication, and Cryptography (TQC’13), pp. 254–262. Springer, 2013. [doi:10.4230/LIPIcs.TQC.2013.254]

[55]   Carl A. Miller and Yaoyun Shi: Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices. J. ACM, 63(4):33, 2016. Preliminary version in STOC’14. [doi:10.1145/2885493, arXiv:1402.0489]

[56]   Anand Natarajan and Thomas Vidick: Constant-soundness interactive proofs for local Hamiltonians, 2015. [arXiv:1512.02090]

[57]   Anand Natarajan and Thomas Vidick: Robust self-testing of many-qubit states, 2016. Conference version STOC’17. [arXiv:1610.03574]

[58]   Roberto Oliveira and Barbara M. Terhal: The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Inf. Comput., 8(10):900–924, 2008. [arXiv:quant-ph/0504050]

[59]   Tobias J. Osborne: Hamiltonian complexity. Reports on Progress in Physics, 75(2):022001, 2012. [doi:10.1088/0034-4885/75/2/022001, arXiv:1106.5875]

[60]   Asher Peres: Incompatible results of quantum measurements. Physics Letters A, 151(3–4):107–108, 1990. [doi:10.1016/0375-9601(90)90172-K]

[61]   S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe: Random numbers certified by Bell’s theorem. Nature, 464(7291):1021–1024, 2010. [doi:10.1038/nature09008, arXiv:0911.3427]

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

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

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

[65]   Yaoyun Shi: Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Inf. Comput., 3(1):84–92, 2003. [arXiv:quant-ph/0205115]

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

[67]   Wim van Dam, Frédéic 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]

[68]   Umesh Vazirani and Thomas Vidick: Certifiable quantum dice: or, true random number generation secure against quantum adversaries. In Proc. 44th STOC, pp. 61–76. ACM Press, 2012. [doi:10.1145/2213977.2213984, arXiv:1111.6054]

[69]   Umesh Vazirani and Thomas Vidick: Fully device-independent quantum key distribution. Phys. Rev. Lett., 113(14):140501, 2014. Conference version in ITCS’14. [doi:10.1103/PhysRevLett.113.140501, arXiv:1210.1810]

[70]   Thomas Vidick: Three-player entangled XOR games are NP-hard to approximate. SIAM J. Comput., 45(3):1007–1063, 2016. Preliminary version in FOCS’13. [doi:10.1137/140956622, arXiv:1302.1242]

[71]   Thomas Vidick and John Watrous: Quantum proofs. Foundations and Trends in Theoretical Computer Science, 11(1–2):1–215, 2015. [doi:10.1561/0400000068, arXiv:1610.01664]

[72]   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]

[73]   John Watrous: Zero-knowledge against quantum attacks. SIAM J. Comput., 39(1):25–58, 2009. Preliminary version in STOC’06. [doi:10.1137/060670997, arXiv:quant-ph/0511020]

[74]   Reinhard F. Werner: Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model. Phys. Rev. A, 40(8):4277–4281, 1989. [doi:10.1103/PhysRevA.40.4277]