2008 IEEE 23rd Annual Conference on Computational Complexity The Power of Unentanglement June 22-June 26 ISBN: 978-0-7695-3169-4
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2008.5
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. *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. *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. *We give evidence that QMA(2) is contained in PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.
Index Terms:
quantum computing, entanglement, QMA, additivity, 3SAT, PCP Theorem
Citation:
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor, "The Power of Unentanglement," ccc, pp.223-236, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||