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.