Are all quantum cellular automata invertible & representable? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T02:47:58Z http://mathoverflow.net/feeds/question/78707 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78707/are-all-quantum-cellular-automata-invertible-representable Are all quantum cellular automata invertible & representable? Squark 2011-10-20T21:43:25Z 2011-10-29T12:25:47Z <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> http://mathoverflow.net/questions/78707/are-all-quantum-cellular-automata-invertible-representable/79462#79462 Answer by Squark for Are all quantum cellular automata invertible & representable? Squark 2011-10-29T12:25:47Z 2011-10-29T12:25:47Z <p><a href="http://cstheory.stackexchange.com/users/248/niel-de-beaudrap" rel="nofollow">Niel de Beausdrap</a> found <a href="http://arxiv.org/abs/quant-ph/0405174%20" rel="nofollow">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>