CaltechAUTHORS
  A Caltech Library Service

The Power of Unentanglement

Aaronson, Scott and Beigi, Salman and Drucker, Andrew and Fefferman, Bill and Shor, Peter (2009) The Power of Unentanglement. Theory of Computing, 5 (Articl). pp. 1-42. ISSN 1557-2862. https://resolver.caltech.edu/CaltechAUTHORS:20091020-132703748

[img]
Preview
PDF - Published Version
Creative Commons Attribution.

474Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20091020-132703748

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.4086/toc.2009.v005a001DOIUNSPECIFIED
http://www.theoryofcomputing.org/articles/v005a001/PublisherUNSPECIFIED
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.
Funders:
Funding AgencyGrant Number
Massachusetts Institute of TechnologyUNSPECIFIED
NSF Integrative Graduate Education and Research TraineeshipUNSPECIFIED
NSFCCF-0829421
Akamai Presidential Graduate FellowshipUNSPECIFIED
Caltech Division of Engineering and Applied Science FellowshipUNSPECIFIED
NSFCCF-0830787
NSFCCF-0829909
Subject Keywords:quantum computing, PCPs, entanglement, Merlin-Arthur, 3SAT
Issue or Number:Articl
Classification Code:ACM Classification: F.1.2, F.1.3; AMS Classification: 81P68, 68Q15, 68Q17
Record Number:CaltechAUTHORS:20091020-132703748
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20091020-132703748
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:16400
Collection:CaltechAUTHORS
Deposited By: Joy Painter
Deposited On:26 Oct 2009 20:33
Last Modified:03 Oct 2019 01:11

Repository Staff Only: item control page