dorsal/arxiv
View SchemaComputational Complexity of Uniform Quantum Circuit Families and Quantum Turing Machines
| Authors | Harumichi Nishimura, Masanao Ozawa |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9906095 |
| URL | https://arxiv.org/abs/quant-ph/9906095 |
| Journal | Theor.Comput.Sci. 276 (2002) 147-181 |
Abstract
Deutsch proposed two sorts of models of quantum computers, quantum Turing machines (QTMs) and quantum circuit families (QCFs). In this paper we explore the computational powers of these models and re-examine the claim of the computational equivalence of these models often made in the literature without detailed investigations. For this purpose, we formulate the notion of the codes of QCFs and the uniformity of QCFs by the computability of the codes. Various complexity classes are introduced for QTMs and QCFs according to constraints on the error probability of algorithms or transition amplitudes. Their interrelations are examined in detail. For Monte Carlo algorithms, it is proved that the complexity classes based on uniform QCFs are identical with the corresponding classes based on QTMs. However, for Las Vegas algorithms, it is still open whether the two models are equivalent. We indicate the possibility that they are not equivalent. In addition, we give a complete proof of the existence of a universal QTM simulating multi-tape QTMs efficiently. We also examine the simulation of various types of QTMs such as multi-tape QTMs, single tape QTMs, stationary, normal form QTMs (SNQTMs), and QTMs with the binary tapes. As a result, we show that these QTMs are computationally equivalent one another as computing models implementing not only Monte Carlo algorithms but exact (or error-free) ones.
{
"annotation_id": "fe7cd835-ee7f-4926-b565-b7645295ea7b",
"date_created": "2026-03-02T18:02:48.361000Z",
"date_modified": "2026-03-02T18:02:48.361000Z",
"file_hash": "64043d853fa308bab340288c489082b92261264c2dba76d970a328fe17765c33",
"private": false,
"record": {
"abstract": "Deutsch proposed two sorts of models of quantum computers, quantum Turing\nmachines (QTMs) and quantum circuit families (QCFs). In this paper we explore\nthe computational powers of these models and re-examine the claim of the\ncomputational equivalence of these models often made in the literature without\ndetailed investigations. For this purpose, we formulate the notion of the codes\nof QCFs and the uniformity of QCFs by the computability of the codes. Various\ncomplexity classes are introduced for QTMs and QCFs according to constraints on\nthe error probability of algorithms or transition amplitudes. Their\ninterrelations are examined in detail. For Monte Carlo algorithms, it is proved\nthat the complexity classes based on uniform QCFs are identical with the\ncorresponding classes based on QTMs. However, for Las Vegas algorithms, it is\nstill open whether the two models are equivalent. We indicate the possibility\nthat they are not equivalent. In addition, we give a complete proof of the\nexistence of a universal QTM simulating multi-tape QTMs efficiently. We also\nexamine the simulation of various types of QTMs such as multi-tape QTMs, single\ntape QTMs, stationary, normal form QTMs (SNQTMs), and QTMs with the binary\ntapes. As a result, we show that these QTMs are computationally equivalent one\nanother as computing models implementing not only Monte Carlo algorithms but\nexact (or error-free) ones.",
"arxiv_id": "quant-ph/9906095",
"authors": [
"Harumichi Nishimura",
"Masanao Ozawa"
],
"categories": [
"quant-ph"
],
"journal_ref": "Theor.Comput.Sci. 276 (2002) 147-181",
"title": "Computational Complexity of Uniform Quantum Circuit Families and Quantum Turing Machines",
"url": "https://arxiv.org/abs/quant-ph/9906095"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "fde146ea-62c2-4df0-bb30-003db0a3b3df",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}