Recent paper on reversible quantum CAs
Ross Rhodes
B. Schumacher (Kenyon College); R.F. Werner (Inst. Math. Phys.,
Braunschweig), "Reversible quantum cellular automata"
http://www.arxiv.org/abs/quant-ph/0405174
Abstract:
We define quantum cellular automata as infinite quantum lattice systems with
discrete time dynamics, such that the time step commutes with lattice
translations and has strictly finite propagation speed. In contrast to
earlier definitions this allows us to give an explicit characterization of
all local rules generating such automata. The same local rules also generate
the global time step for automata with periodic boundary conditions. Our
main structure theorem asserts that any quantum cellular automaton is
structurally reversible, i.e., that it can be obtained by applying two
blockwise unitary operations in a generalized Margolus partitioning scheme.
This implies that, in contrast to the classical case, the inverse of a
nearest neighbor quantum cellular automaton is again a nearest neighbor
automaton.
We present several construction methods for quantum cellular automata, based
on unitaries commuting with their translates, on the quantization of
(arbitrary) reversible classical cellular automata, on quantum circuits, and
on Clifford transformations with respect to a description of the single
cells by finite Weyl systems. Moreover, we indicate how quantum random walks
can be considered as special cases of cellular automata, namely by
restricting a quantum lattice gas automaton with local particle number
conservation to the single particle sector.
Includes references to Wolfram and Zuse.
- - - - - - - - - - - - - - - - - - - - - - - -
His
Rho...@BottomLayer.com
Mark
- - - - - - - - - - - - - - - - - - - - - - - -
Ross Rhodes <www.bottomlayer.com>
Ross Rhodes
> Interesting topic:
> B. Schumacher (Kenyon College); R.F. Werner (Inst. Math. Phys.,
> Braunschweig), "Reversible quantum cellular automata"
> http://www.arxiv.org/abs/quant-ph/0405174
<snip>
Follow up commentary posted to arXiv.
Alexander Yu. Vlasov (Federal Radiological Center, St. Petersburg, Russia
[friend of Plamen's?], "On Quantum Cellular Automata"
http://www.arxiv.org/abs/quant-ph/0406119
Refers directly to Ed Fredkin's second-order CAs.
Abstract:
In recent work [quant-ph/0405174] by Schumacher and Werner was discussed an
abstract algebraic approach to a model of reversible quantum cellular
automata (CA) on a lattice. It was used special model of CA based on
partitioning scheme and so there is a question about quantum CA derived from
more general, standard model of classical CA. In present work is considered
an approach to definition of a scheme with "history", valid for quantization
both irreversible and reversible classical CA directly using local
transition rules. It is used language of vectors in Hilbert spaces instead
of C*-algebras, but results may be compared in some cases. Finally, the
quantum lattice gases, quantum walk and "bots" are also discussed briefly.