Volume 5 (2009) Article 1 pp. 1-42
The Power of Unentanglement
Received: April 22, 2008
Published: May 11, 2009
[PDF (474K)]    [PS (1768K)]    [PS.GZ (399K)]
[Source ZIP]
Keywords: quantum computing, PCP, entanglement, Merlin-Arthur, 3SAT
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.