You know elementary cellular automata, where each of the boolean-valued cells evolves according to 

where $f:\{0,1{\}}^3\to \{0,1\}$.

I think the natural quantum-mechanical extension of this is:

• there are $2^{\text{(N := tape size)}}$ basis states: $|00\cdots 00⟩$ through $|11\cdots 11⟩$
• its time-evolution is given, of course, by a unitary operator $U$, which, expressed in that basis, is:

• ...where $f:\{0,1{\}}^4\to C$.

You can take any elementary cellular automaton and quantum-ize it: just choose $f_{quantum}(a,b,c,z)=\left(\text{if}{f}_{classical}(a,b,c)=z\text{then 1 else 0}\right)$; then that product is 1 exactly when $y$ is the classical evolution of $x$. (Not every $f_{classical}$ gives rise to a unitary $U$, though; only the reversible ones.)

But... are there other unitary operators of this form, which aren't basically equivalent to reversible classical CAs? I think not, disappointingly, but I'm not sure, and I don't understand why not.

Bounty: $100 if you make me feel like I have a significantly deeper understanding of why all quantum elementary CAs are basically equivalent to classical elementary CAs (or show me I'm wrong and there actually is interesting behavior here). Partial payouts for partial successes.

My current understanding (the thing you have to enhance or beat) is:

• Any choice of $f$ is equivalent to a choice of eight complex two-vectors ${\overrightarrow{\lambda }}_{000},\cdots ,{\overrightarrow{\lambda }}_{111}$, each describing roughly "how (0/1)ish the next state of a cell should be given its current neighborhood."
• For unitarity, we want $⟨Ux|Uy⟩=⟨x|y⟩$ for all $x,y$. If you bang through some math, I think this inner product turns out to equal the product of all 64 possible inner products of the ${\overrightarrow{\lambda }}_{abc}$ s, raised to various powers: 

• ...where $N_{000,111}$ is the number of locations where the neighborhood on tape $x$ is 000 and the neighborhood on tape $y$ is 111. For $x=y$, we want this product to be 1; for $x\ne y$, we want this product to be 0, meaning at least one of the inner products with a nonzero $N$ must be zero.

  (Sanity check: if $x=y$, then $N_{abc,abc}=1$ and all the other $N$s are 0. The inner products raised to power 0 disappear; the remaining ones are ${\overrightarrow{\lambda }}_{abc}\cdot {\overrightarrow{\lambda }}_{abc}$, which is 1 as long as the $\overrightarrow{\lambda }$s are normalized, so we get $⟨Ux|Ux⟩=1$ practically for free. Great.)

  • (Note that not all the $N$s can be chosen independently: for example, if $N_{001,000}>0$, then evidently tape $x$ has some stretch of 0s ending in a 1; I'm imagining that the tape wraps around, so there must be a 1 on the left side of the stretch of 0s too; so some $N_{100,abc}$ must be positive too.)
• It feels like there must be some clever geometrical insight, here, but I can't find it. Instead, I just enumerated all possible $x,y$ for a small (4-cell) automaton, computed which $N$s were nonzero, and asked Z3 to find $\overrightarrow{\lambda }$s satisfying the huge pile of constraints (the AND of a bunch of ORs of clauses like "A dot B is zero") and "some $\overrightarrow{\lambda }$ is not parallel to ${\overrightarrow{\lambda }}_{000}$ or ${\overrightarrow{\lambda }}_{111}$". (I think that if there are just two mutually-perpendicular families of $\overrightarrow{\lambda }$, that's basically equivalent to a classical CA.)
• It... well, it didn't print "unsat," but it did hang, whereas, if I left out the interestingness constraint, it promptly spit out a satisfactory output. Shrug. This is my first time with Z3, so it might be a newbie mistake.