Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Simulations of Quantum Turing Machines by Quantum Multi-Counter Machines

Edit abstract data

Speaker: Daowen Qiu
Slot: Mon, 11:40-12:00, Drakopoulos (col. 1)


We establish a kind of quantum multi-stack machines and quantum
multi-counter machines, and use them  to simulate quantum Turing
machines. The major technical contributions are stated as follows:
(i) We define {\it quantum multi-stack machines} (abbr. QMSMs) by
generalizing a kind of {\it quantum pushdown automata} (abbr.
QPDAs), and the {\it well-formedness} (abbr. W-F) conditions for
characterizing the unitary evolution of the QMSMs are presented.
(ii) By means of QMSMs we define {\it quantum multi-counter
machines} (abbr. QMCMs) whose state transition functions are
different from the {\it quantum counter automata} (abbr. QCAs) in
the literature. (iii) To simulate {\it quantum Turing machines}
(abbr. QTMs),  we show that any given QMCM allowed to count with
$\pm n$ for $n>1$ can be simulated by another QMCM that counts
with $0,\pm 1$ only. (iv) We demonstrate the efficient simulations
of QTMs in terms of QMSMs, and show that QTMs can be simulated by
QMCMs as well.

websites: Arnold Beckmann 2008-05-19 Valid HTML 4.01! Valid CSS!