Name
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? 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/CCC.2008.5 | IEEE Computer Society |
Keywords | DocType | Volume |
merlin-arthur,constant soundness,class qma,pcps,• we prove the nonexistence of "perfect disentanglers" for simulating multiple merlins with one. key words and phrases: quantum computing,quantum information theory,size n,pcp theorem,small error,log n,quantum proof,entanglement,unentangled quantum witness,3sat,k quantum proof,quantum computer,satisfiability,registers,additivity,quantum computing,chemistry,quantum entanglement,upper bound,quantum mechanics,computability,hilbert space,protocols,polynomials,information theory,computational complexity | Conference | 5 |
Issue | ISSN | Citations |
1 | 1093-0159 | 6 |
PageRank | References | Authors |
0.54 | 12 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Scott Aaronson | 1 | 1016 | 77.48 |
| Salman Beigi | 2 | 56 | 11.43 |
| Andrew Drucker | 3 | 172 | 11.57 |
| Bill Fefferman | 4 | 28 | 5.75 |
| Peter W. Shor | 5 | 3821 | 574.60 |