dorsal/arxiv
View SchemaPerfect Computational Equivalence between Quantum Turing Machines and Finitely Generated Uniform Quantum Circuit Families
| Authors | Harumichi Nishimura, Masanao Ozawa |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0511117 |
| URL | https://arxiv.org/abs/quant-ph/0511117 |
| DOI | 10.1007/s11128-008-0091-8 |
| Journal | Quant. Inf. Process. 8(1), pp. 13-24, 2009 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
In order to establish the computational equivalence between quantum Turing machines (QTMs) and quantum circuit families (QCFs) using Yao's quantum circuit simulation of QTMs, we previously introduced the class of uniform QCFs based on an infinite set of elementary gates, which has been shown to be computationally equivalent to the polynomial-time QTMs (with appropriate restriction of amplitudes) up to bounded error simulation. This result implies that the complexity class BQP introduced by Bernstein and Vazirani for QTMs equals its counterpart for uniform QCFs. However, the complexity classes ZQP and EQP for QTMs do not appear to equal their counterparts for uniform QCFs. In this paper, we introduce a subclass of uniform QCFs, the finitely generated uniform QCFs, based on finite number of elementary gates and show that the class of finitely generated uniform QCFs is perfectly equivalent to the class of polynomial-time QTMs; they can exactly simulate each other. This naturally implies that BQP as well as ZQP and EQP equal the corresponding complexity classes of the finitely generated uniform QCFs.
{
"annotation_id": "dff0a5f8-35c9-40a8-9c3c-ea6241fb2901",
"date_created": "2026-03-02T18:02:20.549000Z",
"date_modified": "2026-03-02T18:02:20.549000Z",
"file_hash": "185a3597aa9abcd652f63c7fb0c8b6f2af54cece06b765c5d890b26ce41687f2",
"private": false,
"record": {
"abstract": "In order to establish the computational equivalence between quantum Turing\nmachines (QTMs) and quantum circuit families (QCFs) using Yao\u0027s quantum circuit\nsimulation of QTMs, we previously introduced the class of uniform QCFs based on\nan infinite set of elementary gates, which has been shown to be computationally\nequivalent to the polynomial-time QTMs (with appropriate restriction of\namplitudes) up to bounded error simulation. This result implies that the\ncomplexity class BQP introduced by Bernstein and Vazirani for QTMs equals its\ncounterpart for uniform QCFs. However, the complexity classes ZQP and EQP for\nQTMs do not appear to equal their counterparts for uniform QCFs. In this paper,\nwe introduce a subclass of uniform QCFs, the finitely generated uniform QCFs,\nbased on finite number of elementary gates and show that the class of finitely\ngenerated uniform QCFs is perfectly equivalent to the class of polynomial-time\nQTMs; they can exactly simulate each other. This naturally implies that BQP as\nwell as ZQP and EQP equal the corresponding complexity classes of the finitely\ngenerated uniform QCFs.",
"arxiv_id": "quant-ph/0511117",
"authors": [
"Harumichi Nishimura",
"Masanao Ozawa"
],
"categories": [
"quant-ph"
],
"doi": "10.1007/s11128-008-0091-8",
"journal_ref": "Quant. Inf. Process. 8(1), pp. 13-24, 2009",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Perfect Computational Equivalence between Quantum Turing Machines and Finitely Generated Uniform Quantum Circuit Families",
"url": "https://arxiv.org/abs/quant-ph/0511117"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8c2dd0e7-b320-4626-8b3d-643d487eb492",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}