Are all quantum cellular automata invertible & representable?

2011-10-20T21:43:25Z

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?

Answer by Squark for Are all quantum cellular automata invertible & representable?

2011-10-29T12:25:47Z

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

Are all quantum cellular automata invertible & representable? - MathOverflow

Are all quantum cellular automata invertible & representable?

Answer by Squark for Are all quantum cellular automata invertible & representable?