2008 · 27 citations · 27 references
ComputingComputer ScienceMathematicsInformation TheoryQuantum ComputingTheory Of ComputationQuantum BitsQuantum Complexity TheoryQuantum ComputationQuantum CryptographyQuantum Information TheoryAmplificationEntanglement WitnessesPcp ClassQmaQuantum Complexity ClassesQuantum Pcp ConjectureQuantum Proof VerificationSoundness
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 kges2? 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 tilde(radicn) 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 kges=2. *We give evidence that QMA(2) sube 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.
27
<i>Quantum Computation and Quantum Information</i>
Michael A. Nielsen, Isaac L. Chuang, Lov K. Grover · American Journal of Physics · 2002 · 22.7K citations
Quantum computation and quantum information
Jim Law · ACM SIGSOFT Software Engineering Notes · 2001 · 19.2K citations
Computing, Computer Science, Physics +13
Mixed-state entanglement and quantum error correction
Charles H. Bennett, David P. DiVincenzo, John A. Smolin et al. · Physical Review A · 1996 · 5.4K citations · Full text
‘‘Event-ready-detectors’’ Bell experiment via entanglement swapping
Marek Żukowski, Anton Zeilinger, M. A. Horne et al. · Physical Review Letters · 1993 · 2K citations · Full text