Volume 5 (2009)
Article 1 pp. 1-42

The Power of Unentanglement

Received: April 22, 2008

Published: May 11, 2009

Published: May 11, 2009

**Keywords:**quantum computing, PCP, entanglement, Merlin-Arthur, 3SAT

**Categories:**quantum computing, complexity theory, complexity classes, QMA, probabilistically checkable proofs, PCP, entanglement, Merlin, Arthur, interactive proofs, SAT, CNF-DNF formulas

**ACM Classification:**F.1.2, F.1.3

**AMS Classification:**81P68, 68Q15, 68Q17

**Abstract:**
[Plain Text Version]

The class $\mathsf{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 $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for $k\geq2$? Can $\mathsf{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 $\widetilde{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 $\mathsf{QMA}( 2) $ protocol can be amplified to exponentially small error, and $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for all $k\geq2$.
- We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.