Universality of quantum Turing machines with deterministic control
Paulo Mateus, Amı́lcar Sernadas, André Souto · Journal of Logic and Computation · 2015
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.