Berlin 2005 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

Q: Quantenoptik und Photonik

Q 3: Poster Quanteninformation, -kommunikation und Quantencomputer

Q 3.7: Poster

Freitag, 4. März 2005, 11:00–12:30, Poster HU

Computational equivalence of quantum Turing machines and quantum cellular automata — •Torsten Franz and Reinhard F. Werner — Institut für Mathematische Physik, TU Braunschweig, www.imaph.tu-bs.de

Turing machines and cellular automata are two computational models, which in the classical case are known to be equivalent to within polynomial bounds. Here we show how a quantum Turing machine can be considered as a special kind of quantum cellular automaton. On the other hand, we show how to simulate the parallelism of quantum cellular automata by a sequential quantum computation. The relationship to other computational models, such as the one-way computer, the gate model, and adiabatic computation is discussed.