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?
> 
> 
> 



Are all quantum cellular automata invertible & representable?
[Niel de Beausdrap](https://cstheory.stackexchange.com/users/248/niel-de-beaudrap) found [this](http://arxiv.org/abs/quant-ph/0405174%20) 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


