[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!

[XelaP]

It looks to me like James Camancho is wrong, as I pointed out in my comment there. Regardless if he is correct or not, it is in my opinion a terrible explanation if you only know basic quantum mechanics, and also not good even if you have a fair bit more background.

Here is my relatively short explanation of the argument:

James Camancho is arguing that because the symmetries of relativity in 1D must act on quantum states in a simple way. Namely, you should be able to split into subspaces, where in each subspace you just multiply by for angle (giving the angle in the symmetry group) and constant depending only on the subspace. He then says that must be rational to have a finite number of rules.

I disagree—nobody said the cellular automaton’s rules had to be symmetry transformations of the space. Additionally, nobody said the space is 1D—the dimension of the cellular automata you are talking about is just that you have a 1D “tape” of states, not that the states themselves are wavefunctions in 1D. For example, if you were imagining qubits implemented as spin states, then that’s definitely not 1D wavefunctions.

Even if I’m missing something and he’s right anyways, you should note that this would only be about what you can implement in our universe. A different physics could have different symmetries, and thus different representations. Some variant symmetries and representations are even proposed extensions to the current settled science!

More details:

The physical laws of the universe are invariant under certain symmetries, and studying the implications of this fact is quite important to modern physics. If it’s a symmetry then it should be invertible; and the observation probabilities |<x|y>|^2 for normalized states must be the same. In other words if we take two states, normalize, and compute |<x|y>| we should get the same thing before and after transforming. But then by Wigner’s theorem there is a unique (up to global phase scale) unitary or antiunitary transformation (as in, <Ux|Uy> = <x|y> - or for antiunitary it’s the conjugate) that gives the same transformation.^[1] It’s an easy exercise to show that a surjective unitary transformation between inner product spaces must be linear (otherwise I think it must be antilinear). Regardless, we have what’s called a projective unitary representation, meaning our symmetries act on projective space by unitary operators.

A representation is a group acting on a vector space via linear transformations.

Alright, now we can look at the projective representations of the symmetries that relativity implies (called the Poincare group, which has translations (and time translations) and rotations along with Lorentz boosts). Details in footnote^[2].

The projective representations of the 1D version of the Poincare group’s universal cover are apparently of the simple form mentioned earlier.

1. ^

   This is usually written in ‘projective space’, which means you consider two vectors the same when they differ only by a nonzero scale factor—because wavefunctions that differ by a global scale factor aren’t physically different.

2. ^

   We have a problem—projective representations are annoying. Well, if we basically look at the derivative we get a linear algebra thing, which can be easily deprojectivized. Then, we can basically integrate. However, the derivatives only capture the local structure, and will thus “not see” any global problems—for example, the circle and the real line both have the same tangent space at the origin, but the circle ‘curves’ in. If we just integrate, we’ll get the real line. In general we’ll get the version of the circle without any ‘loops’ that can’t be shrunk down continuously to a point. That is, we want the universal cover, which is the simply connected (meaning all loops can be shrunk) space that locally looks like a bunch of copies of the symmetries. For example, the universal cover of the circle is a ‘helix’ that projects down to the circle.

[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.)