Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-051 | 4th April 2008 00:00

The Power of Unentanglement


Authors: Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor
Publication: 2nd May 2008 20:53
Downloads: 1393


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? Can we show any upper bound
on QMA(k), besides the trivial NEXP? 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. First, we give
a protocol by which a verifier can be convinced that a 3SAT formula of
size n is satisfiable, with constant soundness, given ~O(sqrt(n))
unentangled quantum witnesses with O(log n) qubits each. Our protocol
relies on Dinur's version of the PCP Theorem and is inherently
non-relativizing. Second, we show that assuming the famous 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. Third, we give evidence that QMA(2) is contained in PSPACE, by
showing that this would follow from "strong amplification" of QMA(2)
protocols. Finally, we prove the nonexistence of "perfect
disentanglers" for simulating multiple Merlins with one.

ISSN 1433-8092 | Imprint