Quantum Certificate Verification: Single versus Multiple Quantum Certificates

摘要

The class MA consists of languages that can be efficiently verified byclassical probabilistic verifiers using a single classical certificate, and theclass QMA consists of languages that can be efficiently verified by quantumverifiers using a single quantum certificate. Suppose that a verifier receivesnot only one but multiple certificates. In the classical setting, it is obviousthat a classical verifier with multiple classical certificates is essentiallythe same with the one with a single classical certificate. However, in thequantum setting where a quantum verifier is given a set of quantum certificatesin tensor product form (i.e. each quantum certificate is not entangled withothers), the situation is different, because the quantum verifier might utilizethe structure of the tensor product form. This suggests a possibility ofanother hierarchy of complexity classes, namely the QMA hierarchy. From thispoint of view, we extend the definition of QMA to QMA(k) for the case quantumverifiers use k quantum certificates, and analyze the properties of QMA(k). To compare the power of QMA(2) with that of QMA(1) = QMA, we show oneinteresting property of ``quantum indistinguishability''. This gives a strongevidence that QMA(2) is more powerful than QMA(1). Furthermore, we show that,for any fixed positive integer $k \geq 2$, if a language L has a one-sidedbounded error QMA(k) protocol with a quantum verifier using k quantumcertificates, L necessarily has a one-sided bounded error QMA(2) protocol witha quantum verifier using only two quantum certificates.