<p><a href="https://cstheory.stackexchange.com/users/248/niel-de-beaudrap">Niel de Beausdrap</a> found <a href="http://arxiv.org/abs/quant-ph/0405174%20" rel="nofollow noreferrer">this</a> 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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-10-29T12:26:50.463Z
2011-10-29T12:26:50.463Z
2017-04-13T12:32:28.743Z
Vanessa
<p>This questions is cross-posted from <a href="https://mathoverflow.net/questions/78707/are-all-quantum-cellular-automata-invertible-representable">MathOverflow</a></p>

<p>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:</p>

<p>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</p>

<p>$A_S$ := Tensor product of $A_x$ over $x \in S$</p>

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

<p>$i_{S,R}$: $A_S \rightarrow A_R$</p>

<p>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$.</p>

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

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

<blockquote>
  <p>Are all quantum cellular automata invertible?</p>
</blockquote>

<p>Any unit vector $v \in V$ defines a state </p>

<p>$\phi_v$: $A_\Gamma \rightarrow C$</p>

<p>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</p>

<p>$a_S$ := tensor product of $a_x$ over $x \in S$</p>

<p>We then define</p>

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

<p>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.</p>

<p>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 </p>

<p>$\alpha: \Gamma \rightarrow \{1 ... n\}$</p>

<p>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</p>

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

<p>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.</p>

<p>There is a natural *-homomorphism </p>

<p>$\rho$: $A_\Gamma \rightarrow B(H_v)$</p>

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

<p>$\phi_\Psi$: $A_\Gamma \rightarrow C$</p>

<p>by</p>

<p>$\phi_\Psi(a) = (\Psi, \rho(a) \Psi)$</p>

<p>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 <em>$v$-representable</em> if there exists </p>

<p>$U$: $H_v \rightarrow H_v$</p>

<p>a unitary operator s.t. for any $\Psi \in H_v$ we have</p>

<p>$\phi_U \Psi = f^*(\phi_\Psi)$</p>

<p>It is clear that if such $U$ exists it is unique.</p>

<p>The 2nd question is:</p>

<blockquote>
  <p>Is any invertible quantum cellular automaton $v$-representable for any $v$ with $\phi_v$ $f$-invariant?</p>
</blockquote>

CC BY-SA 3.0
2011-10-28T10:09:23.457Z
Welcome to cstheory.SE! A tip: [Latex](http://en.wikibooks.org/wiki/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
CC BY-SA 3.0
2011-10-28T15:04:41.393Z
Have you taken a look at the model described by [Schumacher and Werner](http://arxiv.org/abs/quant-ph/0405174)? 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](http://en.wikipedia.org/wiki/Quantum_cellular_automata) 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
CC BY-SA 3.0
2011-10-28T17:24:37.697Z
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
CC BY-SA 3.0
2011-10-28T17:56:13.240Z
Thx, Niel. Indeed they use the same definition and answer the question of invertibility. See Corollary 7 on p. 10 of the article. Representability follows from their Theorem 6 as well.
Vanessa
CC BY-SA 3.0
2011-10-28T18:10:29.870Z
Isn't this a duplicate of http://mathoverflow.net/questions/78707/are-all-quantum-cellular-automata-invertible-representable ? Our [site policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) is that questions posted elsewhere need to be clearly marked as such.
David Eppstein
CC BY-SA 3.0
2011-10-28T22:30:13.333Z
@David: the first version of it was clearly marked. I think that part must have gotten cut in some later editing.
Peter Shor 
CC BY-SA 3.0
2011-10-29T12:11:24.367Z
Yes, it was lost when I copied Petet's latex
Vanessa
<quantum-computing><cellular-automata>
Quantum cellular automata
Vanessa
# Quantum cellular automata

(Asked by: username_0 on 2011-10-28)

This questions is cross-posted from [MathOverflow](https://mathoverflow.net/questions/78707/are-all-quantum-cellular-automata-invertible-representable)

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?

**Tags:** quantum-computing, cellular-automata
> **Comments:**
> **username_1**: Welcome to cstheory.SE! A tip: [Latex](http://en.wikibooks.org/wiki/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.  
> **username_2**: Have you taken a look at the model described by [Schumacher and Werner](http://arxiv.org/abs/quant-ph/0405174)? 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](http://en.wikipedia.org/wiki/Quantum_cellular_automata) 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.  
> **username_3**: Yes, please use LaTeX. Especially since the MO question has LaTeX enabled, and you should be able to cut and paste directly from there.  
> **username_0**: Thx, Niel. Indeed they use the same definition and answer the question of invertibility. See Corollary 7 on p. 10 of the article. Representability follows from their Theorem 6 as well.  
> **username_4**: Isn't this a duplicate of http://mathoverflow.net/questions/78707/are-all-quantum-cellular-automata-invertible-representable ? Our [site policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) is that questions posted elsewhere need to be clearly marked as such.  
> **username_5**: @David: the first version of it was clearly marked. I think that part must have gotten cut in some later editing.  
> **username_0**: Yes, it was lost when I copied Petet's latex  

---

## 1 answers

### Answer by username_0 on 2011-10-29. Score: 3 | Accepted answer

[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


---

