dorsal/arxiv
View SchemaIdentity check is QMA-complete
| Authors | Dominik Janzing, Pawel Wocjan, Thomas Beth |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0305050 |
| URL | https://arxiv.org/abs/quant-ph/0305050 |
Abstract
We define the problem identity check: Given a classical description of a quantum circuit, determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is equivalence check: Given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that equivalence check is also in QMA and hence QMA-complete.
{
"annotation_id": "687fc1ec-0c3c-4340-8533-ac9b379bf1cc",
"date_created": "2026-03-02T18:01:59.409000Z",
"date_modified": "2026-03-02T18:01:59.409000Z",
"file_hash": "12b4c6faee63744b95e1015f3e40d2269ef4ff140b72378dbd15fcd6dd0790af",
"private": false,
"record": {
"abstract": "We define the problem identity check: Given a classical description of a\nquantum circuit, determine whether it is almost equivalent to the identity.\nExplicitly, the task is to decide whether the corresponding unitary is close to\na complex multiple of the identity matrix with respect to the operator norm. We\nshow that this problem is QMA-complete.\n A generalization of this problem is equivalence check: Given two descriptions\nof quantum circuits and a description of a common invariant subspace, decide\nwhether the restrictions of the circuits to this subspace almost coincide. We\nshow that equivalence check is also in QMA and hence QMA-complete.",
"arxiv_id": "quant-ph/0305050",
"authors": [
"Dominik Janzing",
"Pawel Wocjan",
"Thomas Beth"
],
"categories": [
"quant-ph"
],
"title": "Identity check is QMA-complete",
"url": "https://arxiv.org/abs/quant-ph/0305050"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7d1fa833-b78a-4f6f-be9a-42dd5a22a202",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}