# Quantum cellular automata

This questions is cross-posted from MathOverflow

A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use different definitions. Here I propose my own definition (though I probably consider it my own out of ignorance rather than originality). This definition seems very natural but immediately raises several questions which I find difficult to answer. Here I ask the two questions that seem the most fundumental. Here it goes:

Fix $V$ a complex inner product vector space of finite dimension $n$. Consider $A$ the *-algebra End($V$). Take $\Gamma = \mathbb{Z}^d$ a lattice. Define the *-algebra $A_\Gamma$ (quantum cellular automaton observables) in the following manner. Assign to each element $x$ of $\Gamma$ a copy $A_x$ of $A$. To each finite subset $S$ of $\Gamma$ we can correspond the *-algebra $A_S$ defined by

$A_S$ := Tensor product of $A_x$ over $x \in S$

For two finite subsets $S$, $R$ of $\Gamma$ with $S$ contained in $R$ we have the morphism

$i_{S,R}$: $A_S \rightarrow A_R$

obtained by tensoring with $1 \in A_y$ for all $y \in R\backslash S$. We define $A_\Gamma$ to be the direct limit of $A_S$ w.r.t. $S$.

Denote $T_\Gamma$ the group of translations of $\Gamma (Z^d)$. $T_\Gamma$ acts on $A_\Gamma$ in the obvious manner.

A quantum cellular automaton is defined to be a *-endomorphism of $A_\Gamma$ commuting with the action of $T_\Gamma$. An invertible quantum cellular automaton is defined to be a *-automorphism of $A_\Gamma$ commuting with the action of $T_\Gamma$. The 1st question is:

Are all quantum cellular automata invertible?

Any unit vector $v \in V$ defines a state

$\phi_v$: $A_\Gamma \rightarrow C$

in the following manner. Suppose $S$ is a finite subset of $\Gamma$ and for any $x \in S$, $a_x$ is an element of $A_x$. Then we have $a_S$ an element of $A_S$ (and hence of $A_\Gamma$) defined by

$a_S$ := tensor product of $a_x$ over $x \in S$

We then define

$\phi_v(a_S)$ := product of $(v, a_x v)$ over $x \in S$

It is easy to see this extends uniquely to a linear map $\phi_v$: $A_\Gamma \rightarrow C$ and that the map is a state.

Fix $v$ in $V$. We construct the Hilbert space $H_v$ in the following manner. Choose $v_1$ ... $v_n$ an orthonormal basis of $V$ s.t. $v_1 = v$. Consider maps

$\alpha: \Gamma \rightarrow \{1 ... n\}$

s.t. $\alpha(x) = 1$ for all $x$ except a finite set. Define $J$ to be the set of such $\alpha$. To each $\alpha \in J$ we assign the basis vector $\Psi_\alpha$ of $H_v$, thought of as

$\Psi_\alpha$ := tensor product of $v_\alpha(x)$ over $x \in \Gamma$

Thus $H_v$ is defined to be $l^2(J)$. It is easy to see that $H_v$ thus defined depends only on $v$ and not on $v_2$ ... $v_n$ i.e. that for any two choices of $v_2$ ... $v_n$, there is a canonical isomorphism between the corresponding Hilbert spaces.

There is a natural *-homomorphism

$\rho$: $A_\Gamma \rightarrow B(H_v)$

where $B(H_v)$ is the *-algebra of bounded operators on $H_v$. Thus, any unit vector $\Psi \in H_v$ defines a state

$\phi_\Psi$: $A_\Gamma \rightarrow C$

by

$\phi_\Psi(a) = (\Psi, \rho(a) \Psi)$

Now, fix an invertible quantum cellular automaton $f$: $A_\Gamma \rightarrow A_\Gamma$. Suppose $v$ in $V$ is s.t. $\phi_v$ is $f$-invariant. Then $f$ is called $v$-representable if there exists

$U$: $H_v \rightarrow H_v$

a unitary operator s.t. for any $\Psi \in H_v$ we have

$\phi_U \Psi = f^*(\phi_\Psi)$

It is clear that if such $U$ exists it is unique.

The 2nd question is:

Is any invertible quantum cellular automaton $v$-representable for any $v$ with $\phi_v$ $f$-invariant?

• Welcome to cstheory.SE! A tip: Latex is supported on this site, you should consider using it so your question can be clearer. For example you can start by putting a $sign around your formulas. – Gopi Oct 28 '11 at 10:09 • Have you taken a look at the model described by Schumacher and Werner? It sounds a lot like the model you're proposing. If so, you might be interested in focusing your question on that model, or on models described in further developments. The Wikipedia page on QCA was written in large part by quantum information specialists; you might want to give it a look to allow you to condense your question and attract the attention of the pertinent specialists. – Niel de Beaudrap Oct 28 '11 at 15:04 • Yes, please use LaTeX. Especially since the MO question has LaTeX enabled, and you should be able to cut and paste directly from there. – Suresh Venkat Oct 28 '11 at 17:24 • Isn't this a duplicate of mathoverflow.net/questions/78707/… ? Our site policy is that questions posted elsewhere need to be clearly marked as such. – David Eppstein Oct 28 '11 at 18:10 • @David: the first version of it was clearly marked. I think that part must have gotten cut in some later editing. – Peter Shor Oct 28 '11 at 22:30 ## 1 Answer Niel de Beausdrap found this article. The authors (Schumacher and Werner) propose a definition of quantum cellular automata and prove they are always invertible (Corrolary 7 on p. 10). Nominally their definition is different since they use the norm-completion of the algebra$A_\Gamma$and impose a locality condition. However, it is actually equivalent. Their locality condition states that the image of$A_x$has to be contained in$A_S$for some finite S. However, if we avoid the norm completion it holds automatically since any element of the direct limit is in$A_S$for some finite S and$A_x$is finite dimensional. Moreover, an endomorphism of$A_\Gamma$is always continuous hence extends to the completion. This is because the matrix norm can be defined algebrically as the maximal |lambda| for which a*a - lambda is non-invertible. Representability follows from their Theorem 6 on p. 10 which gives a rather explicit (modulo some complicated constraints) description of all nearest-neighbour quantum cellular automata. As discussed on p. 9 this description encodes two finite-dimensional unitary operators. These operators can be easily used to construct the operator$U\$ I seek.

As discussed on p. 8 the case of non-nearest-neighbour can be easily reduced to this case