# Watrous’s definition of Quantum Cellular Automata

I need some help understanding the second-to-last and final equations of the introduction to quantum cellular automata included below. My specific questions:

• What does it mean when the capital Pi multiplier doesn't have a number above it? Does it just mean for all numbers in the set 'i'? I'm wondering the same thing about the Sigma sign too.
• What does delta(a,b) stand for? I gathered that that equation is basically saying the probabilities of all the cells in a generation being on or off are given by the multiplication of the operation of the ruleset on all the cells, where the states of the neighboring cells and the probabilities of the given cell are taken into account.

I'm pretty lost in the second two equations (I understand the first two mappings), so I'd love it if someone could help.

## 1 Answer

In the classical example given, the rule $\boxed•\boxed•\boxed{\phantom{•}}\to\boxed•$ means that if the symbols at three adjacent positions $i-1$, $i$, and $i+1$ at time $t$ are $\boxed•$, $\boxed•$, and $\boxed{\phantom{•}}$, then the symbol at position $i$ at time $t+1$ will be $\delta(\boxed•,\boxed•,\boxed{\phantom{•}})=\boxed•$. To completely describe a deterministic nearest-neighbor cellular automata with two symbols $\boxed{\phantom{•}}$ and $\boxed•$ (nearest neighbor means the future state of a cell depends only on the cell's state and the state of its two neighbors), a total of eight rules must be given, one for each possible state of a cell and its two neighbors; just one of those eight rules is mentioned here.

If we draw the evolution of an automata with rule $\boxed•\boxed•\boxed{\phantom{•}}\to\boxed•$ as a two-dimensional pattern with time progressing downward (as in the PDF you link to), the subpattern $\genfrac{}{}{0pt}{}{\boxed•\boxed•\boxed{\phantom{•}}}{\boxed•}$ can appear, but $\genfrac{}{}{0pt}{}{\boxed•\boxed•\boxed{\phantom{•}}}{\boxed{\phantom{•}}}$ cannot.

If the configuration $\boxed•\boxed•\boxed{\phantom{•}}$ appears somewhere at time $t$, then the middle symbol at time $t+1$ must be $\boxed•$, and with probability $1$, since the system is deterministic.

In the quantum system, what happens to the middle symbol of $\boxed•\boxed•\boxed{\phantom{•}}$ between time $t$ and $t+1$ is not completely determined. It might be (as in your example) more likely to be $\boxed•$ than $\boxed{\phantom{•}}$. For a non-deterministic (quantum) automaton, we associate to the pattern $\boxed•\boxed•\boxed{\phantom{•}}$ a unit vector in “$\boxed•$-$\boxed{\phantom{•}}$ space.” (In the deterministic example, we do exactly the same thing, but the unit vector is always $1\cdot\boxed•+0\cdot\boxed{\phantom{•}}$ or $0\cdot\boxed•+1\cdot\boxed{\phantom{•}}$.) For reasons I can't explain (some Hilbert space thing), the coefficients of this unit vector can be complex numbers, not just real numbers.

Similarly, we associate vectors to all the possible patterns $(a_{i-1},a_i,a_{i+1})$ of three symbols, which gives us the update rule $\delta:Q\times Q\times Q\to \mathbb C\cdot\boxed•\oplus \mathbb C\cdot\boxed{\phantom{•}}$.

Instead of saying $\delta(a_{i-1},a_i,a_{i+1})= x\cdot\boxed•+y\cdot\boxed{\phantom{•}}$, we can say $\delta(a_{i-1},a_i,a_{i+1},\boxed•)= x$ and $\delta(a_{i-1},a_i,a_{i+1},\boxed{\phantom{•}})= y$, which is the way it’s done here. Either formulation of $\delta$ can describe a non-deterministic transition rule.

To emphasize that the first three parameters of $\delta$ are at time $t$ and the last is at time $t+1$, I'll write the first three parameters without commas.

For simplicity (i.e., because I don't know how to explain things otherwise), assume that a blank ($\boxed{\phantom{•}}$) symbol always stays blank at the next time step if its neighbors are blank. In other words, $\delta(\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}},\boxed{\phantom{•}})=1$ and $\delta(\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}},\boxed•)=0$

Now suppose we want to know what happens to the configuration $\cdots\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•.\boxed•\boxed{\phantom{•}}\boxed•\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}}\cdots$, (where the $.$ simply marks the origin). Thinking probabilistically, we get $\cdots\genfrac{}{}{0pt}{}{\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•.\boxed•\boxed{\phantom{•}}\boxed•\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}}}{\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•\boxed•.\boxed•\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•\boxed{\phantom{•}}\boxed{\phantom{•}}}\cdots$ if (working from the left) the middle symbol of $\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}}$ became $\boxed{\phantom{•}}$, the middle symbol of $\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•$ became $\boxed•$, the middle symbol of $\boxed{\phantom{•}}\boxed•.\boxed•$ became $\boxed•$, and so on. The probability of this happening is the product of the separate transition probabilities: $\delta(\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}},\boxed{\phantom{•}})\delta(\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•,\boxed•)\delta(\boxed{\phantom{•}}\boxed•\boxed•,\boxed•)\delta(\boxed•\boxed•\boxed{\phantom{•}},\boxed•)\delta(\boxed•\boxed{\phantom{•}}\boxed•,\boxed{\phantom{•}})\delta(\boxed{\phantom{•}}\boxed•\boxed{\phantom{•}},\boxed{\phantom{•}})\delta(\boxed•\boxed{\phantom{•}}\boxed{\phantom{•}},\boxed•)\delta(\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}},\boxed{\phantom{•}})$

This is what your PDF calls $\Delta(\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•.\boxed•\boxed{\phantom{•}}\boxed•\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed{\phantom{•}},\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•\boxed•.\boxed•\boxed{\phantom{•}}\boxed{\phantom{•}}\boxed•\boxed{\phantom{•}}\boxed{\phantom{•}})$. Again, I've added a period to mark the origin.

(Added, since I forgot to mention the last equation when I first posted this):

Remember how I first described a function $\delta$ that took each triple of symbols to a vector in “$\boxed•$-$\boxed{\phantom{•}}$ space,” and then noted that your PDF expresses the same information with a function $\delta$ that takes a triple and another symbol and gives a complex number?

Well, if we do the opposite, we can go from $\Delta$, which is a function that takes two sequences of symbols to one complex number and turn it into a function $T$ that takes one sequence and gives all the complex numbers $\Delta(s_t,s_{t+1})$ as one infinite linear combination of all the second sequences. The so-called “ket” notation $|s\rangle$ indicates the basis vector corresponding to $s$. (In other words, where I wrote $x\cdot\boxed•+y\cdot\boxed{\phantom{•}}$ above, I could (should?) have written $x\cdot|\boxed•\rangle+y\cdot|\boxed{\phantom{•}}\rangle$.

Hope that helps.
Anyone who does quantum automata for a living is welcome to elaborate or correct my answer.