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$


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

  • $\begingroup$ Niel de Beaudrap on cstheory.stackexchange.com found the article arxiv.org/abs/quant-ph/0405174 which answers both questions positively $\endgroup$
    – Vanessa
    Oct 28, 2011 at 18:01
  • $\begingroup$ @Squark: Doesn't that article impose an extra locality condition? $\endgroup$
    – Peter Shor
    Oct 28, 2011 at 22:33
  • $\begingroup$ Nominally their definition is different. However, I'm pretty sure it is actually equivalent. They work with the completion of my algebra which is why they need the locality condition. With my algebra the locality condition is automatic. Vice versatile I'm pretty sure that for any automaton in my sense the completion exists. If I find time to think orderly about it sometime soon I'll post it as an answer. $\endgroup$
    – Vanessa
    Oct 29, 2011 at 9:42

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.