Margolus Cellular Automaton

The problem with quantum-mechanical descriptions of cellular automata is one of synchronization. Each site of the automaton may only make a step forward in time if the neighboring sites have caught up, i.e., they have evolved by the same number of steps. In a locally connected system, this synchronization also has to be done locally. Here we describe, how to achieve synchrony with Feynman s trick for a special kind of cellular automaton [23]. 

Consider a one-dimensional automaton with k sites 0,1. A — 1. It has a cyclic architecture, i.e. site 0 and site k — 1 are neighbors. First look at non-overlapping blocks of two adjacent sites. The left site in each block has an even, the right site an odd index. Update these blocks separately by a unitary transformation D, which works locally, i.e. only on the two bits within each block. Then look at those two-bit blocks where the right site in each block has an even, the left site an odd index. Update in the same way as before with another or the same unitary transformation. For this kind of computer, the Feynman trick can be used to achieve local synchrony in the following way. 

A control bit is assigned to each site. At the beginning of the computation, all control bits are set to 0). If the operator D acts on a pair of control bits, both are simply flipped, i.e., a 0) becomes a 11 and vice versa. The problem of synchrony now is that a block may only be updated if both of the associated control bits are set to I 0) for a block with an even index and to 11) for a block with an odd index. Clearly, this synchronization works only locally. It might well be that one part of the automaton has evolved much further than another. However, no block is updated before the bits within this block have the same computational age , i.e., have been updated the same number of times. 

To clarify these ideas, look at the following possible evolution of the control bits of an automaton with 8 sites, i = 0. 7. The time axis goes downwards. The index 

Two sites within one block are always updated at once. If a 0 turns into a 1, the corresponding i of the first site in the block was even. It was odd if a 1 turns into a 0. In this example, synchrony turned out to be only local, not global. In other words, adjacent sites may have different computational ages (no global synchrony), but the difference is only 1 and only bits with the same age have been updated (local synchrony). 

---

Several groups have developed cellular automata models for particular reaction-diffusion systems. In particular, the Belousov-Zhabotinsky oscillating reaction has been examined in a number of studies.84-86 Attention has also been directed at the A + B —> C reaction, using both lattice-gas models 87-90 and a generalized Margolus diffusion approach.91 We developed a simple, direct cellular automaton model92 for hard-sphere bimolecular chemical reactions of the form... 

---