Universality of quantum Turing machines with deterministic control
Souto, A.
;
Sernadas, A.
;
Mateus, P.
Journal of Logic and Computation Vol. 1, Nº 1, pp. 1 - 1, February, 2015.
ISSN (print): 0955-792X
ISSN (online): 1465-363X
Scimago Journal Ranking: 0,38 (in 2015)
Digital Object Identifier: 10.1093/logcom/exv008
Abstract
A simple notion of quantum Turing machine with deterministic, classical control is proposed and shown to be powerful enough to compute any unitary transformation that is computable by a finitely generated quantum circuit. An efficient universal machine with the s-m-n property is presented. The BQP class is recovered. A robust notion of plain Kolmogorov complexity of quantum states is proposed and compared with those previously reported in the literature.
