[Question] 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.

[Optimization Process]

I think compared to the literature you’re using an overly restrictive and nonstandard definition of quantum cellular automata.

That makes sense! I’m searching for the simplest cellular-automaton-like thing that’s still interesting to study. I may have gone too far in the “simple” direction; but I’d like to understand why this highly-restricted subset of QCAs is too simple.

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.

Hmm! That’s not obvious to me; if there’s some general insight like “no operator containing two ~‘partially overlapping’ terms like $\cdots \otimes |x⟩(⟨x|+⟨y|)\otimes |y⟩(⟨y|+⟨z|)\otimes \cdots$ can be unitary,” I’d happily pay for that!

[James Camacho]

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

[Optimization Process]

I’ve never been familiar enough with group-theory stuff to memorize the names (which, warning, also might mean that it will take you a lot of time to write a sufficiently-dumbed-down version), but the internet suggests $\tilde{I}so(n,1)$ is related to… the Minkowski metric? I would be flabbergasted to learn that something so specific-to-our-universe was relevant to this toy mathematical contraption.

[James Camacho]

I wrote up my explanation as its own post here: https://​​www.lesswrong.com/​​posts/​​LpcEstrPpPkygzkqd/​​fractals-to-quasiparticles

[Optimization Process]

I thank you for your effort! I am currently missing a lot of the mathematical background necessary to make that post make sense, but I will revisit it if I find myself with the motivation to learn!

[interstice]

I think the basic reason that it’s hard to make an interesting QCA using this definition is that it’s hard to make a reversible CA. Reversible cellular automata are typically made using block-partitioning or a second-order method. The (classical) laws of physics also seem to have a flavor more similar to these than a GoL-style CA, in that they have independent position and velocity coordinates which each determine the time evolution of the other.

[Ben]

After finding a Unitary that comes from one of your classical Cellular Automata then any power of that unitary will also be a valid unitary. So for example in classical logic their is a the “swap” gate for binary inputs, but in quantum computing the “square-root swap” gate also exists.

So you can get one of your existing unitary matrices, and (for example) take its square root. That would kind of be like a quantum system doing the classical Cellular Automata, that is interrupted halfway through the first step. (Because applying the root matrix twice is the same as applying the matrix). Similarly you can look at the 1/​3rd step by applying the cube root of the matrix.

So would you consider the square root matrix a quantum elementary CA? Its not exactly equivalent to anything classical, because classically you can’t look “between the steps”.

[This is a long winded way of me saying that I don’t “get” the question. You want a unitary, U, of the form given in that equation for <y|U|x>, but you also don’t want U to be “basically equivalent” to a classical CA. How are you defining “basically equivalent”, is anything satisfying your equation automatically “basically equivalent”?]

[Optimization Process]

This is a good point! I’ll send you $20 if you send me your PayPal/​Venmo/​ETH/​??? handle. (In my flailings, I’d stumbled upon this “fractional step” business, but I don’t think I thought about it as hard as it deserved.)

How are you defining “basically equivalent”

Nyeeeh, unfortunately, sort of “I know it when I see it.” It’s kinda neat being able to take a fractional step of a classical elementary CA, but I’m dissatisfied because… ah, because the long-run behavior of the fractional-step operator is basically indistinguishable from the long-run behavior of the corresponding classical CA.

So, tentative operationalization of “basically equivalent”: $U$ is “basically equivalent” to a classical elementary CA if the long-run behavior of $U$ is very close to the long-run behavior of some $U_{classical}$, i.e., uh,

$$\begin{array}{c}\forall n\in N,ϵ\in R^{+}:\\ \exists N>n,M\in N,U_{cl}:\\ |U^N-U_{cl}^M|<ϵ\end{array}$$

...but I can already think of at least one flaw in this operationalization, so, uh, I’m not sure. (Sorry! This being so fuzzy in my head is why I’m asking for help!)

[Ben]

Random thoughts. You can relatively simply get a global phase factor at each timestep if you want. I don;t think a global phase factor at each step really counts as meaningfully different though. Anyway, as an example of this:

$f(x_{k-1},x_k,x_{k+1})=x_{k-1}$

So that, at each (classical) timestep every single element of the CA tape just moves one step to the right. (So any patterns of 1′s and 0′s just orbit the tape in circles forever, unchanging.). Its quite a boring CA, but a simple example.

We can take the quantum CA that is exactly the same, but with some complex phase factor:

$f_q(x_{k-1},x_k,x_{k+1},y_k)={\delta }_{x_{k-1}}^{y_k}\exp \left(i\theta \right)$

Where the delta function is saying “1 iff $y_k=x_{k-1}$ , else 0.”

This is exactly the same as the old classical one (everything moves on step to the right), but this time we also have a global phase factor applied to the total system. The total phase factor is $\exp \left(i\theta N\right)$, where N is the total number of cells on the tape.

Tiny bit more interesting:

$f_q(x_{k-1},x_k,x_{k+1},y_k)={\delta }_{x_{k-1}}^{y_k}\exp \left(i\theta x_{k-1}\right)$

Now we only gain phase factors on values of 1, so the global phase depends on the total number of 1′s on the tape, rather than its length.

To get proper quantum stuff we need phase factors that are not global. (IE some relative phases). I feel like this equation below is a reasonable kind of place to start, but I have run out of time for now so might return to this later.

$f_q(x_{k-1},x_k,x_{k+1},y_k)=\left(1/\sqrt{2}\right)\left[{\delta }_{x_{k-1}}^{y_k}\exp \right(i\theta )+{\delta }_{x_{k+1}}^{y_k}\exp (-i\theta \left)\right]$

[deleted]

[the gears to ascension]

What is a concise intro that will teach me everything I need to know for understanding every expression here? I’m also asking Claude, interested in input from people with useful physics textbook taste

[Alfred Harwood]

When you are considering finite tape length, how do you deal with $x^{(k-1)}$ when $k=0$ or $x^{(k+1)}$ when $k=N$ ?

[Optimization Process]

I was imagining the tape wraps around! (And hoping that whatever results fell out would port straightforwardly to infinite tapes.)