Workshop on QUANTUM INFORMATION PROCESSING AND QUANTUM COMMUNICATIONS

Quantum Information Processing and Quantum Communications
Quantum Cellular automata, Random walks, and Turing
machines

aula 102  Martedì 1 giugno ore 15.00 

REINHARDT WERNER, Technical University of Braunschweig 
>VITAE:
Professor at the Technical University of Braunschweig, is the leader of
a research group on quantum information theory. He studied in Marburg,
in the group of G. Ludwig, and has been working on the conceptual and
mathematical foundations of quantum theory, including quantum statistical
mechanics. He is expecially known among physicists of Quantum Information
for his studies on quantum cloning, capacities of channels, quantum error
correction, and entanglement. Author of popular reviews
of Quantum Information.


Abstract 


The notion of quantum cellular automata is expressed most
naturally in the language of observable algebras. We present a general theory,
allowing a decomposition of arbitrary quantum cellular automata into two
steps of unitary transformations acting on local blocks. General construction
methods are presented, including the quantization of reversible classical
cellular automata, and the second quantization of random walks. Quantum
random walks (see e.g., the recent review of J. Kempe) are shown to be special
cases of quantum cellular automata, restricted to a subspace of configurations
withonly one particle present. Similarly, quantum turing machines are shown
to be special cellular automata, proving that quantum cellular automata
are capable of universal quantum computation. 

