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.
In 2003, Kobayashi, Matsumoto, and Yamakami @cite_20 defined a generalization of @math called @math . Here there are @math Merlins, who send Arthur @math quantum proofs @math respectively that are guaranteed to be unentangled with each other. (Thus @math .) Notice that in the classical case, this generalization is completely uninteresting: we have @math for all @math , since we can always simulate @math Merlins by a single Merlin who sends Arthur a concatenation of the @math proofs. In the quantum case, however, a single Merlin could cheat by the @math proofs, and we know of no general way to detect such entanglement.
@cite_20
2951054288
This paper introduces quantum multiple-Merlin''-Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical multi-proof systems are obviously equivalent to classical single-proof systems (i.e., usual Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., usual quantum Merlin-Arthur proof systems). This paper presents a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.