Qu-ants

Reversible cellular automata may be useful for design of quantum computers. It is common to consider Margolus block CA with 2×2 partitions, but second-order Fredkin CA may also generate interesting behavior. Second-order reversible CA may be derived from any irreversible CA. Number of states of such reversible CA is the square of an initial one (RCA with four states for two-states CA).

    

Let us consider two-states irreversible CA with the rule: current state of a cell is not taken into account and next state of the cell is alive if two conditions are satisfied: (1) number of live cells in four closest positions (up, down, left, right) is one or two, (2) four diagonal positions are empty. The rule itself is not very interesting, but reversible second-order CA with four states derived from that has rather rich behavior.

This RCA may be also described without reference to theory of second-order CA.  There are four states: 0 (empty, white), 1 (red), 2 (green), 3 (blue). A step may be divided into two stages:
First stage. Mark all cells satisfying two conditions:

1. total number of red and blue cells in four closest positions is one or two
2. cells in four diagonal positions are either white (empty) or green.

Second stage. Change unmarked red cells to green, unmarked green cells to red, marked empty cells to red, marked red cells to blue, marked green cells to empty, and marked blue cells to green.