Theory of Computing ------------------- Title : The Power of Unentanglement Authors : Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor Volume : 5 Number : 1 Pages : 1-42 URL : https://theoryofcomputing.org/articles/v005a001 Abstract -------- 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 O~(sqrt{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.