The Power of Unentanglement

Details The Power of Unentanglement The Power of Unentanglement

2008-04-04

arxiv.org/abs/0804.0802v2

Physics

Quantum Physics

Several errors fixed; based amplification result on "Weak Additivity Conjecture" rather than now-falsified Additivity Conjectu

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Power of Unentanglement does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Power of Unentanglement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Power of Unentanglement will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-269986