The Power of Unentanglement
Abstract
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.
Additional Information
© 2009 Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. Received: April 22, 2008, Published: May 11, 2009. We thank Fernando Brandão for pointing out that our "Strong Amplification Conjecture" implies not only QMA(2) ⊆ PSPACE but QMA(2) = QMA, and that our original version of Lemma 4.3 contained a bug, among other extremely helpful comments; Norbert Schuch for pointing out that Theorem 4.5 can be based on a conjecture about entanglement of formation rather than squashed entanglement; Madhu Sudan for pointers on the PCP Theorem; John Watrous for posing Conjecture 5.2; an anonymous reviewer for greatly simplifying the proof of Lemma 4.3 and other help; and Patrick Hayden, Ryan O'Donnell, Alain Tapp, and Andreas Winter for helpful discussions.Attached Files
Published - Aaronson2009p6063Theory_Comput.pdf
Files
Name | Size | Download all |
---|---|---|
md5:b78999530693163c64beca02f53e1f82
|
486.2 kB | Preview Download |
Additional details
- Eprint ID
- 16400
- Resolver ID
- CaltechAUTHORS:20091020-132703748
- Massachusetts Institute of Technology
- NSF Integrative Graduate Education and Research Traineeship
- CCF-0829421
- NSF
- Akamai Presidential Graduate Fellowship
- Caltech Division of Engineering and Applied Science Fellowship
- CCF-0830787
- NSF
- CCF-0829909
- NSF
- Created
-
2009-10-26Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field