[Question] [bounty $100] Why are there no interesting (1D, 2-state) quantum cellular automata?

[Optimization Process]

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

$$x_{t+1}^{\left(k\right)}=f(x_t^{(k-1)},x_t^{\left(k\right)},x_t^{(k+1)})$$

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:

$$⟨y|U|x⟩=\prod _{k}f(x^{(k-1)},x^{\left(k\right)},x^{(k+1)},y^{\left(k\right)})$$

• ...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:

$$⟨Ux|Uy⟩=({\overrightarrow{\lambda }}_{000}\cdot {\overrightarrow{\lambda }}_{111}{)}^{N_{000,111}}\cdots ({\overrightarrow{\lambda }}_{000}\cdot {\overrightarrow{\lambda }}_{111}{)}^{N_{000,111}}$$

• ...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.

[Jordan Taylor]

There are many articles on quantum cellular automata. See for example “A review of Quantum Cellular Automata”, or “Quantum Cellular Automata, Tensor Networks, and Area Laws”.
I think compared to the literature you’re using an overly restrictive and nonstandard definition of quantum cellular automata. Specifically, it only makes sense to me to write $U$ as a product of operators like you have if all of the terms are on spatially disjoint regions.

Consider defining quantum cellular automata instead as local quantum circuits composed of identical two-site unitary operators everywhere:

If you define them like this, then basically any kind of energy and momentum conserving local quantum dynamics can be discretized into a quantum cellular automata, because any two-site time and space independent quantum Hamiltonian can be decomposed into steps with identical unitaries like this using the Suzuki-Trotter decomposition.

[James Camacho]

I think you’re looking for the irreducible representations of $\tilde{I}so(n,1)$. I’ll come back and explain this later, but it’s going to take awhile to write up.