pdf icon
Volume 5 (2009) Article 1 pp. 1-42
The Power of Unentanglement
Received: April 22, 2008
Published: May 11, 2009
Download article from ToC site:
[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.