dorsal/arxiv
View SchemaQuantum Certificate Verification: Single versus Multiple Quantum Certificates
| Authors | Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0110006 |
| URL | https://arxiv.org/abs/quant-ph/0110006 |
Abstract
The class MA consists of languages that can be efficiently verified by classical probabilistic verifiers using a single classical certificate, and the class QMA consists of languages that can be efficiently verified by quantum verifiers using a single quantum certificate. Suppose that a verifier receives not only one but multiple certificates. In the classical setting, it is obvious that a classical verifier with multiple classical certificates is essentially the same with the one with a single classical certificate. However, in the quantum setting where a quantum verifier is given a set of quantum certificates in tensor product form (i.e. each quantum certificate is not entangled with others), the situation is different, because the quantum verifier might utilize the structure of the tensor product form. This suggests a possibility of another hierarchy of complexity classes, namely the QMA hierarchy. From this point of view, we extend the definition of QMA to QMA(k) for the case quantum verifiers 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 one interesting property of ``quantum indistinguishability''. This gives a strong evidence 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-sided bounded error QMA(k) protocol with a quantum verifier using k quantum certificates, L necessarily has a one-sided bounded error QMA(2) protocol with a quantum verifier using only two quantum certificates.
{
"annotation_id": "8b231538-3a40-4500-88c8-ef77d7810001",
"date_created": "2026-03-02T18:01:46.079000Z",
"date_modified": "2026-03-02T18:01:46.079000Z",
"file_hash": "517f210e64a62c5801c5688046acc26f6bcc5af97996a5636d4a71d6e4beb03f",
"private": false,
"record": {
"abstract": "The class MA consists of languages that can be efficiently verified by\nclassical probabilistic verifiers using a single classical certificate, and the\nclass QMA consists of languages that can be efficiently verified by quantum\nverifiers using a single quantum certificate. Suppose that a verifier receives\nnot only one but multiple certificates. In the classical setting, it is obvious\nthat a classical verifier with multiple classical certificates is essentially\nthe same with the one with a single classical certificate. However, in the\nquantum setting where a quantum verifier is given a set of quantum certificates\nin tensor product form (i.e. each quantum certificate is not entangled with\nothers), the situation is different, because the quantum verifier might utilize\nthe structure of the tensor product form. This suggests a possibility of\nanother hierarchy of complexity classes, namely the QMA hierarchy. From this\npoint of view, we extend the definition of QMA to QMA(k) for the case quantum\nverifiers use k quantum certificates, and analyze the properties of QMA(k).\n To compare the power of QMA(2) with that of QMA(1) = QMA, we show one\ninteresting property of ``quantum indistinguishability\u0027\u0027. This gives a strong\nevidence that QMA(2) is more powerful than QMA(1). Furthermore, we show that,\nfor any fixed positive integer $k \\geq 2$, if a language L has a one-sided\nbounded error QMA(k) protocol with a quantum verifier using k quantum\ncertificates, L necessarily has a one-sided bounded error QMA(2) protocol with\na quantum verifier using only two quantum certificates.",
"arxiv_id": "quant-ph/0110006",
"authors": [
"Hirotada Kobayashi",
"Keiji Matsumoto",
"Tomoyuki Yamakami"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Quantum Certificate Verification: Single versus Multiple Quantum Certificates",
"url": "https://arxiv.org/abs/quant-ph/0110006"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "eab671ff-982f-4a13-93c8-26cf5f60c118",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}