[1]   Scott Aaronson: Quantum Computing since Democritus. Cambridge Univ. Press, 2013.

[2]   Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor: The power of unentanglement. Theory of Computing, 5(1):1–42, 2009. Preliminary version in CCC’08. [doi:10.4086/toc.2009.v005a001]

[3]   Andris Ambainis, Adam Smith, and Ke Yang: Extracting quantum entanglement (general entanglement purification protocols). In Proc. 17th IEEE Conf. on Computational Complexity (CCC’02), pp. 82–91, 2002. [doi:10.1109/CCC.2002.1004345, arXiv:quant-ph/0110011]

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

[5]   László Babai and Shlomo Moran: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. System Sci., 36(2):254–276, 1988. [doi:10.1016/0022-0000(88)90028-1]

[6]   Adriano Barenco, Andre Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello: Stabilization of quantum computations by symmetrization. SIAM J. Comput., 26(5):1541–1557, 1997. [doi:10.1137/S0097539796302452, arXiv:quant-ph/9604028]

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

[8]   Salman Beigi: NP vs QMA_log(2). Quantum Inf. Comput., 10(1&2):141–151, 2010. [arXiv:0810.5109]

[9]   Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters: Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70(13):1895–1899, 1993. [doi:10.1103/PhysRevLett.70.1895]

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

[11]   Charles H. Bennett, Peter W. Shor, John A. Smolin, and Ashish V. Thapliyal: Entanglement-assisted classical capacity of noisy quantum channels. Physical Review Letters, 83(15):3081–3084, 1999. [doi:10.1103/PhysRevLett.83.3081, arXiv:quant-ph/9904023]

[12]   Charles H. Bennett, Peter W. Shor, John A. Smolin, and Ashish V. Thapliyal: Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem. IEEE Trans. Inform. Theory, 48(10):2637–2655, 2002. [doi:10.1109/TIT.2002.802612, arXiv:quant-ph/0106052]

[13]   Charles H. Bennett and Stephen J. Wiesner: Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Physical Review Letters, 69(20):2881–2884, 1992. [doi:10.1103/PhysRevLett.69.2881]

[14]   Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders: Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 270(2):359–371, 2007. [doi:10.1007/s00220-006-0150-x, arXiv:quant-ph/0508139]

[15]   Hugue Blier and Alain Tapp: All languages in NP have very short quantum proofs. In Third International Conference on Quantum, Nano and Micro Technologies, 2009. ICQNM ’09., pp. 34–37, 2009. [doi:10.1109/ICQNM.2009.21, arXiv:0709.0738]

[16]   Fernando G. S. L. Brandão and Matthias Christandl: Detection of multiparticle entanglement: Quantifying the search for symmetric extensions. Physical Review Letters, 109(16):160502, 2012. [doi:10.1103/PhysRevLett.109.160502, arXiv:1105.5720]

[17]   Fernando G. S. L. Brandão, Matthias Christandl, and Jon Yard: Faithful squashed entanglement. Communications in Mathematical Physics, 306(3):805–830, 2011. [doi:10.1007/s00220-011-1302-1, arXiv:1010.1750]

[18]   Fernando G. S. L. Brandão, Matthias Christandl, and Jon Yard: A quasipolynomial-time algorithm for the quantum separability problem. In Proc. 43rd STOC, pp. 343–351. ACM Press, 2011. [doi:10.1145/1993636.1993683, arXiv:1011.2751]

[19]   Fernando G. S. L. Brandão and Aram Wettroth Harrow: Quantum de Finetti theorems under local measurements with applications. In Proc. 45th STOC, pp. 861–870. ACM Press, 2013. [doi:10.1145/2488608.2488718, arXiv:1210.6367]

[20]   Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf: Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. [doi:10.1103/PhysRevLett.87.167902, arXiv:quant-ph/0102001]

[21]   André Chailloux and Or Sattath: The complexity of the separable Hamiltonian problem. In Proc. 27th IEEE Conf. on Computational Complexity (CCC’12), pp. 32–41, 2012. [doi:10.1109/CCC.2012.42, arXiv:1111.5247]

[22]   Jing Chen and Andrew Drucker: Short multi-prover quantum proofs for SAT without entangled measurements. 2010. [arXiv:1011.0716]

[23]   Lin Chen, Martin Aulbach, and Michal Hajdusek: Comparison of different definitions of the geometric measure of entanglement. Physical Review A, 89(4):042305, 2014. [doi:10.1103/PhysRevA.89.042305, arXiv:1308.0806]

[24]   Alessandro Chiesa and Michael A. Forbes: Improved soundness for QMA with multiple provers. Chicago Journal of Theoretical Computer Science, 2013, Article 1. [doi:10.4086/cjtcs.2013.001]

[25]   Richard Cleve and Harry Buhrman: Substituting quantum entanglement for communication. Physical Review A, 56(2):1201–1204, 1997. [doi:10.1103/PhysRevA.56.1201, arXiv:quant-ph/9704026]

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

[27]   Stephen A. Cook and Phuong Nguyen: Logical Foundations of Proof Complexity. Cambridge Univ. Press, 2010. [doi:10.1017/CBO9780511676277]

[28]   Toby S. Cubitt, Debbie Leung, William Matthews, and Andreas Winter: Improving zero-error classical communication with entanglement. Physical Review Letters, 104(23):230503, 2010. [doi:10.1103/PhysRevLett.104.230503, arXiv:0911.5300]

[29]   David P. DiVincenzo, Patrick Hayden, and Barbara M. Terhal: Hiding quantum data. Foundations of Physics, 33(11):1629–1647, 2003. [doi:10.1023/a:1026013201376, arXiv:quant-ph/0207147]

[30]   David P. DiVincenzo, Debbie W. Leung, and Barbara M. Terhal: Quantum data hiding. IEEE Trans. Inform. Theory, 48(3):580–598, March 2002. [doi:10.1109/18.985948, arXiv:quant-ph/0103098]

[31]   Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri: Distinguishing separable and entangled states. Physical Review Letters, 88(18):187904, 2002. [doi:10.1103/PhysRevLett.88.187904, arXiv:quant-ph/0112007]

[32]   Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri: Complete family of separability criteria. Physical Review A, 69(2):022308, 2004. [doi:10.1103/PhysRevA.69.022308, arXiv:quant-ph/0308032]

[33]   Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri: Detecting multipartite entanglement. Physical Review A, 71(3):032333, 2005. [doi:10.1103/PhysRevA.71.032333]

[34]   Tilo Eggeling and Reinhard F. Werner: Hiding classical data in multipartite quantum states. Physical Review Letters, 89(9):097905, 2002. [doi:10.1103/physrevlett.89.097905, arXiv:0203004]

[35]   Artur K. Ekert: Quantum cryptography based on Bell’s theorem. Physical Review Letters, 67(6):661–663, 1991. [doi:10.1103/PhysRevLett.67.661]

[36]   Christopher A. Fuchs and Jeroen van de Graaf: Cryptographic distinguishability measures for quantum-mechanical states. IEEE Trans. Inform. Theory, 45(4):1216, 1999. [doi:10.1109/18.761271, arXiv:quant-ph/9712042]

[37]   Sevag Gharibian: Strong NP-hardness of the quantum separability problem. Quantum Inf. Comput., 10(3):343–360, 2010. [arXiv:0810.4507]

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

[39]   Leonid Gurvits: Classical deterministic complexity of Edmonds’ problem and quantum entanglement. In Proc. 35th STOC, pp. 10–19. ACM Press, 2003. [doi:10.1145/780542.780545, arXiv:quant-ph/0303055]

[40]   Gus Gutoski and John Watrous: Quantum interactive proofs with competing provers. In Proc. 22nd Symp. Theoretical Aspects of Comp. Sci. (STACS’05), volume 3404 of LNCS, pp. 605–616. Springer, 2005. [doi:10.1007/978-3-540-31856-9_50, arXiv:cs/0412102]

[41]   Gus Gutoski and Xiaodi Wu: Parallel approximation of min-max problems. Comput. Complexity, 22(2):385–428, 2013. Preliminary version in CCC’12. [doi:10.1007/s00037-013-0065-9, arXiv:1011.2787]

[42]   Daniel Harlow and Patrick Hayden: Quantum computation vs. firewalls. Journal of High Energy Physics, 2013(6):85, 2013. [doi:10.1007/JHEP06(2013)085, arXiv:1301.4504]

[43]   Aram Wettroth Harrow and Debbie Leung: A communication-efficient nonlocal measurement with application to communication complexity and bipartite gate capacities. IEEE Trans. Inform. Theory, 57(8):5504–5508, 2011. [doi:10.1109/TIT.2011.2158468, arXiv:0803.3066]

[44]   Aram Wettroth Harrow and Ashley Montanaro: An efficient test for product states with applications to quantum Merlin-Arthur games. In Proc. 51st FOCS, pp. 633–642. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.66, arXiv:1001.0017]

[45]   Patrick Hayden, Michal Horodecki, Andreas Winter, and Jon Yard: A decoupling approach to the quantum capacity. Open Systems & Information Dynamics, 15(1):7–19, 2008. [doi:10.1142/S1230161208000043, arXiv:quant-ph/0702005]

[46]   Patrick Hayden, Kevin Milner, and Mark M. Wilde: Two-message quantum interactive proofs and the quantum separability problem. Quantum Inf. Comput., 14(5 & 6):384–416, 2014. Preliminary version at CCC’13. [arXiv:1211.6120]

[47]   Patrick Hayden and Brian Swingle: Quantum error correction and QSZK. unpublished, 2012.

[48]   Carl W. Helstrom: Quantum detection and estimation theory. Journal of Statistical Physics, 1(2):231–252, 1969. [doi:10.1007/BF01007479]

[49]   Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki: Quantum entanglement. Reviews of Modern Physics, 81(2):865–942, 2009. [doi:10.1103/RevModPhys.81.865, arXiv:quant-ph/0702225]

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

[51]   Rahul Jain, Sarvagya Upadhyay, and John Watrous: Two-message quantum interactive proofs are in PSPACE. In Proc. 50th FOCS, pp. 534–543. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.30, arXiv:0905.1300]

[52]   Masaru Kada, Harumichi Nishimura, and Tomoyuki Yamakami: The efficiency of quantum identity testing of multiple states. Journal of Physics A: Mathematical and Theoretical, 41(39):395309, 2008. [doi:10.1088/1751-8113/41/39/395309, arXiv:0809.2037]

[53]   Alexei Yu. Kitaev: Quantum measurements and the Abelian Stabilizer Problem. ECCC, TR96-003, 1995. [arXiv:quant-ph/9511026]

[54]   Alexei Yu. 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]

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

[56]   Cécilia Lancien and Andreas Winter: Distinguishing multi-partite states by local measurements. Communications in Mathematical Physics, 323(2):555–573, 2013. [doi:10.1007/s00220-013-1779-x, arXiv:1206.2884]

[57]   François Le Gall, Shota Nakagawa, and Harumichi Nishimura: On QMA protocols with two short quantum proofs. Quantum Inf. Comput., 12(7&8):589–600, 2012. [arXiv:1108.4306]

[58]   Yi-Kai Liu, Matthias Christandl, and Frank Verstraete: Quantum computational complexity of the N-representability problem: QMA complete. Physical Review Letters, 98(11):110503, 2007. [doi:10.1103/PhysRevLett.98.110503, arXiv:quant-ph/0609125]

[59]    Seth Lloyd: Universal quantum simulators. Science, 273(5278):1073–1078, 1996. [doi:10.1126/science.273.5278.1073]

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

[61]   Chris Marriott and John Watrous: Quantum Arthur-Merlin games. Comput. Complexity, 14(2):122–152, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0194-x, arXiv:cs/0506068]

[62]   William Matthews, Stephanie Wehner, and Andreas Winter: Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding. Communications in Mathematical Physics, 291(3):813–843, 2009. [doi:10.1007/s00220-009-0890-5, arXiv:0810.2327]

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

[64]   Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994.

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

[66]   Yaoyun Shi and Xiaodi Wu: Epsilon-net method for optimizations over separable states. In Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP’12), volume 7391 of LNCS, pp. 798–809. Springer, 2012. [doi:10.1007/978-3-642-31594-7_67, arXiv:1112.0808]

[67]   Michael Sipser: Introduction to the Theory of Computation. International Thomson Publishing, 1996.

[68]   Larry J. Stockmeyer: The polynomial-time hierarchy. Theoret. Comput. Sci., 3(1):1–22, 1976. [doi:10.1016/0304-3975(76)90061-X]

[69]   Umesh Vazirani and Thomas Vidick: Fully device independent quantum key distribution. Physical Review Letters, 113(14)(14):140501, 2014. [doi:10.1103/PhysRevLett.113.140501, arXiv:1210.1810]

[70]   John Watrous: Limits on the power of quantum statistical zero-knowledge. In Proc. 43rd FOCS, pp. 459–468. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181970, arXiv:quant-ph/0202111]

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

[72]   John Watrous: Theory of Quantum Information (course lecture notes). 2004.

[73]   John Watrous: Quantum computational complexity. Encyclopedia of Complexity and System Science, pp. 7174–7201, 2009. [doi:10.1007/978-0-387-30440-3_428, arXiv:0804.3401]

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

[75]   Tzu-Chieh Wei and Paul M. Goldbart: Geometric measure of entanglement and applications to bipartite and multipartite quantum states. Physical Review A, 68(4)(4):042307, 2003. [doi:10.1103/PhysRevA.68.042307, arXiv:quant-ph/0307219]

[76]   Reinhard F. Werner: An application of Bell’s inequalities to a quantum state extension problem. Letters in Mathematical Physics, 17(4):359–363, 1989. [doi:10.1007/BF00399761]

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

[78]   Mark M. Wilde: From Classical to Quantum Shannon Theory. 2011. Published in [79]. [arXiv:1106.1445]

[79]   Mark M. Wilde: Quantum Information Theory. Cambridge Univ. Press, 2013.

[80]   Nengkun Yu, Runyao Duan, and Quanhua Xu: Bounds on the distance between a unital quantum channel and the convex hull of unitary channels, with applications to the asymptotic quantum Birkhoff conjecture. 2012. [arXiv:1201.1172]

[81]   Paolo Zanardi, Christof Zalka, and Lara Faoro: Entangling power of quantum evolutions. Physical Review A, 62(3):030301, 2000. [doi:10.1103/PhysRevA.62.030301, arXiv:quant-ph/0005031]