Volume 5 (2009)
Article 1 pp. 1-42
The Power of Unentanglement
by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor
Received: April 22, 2008
Published: May 11, 2009
Keywords: quantum computing, PCP, entanglement, Merlin-Arthur, 3SAT
Categories: quantum,
complexity theory,
complexity classes,
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 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.
Licensed under a Creative Commons Attribution License