01446nas a2200157 4500008004100000245003200041210002800073260001500101520104100116100002001157700001801177700002001195700002001215700001601235856003701251 2008 eng d00aThe Power of Unentanglement0 aPower of Unentanglement c2008/04/043 a 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.
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
the existence of very short PCPs. Second, 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. Third, we prove the nonexistence of "perfect disentanglers" for
simulating multiple Merlins with one.
1 aAaronson, Scott1 aBeigi, Salman1 aDrucker, Andrew1 aFefferman, Bill1 aShor, Peter uhttp://arxiv.org/abs/0804.0802v2