Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Computational Complexity of Uniform Quantum Circuit Families and Quantum
  Turing Machines   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.

35
The categories of this paper are: mtrl-th
31
The categories of this paper are: ao-sci
34
The categories of this paper are: chem-ph
12
The categories of this paper are: nucl-th
10
The categories of this paper are: q-bio
19
The categories of this paper are: eess
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
8
The categories of this paper are: hep-ex
25
The categories of this paper are: patt-sol
28
The categories of this paper are: alg-geom
2
The categories of this paper are: math
27
The categories of this paper are: comp-gas
36
The categories of this paper are: cmp-lg
37
The categories of this paper are: supr-con
29
The categories of this paper are: funct-an