The Power of Unentanglement

by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor

Theory of Computing, Volume 5(1), pp. 1-42, 2009

Bibliography with links to cited articles

[1]   S. Aaronson and G. Kuperberg: Quantum versus classical proofs and advice. Theory of Computing, 3(7):129–157, 2007. Previous version in Proc. CCC 2007 and quant-ph/0604056. [ToC:v003/a007, arXiv:quant-ph/0604056].

[2]    D. Aharonov and T. Naveh: Quantum NP - a survey. quant-ph/0210077, 2002. [arXiv:quant-ph/0210077].

[3]   M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson: Multi-prover interactive proofs: how to remove the intractability assumptions. In Proc. 20th STOC, pp. 113–131, New York, NY, USA, 1988. ACM Press. [STOC:62212.62223].

[4]   C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [SICOMP:10.1137/S0097539796300933, arXiv:quant-ph/9701001].

[5]   C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. Wootters: Teleporting an unknown quantum state by dual classical and EPR channels. Phys. Rev. Lett., 70:1895–1898, 1993. [PRL:10.1103/PhysRevLett.70.1895].

[6]   C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters: Mixed-state entanglement and quantum error correction. Phys. Rev. A, 54(5):3824–3851, 1996. [PRA:10.1103/PhysRevA.54.3824, arXiv:quant-ph/9604024].

[7]   H. Blier and A. Tapp: All languages in NP have very short quantum proofs. arXiv:0709.0738, 2007. [arXiv:0709.0738].

[8]   D. M. Bloom and W. Knight: A birthday problem. Amer. Math. Monthly, 80(10):1141–1142, December 1973.

[9]   F. Brandão: Entanglement Theory and the Quantum Simulation of Many-Body Physics. PhD thesis, Imperial College, London, 2008. [arXiv:0810.0026].

[10]   M. Christandl and A. Winter: “Squashed entanglement” - an additive entanglement measure. J. Math. Phys., 45(3):829–840, 2004. [arXiv:quant-ph/0308088].

[11]   I. Dinur: The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. [JACM:1236457.1236459].

[12]   D. Gavinsky: On the role of shared entanglement. Quantum Inf. Comput., 8(1-2):82–95, 2008. [arXiv:quant-ph/0604052].

[13]   M. B. Hastings: A counterexample to additivity of minimum output entropy. arXiv:0809.3972, 2008. [arXiv:quant-ph/0809.3972].

[14]   S. Khanna, M. Sudan, L. Trevisan, and D. P. Williamson: The approximability of constraint satisfaction problems. SIAM J. Comput., 30(6):1863–1920, 2000. [SICOMP:10.1137/S0097539799349948].

[15]   A. Kitaev, A. Shen, and M. N. Vyalyi: Classical and Quantum Computation. American Mathematical Society, 2002.

[16]   H. Klauck, A. Nayak, A. Ta-Shma, and D. Zuckerman: Interaction in quantum communication. IEEE Trans. Inform. Theory, 53(6):1970–1982, 2007. Earlier version in STOC’2001 and quant-ph/0603135. [doi:10.1109/TIT.2007.896888].

[17]   E. Knill: Quantum randomness and nondeterminism. quant-ph/9610012, 1996. [arXiv:quant-ph/9610012].

[18]   H. Kobayashi and K. Matsumoto: Quantum multi-prover interactive proof systems with limited prior entanglement. J. Comput. System Sci., 66(3):429–450, 2003. [JCSS:10.1016/S0022-0000(03)00035-7].

[19]   H. Kobayashi, K. Matsumoto, and T. Yamakami: Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur? In Proc. 14th Intern. Symp. Algorithms and Computation, volume 2906 of LNCS, pp. 189–198, 2003. [ISAAC:847uk09hm42tdu3q, arXiv:quant-ph/0306051].

[20]   R. König and R. Renner: A de Finetti representation for finite symmetric quantum states. J. Math. Phys., 46(122108), 2005. quant-ph/0410229. [arXiv:quant-ph/0410229].

[21]   Y.-K. Liu, M. Christandl, and F. Verstraete: Quantum computational complexity of the N-representability problem: QMA complete. Phys. Rev. Lett., 98(11), 2007. [PRL:10.1103/PhysRevLett.98.110503, arXiv:quant-ph/0609125].

[22]   C. Marriott and J. Watrous: Quantum Arthur-Merlin games. Comput. Complexity, 14(2):122–152, 2005. [CC:h0521k6666871652].

[23]   M. Nielsen and I. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[24]   M. Ohya and D. Petz: Quantum Entropy and its Use. Springer, 1993.

[25]   C. H. Papadimitriou and M. H. Yannakakis: Optimization, approximation, and complexity classes. J. Comput. System Sci., 43(3):425–440, 1991. [JCSS:10.1016/0022-0000(91)90023-X].

[26]   R. Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Earlier version in STOC 1995. [SICOMP:10.1137/S0097539795280895].

[27]   P. W. Shor: Equivalence of additivity questions in quantum information theory. Comm. Math. Phys., 246(3):453–472, 2004. [Springer:a6d2vegprhlqvrby, arXiv:quant-ph/0305035].

[28]   V. Vedral and M. B. Plenio: Entanglement measures and purification procedures. Phys. Rev. A, 57(3):1619–1633, 1998. [PRA:10.1103/PhysRevA.57.1619, arXiv:quant-ph/9707035].

[29]   J. Watrous: Succinct quantum proofs for properties of finite groups. In Proc. 41st FOCS, pp. 537–546, Silver Spring, MD, USA, 2000. IEEE Computer Society Press. [doi:10.1109/SFCS.2000.892141].

[30]   M. Zukowski, A. Zeilinger, M. A. Horne, and A. K. Ekert: “event-ready-detectors”: Bell experiment via entanglement swapping. Phys. Rev. Lett., 71(26):4287–4290, 1993. [PRL:10.1103/PhysRevLett.71.4287].