text: The class QMA(k), introduced by , 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. First, 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 the existence of very short PCPs. Second, 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. Third, we prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.
  @cite_24: Introduction Classical computation Quantum computation Solutions Elementary number theory Bibliography Index.
  @cite_19: In this article we introduce a new complexity class called PQMA_log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts. We then show that PQMA_log(2) = NP. For this to be possible, it is important, when defining the class, not to give too much power to the verifier. This result, when compared to the fact that QMA_log = BQP, gives us new insight on the power of quantum information and the impact of entanglement.
  @cite_9: Does the notion of a quantum randomized or nondeterministic algorithm make sense, and if so, does quantum randomness or nondeterminism add power? Although reasonable quantum random sources do not add computational power, the discussion of quantum randomness naturally leads to several definitions of the complexity of quantum states. Unlike classical string complexity, both deterministic and nondeterministic quantum state complexities are interesting. A notion of is introduced for decision problems. This notion may be a proper extension of classical nondeterminism.
  @cite_23: The additivity conjecture of quantum information theory implies that entanglement cannot, even in principle, help to funnel more classical information through a quantum-communication channel. A counterexample shows that this conjecture is false.
summary: The class @math , or Quantum Merlin-Arthur, consists of all languages that admit a proof protocol in which Merlin sends Arthur a polynomial-size quantum state @math , and then Arthur decides whether to accept or reject in quantum polynomial time. This class was introduced by Knill @cite_9 , Kitaev @cite_24 , and Watrous @cite_23 as a quantum analogue of @math . By now we know a reasonable amount about @math : for example, it allows amplification of success probabilities, is contained in @math , and has natural complete promise problems. (See Aharonov and Naveh @cite_19 for a survey.)