dorsal/arxiv
View SchemaNQP_{C} = co-C_{=}P
| Authors | Tomoyuki Yamakami, Andrew C. Yao |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9812032 |
| URL | https://arxiv.org/abs/quant-ph/9812032 |
| Journal | Inform.Proc.Lett. 71 (1999) 63-69 |
Abstract
Adleman, DeMarrais, and Huang introduced the nondeterministic quantum polynomial-time complexity class NQP as an analogue of NP. Fortnow and Rogers implicitly showed that, when the amplitudes are rational numbers, NQP is contained in the complement of C_{=}P. Fenner, Green, Homer, and Pruim improved this result by showing that, when the amplitudes are arbitrary algebraic numbers, NQP coincides with co-C_{=}P. In this paper we prove that, even when the amplitudes are arbitrary complex numbers, NQP still remains identical to co-C_{=}P. As an immediate corollary, BQP differs from NQP when the amplitudes are unrestricted.
{
"annotation_id": "c0a50cc9-f40d-4ebc-bc22-76b8289bc090",
"date_created": "2026-03-02T18:02:44.487000Z",
"date_modified": "2026-03-02T18:02:44.487000Z",
"file_hash": "b68b363bf052aa033be4d24274bc4658f6106507d45ff3ab00c3ed12f953a41b",
"private": false,
"record": {
"abstract": "Adleman, DeMarrais, and Huang introduced the nondeterministic quantum\npolynomial-time complexity class NQP as an analogue of NP. Fortnow and Rogers\nimplicitly showed that, when the amplitudes are rational numbers, NQP is\ncontained in the complement of C_{=}P. Fenner, Green, Homer, and Pruim improved\nthis result by showing that, when the amplitudes are arbitrary algebraic\nnumbers, NQP coincides with co-C_{=}P. In this paper we prove that, even when\nthe amplitudes are arbitrary complex numbers, NQP still remains identical to\nco-C_{=}P. As an immediate corollary, BQP differs from NQP when the amplitudes\nare unrestricted.",
"arxiv_id": "quant-ph/9812032",
"authors": [
"Tomoyuki Yamakami",
"Andrew C. Yao"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "Inform.Proc.Lett. 71 (1999) 63-69",
"title": "NQP_{C} = co-C_{=}P",
"url": "https://arxiv.org/abs/quant-ph/9812032"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b19f8893-3c4e-4ef0-b113-cd9f3391c797",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}