A Caltech Library Service

The Power of Unentanglement

Aaronson, Scott and Beigi, Salman and Drucker, Andrew and Fefferman, Bill and Shor, Peter (2009) The Power of Unentanglement. Theory of Computing, 5 (Articl). pp. 1-42. ISSN 1557-2862.

PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


The class QMA(k). introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Does QMA(k) = QMA(2) for k ≥ 2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. * We give a protocol by which a verifier can be convinced that a 3SAT formula of size m is satisfiable, with constant soundness, given Õ (√m) unentangled quantum witnesses with O(log m) qubits each. Our protocol relies on the existence of very short PCPs. * We show that assuming a weak version of the Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k) = QMA(2) for all k ≥ 2. * We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2009 Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. Received: April 22, 2008, Published: May 11, 2009. We thank Fernando Brandão for pointing out that our “Strong Amplification Conjecture” implies not only QMA(2) ⊆ PSPACE but QMA(2) = QMA, and that our original version of Lemma 4.3 contained a bug, among other extremely helpful comments; Norbert Schuch for pointing out that Theorem 4.5 can be based on a conjecture about entanglement of formation rather than squashed entanglement; Madhu Sudan for pointers on the PCP Theorem; John Watrous for posing Conjecture 5.2; an anonymous reviewer for greatly simplifying the proof of Lemma 4.3 and other help; and Patrick Hayden, Ryan O’Donnell, Alain Tapp, and Andreas Winter for helpful discussions.
Funding AgencyGrant Number
Massachusetts Institute of TechnologyUNSPECIFIED
NSF Integrative Graduate Education and Research TraineeshipUNSPECIFIED
Akamai Presidential Graduate FellowshipUNSPECIFIED
Caltech Division of Engineering and Applied Science FellowshipUNSPECIFIED
Subject Keywords:quantum computing, PCPs, entanglement, Merlin-Arthur, 3SAT
Issue or Number:Articl
Classification Code:ACM Classification: F.1.2, F.1.3; AMS Classification: 81P68, 68Q15, 68Q17
Record Number:CaltechAUTHORS:20091020-132703748
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:16400
Deposited By: Joy Painter
Deposited On:26 Oct 2009 20:33
Last Modified:03 Oct 2019 01:11

Repository Staff Only: item control page