#
Quantum Cellular Automata

Reinhard F. Werner (TU Braunschweig)

## Abstract

The idea of quantum cellular automata is clearly present already in the
work of Feynman. A satisfactory formal definition, however, was lacking so
far, if we require the following features: (1) A QCA is specified in terms
of a local transition rule, which readily determines and is in turn
determined by the global evolution time step. (2) There is an effective way
of verifying whether a proposed local rule is legitimate. (3) The same
local rule generates global transition rules for an infinite system but
also for any lattice with periodic boundary conditions. (4) The
concatenation of QCAs and the inverse of a QCA
is a QCA with appropriately enlarged neighbourhood scheme. (5) All
classical reversible CAs are restrictions of QCAs to the diagonal
subalgebra.

In this talk we present a satisfactory definition of reversible QCAs, and
show that all such QCAs are ``structurally reversible'' in the sense that
they can be represented by two steps of blockwise unitary operations for
suitable Margolus-type block decompositions.

ERATO QCI Project HOME |
EQIS'03 TOP |