Renormalisation of quantum cellular automata

Lorenzo Siro
Trezzini<EMAIL_ADDRESS>Dipartimento di Fisica dell'Università di Pavia, via
Bassi 6, 27100 Pavia Istituto Nazionale di Fisica
Nucleare, Gruppo IV, via Bassi 6, 27100 Pavia
Bisio<EMAIL_ADDRESS>Dipartimento di Fisica dell'Università di Pavia, via
Bassi 6, 27100 Pavia Istituto Nazionale di Fisica
Nucleare, Gruppo IV, via Bassi 6, 27100 Pavia
Perinotti<EMAIL_ADDRESS>Dipartimento di Fisica dell'Università di Pavia, via
Bassi 6, 27100 Pavia Istituto Nazionale di Fisica
Nucleare, Gruppo IV, via Bassi 6, 27100 Pavia

We study a coarse-graining procedure for quantum
cellular automata on hypercubic lattices that
consists in grouping neighboring cells into tiles
and selecting a subspace within each tile. This
is done in such a way that multiple evolution
steps applied to this subspace can be viewed as
a single evolution step of a new quantum
cellular automaton, whose cells are the
subspaces themselves. We derive a necessary and
sufficient condition for renormalizability and
use it to investigate the renormalization flow
of cellular automata on a line, where the cells
are qubits and the tiles are composed of two
neighboring cells. The problem is exhaustively
solved, and the fixed points of the
renormalization flow are highlighted.

§ INTRODUCTION

Quantum Cellular Automata have been developed in the years since the very advent of quantum computation [1], as the quantum counterpart of classical cellular automata [2, 3]. The notion of a QCA was made more and more rigorous over the years [4, 5, 6, 7, 8], until the algebraic formulation that is still presently used [9, 10].
The interest in QCA is due to many reasons, the main ones being that they constitute a computational model that is equivalent to a universal quantum computer [11, 12], that
their geometric structure suggests their use in the simulation and modelling of quantum physical systems [13, 14, 15, 16, 17, 18, 19], and that they represent interesting many body systems [20, 21, 22], with a peculiar role in the study of the topological phases of matter [23, 24, 25, 26]. The characteristic trait of QCAs, as of cellular automata in general [27] is that they are defined by a simple local rule, and yet they can give rise to arbitrarily complex and interesting large-scale dynamics, as witnessed by their computational universality. As a consequence, the connection between the local rule and the large-scale phenomenology is clearly a problem as difficult as crucial, that calls for understanding.

A typical feature of large-scale behaviour of physical models is that it is rather
insensitive to most of the details of small-scale dynamics. This statement reflects
e.g. the notion of universality classes of statistical mechanical models [We
stress that the universality notion invoked here is different from computational
universality, which in simple words refers to the ability of a computational model to
simulate any other conceivable computer.], where the relevant physical parameters
take on values in an astonishingly limited range, collecting very different models in the
same large-scale equivalence class [29]. In
this context, the renormalisation procedure due to
Kadanoff [30], and perfected by
Wilson [31, 32], represents the basic idea underpinning all
the techniques for recovering the large-scale features of a physical model starting from
its microscopic description, and is based on the progressive erasure
of degrees of freedom that are supposed to be irrelevant to the large-scale picture. The
validation of the approach comes from the convergence of the recursive application of the
procedure, and thus to the existence of fixed point models that become stable in the
process. This technique led to the discovery of critical exponents in phase transitions
and is intimately connected to renormalisation techniques in quantum field
theories [29]. A similar approach to the
large scale behaviour of classical cellular automata was explored in
Ref. [33, 34], where the renormalisation flow was
interestingly connected to the idea that a cellular automaton $A$ that is renormalised to
another one $B$ has a larger complexity than $B$, in the sense that it can simulate $B$
and then it is at least as complex as $B$.

The connection of small-scale dynamics with its large-scale emergent phenomenology
is of particular interest for application of the theory of QCAs to quantum simulations,
where QCAs serve both as primitive models [13] and as approximations of Floquet systems or Trotterised approximations of local Hamiltonians [35]. The paradigm of quantum computation—even more so in the present, so-called NISQ era [36]—is based on the run of algorithms a large noisy physical qubit register where only a smaller logical error-free register is considered. This is an extreme summary of the notion of error correction. A renormalisation technique, discarding detailed and fast variables in favour of a fraction of the total pool of degrees of freedom, where an effective dynamics occurs, can then be seen as an error correction technique for quantum simulations through QCAs: a large QCA where we do not have full control can be used to run a simulation on its renormalised QCA.

In the present work, we adapt the Kadanoff renormalisation idea to the coarse-graining of
quantum cellular automata. Unlike the case of classical cellular automata, it is so hard
to include irreversible evolutions in the picture of quantum cellular automata that the
very definition of a QCA entails reversibility. This fact determines the consequence that,
despite the initial formulation of the problem of coarse-graining is very close to that of
classical cellular automata [33, 34] or even of
classical networks [37], the subsequent solution has to face more
constraints and has a radically different family of solutions. We start analysing the case
of QCAs on a hypercubic lattice, and pose the question as to what QCAs $A$ admit a
block-tiling and, on each block, a projection $P$ on a subspace that is equivalent to that
of a single cell, with the requirement that projecting after $N$ steps is equivalent to
projecting right away, then applying one step of a different QCA $B$ on the lattice whose
elementary cells correspond to the tiles. After writing the general equations whose
solution gives both the projection $P$ and the renormalised QCA $B$, we restrict to the
case of 1-dimensional QCAs that can be implemented as a Finite Depth Quantum Circuit
(FDQC), with tiles made of two neighbouring nodes and coarse-graining two time-steps into
one. The problem in this case can be manipulated, revealing a general algebraic structure
that can be further simplified in the case where the cells are qubits. The main reason why
the simplification occurs is that for qubit QCAs a full classification of FDQCs has been
provided [9]. We then solve the problem
exhaustively, providing the renormalisation flow for the 1-d qubit case, along with a
classification of the fixed points.

As a remark, we can observe that very few qubit QCAs are renormalisable in this sense, and
those that are, have a trivial evolution. This fact can reasonably be ascribed to the very
limited choice of degrees of freedom due to the smallness of both the cells and the tiles
that we are considering. The solution, however, provides technical tools that pave the way
to similar analysis in more general cases, even considering special case-studies.

The manuscript is structured as follows: In section (<ref>) we introduce the
notion of Quantum Cellular Automaton following the definition proposed by Schumacher and
Werner [9].
We will then focus on two important tools that we will use extensively: the Wrapping Lemma
and the index. The former is a procedure to represent the evolution of a QCA defined over
an infinite lattice of cells (say, for concreteness, $\mathbb{Z}^s$) on a finite lattice.
The latter is a topological invariant quantity that classifies the QCA modulo FDQC.
In section (<ref>) we introduce the notion of coarse-graining and renormalisation,
and we derive the renormalisability conditions.
In section (<ref>) we focus our attention on the case of one-dimensional FDQC.
Finally, in section (<ref>) we solve the above equations in the case
of QCA with qubit cells. After the classification of all such QCAs that are
renormalisable, we study the renormalised evolutions and the fixed points of the
renormalisation flow.

§ QUANTUM CELLULAR AUTOMATA

A Quantum Cellular Automaton $\tT$ is a reversible, local and homogeneous
discrete time evolution of a lattice $\mathcal L$ of cells, each
containing a finite-dimensional quantum system.

The locality condition means that, at each step of
the evolution, a cell $x \in \mathcal L$ interacts
with a finite set $\mathcal{N}_x$ of
cells, called the neighourhood of $x$. Therefore, the speed of
propagation of information in a QCA is bounded
and we have a natural notion of future and past “light
cone” or, more precisely, cone of causal influence.
Homogeneity—or translation invariance—on the other hand,
is the requirement that every cell is updated
according to the same rule. The latter is equivalent to the
requirement that the evolution commutes with the
lattice translations [Sometimes in the literature QCAs can be defined
without the homogeneity property, and what we call a QCA would then be a
homogeneous QCA (see e.g. Ref. [43]).].

Let us now make these
concepts mathematically precise.
First of all, for the purpose of the present study we will focus on the case where the
lattice $\mathcal L$ is a square lattice, i.e.

\begin{align}
\L \coloneqq \tor, \quad  f_i \in \mathbb{N} \cup \infty, \quad s < \infty, \label{eq:latticedefinition}
\end{align}

where $\mathbb Z_{f_i}$ denotes the additive group
modulo $f_i$, and $\mathbb Z_\infty=\mathbb Z$
[The most general structure on which
homogeneous QCAs can be defined is the
Cayley graph of some finitely presented
group $G$ [48, 3, 27]. However
here we will restrict to the case where $G$ is
abelian.].  Therefore, each cell of the lattice
is represented by a vector $x \in \tor $ of
integer coefficients.

This notation allows us to treat the case in which
$\mathcal L$ is infinite and that where
$\mathcal L$ is finite in a unified way.

Typically, one considers the lattice $\mathcal L$ as a graph, the edges corresponding to
neighbourhood relations. One can prove that the homogeneity requirement makes the graph
of causal connections the Cayley graph of some
group [13, 40, 27], that in
the present case is $\mathcal L$ imagined as an abelian additive group.

Since we will deal with lattices of infinitely many
quantum systems, it is convenient to formulate the
QCA dynamics in the Heisenberg picture, namely defining
the evolution by its action on the algebra of operators
rather than on states. This approach, introduced in
Ref. [9] and inspired by the algebraic approach to the
statistical mechanics of spin systems [41] or to quantum field theory [42] has the advantage that the notion of local observable is
always well defined, whereas defining locality through the action on
the local state is highly problematic. This
construction is based on the concept of
quasi-local algebra of operators
$\mathsf{A}(\mathcal L)$.  If each cell contains a
finite dimensional quantum system of dimension
$d\ge2$, we can associate to each cell $x$ the
observable algebra $\mathsf A_x$ which is
isomorphic to the $C^*$-algebra $\MdC$ of $d\times d$
complex matrices.

When $\Lambda \subset \L$ is a
finite subset of $\L$ we denote with
$\mathsf{A}(\Lambda)$ the algebra of operators
acting on all cells in $\Lambda$, namely
$\mathsf{A}(\Lambda)=\bigotimes_{x\in\Lambda}\mathsf{A}_x$. If
we consider two different subsets
$\Lambda_1,\Lambda_2\subset\L$, we can consider
$\mathsf{A}(\Lambda_1)$ as a subalgebra of
$\mathsf{A}(\Lambda_1\cup\Lambda_2)$ by tensoring
each element $O\in\mathsf{A}(\Lambda_1)$ with the
identity over $\Lambda_2\setminus \Lambda_1$,
$O\otimes I_{\Lambda_2 \setminus
\Lambda_1}\in\mathsf{A}(\Lambda_1\cup\Lambda_2)$. In
this way the product $O_1O_2$ with
$O_i\in\mathsf{A}(\Lambda_i)$ is a well defined
element of
$\mathsf{A}(\Lambda_1\cup\Lambda_2)$. Each local
algebra is naturally endowed with the operator
norm $\uon \cdot$. We denote with
$\mathsf{A}^\mathrm{loc}(\L)$ the local algebra
of operators, i.e. the algebra of all the
operators acting non-trivially over any finite set
of cells.

Since tensoring with the identity does
not change the norm of an operator, every local operator has a well defined norm,
which is independent of the region on which we are considering the
action of the operator. Thus, $\mathsf{A}^\mathrm{loc}(\L)$, is a
normed algebra, whose completion is the
quasi-local algebra $\mathsf{A}(\L)$. For
a detailed construction of $\mathsf{A}(\L)$ see
Appendix <ref>.  Clearly, for finite
lattices $\mathsf{A}^\mathrm{loc}(\L)$ is a finite
dimensional algebra and
$\mathsf{A}(\L)=\mathsf{A}^\mathrm{loc}(\L)$.  We could
regard $\mathsf{A}(\L)$ as the $C^*$-algebra of
operators that can be approximated arbitrarily
well by local operators.

A reversible dynamics then
corresponds to an automorphism
$\tT : \mathsf{A}(\L) \to \mathsf{A}(\L)$ of the
quasi local algebra. The algebraic approach allows
us not to chose a representation of the observable
algebra. When dealing with finitely many systems
(i.e. when $\L$ is a finite lattice) this is rather
negligible advantage, since all the representation
are unitarily equivalent. In this case, then $\tT $
would be the conjugation by some unitary operator, i.e.
$\tT(O) = U^\dag OU$. However, when $\L$ is an
infinite lattice we have that $\mathsf{A}(\L)$ is
an infinite dimensional $C^*$-algebra, which
generally decomposes into inequivalent representations.
Thus working in a representation-independent framework is highly

In order to define a homogeneous dynamics, we have to define the
operators that implement the lattice
For any $x\in \L$ we
define the shift $\tau_x$ as the extension to
the whole $\mathsf{A}(\L)$ of the isomorphism
from each $\mathsf{A}_y$ to

If $O \in \mathsf{A}_\Lambda$ is an operator
localized in the region $\mathsf{A}_\Lambda$, then
$\tau_x(O) \in \mathsf{A}_{\Lambda + x}$ is an
operator localized in the region
$\Lambda + x := \{y+x | y \in
\Lambda \}$.
For $\L = \mathbb{Z}$ one can refer to the pictorial
representation of e.g. $\tau_{1}$:

\begin{align}
\begin{split}
\tau_{1 } = \tikzfig{Leftsh} .
\end{split}
\end{align}

We are now in position to define a Quantum Cellular Automaton.

A $\emph{Quantum Cellular Automaton}$ (QCA)
over a lattice $\L$ with finite neighbourhood
scheme $\mathcal{N} \subset\L$ is an
$\tT:\mathsf{A}(\L) \longrightarrow
\mathsf{A}(\L)$ of the quasi-local
algebra such that

* $\tT(\mathsf{A}(\Lambda))\subset
\mathsf{A}(\Lambda+\mathcal{N}) \hspace{5pt}
\forall \Lambda\subset \L$ (locality),

* $\tT\circ\tau_x=\tau_x\circ\tT$
$\forall x\in \L$ (homogeneity),

where $\Lambda+\mathcal{N} := \{ y+x | y \in
\Lambda, x \in \mathcal{N}  \}$.
The homomorphism $\tT_0:\mathsf{A}_0\longrightarrow
\mathsf{A}(\mathcal{N})$ given by the
restriction of the QCA to the cell labelled $x=0$ is called the
$\emph{transition rule}$.

The identity and the shifts $\tau_x$ are (trivial)
examples of QCA. Another example of a QCA is a finite depth quantum circuit,
whose action can be decomposed in terms of local gates as follows

\begin{equation}
\tikzfig{QCAexample}.
\end{equation}

The boxes represent unitary completely positive maps, e.g. those labelled $\mathcal U$ represent the maps $\mathcal U(X)\coloneqq UXU^\dag$.
Notice that the algebra $\mathsf A_0$ is isomorphic to $\MdC$ (say via $\transf H_\mathcal L:\mathsf A_0\to\MdC$), and $\mathsf A(\mathcal N)$ is isomorphic to $\MdC^{\otimes|\mathcal N|}$ (via $\tK_\mathcal L:\mathsf A(\mathcal N)\to\MdC^{\otimes|\mathcal N|}$). Thus, the transition rule can be equivalently identified by the homomorphism

\begin{align}
\tT_*\coloneqq \tK_\mathcal L\circ\tT_0\circ\tH^{-1}_\mathcal L:\MdC\to\MdC^{\otimes|\mathcal N|}.
\label{eq:isoabs}
\end{align}

In this way, the restriction of $\tK_\mathcal L$ to $\tT_0(\mathsf A_0)$ is an isomorphism to $\tT_*(\MdC)$.

It is possible to prove ([9]) that the
local transition rule and the global evolution are
in one-to-one correspondence. This result is
stated in the following Lemma:

A homomorphism
$\tT_0 : \mathsf{A}_0 \longrightarrow
\mathsf{A}(\mathcal{N})$ is the transition rule
of a cellular automaton if and only if for all
$x \in \L$ such that
$\mathcal{N}\cap\mathcal{N}_x\neq \emptyset$,
$\mathcal N_x := \{x\}+\mathcal N$, the
algebras $\tT_{0}(A_0)$ and
${\tau}_x(\tT_{0}(A_0))$ commute
Given a local transition rule $\tT_0$
the global homomorphism $\tT$
is given by

\begin{equation}
\tT(\bigotimes_{x\in \mathcal L}A_x)=\prod_{x\in \mathcal L}\tT_x(A_x)
\label{eq:autom}
\end{equation}

Since the image $\tT_0(\mathsf A_0)$ is a
subalgebra of the full matrix algebra
$\mathsf A_\mathcal N$, from the characterisation
theorem of
finite dimensional $C^*$-algebra (see
e.g. [9])
we have

\begin{equation}
\tT_0(X)=U^\dag(I_{\mathcal N\setminus \{0\}}\otimes X)U,\quad\forall X\in\mathsf A_0
\label{eq:ev}
\end{equation}

for a suitable unitary $U$ in $\mathsf A_{\mathcal
N\cup\{0\}}$, and analogously for $\tT_*$. In the following we will use
eq. (<ref>) both for $\tT_0$ and $\tT_*$, leaving to the context the specification
as to which is the case.

§.§ The wrapping Lemma

Our definition of QCA encompasses both
infinite lattice and finite lattices embedded
in a torus. However, a result known as Wrapping Lemma (see Ref. [27]) relates the
evolution of the QCAs over the infinite lattice
with the one over a finite one. The idea is
to “wrap” a sufficiently large finite
sub-lattice of a QCA over the infinite
lattice $\mathbb{Z}^s$ by impose suitably periodic
boundary conditions, obtaining a discrete torus.
The “unwrapped” QCA and the “wrapped” one then have
the same local transition rule. The concept of
“sufficiently large” is grasped by the
requirement that, after wrapping, still
$\tT_0(A)$ should commute with $\tT_x(B)$ for all $A\in\mathsf A_0$ and $B\in\mathsf A_x$,
for any $x$ such that $\mathcal{N}\cap\mathcal{N}_x\neq\emptyset$.
Therefore, a “sufficiently large” wrapping is such that the
set of elements $x\in\L$ such that
$\mathcal{N}\cap\mathcal{N}_x\neq\emptyset$ is the
same as in the infinite case, i.e. no new
overlapping between neighbourhoods is introduced
after wrapping the lattice.

We will now make this idea more precise.
Let us begin defining a wrapping,
i.e. a homomorphism of the infinite lattice $\mathbb Z^s$ into
a discrete torus.

A wrapping of the additive group $\mathbb Z^s$ is a homomorphism

\begin{align*}
\varphi:\mathbb Z^s\to\mathcal L\coloneqq\bigtimes_{t=1}^s\mathbb Z_{f_t}, \hspace{5pt} f_t<\infty \hspace{5pt} \forall t,
\end{align*}

where $\mathbb Z_f$ stands for the additive group
$\mathbb Z$ modulo $f$.

More concretely, if an element $x\in \mathbb Z^s$ is identified by the s integer numbers $x=(x_1,...,x_s)$ the action of the wrapping is:

\begin{align*}
\varphi(x)=((x_1\Mod{f_1}) ,..., (x_s\Mod{f_s})).
\end{align*}

We now define a regular neighbourhood scheme for a wrapping $\varphi$,
that pins down the idea of a “sufficiently large” wrapping.

Let $\mathcal N\subset\mathbb Z^s$ be a finite set. We say that $\mathcal N$ is regular for the wrapping $\varphi$ if

\begin{align*}
\{\varphi^{-1}(\mathcal N_{\varphi(x)})\cap \varphi^{-1}(\mathcal N_{\varphi(y)})\}\cap
\{\mathcal N_x\cup \mathcal N_y\}=\mathcal N_x\cap \mathcal N_y
\end{align*}

for every pair $x,y\in\mathbb Z^s$ such that $\mathcal N_x\cap\mathcal N_y\neq\emptyset$.

The above definition captures the idea that the neighbourhoods of close cells $x$ and $y$,
after wrapping, should have the same intersection as before wrapping. The intersection with $\mathcal N_x\cup \mathcal N_y$ on the r.h.s. in the definition is required because the inverse image of $\mathcal N_{\varphi(x)}\cup \mathcal N_{\varphi(y)}$ contains infinitely many intersections, due to periodicity of the set $\varphi^{-1}(x)$. Now, we can finally understand the meaning of “sufficiently large” wrapping, with respect to a neighbourhood scheme: the periodic boundary conditions should be such that the neighbourhood scheme is regular. For a single step of evolution of a nearest neighbour automaton, this is true for all lattices with more than four cells in each coordinate direction.

With the above notions in mind, we can now state the wrapping lemma.

QCAs with a regular neighbourhood scheme $\mathcal N$ on a lattice
$\mathcal{L}$ with given periodic boundary conditions are in one-to-one correspondence
with those on the infinite lattice, and the correspondence is defined by “having the same
transition rule”.

Notice that we did not give a formal definition of the (equivalence) relation “having the same transition rule”. However, this notion is straightforward if we think of the transition rule as $\tT_*$ rather than $\tT_0$.

Given a wrapping $\varphi:\mathbb Z^s\to\mathcal L$, let us now introduce the following isomorphisms, referring to those introduced in Remark <ref>

\begin{align*}
&\mathcal{U}_\varphi\coloneqq\tH^{-1}_{\mathbb Z^s}\circ\tH_\mathcal L:\mathsf{A}_0^w\rightarrow\mathsf{A}_0^\infty \\
&\mathcal{W}_\phi\coloneqq\tK^{-1}_\mathcal L\circ\tK_{\mathbb Z^s}:\mathsf{A}_{\mathcal{N}}^\infty\rightarrow\mathsf{A}_{\mathcal{N}}^w.
\end{align*}

The map $\mathcal{U}_\varphi$ maps the single cell algebra $\mathsf{A}^w_0$ of the wrapped lattice and into the single cell algebra $\mathsf{A}^\infty_0$ of the algebra of the infinite lattice, while the map $\mathcal{W}_\varphi$ maps the algebra of the neighbourhood $\mathsf{A}^\infty_{\mathcal{N}}$ of the infinite lattice into that of the wrapped lattice denoted $\mathsf{A}_{\mathcal{N}}^w$.
The regularity requirement in def. <ref> ensures that the application of
$\varphi$ to $\mathcal{N}_x$ does not change the neighbourhood structure: $\varphi(\mathcal N_x)=\mathcal N_{\varphi(x)}\leftrightarrow\mathcal N_x$.

If we now consider a QCA $\tT$ over $\mathbb{Z}^s$, with transition rule $\tT^{(\infty)}_0$, we can define its wrapped version as follows.

The wrapped evolution $\tT_w$ on the wrapped lattice $\mathcal{L}=\varphi(\mathbb Z^s)$ of a QCA $\tT$ over $\mathbb{Z}^s$ is the QCA over the lattice $\mathcal{L}$ with local rule given by:

\begin{align} \label{eq:wrapping}
\tT^{(w)}_0=\mathcal{W}_\varphi\tT^{(\infty)}_0\mathcal{U}_\varphi.
\end{align}

Notice that, in this case,

\begin{align*}
\tK_\mathcal L\circ\tT^{(w)}_0\circ\tH_\mathcal L=\tK_{\mathbb Z^s}\circ\tT^{(\infty)}_0\circ\tH_{\mathbb Z^s}=\tT_*.
\end{align*}

Consequently, we can say that wrapped QCAs over different lattices share the same local rule if their local rule can be described as in eq.(<ref>) starting from the same infinite QCA $\tT$, namely $\tT^{(w)}$ and $\tT^{(w')}$ share the same local rule if:

\begin{align*}
\tK_\mathcal L\circ\tT^{(w)}_0\circ\tH_\mathcal L=\tK_{\mathcal L'}\circ\tT^{(w')}\circ\tH_{\mathcal L'}=\tT_*
\end{align*}

§.§ One dimensional QCA: Index Theory

One key feature of QCAs on $\mathbb Z$ is their
index, which was introduced in
Ref. [43] for QCAs without the
translation-invariance hypothesis. The index is a
locally computable invariant, meaning it can be
determined from a finite portion of the automaton
and will yield the same result regardless of the
portion chosen, even if the QCA is not

Intuitively, the index theory for one dimensional
QCAs suggests that information can be
thought as an incompressible fluid, with the index
representing its flow rate.

Let us now review the main results of index
theory.  The whole construction is based on the
notion of support algebras [43] (also called interaction algebras [44]).

Let $\mathsf B_1$ and $\mathsf B_2$ be
$C^*$-algebras, and consider a $*$-subalgebra
$\mathsf{A}\subset \mathsf B_1\otimes \mathsf
B_2$. Each element $a\in\mathsf{A}$ can be
expanded uniquely in the form
$a=\sum_{\mu}a_\mu\otimes e_{\mu}$, where
$\{e_{\mu}\}$ is a fixed basis of $\mathsf
B_2$. The support algebra
$\mathsf S(\mathsf A,\mathsf B_1)$ of
$\mathsf A$ in $\mathsf B_1$ is the smallest
$C^*$-algebra generated by all $a_\mu$ in such
an expansion [It is easy to prove that the support algebra
does not depend on the choice of the basis $\{e_\mu\}$].

Let us now consider a nearest neighbour QCA on $\mathbb Z$,
i.e. with $\mathcal N_x = \{ x-1,x,x+1\}$ for all
$x$. Two comments are now in order. First,
any QCA on $\mathbb Z$ can be expressed as a nearest-neighbour QCA
by grouping multiple cells in a single one. In the following
discussion we will
assume that all the QCAs that we introduce are
nearest-neighbour QCAs.
Second, since
translation invariance is not assumed, local
algebras at different sites may not to be
isomorphic.  Let us now define the left and right
support algebras around cells $2x$ and $2x+1$ for a QCA with evolution $\tT$ as

\begin{equation}
\begin{split}
&\mathsf{L}_{2x}= \mathsf{S}(\tT(\mathsf{A}_{2x} \otimes \mathsf{A}_{2x+1}),(\mathsf{A}_{2x-1}\otimes \mathsf{A}_{2x}))\\
&\mathsf{R}_{2x}= \mathsf{S}(\tT(\mathsf{A}_{2x} \otimes \mathsf{A}_{2x+1}),(\mathsf{A}_{2x+1}\otimes \mathsf{A}_{2x+2}))
\end{split}
\end{equation}

We have the following lemma

Each $\mathit{R}_x$ is isomorphic to the matrix algebra $\mathcal{M}_{r(x)}$ of the  $r(x)\times r(x)$ matrices for some $r$ depending on $x$. Furthermore,

\begin{equation}
\mathit{R}_{2x}\otimes\mathit{R}_{2x+1}=T(A_{2x}\otimes A_{2x+1})
\end{equation}

Notice that, since the evolution is an automorphism,

\begin{equation}
\operatorname{dim}[\mathit{R}_{2x}]\operatorname{dim}[\mathit{R}_{2x+1}]=\operatorname{dim}[A_{2x}]\operatorname{dim}[A_{2x+1}]
\label{eq:dim1}
\end{equation}

Also, we  have $\mathit{R}_{2x+1}\otimes\mathit{R}_{2x+2}=T(A_{2x+1}\otimes A_{2x+2})$ since the $\mathit{R}$ generates the chain algebra and $\mathit{R}_{2x+1}$,$\mathit{R}_{2x+2}$ are the only ones that have support on sites $2x+1$,$2x+2$. This means

\begin{equation}
\operatorname{dim}[\mathit{R}_{2x+1}]\operatorname{dim}[\mathit{R}_{2x+2}]=\operatorname{dim}[A_{2x+1}]\operatorname{dim}[A_{2x+2}]
\label{eq:dim2}
\end{equation}

The first result of index theory is the
following theorem.
For any
QCA $\tT$ on $\mathbb Z$, the quantity

\begin{equation}
\ind(\tT)=\sqrt{\frac{\operatorname{dim}[\mathsf{L}_{2x}]}{\operatorname{dim}[\mathsf{A}_{2x}]}}
\end{equation}

does not depend on $x$.
We call $\ind(\tT )$ the index of the QCA.

The following Proposition presents the most
important consequences of index theory.

For any
QCAs $\tT$ and $\tS$ we have that
$\ind[\tT\tS] = \ind[\tT]\ind[\tS]$ and
$\ind[\tT] = 1$ $\textit{iff}$ $\tT$ has a
Margolus partitioning scheme,

\begin{equation}
\begin{split}
&\tT = \mathcal{W} \circ \mathcal{V}\\
&\mathcal{V}(\cdot) = (\prod_{n\in\mathbb{Z}}V^\dag_{2n})(\cdot)(\prod_{m\in\mathbb{Z}}V_{2m})\\
&\mathcal{W}(\cdot) = (\prod_{k\in \mathbb{Z}} W^\dag_{2k+1})(\cdot)(\prod_{l\in\mathbb{Z}}W_{2l+1})
\end{split}
\end{equation}

where $V_{2n}$ are unitaries acting on sites $2n$ and $2n + 1$, and $W_{2m+1}$ are unitaries acting on sites $2m+1$ and $2m+2$.

§.§ One Dimensional Nearest Neighbour Qubit Automata

We now restore the translation invariance
assumption. It is possible to show
[9] that a nearest-neighbor (i.e.
$\mathcal{N}=\{-1,0,1\}$) QCA $\tT$ on
$\mathbb{Z}$ where each cell is a qubit, has
$\ind( \tT ) = 1$ if and only if

\begin{equation}
\label{eq:10}
\tT=\tikzfig{Qubitev}
\end{equation}

where $\mathcal U(X)\coloneqq U^\dag X U$, where $U$ is an arbitrary unitary gate acting
on a single cell, and $\mathcal C_\phi(X)\coloneqq C_\phi^\dag XC_\phi$, where $C_\phi$ is
a controlled-phase gate, i.e.

\begin{align*}
\end{pmatrix}.
\end{align*}

The expression (<ref>) of the local rule of
the QCA is

\begin{equation}
\begin{split}
&\tT_0({A}_0)=X^{\dag}(I\otimes U^{\dag}A_0 U\otimes I)X,\\
&X=(C_\phi\otimes I_3)(I_1\otimes C_\phi)
\end{split}
\label{eq:x}
\end{equation}

From now on, we will set the basis in which $C_\phi$ is diagonal as the basis $\{\ket{a}\}_{a=0,1}$ such that $\sigma_z\ket{a}=(-1)^{a}\ket{a}$. We will refer to this basis as the computational basis.

§ QCA RENORMALISATION

Following the idea presented in [34] we
now define a procedure to provide a coarse-grained
description of the dynamics of a QCA, in such a
way that the large scale description that we
eventually obtain is still a QCA. Intuitively
speaking, the procedure consists in choosing a
subset of degrees of freedom of the original
evolution through a projection on a subspace of
the Hilbert space of $N$ neighbouring cells, and
requiring that the restriction of $N$ steps of the
original QCA to such a subspace is still a QCA.

The first step is to exploit the
wrapping lemma to reduce the coarse-graining
problem of an infinite lattice to the corresponding problem
over all possible wrappings $\mathcal L$. In order to do that,
we have to define a partition
$\{\Lambda_x\}_{x\in\mathcal{L}'}$ of the original
lattice $\mathcal{L}$ . The indices $x$ of such
a partition will be the cells of a new lattice
$\mathcal{L}'$: this will establish the relation
between the wrapped lattice $\mathcal{L}$
and the coarse-grained one $\mathcal{L'}$. Once
this is done, we have a formulation of the
problem in terms of coarse-graining of the family of
evolution rules over all the possible wrapped lattices
$\mathcal{L}$. We will then find conditions for the coarse-graining
to exist, and show that these
conditions do not depend on the choice of the
lattice $\mathcal{L}$. This means that our
coarse-graining condition ultimately boils down to
a single condition over a minimal regular lattice
$\mathcal{L}$. In particular, in the first
subsection we will introduce the technical tools
to properly formulate the problem of coarse-graining
a finite lattice $\mathcal{L}$ in another
finite lattice $\mathcal{L'}$, while in the second
subsection we will apply these tools to the study
of the coarse-graining condition for a  QCA over an infinite lattice.

A QCA that admits a solution to the coarse-graining equation is renormalisable. The
coarse-graining of QCAs determines a displacement in the space of QCAs as specified by
their defining parameters, that represents a renormalisation flow, whose fixed
points play a distinguished role as in any renormalisation scenario.

§.§ Coarse-grained algebra

Let $\tT$ be a QCA on $\mathbb Z^s$ such that the
algebra of each cell is the isomorphic
to the $C^*$-algebra of $d\times d$ complex
matrices, and let us fix some $N \in \mathbb{N}$.
Let us now consider a regular
tessellation  of $\mathbb Z^s$ such that each tile
is a $s$-dimensional cube of side $N$ i.e.

\begin{align}
&\bigcup_{{x}\in \mathbb{Z}^s}\Lambda_{x}= \mathbb{Z}^s,\label{eq:part}\\
&\Lambda_0\coloneqq [0,N-1]^s,&&\Lambda_{{x}}\coloneqq\Lambda_0+Nx,\label{eq:transpal}
\end{align}

where $[a,b]$ denotes the set
$\{a,a+1,\ldots,b-1,b\}\subset\mathbb Z$ (see Fig. (<ref>) ).

(a) 0.25!

(b) 0.25!

(c) 0.2!

Example of tessellation of $\mathcal{L}$ and mapping in $\mathcal{L'}$ in $\mathbb{Z}^2$. (a) The wrapped lattice $\mathcal{L}\simeq\mathbb Z_6\times\mathbb Z_6$. (b) Tessellation $\mathcal L'\simeq \mathbb Z_3\times\mathbb Z_3$ of the lattice $\mathcal{L}$ through $\{\Lambda_x\}$ with $\Lambda_{0,0}=[0,1]^2$. (c) The new lattice $\mathcal{L'}$ is given by the identification $\Lambda_{\vc{x}}\rightarrow \vc{x}=(x,y)$.

Eq. (<ref>) we have that the cubes
$\{\Lambda_{{x}}\}$ are related to each other by a
translation.  Consider now a projection $\Pi_y$ in
the algebra $\mathsf{A}(\Lambda_y)$ of each of the
cubic tiles. We would like to restrict the domain of
the QCA to the operators whose support is
contained in the support of the
$\bigotimes_y \Pi_y$. However, this infinite
tensor product is ill-defined, lying outside the
quasi local algebra.  We then exploit the wrapping
lemma and consider the wrapped evolution $\tT_w$
on a finite lattice

\begin{align}
\label{eq:2}
\mathcal{L} = \mathbb{Z}_{Nf}^s \quad f \in \mathbb{N}
\end{align}

where $f$ is suffieciently large such that
that the regular neighborhood condition is
satisfied. Clearly,  the lattice $\mathcal{L}$ admits a tessellation in terms of
the same $s$-dimensional hypercubes. Then we have

\begin{align}
\label{eq:1}
\bigcup_{{y}\in \mathcal{L}'}\Lambda_{y}=
\mathcal{L}, \quad \mathcal{L}' :=
\mathbb{Z}_{f}^s
\end{align}

If $\Pi_{{0}}$ is a given a projection belonging to
the local algebra of the tile $\Lambda_0$, we can
define the projection $\Pi_{{{x}}}$ on the tile $\Lambda_x$ by translating
$\Pi_{{0}}$, namely $ \Pi_{x}\coloneqq\tau_{Nx}(\Pi_{0})$.
We now define the coarse-grained algebra $\mathsf A\vert_\Pi(\mathcal{L})$  over $\mathcal{L}$
as follows:

\begin{align}
\begin{aligned}
\{ A \in \mathsf{A}(\mathcal{L}) \mbox{ s.t. }
\Pi A \Pi = A\} , \\
&\Pi\coloneqq\bigotimes_{x\in \mathcal{L'}}\Pi_{x}.
\label{eq:restop}
\end{aligned}
\end{align}

i.e. $\mathsf A\vert_\Pi(\mathcal{L})$ is the
algebra of operators with support and range
contained in those of $\Pi$. The algebra
$\mathsf A\vert_\Pi(\mathcal{L})$
is isomorphic to the
algebra $\mathsf A(\mathcal{L'})$ on the lattice
$\mathcal{L'}$ where each local system has
dimension $d'\coloneqq\operatorname{rank}(\Pi)$.
The node $x\in \mathcal L'$ corresponds to
the tile $\Lambda_x$ in $\mathcal L$, and operators
$A\in\mathsf A(\mathcal{L'})$ are in one-to-one
correspondence with operators in
$\mathsf A\lvert_{\Pi}(\mathcal{L}) $.
Let us explicitly construct such isomorphisms.
Let $\{\ket{\psi_k}\}$ be a basis on the
Hilbert space of the tile $\Lambda_x$ such that

\begin{equation}
\Pi_{{{x}}}=\sum_{k=0}^{d'-1} \ket{\psi_k}\bra{\psi_{k}}.
\end{equation}

We then define

\begin{equation}
\J\coloneqq\Jopconj{ }, \quad \Jop\coloneqq\sum_{k=0}^{d'-1}\ket{k}\bra{\psi_k},
\label{eq:Jop}
\end{equation}

where $\{\ket{k}\}_{k=0}^{d'-1}$ is a basis of
$\mathbb{C}^{d'}$, i.e. the Hilbert space of the
cell $x \in \mathcal{L}'$.  This operator applies
the $\Jop$ over the support of each $\Lambda_x$.
It is easy to verify that

\begin{align}
\label{eq:3}
\Jop^\dag\Jop=\Pi_{x},\; \Jop\Jop^\dag= I,
\;
\J^\dag\J=\Pi, \; \J\J^\dag=I.
\end{align}

Then we define

\begin{align}
\begin{aligned}
&\tV:\Aredloc \to \mathsf{A}(\mathcal{L})
,\quad \tJ: \mathsf{A}(\mathcal{L}) \to\Aredloc , \\
&\tV(A) := J^\dag A J \\
& \mathcal{J}(A):= J \mathcal{P} (A) J^\dag,
\quad
\mathcal{P} (A):= \Pi A \Pi
\end{aligned}
\label{eq:Jiso3}
\end{align}

and from Equation (<ref>) we have

\begin{align}
\tJ\circ\tV=\tI, \quad
\tV\circ\tJ=\tP
\end{align}

i.e. $\tV$ is an
ismomorphism between
$\Aredloc$ and its image $\Aplocc$ and  the
restriction of $\tJ$ to
$\Aredloc$ is the inverse isomorphism.

With the choice of basis in which each $\Pi_x$ is diagonal, the
matrices representing operators
$A\in\mathsf A\lvert_{\Pi}(\mathcal{L})$, are
obtained by padding with zeros the matrices that
represent their correspondent
$A_r\in\mathsf A(\mathcal{L'})$, and viceversa,
given the matrix of an operator
$A\in\mathsf A\lvert_{\Pi}(\mathcal{L})$,
the corresponding operator on
$A_r\in\mathsf A(\mathcal{L'})$ is obtained
by removing the
null blocks with image or support on the kernel of

We can now define the map $(\tT)_r$ induced by $\tT_w$ on $\Aredloc$ as follows

Let $\tT$ be a QCA on $\mathbb{Z}^s$
and let $\mathcal{L} = \mathbb{Z}_{Nf}^s$,
be a wrapped lattice such that the regular
neighbourhood condition is satisfied.
Let $\mathcal{L}' = \mathbb{Z}_{f}^s$
and let $\tJ$ and $\tV$ be defined as in Eq.
The induced map on the lattice
$\mathcal{L'}$ is defined as follows:

\begin{align}
\begin{aligned}
&\tT_r:\Aredloc \to\Aredloc ,\quad
\tT_r\coloneqq \tJ\circ\tT_{w}\circ\tV.
\end{aligned}
\label{eq:induced}
\end{align}

Notice that the induced map depends on the choice of the
lattices $\mathcal{L}$ and $\mathcal L'$, and we have a
family of induced maps
$\{\tT_r\}_{\mathcal L,\mathcal{L'}}$.  In order to lighten
the notation, we will not explicitly write
dependance of the induced map on the lattices
$\mathcal{L}$ and $\mathcal{L}'$. This simplification is also justified by
the fact that that there is no
dependency of the local rule on the choice of the
lattices, as we will prove later.
We remark that, in general, we need to differentiate between the map induced by $k$
steps of the QCA $\tT_w$ and $k$ subsequent applications of the map induced by $\tT_w$.
The above two transformations of the quasi-local algebra are given by

\begin{align}
&(\tT^k)_r= \tJ\circ\tT_w^k\circ\tV && (\tT_r)^k= (\tJ\circ\tT_w\circ\tV)^k,
\end{align}

In the following we will see how the induced map pins down the idea of coarse-graining.

§.§ Renormalisable QCAs

We are now in position to provide a definition of renormalisable QCA.

Let $\tT$ and $\tS$ be two QCAs on $\mathbb{Z}^s$,
$N$ be a natural number,
and $\Pi_0 \in \mathsf{A}(\Lambda_0)$ be a
projection on the local algebra of the region
$\Lambda_0 \coloneqq [0,N-1]^s$.
We say that $\tT$  is
renormalisable through the coarse-graining $(\Pi_0,\Lambda_0)$
to $\tS$  if

\begin{equation}
\tT^N_{w}\circ \tV=\tV\circ\tS_w
\label{eq:cg}
\end{equation}

holds for any any wrapping $\tT_w$ on $\mathcal{L} = \mathbb{Z}_{Nf}^s$
such that the neighbourhood of $\tT^N$ is regular over $\mathcal{L}$.
We say that $\tS$ is a size-$N$ renormalisation of $\tT$ through the
coarse-graining $(\Pi_0,\Lambda_0)$. We will also  say that
$\tT$ admits a size-$N$ renormalisation if there exists
a QCA $\tS$ and a coarse-graining $(\Pi_0,\Lambda_0)$ such that $\tS$ is a size-$N$
renormalisation of $\tT$ through $(\Pi_0,\Lambda_0)$.

Notice that this definition involves the map $\tV$, whose role is to embed the single cell algebra into the N-cell algebra. This definition may seem in contrast with the one in [34], where the coarse-graining map takes the state of the $N$-supercell and projects it into the state of a single cell. However, we have to remember that we are working in the Heisenberg picture here. The above definition represent the faithful transposition of that in [34] to the quantum case.

[remember picture]
(A) at (-2,2.25) ;
(B) at (-2,-2.25) ;
[->,line width=2 pt] ($(A)-(0,1.25)$) to node[anchor=east] $\tS$ ($(B)+(0,1)$) ;
(C) at (3.5, 2.25 ) ;
(D) at (3.5,-2.25) ;
[->,line width=2 pt] ($(C)-(0,1.25)$) to node[anchor=west] $\tT^N$ ($(D)+(0,1)$) ;
[->,line width=2 pt]  ($(A)+(1.75,-0.25)$) to node[anchor=south] $\tV$  ($(C)-(1.75,0.25)$) ;
[->,line width=2 pt]  ($(B)+(1.75,-0.25)$) to node[anchor=north] $\tV$ ($(D)-(1.75,0.25)$);

The condition in eq.(<ref>) amounts to ask the commutativity of the above diagram: if $\tS$ is a renormalisation of $\tT$ then evolving with a single step of $\tS$ in the coarse-grained algebra and then embed the coarse-grained algebra in the original one through the map $\tV$ is the same than embed the coarse-grained algebra in the original one and consider N steps of $\tT$ . In this way, a single step of $\tS$ mimics the behaviour of $\tT^N$ if reduced to the chosen degrees of freedom.

This definition is modelled on the analogous one
from [34].
However it is
not particularly amenable for the analysis of the
problem due to the reference to all possible wrappings $\tT^N_w$. The following lemmas
will show that it is sufficient to consider just one wrapping and check the renormalisation condition there.

If a QCA $\tT$ on $\mathbb{Z}^s$ is
renormalisable through $(\Pi_0,\Lambda_0)$ to some QCA $\tS$ as in eq.(<ref>),

then every induced map $(\tT^N)_r$ is a QCA.

Let us begin remembering the expression of the induced map of N-steps of $\tT$:

\begin{equation}
(\tT^N)_r= \tJ\circ\tT^N_{w}\circ\tV.
\label{eq:inducedN}
\end{equation}

Composing (<ref>) on the left with $\tJ$ we have

\begin{equation}
\tJ\circ\tT^N_{w}\circ\tV=\tJ\circ\tV\circ\tS_w=\tS_w,
\end{equation}

which reads

\begin{equation}
\tS_w=(\tT^N)_r,
\end{equation}

for every possible choice of the lattice $\mathcal{L}$.
This means that, if $\tS$ is a renormalisation of $\tT$, then $(\tT^N)_r$ is a QCA.

Notice that, if $(\tT^N)_r$ is a QCA for every
choice of the lattice $\mathcal{L}$, the Wrapping
Lemma allows us to extend it to a QCA $\tS$ on the
quasi-local algebra over the infinite
lattice $\Aqloc s$. However, the local rule of $\tS$ may depend on the specific wrapping.
In the following, we prove that this is not the case.

Let us now study when the
condition (<ref>)  holds for a given
wrapped lattice $\mathcal{L}$. First of all, since $\tT_w$
is a $C^*$-algebra automorphism,

we can
always find a unitary $U_\tT$ such that

\begin{equation}
\tT_w(A)=\Tmat^\dag A \Tmat \hspace{10pt} \forall A\in \mathsf{A}(\mathcal{L}),
\end{equation}

and the same holds for $\tS_\mathcal{L'}$:

\begin{equation}
\tS_w(A)=(U_\tS)^\dag A (U_\tS)\hspace{10pt} \forall A\in \mathsf{A}(\mathcal{L'}).
\end{equation}

Moreover, eq.(<ref>) allows us to write:

\begin{align}
&\Tred (A)=\Tredmat^\dag A \Tredmat\label{eq:tred}\\
&\Tredmat \coloneqq \J  \Tnmat \J^\dag \label{eq:tredmat}
\end{align}

Let us begin providing some trivial examples of renormalisation to develop the intuition.

* Local Unitaries: Let $\tT$ be a QCA
over $\mathbb{Z}$ whose effect is to apply the
same local transformation $U_x$ on each cell
$x$, namely:

\begin{equation*}
\tT(\mathsf{A}_{\Lambda})=\left(\bigotimes_{x\in\Lambda} U^\dag_x\right)\mathsf{A}_{\Lambda}\left(\bigotimes_{y\in\Lambda}U_y\right).
\end{equation*}

Wrapping $\tT$ over a lattice $\mathcal{L}$ we obtain
the induced map:

\begin{align*}
\begin{aligned}
&\Tredmat=\J \left(\bigotimes_{x\in\L} U^N_x \right) \J^\dag=\\
&=\left(\bigotimes_{x\in\mathcal{L}'}\J_{\Lambda_x} \right) \left(\bigotimes_{x\in\L} U^N_x \right) \left(\bigotimes_{y\in\mathcal{L}'}\J_{\Lambda_y} \right).
\end{aligned}
\end{align*}

Since the
transformation is completely factorized, we can
evaluate the expression over the support of a
single tile $\Lambda_x$, i.e.:

\begin{align*}
\begin{aligned}
&=\J_{\Lambda_x} \left(\bigotimes_{x'\in\Lambda_x} U^N_{x'} \right) \J^\dag_{\Lambda_x}=\sum_{k,k'} u_{k,k'}\ketbra{k}{k'},
\end{aligned}
\end{align*}

\begin{align*}
u_{k,k'}\coloneqq \bra{\psi_k^{(x)}}\left(\bigotimes_{x'\in\Lambda_x} U^N_{x'} \right)\ket{\psi_{k'}^{(x)}}.
\end{align*}

The total matrix is then $\Tredmat=\bigotimes_{x\in\L'}(\Tredmat)_x$.
In particular, if we choose the $\{\ket{\psi^{(x)}_k}\}_k$ to be eigenvalues of $\left(\bigotimes_{x\in\Lambda_x} U^N_x \right)$ we have:

\begin{equation*}
(\Tredmat)_x=\sum_k u_{k,k}\ketbra{k}{k}.
\end{equation*}

That is, the renormalised evolution is still a local unitary with eigenvalues given by a subset of the eigenvalues of $\left(\bigotimes_{x\in\Lambda_x} U^N_x \right)$ and eigenvector corresponding to the chosen basis $\{\ket{k}\}_{k=0}^{d'-1}$. A pictorial representation of the size-2 renormalisation is shown in fig.(<ref>).

* Shift: Consider the shift $\tau_{\pm 1}$ as in Definition (<ref>). Following the same steps as before we can compute the matrix implementing the induced map as:

\begin{equation*}
\begin{aligned}
&\Tredmat=\J \left(\bigotimes_{x\in\L} \tau_{\pm 1}^N \right) \J^\dag=\\
&=\left(\bigotimes_{x\in\mathcal{L}'}\J_{\Lambda_x} \right) \left(\bigotimes_{x\in\L} \tau_{\pm N} \right) \left(\bigotimes_{y\in\mathcal{L}'}\J_{\Lambda_{y}} \right).
\end{aligned}
\end{equation*}

Exploiting the fact that the size of each $\Lambda_x$ is N, we have $\tau_{\pm N}\ket{\psi_{k}^{(x)}}=\ket{\psi_{k}^{(x\pm 1)}}$, i.e. $\tau_{\pm N}$ shifts the whole $\Lambda_x$ in $\Lambda_{x\pm 1}$ and, consequently, $\tau_{\pm N} \J_{\Lambda_x}=\J_{\Lambda_{x+1}}$. In this way we have:

\begin{equation*}
\begin{aligned}
&=\left(\bigotimes_{x\in\mathcal{L}'}\J_{\Lambda_x} \right) \left(\bigotimes_{y\in\mathcal{L}'}\J_{\Lambda_{y+1}} \right)=\tau_{\pm 1}.
\end{aligned}
\end{equation*}

In other words, N steps of a shift in $\L$ are renormalised to a single step of a shift in $\L'$. A pictorial representation of the size-2 renormalisation is shown in fig.(<ref>).

(A) at (-3,0)  0.5!LocUnit;
(B) at (2,0) 0.4!LocUnitprim;
[->,line width=2pt] ($(A)+(2.2,0)$)–($(B)-(1.8,0)$);

(A) at (-3,0)  0.5!Leftshtwo;
(B) at (2.1,-0.1) 0.4!Leftshmod;
[->,line width=2pt] ($(A)+(2.3,0.2)$)–($(B)-(1.9,-0.3)$);

Trivial examples of size-2 renormalisation over one dimensional lattices. (a) Example of renormalisation of a local transformation. Here we have $\Lambda_x=\{2x,2x+1\}$, two steps of the unitary matrix $U$ over two cells are mapped in a single application of the new matrix $U'$. (b) Example of renormalisation of two steps of a right shift with $\Lambda_x=\{2x,2x+1\}$. After two steps, all the content of $\Lambda_x$ is moved in $\Lambda_{x+1}$. Thus the renormalised evolution is a shift $x\rightarrow x+1$ in the $\L'$ lattice.

Notice that, in principle, when we deal with more complex automata, we have no reason to believe that $\Tredmat$ is a unitary matrix. However, condition (<ref>) implies that $\Tredmat=U_\tS e^{i\phi}$ is a unitary matrix for every suitable lattice $\mathcal{L}$. If this is the case eq.(<ref>) guarantees that $\Tred$ is an

The following Lemma imposes a necessary and sufficient condition on $U_\tT$ for eq.(<ref>) to hold:

Eq.(<ref>) holds with $\tS_\mathcal{L}=(\tT^N)_r$ being an automorphism iff

\begin{equation}\label{eq:commuwrap}
\end{equation}

If (<ref>) holds, we can compose it on the right with $\tJ$ and get

\begin{equation}
\tT^N_w\circ \tP=\tV\circ\tS_w\circ\tJ.
\end{equation}

Now, composing r.h.s. of the latter expression with $\tP=\tV\circ\tJ$ on the left gives
\tP\circ\tV\circ\tS_w\circ\tJ=\tV\circ\tS_w\circ\tJ=\tT^N_w\circ\tP,
while on the other hand, considering l.h.s., we obtain
\tP\circ\tT^N_w\circ\tP=\tT^N_w\circ\tP.

In terms of the unitary matrix $U_{\tT^N}$ this means:
\Pi U_{\tT^N}\Pi=\Pi U_{\tT^N}$,
i.e.  $U_{\tT^N}$ is block-diagonal over $\operatorname{Supp}(\Pi)$,

and the commutation relation (<ref>) trivially follows.
To prove the converse,
we now remind that $\Tredmat =\J\Tnmat\J^\dag$. Remembering that $\J\J^\dag=I$ and
$\J^\dag\J=\Pi_{\mathcal{L}}$, we then have

\begin{align*}
&\Tredmat \Tredmat^\dag= \J \Tnmat \J^\dag\J \Tnmat^\dag \J^\dag=\\
&= \J \Tnmat \Pi \Tnmat^\dag \J^\dag  = \J \Pi \Tnmat\Tnmat^\dag \J^\dag=\\
&=\J\J^\dag\J\J^\dag= I_{\mathcal{L'}},
\end{align*}

where we exploited the commutation of $\Tnmat$
with $\Pi$. The same holds for
$\Tredmat^\dag\Tredmat$ and thus $\Tredmat$ is
unitary over $\Aredloc $.  We can thus make the
identification $U_\tS=\Tredmat$, and obtain the
which yelds
\tV\circ\tS_w=\tT^N_w\circ\tV,
with  $\tS_w$ an automorphism of the lattice algebra

Notice that eq. (<ref>) is necessary and sufficient for condition (<ref>) for some automorphism $\tS_\mathcal L$, which by now is not necessarily the wrapped version of a fixed QCA $\tS$ on $\mathbb Z^s$. Thus, we do not have yet a necessary and sufficient condition for renormalisability.

It is easy to see that the commutation
relation (<ref>) can be formulated as

\begin{align}
\begin{aligned}
&\Tnmat \Pi
\Tnmat^\dag=\Pi \iff
\tT^N_w(\Pi)=\Pi,
\end{aligned}
\label{eq:conschaingen}
\end{align}

for all the possible lattices.  We now show that all
maps $\tS_\mathcal L$ share the same local rule. This has
two important consequences. The first one is that eqs. <ref>
and (<ref>) become necessary and sufficient for renormalisability through
$(\Pi_0,\Lambda_0)$. The second and most powerful one is that we can check the
condition in eq.(<ref>) only on
the smallest lattice such that the neighborhood of
$\tT^N$ is regular.  We first state the
following two lemmas. The first one relates the
translations in $\mathcal{L}$ with the ones in the
coarse-grained lattice $\mathcal{L}'$:

$(\tT^N)_r$ is invariant under shifts on $\mathcal{L'}$

A shift $\tau_x^w$ along the vector $x$ in $\mathcal{L'}$
corresponds to a shift $\tau_{Nx}^w$
along the vector $Nx$ in $\mathcal{L}$.
Since  $\tJ,\tV$ and the evolution
$\tT^N$ commute with $\tau_{Nx}^w$,
their composition $(\tT^N)_r$ commutes as well.

The other Lemma we have to prove is about the form of the unitary matrix $\Tnmat$.

$\Tnmat$ can be written in the following form:

\begin{align*}
&\Tnmat=[(I_{\Lambda_{0}}\otimes V)(U\otimes I_{\Lambda_{\mathcal W}})],\\
&\mathcal W\coloneqq\mathcal{L}\setminus(\Lambda_0\cup\mathcal{N}^N_{\Lambda_0}),
\end{align*}

where $U$ is independent of the wrapping, and $\mathcal{N}^N_{\Lambda_0}$ denotes the neighbourhood of $\Lambda_0$ for $\tT^N$.

Since $\tT(\mathsf{A}(\Lambda_0))\subseteq\mathsf{A}(\mathcal{N}_{\Lambda_0})$, this means that $\tT^N(\mathsf{A}(\Lambda_0))\subseteq\mathsf{A}(\mathcal{N}^N_{\Lambda_0})$.
In other words, the algebra $\tT^N(\mathsf{A}(\Lambda_0))$ is an homomorphic
representation of the full matrix algebra $\mathsf{A}(\Lambda_0)$ in
$\mathsf{A}(\mathcal N^N_{\Lambda_0})$, which means that there exists a unitary
$U\in\mathsf{A}(\Lambda_0\cup\mathcal N^N_{\Lambda_0})$ such that, for every
$X\in\mathsf A(\Lambda_0)$,

\begin{align*}
&\tT(X)=U^\dag(X\otimes I_{\mathcal{N}^N_{\Lambda_0}\setminus\Lambda_0})U\in\mathsf A(\Lambda_0\cup\mathcal{N}_{\Lambda_0}).
\end{align*}

Since $\tT$ and $\tT_w$ share the same local rule, we then have

\begin{align*}
\tT_w(X)&=\Tnmat^\dag(X\otimes I_{\mathcal{L}\setminus\Lambda_0})\Tnmat\\
%\tilde{X}_{\Lambda+\mathcal{N}^N_\Lambda}\otimes I_{\mathcal{L}\setminus(\Lambda+\mathcal{N}^N_{\Lambda})},
%where $\tilde X$
U^\dag(X\otimes I_{\mathcal{N}^N_{\Lambda_0}\setminus\Lambda_0})U\otimes I_{\mathcal{L}\setminus(\Lambda_0\cup\mathcal{N}^N_{\Lambda_0})}.
\end{align*}

One can easily prove that this implies

\begin{equation*}
\Tnmat(U\otimes I_{\mathcal{L}\setminus(\Lambda_0\cup\mathcal{N}^N_{\Lambda_0})})^\dag=(I_{\Lambda_0}\otimes V),
\end{equation*}

for some unitary $U\in\mathsf A(\mathcal L\setminus \Lambda_0)$, and finally

\begin{equation}\label{eq:decompun}
\Tnmat=(I_{\Lambda_0}\otimes V)(U\otimes I_{\mathcal{L}\setminus(\Lambda_0\cup\mathcal{N}^N_{\Lambda_0})}).
\end{equation}

Since the neighbourhood of $\Lambda_0$ after $N$ steps is $\Lambda_{\mathcal{N}}$, this gives the above decomposition.

We now prove that the commutation condition is independent of the lattice $\mathcal L$.
If condition in (<ref>) is satisfied for a lattice $\mathcal{L}$ where $\tT^N$ is regular, then it is true for every other such lattice.

Let us divide the chain $\Pi_\mathcal{L}$ over $\mathcal{L}$ in

\begin{equation}
\begin{split}
&\Pi=\Pi_{0}\otimes\Pi_{{\mathcal{M}}}\otimes \Pi_{\mathcal W},\\
&{\mathcal M}\coloneqq\mathcal{N}\setminus\{0\},\\
&\mathcal W\coloneqq\mathcal{L}\setminus(\mathcal{N}\cup \{0\}),
\end{split}
\end{equation}

with the convention:

\begin{align*}
\Pi_{{R}}=\left(\bigotimes_{x\in R}\Pi_{{x}}\right).
\end{align*}

The commutation relation (<ref>) can then be expressed as

\begin{equation}
%&\Tnmat(\Pi_{0}\otimes\Pi_{{\mathcal{N}}}\otimes \Pi_W)\Tnmat^\dag=\\
%&=\Pi_{0}\otimes\Pi_{\mathcal{N}\setminus\{0\}}\otimes \Pi_W.
\begin{split}
&\Tnmat(\Pi_{0}\otimes\Pi_{\mathcal M}\otimes \Pi_{\mathcal W})\Tnmat^\dag=\Pi_{0}\otimes\Pi_{\mathcal M}\otimes \Pi_{\mathcal W}.
\end{split}
\label{eq:Tpi}
\end{equation}

We can represent eq. (<ref>) diagrammatically, with the decomposition (<ref>) of $\Tnmat$, as follows

\begin{equation}
\tikzfig{TnPi} = \tikzfig{PiLact}\ .
\end{equation}

Exploiting the decompositon in eq.(<ref>) and conjugating both members of eq. (<ref>) with $(I_{\Lambda_{0}}\otimes V)^\dag$ we get to:

\begin{equation}
\begin{split}
&(U \otimes I_{\Lambda_{\mathcal W}})(\Pi_{0}\otimes\Pi_{\mathcal M}\otimes \Pi_{{W}})(U\otimes I_{\Lambda_{\mathcal W}})^\dag=\\
&=(I_{\Lambda_{0}}\otimes V)^\dag(\Pi_{0}\otimes\Pi_{\mathcal M}\otimes \Pi_{{W}})(I_{\Lambda_{0}}\otimes V).
\end{split}
\end{equation}

\begin{equation}\label{eq:diagfact}
\tikzfig{TnPiLeft}=\tikzfig{TnPiRight}\ .
\end{equation}

The two members of eq. (<ref>) are factorised in two different ways. This implies that both factorisations must hold, and then

the transformation $V$ on the right produces a factorised projection map, i.e.

\begin{equation}
\begin{split}
&(I_0\otimes V)^\dag(\Pi_{0}\otimes\Pi_{\mathcal M}\otimes \Pi_{{\mathcal W}})(I_0\otimes V )=\\
&=\Pi_{0}\otimes Z^\dag\Pi_{{\mathcal{M}}}Z\otimes \Pi_{{\mathcal W}},
\end{split}
\end{equation}

for some unitary $Z\in\mathsf A(\Lambda_\mathcal M)$. In particular, we have the following diagrammatic identity

\begin{equation}
\tikzfig{TnPish}=\tikzfig{TnPiZen}\ .
\end{equation}

The latter is independent of the lattice $\mathcal L$, and proves that the image of
$\Pi$ under $\Tnmat \rvert_\Pi$ is a projection of the form
$\tilde\Pi_{{\mathcal L'\setminus\{0\}}}\otimes\Pi_{0}$. Finally, by translation
invariance we can conclude that for every $\mathcal L$ such that $\tT^N$ is regular over
$\mathcal L$ one has

\begin{align*}
\Tnmat^\dag \Pi \Tnmat=\Pi,
\end{align*}

namely condition (<ref>) holds.

This immediately implies the following corollary

If condition in (<ref>) is satisfied for a lattice $\mathcal{L}$ where $\tT^N$ is regular, then

\begin{align}
\begin{split}
&(U\otimes I_\mathcal W)^\dag(\Pi_{0}\otimes Z^\dag\Pi_{{\mathcal{M}}}Z\otimes \Pi_{{\mathcal W}})(U\otimes I_\mathcal W)\\
&=\Pi_{0}\otimes \Pi_{{\mathcal{M}}}\otimes \Pi_{{\mathcal W}}.
\end{split}
\end{align}

The above result allows us to show that condition (<ref>) is necessary and sufficient for renormalisability through $(\Pi_0,\Lambda_0)$.

Let $\tT^N$ be regular on the lattices $\mathcal L'$ and $\tilde{\mathcal L}'$, and let condition (<ref>) be satisfied for both. Then the local rule of $(\tT^N)_r$ over

$\mathcal{L'}$ and $\mathcal{\tilde{L}'}$ is the same.

It is sufficient to notice that a local operator $A_x$ in $\Aplocc$ is obtained as $\Pi A_{\Lambda_x}\Pi$ for some $A_{\Lambda_x}$ on the macro-cell
$\Lambda_x$. As a consequence, one has

\begin{align*}
&\Tnmat^\dag A_x \Tnmat=\Tnmat^\dag \Pi A_{\Lambda_x}\Pi\Tnmat\\
%&=\Pi\Tnmat^\dag \Pi A_{\Lambda_x}\Pi \Tnmat\Pi\,.
%Remembering eq.~\eqref{eq:decompun}, we have
%\Tnmat^\dag A_x \Tnmat
&\quad=U^\dag(\Pi_xA_{\Lambda_x}\Pi_x\otimes Z^\dag\Pi_{\mathcal N_{\Lambda_x}\setminus\Lambda_x} Z)U \otimes\Pi_{\mathcal L\setminus(\Lambda_x\cup\mathcal N_{\Lambda_x})}),
\end{align*}

where $U$ is independent of $\mathcal L'$. Finally, reminding eq. (<ref>) and (<ref>), one has

\begin{align*}
\end{align*}

for every $\tilde{\mathcal L'}$, where we indicated with $(\tT^N)_r\rvert_{\mathcal{L}}$ the evolution $(\tT^N)_r$ restricted to the particular lattice $\mathcal{L}$.

We have then proved the main result of this section

Let $\tT$ be a QCAs on $\mathbb{Z}^s$,
$N$ be a natural number
and let $\Pi_0 \in \mathsf{A}(\Lambda_0)$ be a
projection on the local algebra of the region
$\Lambda_0 \coloneqq [0,N-1]^s$.
The following conditions are equivalent:

* there exists a QCA $\tS$
on $\mathbb{Z}^s$ which is a size-$N$ renormalisation of
through $(\Pi_0,\Lambda_0)$.

* there exist a lattice
$\mathcal{L} = \mathbb{Z}^s_{Nf}$ such that the
regular neighborhood condition is satisfied for
$\tT^N$ and $[\Tnmat,\Pi]=0$, where $\Tnmat$ is
the unitary matrix defining
the QCA on the lattice $\mathcal{L}$.

This proves that the renormalisability condition of
Eq.(<ref>), reduces to a finite dimensional
equation in terms of the unitary matrix defining
the QCA on a wrapped lattice. In particular, the renormalisability condition can be checked by considering the
smallest wrapped lattice such that the regular neighbourhood condition is satisfied.

We showed that our definition of renormalisability boils down to having a chain of factorised projections that commute with the evolution as in eq.(<ref>). This chain of projections $\Pi$ identifies the degrees of freedom of the observable algebra of the lattice that we are preserving in the coarse-graining—i.e.its support—while the discarded ones correspond to the kernel of $\Pi$.  To each such projection, we can associate a family of operators $\J$ as defined in eq.(<ref>) and related to the projection as in eq.(<ref>). Each element of the family differs from each other by a unitary rotation, namely the operators $\J$ and $\J'$ give rise to the same projection if :

\begin{align*}
\J'=\bigotimes_{x\in\mathcal{L'}} U_x \J \hspace{10pt} U_x \in SU(d).
\end{align*}

To such family of operators $\J$ we can naturally associate a family of $\tJ,\tV$ as in eq.(<ref>).
Each of those choices give rise to renormalised automata that differ by a local change of basis, namely, considering $\J$ and $\J'$ as above the respective unitaries that implement the induced maps are:

\begin{align*}
&\Tredmat^{\J} = \J  \Tnmat \J^\dag \\
&\Tredmat^{\J'} = \J'  \Tnmat \J'^\dag =\left (\bigotimes_{x\in\mathcal{L'}} U_x \J \right) \Tnmat \left (\bigotimes_{y\in\mathcal{L'}} U_y \J\right )^\dag=\\
&=\left (\bigotimes_{x\in\mathcal{L'}} U_x \right) \Tredmat \left (\bigotimes_{y\in\mathcal{L'}} U_y \right )^\dag.
\end{align*}

In other words, the choice of the basis $\{\ket{k}\}_k$ in the operator $\J$ represents the basis of the coarse-grained algebra in which we are mapping the degrees of freedom identified by $\Pi$.

§ RENORMALISATION OF
ONE-DIMENSIONAL QUANTUM CIRCUITS

In this section we specify our analysis to QCAs on
a one dimensional lattice that can be realised as
FDQCs. In
particular, we will consider size-$2$ coarse-graining,
i.e. two cells and two steps are coarse-grained
into one cell and one step (the
projections $\Pi_{x}$ act on two cells).  Up
to grouping neighbouring cells together, we can
consider the case in which the QCA $\tT$ is
nearest-neighbuor. From the index theory of QCAs
[43] we have that $\tT$ is realisable as
a quantum circuit if and only if $\ind(\tT) =
1$. Then $\tT$ can be implemented as a Margolous
partitioning scheme (see Proposition
<ref>) as follows:

\begin{equation}
\tT =\tikzfig{MargInd1}\ ,
\label{eq:marg}
\end{equation}

Let us now focus on the action of $M_1$. We have:

\begin{equation}
\tikzfig{Margact}\eqqcolon\tikzfig{Margact2}\subseteq L\otimes R
\end{equation}

This means that after the application of
M1, the transformation M2 will
embed the left and right subsystem in the left and
right support algebra. In other words M1
separates the counterimage under the evolution of
the QCA of the left and right support algebra of
the two cells in the left and right cell,
respectively. Diagrammatically:

\begin{equation}
\tikzfig{Separator}\subseteq \tT^{-1}(\mathsf{L})\otimes \tT^{-1}(\mathsf{R})
\end{equation}

That is, the content of the left cell after the
application of $M_1$ will be mapped in the two
cells on the left after the evolution, and the one
of the right cell into the two cells on the right.

In this way the role of the Margolous is to take
two cells and divide them into the counterimage
of the left and right support algebra. This mean
that the first transformation acts on the two
cells as

\begin{equation}
\begin{split}
&\tikzfig{Separator}=\sum_{\mu_x}\lambda^{(x)}_{\mu_x}\otimes \rho^{(x)}_{\mu_x}\\
&\tikzfig{Separator}\subseteq T^{-1}(L)\otimes T^{-1}(R)\\
\end{split}
\end{equation}

i.e. it is the counterimage of the right and left support algebra of the super cell or- less formally- it is what the evolution will move to the right and to the left respectively. The role of the transformation $\tikzfig{M2}$ is to re-embeds the right and left support algebra into two cells, i.e.

\begin{equation}
\prod_{(x,x')\in(\mathcal{N}^+,\mathcal{N}^-)}\sum_{\mu_x\mu_x'}\tikzfig{remix}\subseteq L\otimes R
\end{equation}

Let us now consider a size-$2$ renormalisation of
a QCA that can be implemented as in Equation
<ref>.  Thanks to Proposition
(<ref>) we can
consider the case in which $\tT$ is defined on a
finite lattice. We start with the following lemma.

Let $\tT$ be QCA that admits a realisation as a
finite depth quantum circuit as in  Equation
<ref>. Then $\tT$  admits a size-$2$ renormalisation if and only if

\begin{equation}
\resizebox{0.8\hsize}{!}{
\tikzfig{SepevConj}=\tikzfig{RLChain}}
\label{eq:RenIndex}
\end{equation}

where we define

\begin{align}
\label{eq:4}
P_{\Lambda_x} = \tikzfig{Piseparated}\coloneqq\tikzfig{Pisep}.
\end{align}

We can write

\begin{equation}
\tT^{2}(\bigotimes_{x\in\mathcal{L'}}\Pi_{x})=\tikzfig{T2}
\end{equation}

Since each step is translationally invariant we can shift the second evolution step in order to have

\begin{equation}
\tT^{2}(\bigotimes_{x\in\mathcal{L'}}\Pi_{x})=\tikzfig{T2shift}.
\end{equation}

By introducing the projection $P_{\Lambda_x}$, we have

\begin{equation}
\resizebox{0.8\hsize}{!}{\tikzfig{Sepev}=\tikzfig{Pichain}
\end{equation}

and by applying $\tikzfig{M1}$ on both sides we obtain the thesis.

It is now convenient to define the operator

\begin{equation}
\label{eq:definitionofG}
G\coloneqq \tikzfig{Ggen}\eqqcolon\tikzfig{Gfig},
\end{equation}

so that we have

\begin{equation}
\resizebox{0.8\hsize}{!}{
\tikzfig{SepevConj}=\tikzfig{Gev}}.
\label{eq:Gev}
\end{equation}

It is also convenient to consider the
Schmidt decomposition of the projection $P_{\Lambda_x}$:

\begin{equation}
P_{\Lambda_x}= \tikzfig{Piseparated}
\label{eq:SchmidtLR}
\end{equation}

In terms of $G$ and of the operators $\{\lambda_{\mu_x}, \rho_{\mu_x}\}$ we have the
following necessary and sufficient condition for $\tT$ to admit a size-$2$ renormalisation.

A one dimensional QCA $\tT$ that has a
Margolus partitioning scheme as in Equation <ref> admits a size-$2$ renormalisation iff

\begin{align}
G^\dag (\rho_{\mu}\otimes\lambda_{\nu}) G=\tilde\rho_{\mu}\otimes\tilde\lambda_{\nu},\quad \forall \mu,\nu,
\label{eq:cond}
\end{align}

where we introduced the Schmidt decomposition of the projection $G P_{\Lambda_x}G^\dag $, i.e.

\begin{align}
\tikzfig{NewDiff}\coloneqq G\left(\sum_{\mu}{\lambda}_\mu\otimes{\rho}_\mu\right)G^\dag=:\sum_{\mu}\tilde{\lambda}_\mu\otimes\tilde{\rho}_\mu.
\end{align}

Inverting the second layer of $G$'s on both sides of (<ref>) we have:

\begin{align}
\begin{aligned}
&\sum_{\boldsymbol\mu}\bigotimes_{x\in\mathcal{L'}} G^\dag(\rho_{\mu_{x-1}}\otimes\lambda_{\mu_x})G= \\
& =\bigotimes_{x\in\mathcal{L'}}\sum_{\mu_x}G(\lambda_{\mu_x}\otimes\rho_{\mu_x})G^\dag
\end{aligned}
\label{eq:Gconv}
\end{align}

where the sum over $\boldsymbol\mu$ is shorthand for the sum over all the indices $\mu_x$,
for $x\in\mathcal L'$.

In diagrams, eq. (<ref>) reads

\begin{equation}
\resizebox{0.85\hsize}{!}{
\tikzfig{LeftG}=\tikzfig{Newchain}}\ .
\end{equation}

Since the right hand side in eq. (<ref>) is factorised, so should be the left
hand side. This means that we can invert all the $G$'s but one, and use linear independence of the terms in the Schmidt decomposition to get

\begin{equation}
G^\dag (\rho_{\nu}\otimes\lambda_{\mu})G=\tilde\rho_{\nu}\otimes\tilde\lambda_{\mu}
\label{eq:tilde}
\end{equation}

for all the possible combinations of $\mu,\nu$.

It is easy to see that the renormalisability conditions (<ref>) imply that

\begin{align}
(  {\rho}^{(n)}\otimes  {\lambda}^{(n)})
\tilde{\rho}^{(n)} \otimes   \tilde{\lambda}^{(n)}
\label{eq:mon}
\end{align}

where ${\rho}^{(n)},  {\lambda}^{(n)},
\tilde{\rho}^{(n)}$ and  $ \tilde{\lambda}^{(n)}$ denote the monomials of order $n$ in
$\rho_\mu, \lambda_\mu , \tilde{\rho}_\mu$ and
$\tilde{\lambda_\mu} $ respectively, i.e.

\begin{align*}
\quad
\rho^{(n)}= \rho_{x_1}...\rho_{x_n} \\
\tilde{\rho}^{(n)}=\rho_{x_1}...\rho_{x_n}
\end{align*}

We have then the following result.

Let us denote with
$\mathsf{M} = \langle \{ \rho_\mu \} \rangle$,$\mathsf{N}=\langle \{ \lambda_\mu \} \rangle, \tilde{\mathsf{M}}=\langle \{ \tilde{\rho}_\mu \} \rangle$
and $\tilde{\mathsf{N}} = \langle \{ \tilde{\lambda}_\mu \} \rangle$ the algebras generated
by $\rho_\mu, \lambda_\mu , \tilde{\rho}_\mu$
and $\tilde{\lambda_\mu} $. Then, for any
$ A \in \mathsf{N}$, $B \in \mathsf{M}$ there exist
$\tilde{A} \in \tilde{\mathsf{N}}$ and
$\tilde{B}\in   \tilde{\mathsf{M}}$
such that

\begin{equation}
\begin{split}
G^\dag (A\otimes B)G=\tilde{A}\otimes\tilde{B}
\end{split}
\label{eq:GAlg}
\end{equation}

Since $P^2=P$, we have

\begin{align}
\label{eq:6}
\lambda_\mu=\sum_{j,k}
c_\mu^{j,k}\lambda_j\lambda_k \quad
\rho_\nu=\sum_{j,k}d_\nu^{j,k}\rho_j\rho_k.
\end{align}

for suitable coefficients $c_\mu^{j,k}$ and
$d_\nu^{j,k}$. By iteratively using Equation (<ref>) we can express any homogeneous polynomial of degree $n$
in the variables $\lambda_\mu$ as a homogeneous polynomial of degree $n+k$ for any $k$,  and the same holds for homogeneous polynomial in the variables $\rho_\mu$.
Then, any arbitrary $A \in \mathsf{M}$ and $B \in \mathsf{N}$ can be written as homogeneous polynomials of the same degree $n$ for sufficiently large $n$.
The thesis now follows from Eq. (<ref>).

If $G$ commutes with the swap

then  $[G^2,P]=0$ and

\begin{align}
\label{eq:5}
\begin{aligned}
&\forall A \otimes B \in \mathsf{K}, \exists
\tilde{A} \otimes \tilde{B} \in \tilde{\mathsf{K}}  \mbox{ such that }\\
&G^\dag (A\otimes B)G=\tilde{A}\otimes\tilde{B},
\end{aligned}
\end{align}

where we defined

\begin{align}
\label{eq:7}
\begin{aligned}
\mathsf{K}:=
(\mathsf{M}\otimes\mathsf{N} \cup
\mathsf{N}\otimes\mathsf{M} )''
\\
\tilde{\mathsf{K}}:=
(\tilde{\mathsf{M}}\otimes \tilde{\mathsf{N}} \cup
\tilde{  \mathsf{N}} \otimes  \tilde{\mathsf{M}} )''
\end{aligned}
\end{align}

If $G$ commutes with the swap, Equation
$(\ref{eq:cond})$ implies that

\begin{align}
\label{eq:9}
\lambda_{\mu}\otimes\rho_{\nu}=
G (
\tilde{\lambda}_{\mu}\otimes\tilde{\rho}_{\nu}
G^{\dag}   .
\end{align}

Then we have:
$G^2PG^{\dag 2} = G(G P G^{\dag} ) G^{\dag} = G(
\sum_ \mu  \tilde{\lambda}_{\mu}\otimes\tilde{\rho}_{\mu})  G^{\dag}  =
\sum_ \mu  \lambda_{\mu}\otimes \rho_{\mu} = P$.
From Equation (<ref>) we have that
Equation <ref>
holds for every operator generated by $\{\lambda_\mu\otimes\rho_\nu\}
\cup \{\rho_\nu\otimes\lambda_\mu\}$.

§.§ Renormalisation of a quantum circuit to a QCA with a different index

In this section we we will consider the case in
which a one dimensional QCA with index equal to
$1$ admits a size-$2$ renormalisation to a QCA
which is given by a left or right shift
followed by local unitaries.

need to be able to identify a full matrix algebra
of $d\times d$ matrices in the macro-cell
$\Lambda_x$, that after two steps is totally moved
to the left macro-cell. The following proposition
specialises the renormalisability condition to this

The condition (<ref>) in the case of renormalisation of a unit index QCA to a QCA with different index reduces to

\begin{equation}
\sum_{\boldsymbol\mu}\bigotimes_{x\in\mathcal{L}}\tilde{\lambda}_{\mu_{x+1}}\otimes\tilde{\rho}_{\mu_{x-1}} =\sum_{\boldsymbol\mu}\bigotimes_{x\in\mathcal{L}}\lambda_{\mu_{x}}\otimes\rho_{\mu_{x}} ,
\end{equation}

where $\tilde{\lambda}_{\mu_{x+1}}=V{\lambda}_{\mu_{x+1}}V^\dag$ and $\tilde{\rho}_{\mu_{x-1}}=V{\rho}_{\mu_{x-1}}V^\dag$ for some unitary operator $V$.

The support algebra of a macro-cell $\Lambda_x$ in $\Lambda_{x-1}$ after two steps is a subalgebra $\mathsf L'$ of $\mathsf L_{2x-1}\cap\tT(\mathsf L_{2x})\simeq\mathsf \tT^{-1}(L_{2x-1})\cap\mathsf L_{2x}$, and that of $\Lambda_x$ in $\Lambda_{x+1}$ after two steps is a subalgebra $\mathsf R'$ of $\mathsf R_{2x+1}\cap\tT(\mathsf R_{2x})\simeq\mathsf \tT^{-1}(R_{2x+1})\cap\mathsf R_{2x}$. Starting from an index 1-QCA $\tT$, we have $\dim\mathsf L=\dim\mathsf R=d^2$. If we now consider a projection $\Pi$ with rank $d$, and a general subalgebra $\mathsf S$ of $\mathsf A_{\Lambda_{x\pm1}}$, we have

\begin{align*}
\dim(\Pi\mathsf S\Pi)\leq\dim(\mathsf S),
\end{align*}

and thus, if we want to have

\begin{align*}
\dim(\Pi\mathsf L'\Pi)=d^2\qquad(\textrm{or }\dim(\Pi\mathsf R'\Pi)=d^2),
\end{align*}

we need to have

\begin{align*}
&\mathsf L'=\tT^{-1}(\mathsf L_{2x-1})\cap\mathsf L_{2x}\equiv\tT^{-1}(\mathsf L_{2x-1})\equiv\mathsf L_{2x}\\
&\ (\textrm{or }\mathsf R'=\tT^{-1}(\mathsf R_{2x+1})\cap\mathsf R_{2x}\equiv\tT^{-1}(\mathsf R_{2x+1})\equiv\mathsf R_{2x})
\end{align*}

Finally, this implies that, in order to have a renormalisation to a left shift or right shift, we need to have $\tT(\mathsf L)\equiv\mathsf L$ or $\tT(\mathsf R)\equiv\mathsf R$, respectively. Notice however that $\tT(\mathsf L)\equiv\mathsf L$ if and only if
$\tT(\mathsf R)\equiv\mathsf R$.

This implies that $M_2$ must map the algebra in its right input cell to
$\tT^{-1}(\mathsf L)$ and that in its left input in $\tT^{-1}(\mathsf R)$, i.e. it must be equal to a swap followed by local isomorphisms followed by $M^{-1}_1$. Finally, this implies that

the composition of $\tikzfig{M2}$ and $\tikzfig{M1}$ results in a swap up to a local unitary, or—diagrammatically—

\begin{equation}
\tikzfig{Ggen}=\tikzfig{Uswap}\\
\label{eq:Uswap}
\end{equation}

In this way eq.$(\ref{eq:RenIndex})$ becomes

\begin{equation}
\resizebox{0.8\hsize}{!}{\tikzfig{RenInd1}=\tikzfig{RLChain}},
\label{eq:not1}
\end{equation}

Using the decomposition in eq.$(\ref{eq:SchmidtLR})$ and computing the left side of the previous equation we get

\begin{equation}
\tikzfig{RenInd1}=\sum_{\boldsymbol\mu}\bigotimes_{x\in\mathcal{L}}\tilde{\lambda}^{(x)}_{\mu_{x+1}}\otimes\tilde{\rho}^{(x)}_{\mu_{x-1}} ,
\end{equation}

where $\tilde{\lambda}^{(x)}_{\mu_{x+1}}=U^2{\lambda}^{(x)}_{\mu_{x+1}}{U^\dag}^2$ and $\tilde{\rho}^{(x)}_{\mu_{x-1}}=U^2{\rho}^{(x)}_{\mu_{x-1}}{U^\dag}^2$
Here we introduced a superscript to keep track of the the macro-cell on which an operator acts $\textit{after}$ the evolution, while the subscript is a summation index that is reminiscent of the macro cell on which the operator acted $\textit{before}$ the evolution. In this way eq.$(\ref{eq:not1})$ becomes

\begin{equation}
\sum_{\boldsymbol\mu}\bigotimes_{x\in\mathcal{L}}\tilde{\lambda}^{(x)}_{\mu_{x+1}}\otimes\tilde{\rho}^{(x)}_{\mu_{x-1}} =\sum_{\boldsymbol\mu}\bigotimes_{x\in\mathcal{L}}\lambda^{(x)}_{\mu_{x}}\otimes\rho^{(x)}_{\mu_{x}} \,.
\label{eq:diffind}
\end{equation}

In the following we prove that, if eq.(<ref>) holds, then no renormalisation
other than the one that changes the index is allowed.

If eq.(<ref>) holds for a given unitary index QCA, that QCA can only be
renormalised into a QCA with non-unitary index. Moreover, the rank-2 projections $P$ can
only be:

\begin{equation}
\ket{\phi_0}\bra{\phi_0}\otimes I\\
\end{equation}

On the left we have that the summation index $\mu$ is the same for $\tilde{\lambda}^{(x)}_\mu$ and $\tilde{\rho}^{({x+2})}_\mu$. So if we multiply both sides by a fixed
$(\tilde{\rho}^{({x+2})}_\nu)^\dag$ in the macro-cell $(\Lambda_{x+2})$ and
$(\tilde{\lambda}^{({x-2})}_\gamma)^\dag$ in the macro-cell $(\Lambda_{x-2})$, and take the partial trace on the corresponding spaces, the expression on both sides is left such that the operator on the macro-cell $\Lambda_{x}$ is factorized from the rest, and

we have

\begin{equation}
\tilde{\lambda}^{({x})}_{\nu}\otimes\tilde{\rho}^{({x})}_{\gamma}=\sum_{\mu_x}\lambda^{(x)}_{\mu_x}\otimes\rho^{(x)}_{\mu_x}.
\end{equation}

In order to have the equality between the two members we need to have only one term in the expression of eq.$(\ref{eq:SchmidtLR})$, i.e.

\begin{equation}
\tikzfig{Pisep}=\tikzfig{Piseparated}=\begin{cases}
\ket{\phi_0}\bra{\phi_0}\otimes I\\
\end{equation}

Moreover, in order for eq.$(\ref{eq:not1})$ to be
satisfied, either $\ket{\phi_0}$ or $\ket{\psi_0}$
should be eigenstates of the local unitary U in
eq.$(\ref{eq:Uswap})$.  But this means that our
projection will select only the left or the right
algebra. Thus the renormalised evolution will
consist in an algebra moving to the left or to the
right, depending on the choice of the projection.

§ RENORMALISATION OF ONE DIMENSIONAL QUBIT QCA

In this section we will apply the tools developed
so far to the renormalisation of one dimensional
qubit QCAs with index $1$, i.e. QCA on
$\mathbb{Z}$ such that each cell is a two
dimensional quantum system and such that they can
be realized as a finite depth quantum circuit.

Comparing Equation (<ref>) with Equation (<ref>) we have

\begin{align}
\tikzfig{M2}=\tikzfig{M2qbit}\ ,\
\tikzfig{M1}=\tikzfig{def2}\ .
\end{align}

and the operator $G$ of Equation (<ref>) becomes

\begin{align}
G=C_{\phi}(U\otimes U)C_\phi
\label{eq:Gqubit}
\end{align}

A qubit QCA that is renormalisable only admits unit index renormalisations.

By the argument in the previous section, in order to have a renormalised QCA with index different from unit we should have

\begin{equation}
G=(U'\otimes U'){S},
\end{equation}

where ${S}$ is the swap operator, $S\ket{\psi}\ket{\phi} = \ket{\phi}\ket{\psi} $.
Diagrammatically this reads

\begin{equation}
\tikzfig{G}=\tikzfig{Uprimeswap} .
\end{equation}

This is impossible, since we need at least three controlled gates in order to have a swap, and only two controlled phases appear in the expression of $G$. Thus the renormalised evolution will have index 1.

4|c|Renormalised evolutions

$\tT$     $P=Q_1$     $P=Q_2$     $P=I\otimes\ketbra{c}{c}$

2*$\begin{cases}\phi\not\in\{0, \pi\}\\
n_x=n_y=0\end{cases}$     $\begin{cases}
\phi'=2\phi\\
\theta'=\phi-4\theta
\end{cases}$
2*  $\begin{cases}
\phi'=-2\phi\\
\theta'=\phi
\end{cases}$     2*$\begin{cases}
\phi'=0\\
\theta'=\pm 2(\theta+\delta_{c,0} \phi)
\end{cases}$

\phi'=2\phi\\
\theta'=4\theta-3\phi
\end{cases}$

$\begin{cases}\phi\not\in\{0, \pi\}\\
\theta=\frac{\pi}{2}
\end{cases}$    $\begin{cases}
\phi'=2\phi\\
\theta'=-\phi
\end{cases}$     $\begin{cases}
\phi'=-2\phi\\
\theta'=\phi
\end{cases}$     $\begin{cases}
\phi'=0\\
\theta'=\mp (2c-1)\phi
\end{cases}$

The table sums up the renormalisation flow of QCAs with $\phi\neq 0$: for each choice of the parameters in $\tT$ the renormalised evolutions associated to a particular choice of the projection P are shown: $Q_1\coloneqq\ketbra{0}{0}\otimes\ketbra{0}{0}+\ketbra{1}{1}\otimes\ketbra{1}{1}$ and $Q_2\coloneqq\ketbra{0}{0}\otimes\ketbra{1}{1}+\ketbra{1}{1}\otimes\ketbra{0}{0}$.

Let $\tT$ be a one dimensional qubit QCA with
index $1$ which admits admits a size-$2$ and let
us denote with  $\mathcal{M}$ the algebra of
$2\times 2$ complex matrices.
Then either we have

\begin{align}
\label{eq:factorfullmatrix}
\begin{aligned}
\forall A, B \in \mathcal{M},  \exists
\tilde{A}, \tilde{B} \in \mathcal{M}  \mbox{ such that}\\
&G (A\otimes B) G^\dag=\tilde{A}\otimes\tilde{B}
\end{aligned}
\end{align}

or there exist a unital abelian
algebra $\mathcal{A}$ and a unital abelian algebra
of commuting $2\times 2$ matrices such that

\begin{align}
\label{eq:factorabelian}
\begin{aligned}
&\forall  A, B \in \mathcal{A},  \exists
\tilde{A}, \tilde{B} \in \tilde{ \mathcal{A}}
\mbox{ such that}\\
&G (A\otimes B) G^\dag=\tilde{A}\otimes\tilde{B}
\end{aligned}
\end{align}

From Equation (<ref>) we have that
$[G,S] = 0$, where $S$ is the swap operator.
Then Corollary <ref>
holds.  If $\mathsf{X}$ is a $C^*$-subalgebra
of $\mathcal{M}$, then one of the following must be the case
$ i)$
$\mathsf{X} = \mathcal{M}$, $ii)$
$\mathsf{X} = \mathcal{A}$ where $ \mathcal{A}$
is 2-dimensional unital abelian algebra, $iii)$
$\mathsf{X} = \mathsf{I} := \{z I, z\in\mathbb
C\}$, or $iv)$
$\mathsf{X}=\mathsf{O} :=
\{z\ket\psi\bra\psi\mid z\in\mathbb C\})$.  Let
$\mathsf{M}$, $\mathsf{N}$, $\tilde{\mathsf{M}}$
and $\tilde{\mathsf{N}}$ be the algebras defined
in Lemma <ref> and let
$\mathsf{K}$ and $\tilde{\mathsf{K}}$ be the
algebras defined in Corollary
<ref>.  If
$\mathsf M = \mathsf{O}$ and
$\mathsf N = \mathsf{O}'$ then $\rank(P) = 1$,
and since we require that $\rank(P) = 2$, this
case is ruled out.  Then at least one between
$\mathsf M $ and $\mathsf N $ must be a unital
algebra.  Without loss of generality, let us
assume that $\mathsf M $ is unital. Let us now
examine the several cases that can occur.  If
either $\mathsf M = \mathcal{M}$ or
$[\mathsf M , \mathsf N] \neq 0$ then it must be
$ \mathsf{K} = \mathcal{M} \otimes \mathcal{M}$.
If $\mathsf M = \mathcal{A}$ and
$[\mathsf M , \mathsf N] = 0$ then
$ \mathsf{K} = \mathcal{A} \otimes \mathcal{A}$.
If $\mathsf M = \mathsf{I}$ then
$\mathsf N \neq \mathsf{I}$, since otherwise we
would have $\rank{P} = 4$.  If
$\mathsf M = \mathsf{I}$ and
$\mathsf N = \mathcal{M}$ then
$ \mathsf{K} = \mathcal{M} \otimes \mathcal{M}$.
If $\mathsf M = \mathsf{I}$ and
$\mathsf N = \mathcal{A}$ then
$ \mathsf{K} = \mathcal{A} \otimes \mathcal{A}$.
Finally, If $\mathsf M = \mathsf{I}$ and
$\mathsf N = \mathsf{O}$ then
$ \mathsf{K} = \mathcal{A} \otimes \mathcal{A}$
where $\mathcal{A}$ is the abelian algebra
generated by $I$ and $\ketbra{\psi}{\psi}$.
Then either
$\mathsf{K} = \mathcal{A} \otimes \mathcal{A}$
$\mathsf{K} = \mathcal{M} \otimes \mathcal{M}$.
In the same way, we can prove that either
$\tilde{\mathsf{K}} = \mathcal{M} \otimes
\mathcal{M}$ or
$\tilde{\mathsf{K}} = \tilde{\mathcal{A}
}\otimes \tilde{\mathcal{A}}$.  Since $G$ is
$\mathsf{K} = \mathcal{M} \otimes \mathcal{M}$
$\tilde{\mathsf{K}} = \mathcal{M} \otimes \mathcal{M}$ and
$\mathsf{K} = \mathcal{A} \otimes \mathcal{A}$
$\tilde{\mathsf{K}} = \mathcal{A} \otimes \mathcal{A}$.

Let $\tT$ be a one dimensional qubit QCA with
index $1$, and let us express the corresponding operator $G$ as follows: $G = C_\phi  (U_n \otimes U_n) C_\phi $ where

\begin{align}
\label{eq:8}
\begin{aligned}
&  U_n := \exp(-i \theta\vc{n} \cdot \sigma ) \\
&C_\phi\ket{a}\ket{b} = e^{i \phi ab }\ket{a}\ket{b}, \quad a,b \in \{0,1\} \\
&    \vc{n} = (n_x,n_y,n_z)^T, \lvert \vc{n}\rvert =1 \quad
\sigma_z\ket{a} = (-1)^a\ket{a}.
\end{aligned}
\end{align}

Then $\tT$ admits a size-2 renormalisation iff

\begin{align}
\label{eq:12}
\begin{aligned}
& (\phi=0) \lor (n_x=n_y= 0 )\lor( n_z =0 , \theta=\tfrac{\pi}{2}).
\end{aligned}
\end{align}

Let us suppose that $\tT$ admits a
size-$2$ renormalisation.  From Lemma
<ref> we know that either Equation
(<ref>) or Equation
(<ref>) must hold.  If Equation
(<ref>) holds then $G$ is a
unitary operator that maps factorised states into
factorised states, which implies
[46] that either
$G = V\otimes W$ or $G = (V\otimes W) S$ where
$V,W$ are some unitary operators and $S$ is the
swap gate.  Since $[G,S] = 0$ we must have
$G = V\otimes V$ or $G = (V\otimes V) S$.
However, the case $G = (V\otimes V) S$ was ruled
out in the proof of Lemma
<ref> and and we are
left with $G = V\otimes V$.
Then we must have the identity  $ V\otimes V =  C_\phi  (U_n \otimes U_n) C_\phi $, which in the basis of the eigenstate of $\sigma_z$ reads as follows

\begin{align*}
& \begin{aligned}
\begin{pmatrix}
v_{00}V & v_{01}V \\
v_{10}V & v_{11}V
\end{pmatrix}
& =
\begin{pmatrix}
I& 0\\
0 & \Phi
\end{pmatrix}
\begin{pmatrix}
u_{00}U & u_{01}U \\
u_{10}U & u_{11}U
\end{pmatrix}
\begin{pmatrix}
I& 0\\
0 & \Phi
\end{pmatrix} = \\
u_{00}U & u_{01}U\Phi \\
u_{10}\Phi U & u_{11}\Phi U \Phi
\end{pmatrix}
\end{aligned}\\
& V =
\begin{pmatrix}
v_{00} & v_{01} \\
v_{10} & v_{11}
\end{pmatrix},
\quad
U =
\begin{pmatrix}
u_{00} & u_{01} \\
u_{10} & u_{11}
\end{pmatrix},
\quad
\Phi =
\begin{pmatrix}
1 &0 \\
0 &e^{i \phi}
\end{pmatrix}
\end{align*}

If $v_{00} \neq 0$ then $v_{00} V = u_{00}U$
implies that $u_{00} \neq 0$ and $V \propto U$.
Then the condition $v_{01}V = u_{01}U\Phi $
implies that either $\Phi \propto I$, i.e.
$\phi = 0$, or $v_{01}=u_{01} = 0$,
i.e. $n_y=n_x =0$.  On the other hand if
$v_{00} = 0$ then we must have that
$u_{00} = u_{11} = 0$, i.e. $n_z = 0, \theta=\frac{\pi}{2}$.
case in which Equation (<ref>)
holds is more elaborate and it is carried out in
Appendix <ref>.
Conversely, suppose that
$ (\phi=0) \lor( n_x = n_y= 0 )\lor (n_z =0, \theta={\pi}/{2})$.  If
$\phi=0$ then $\tT$ is a QCA made of local
unitaries and it clearly admits a size-$2$
renormalisation (see Fig. <ref>). We then focus on the remaining cases. Let us
consider a wrapping of $\tT$ on $\mathbb{Z}_n$ where $n$ is
an even number greater than $8$ [Actually, it is shown in the Appendix that it is sufficient to consider a lattice $\mathbb{Z}_n$ with n even and greater than $6$.]. One
can see that the regular neighborhood condition is
satisfied for $\tT^2$ and that $\tT^2$ is
diagonal in the computational basis, i.e.
$\tT^2 = \sum_{i_1=0}^1\dots \sum_{i_n=0}^1
\lambda (i_1, \dots, i_n) \bigotimes_{x=1}^n
\ketbra{i_x}{i_x} $
for suitable phases $ \lambda (i_1, \dots,
i_n)$. Then $[U_{\tT^2},\Pi] = 0$ for
$\Pi := \otimes_x \Pi_x$ and
$\Pi_x := \ketbra{a}{a}\otimes \ketbra{b}{b} +
\ketbra{a'}{a'}\otimes \ketbra{b'}{b'}$ for any
choices of $a,b,a',b' \in \{0,1\}$ such that
$\Pi_x$ has rank $2$.

We now want to classify all the renormaisable QCAs, along with
their respective renormalised evolution. The explicit calculations are straightforward
but tedious and are carried out in Appendix <ref>. There are three main classes
of such QCA:

* QCA that trivialise after two steps: This class of QCA corresponds to $\tT^2=\mathcal{I}$ and is renormalised in a local unitary. Since two steps of the evolution correspond to the identity, any choice of the projection $P$ constitutes a legitimate choice for the coarse-graining.

* QCA that apply a local unitary transformation: This class of QCA corresponds to an evolution made of local unitaries. Imposing the commutation of two steps with the projection, it is easy to see that the only suitable projections are the abelian one over a factorised basis of $U^2$ (see Figure (<ref>)).

* QCA that after two steps are diagonal on a factorised basis: This class of QCA can be renormalised through a projection diagonal in the factorised computational basis. Those are the only QCAs that admit a size-2 renormalisation without reducing to a local unitary, i.e. they have $\phi\neq 0$. There are two main subclasses:

* QCA with a single step diagonal over the computational basis

* QCA with a single step anti-diagonal over the computational basis

The first two cases are trivial, and essentially boil down to the example in Fig. <ref>. Table <ref> summarises the results for the non trivial case where $\phi\neq 0$.
We can observe that all the size-2 renormalisable QCAs do not propagate information, since either they are factorised, or their Margolus partitioning scheme involves commuting layers, which implies that all the odd layers can be grouped into one, and the same for the even layers,

thus collapsing in a transformation with a neighbourhood contained in that of a single step, independently of how many steps are performed (see Fig.(<ref>)).

We are going to neglect the solutions obtained through the projection $P=I\otimes \ketbra{c}{c}$ since they. Let us begin with the case $3.(b)$. The two solutions are given by:

\begin{align}
\begin{cases}
\phi=2n\pi\\
\theta=\phi.
\end{cases}
\\
\begin{cases}
\phi=-2\phi\\
\theta=\phi.
\end{cases}
\end{align}

The first case leads to trivial solution, while the second case leads to:

\begin{align}
\begin{cases}
\phi=\frac{2n\pi}{3},\\
\theta=\frac{2n\pi}{3}.
\end{cases}
\end{align}

Since the assumption for case $3.(b)$ is $\theta=\frac{\pi}{2}$ this is not a fixed point. Let us examine the case $3.(a)$. The fixed points are given by the solutions to the equations:

\begin{align}
\phi=2\phi,\\
\theta=\phi-4\theta.
\end{cases}
\\
\phi=2\phi,\\
\theta=4\theta-3\phi.
\end{cases}
\\
\phi=-2\phi,\\
\theta=\phi.
\end{cases}
\end{align}

The first and the second cases lead to the solution:

\begin{align}
\begin{cases}
\phi=2n\pi,\\
\end{cases}
\\
\begin{cases}
\phi=2n\pi,\\
\end{cases}
\end{align}

which are local unitary. Finally, the third equation leads
By direct inspection of the solutions in Table <ref>, one can straightforwardly
see that the only fixed point with $\phi\neq 0$ is given by case $3.(a)$. This is given by
the evolution:

\begin{align}
\begin{cases}
\phi=\frac{2n\pi}{3},\\
\theta=\frac{2n\pi}{3},
\end{cases}
\end{align}

which is mapped into itself by means of the projection $P=\ketbra{0}{0}\otimes\ketbra{1}{1}+\ketbra{1}{1}\otimes\ketbra{0}{0}.$
This case corresponds to the local evolution given by:

\begin{align}
\begin{aligned}
&\tT_0({A}_0)=X^{\dag}(I\otimes e^{-i\frac{2n\pi}{3}\sigma_z}A_0 e^{i\frac{2n\pi}{3}\sigma_z}\otimes I)X,\\
&X=(C_{\frac{2n\pi}{3}}\otimes I_3)(I_1\otimes C_{\frac{2n\pi}{3}})\,.
\end{aligned}
\end{align}

(A) at (-1,0) 0.20!T2noproj;
(B) at ($(A)+(4,0)$) 0.20!MargInd1sqr;
[->] (A)–(B);

Two steps of the evolutions that can be renormalised collapse in a single one: no information can be propagated after the first step.

§ CONCLUSION

In conclusion, we analysed the problem of renormalising cellular automata on $\mathbb Z^s$
via a Kadanoff-like coarse-graining procedure. We provide necessary and sufficient conditions for renormalisability that are amenable to further analysis. We then specialised to the case where $s=1$ and the cells are qubits, with a coarse-graining where two cells and two time steps are mapped into a single one. We completely solved this case. The solution that we found tells two important facts: for our special case $s=1$ and qubit cells, we cannot change the index upon renormalisation, and most QCAs are not renormalisable, with the exception of QCAs where information does not actually propagate. We conjecture that this very restrictive result is due to the extremely limited choice of degrees of freedom that one can “erase” in the coarse-graining process in this simple case. In order to prove that more interesting cases exist, the present analysis should be developed either for coarse-grainings where more than two cells and more than two steps are renormalised into a single one, or move beyond the qubit-cell case. One can easily prove that the second choice includes the first one as a special case. Further developments can then be achieved provided a generalisation of the classification of Margolus partitioning schemes.

Another interesting development would be to carry a similar analysis in the case of
Fermionic cellular automata. Also this case requires a generalisation of the classification of Margolus partitioning schemes, which is then a required intermediate step.

Finally, our necessary and sufficient condition might be exploited to study the
renormalisation problem for QCAs on higher-dimensional graphs, such as $\mathbb Z^2$ or
$\mathbb Z^3$. We expect that in these cases more interesting situations can arise, with
fixed points that might represent phase transitions for the statistical mechanics of QCAs,
opening interesting questions about the universality classes of QCAs and their relation to
other models, both in statistical mechanics and in quantum field theory.

PP acknowledges financial support from European Union—Next Generation EU through the MUR project Progetti di Ricerca d'Interesse Nazionale (PRIN) QCAPP No. 2022LCEA9Y.
AB acknowledges financial support from European Union—Next Generation EU through the MUR project Progetti di Ricerca d'Interesse Nazionale (PRIN) DISTRUCT No. P2022T2JZ9.
LT acknowledges financial support from European Union—Next Generation EU through the National Research Centre for HPC, Big Data
and Quantum Computing, PNRR MUR Project CN0000013-ICSC.

§ THE QUASI-LOCAL ALGEBRA

Here we define rigorously the quasi-local algebra.
In the following $\Omega$ and $\Omega_i$ denote finite subsets of $\mathbb Z^s$.
Consider now the  algebras of operators acting on a finite set of sites $\Omega\subset\mathbb{Z}^s$

\begin{equation}
\mathsf{A}(\Omega)=\bigotimes_{x\in\Omega}\mathsf{A}_{x},
\end{equation}

where $\mathsf{A}_x$ is the C*-algebra of operators acting on cell $x$.
For $\Omega_1\subset\Omega_2$ we can consider $\mathsf{A}(\Omega_1)$ as a subalgebra of $\mathsf{A}(\Omega_2)$ by tensoring with the identity over the region $\Omega_2\setminus\Omega_1$ the operators in $\mathsf{A}(\Omega_1)$, that is:

\begin{equation}\label{eq:embed}
O\otimes I_{\Omega_2\setminus\Omega_1}\in\mathsf{A}(\Omega_2)\hspace{5pt}\forall O\in\mathsf{A}(\Omega_1).
\end{equation}

In this way the product $O_1O_2$ is well defined over $\Omega_1\cup \Omega_2$ for $O_1\in\mathsf{A}(\Omega_1)$ and $O_2\in\mathsf{A}(\Omega_2)$. We can now define the equivalence relation $\thicksim$ by saying that $O_1\thicksim O_2$ with $O_i\in\mathsf{A}(\Omega_i)$ if

\begin{equation}
O_1\otimes I_{{(\Omega_1\cup\Omega_2)\setminus\Omega_1}}=O_2\otimes I_{{(\Omega_1\cup\Omega_2)\setminus\Omega_2}} .
\end{equation}

In other words two operators over $\Omega_1$ and $\Omega_2$ are equivalent under $\thicksim$ if they are are the same operator when seen as elements of $\Omega_1\cup\Omega_2$. The local algebra is then the algebra of the equivalence classes under $\thicksim$ of all operators algebras over finite set of sites, or

The Local Algebra $\mathsf{A}^{\mathrm{loc}}$ is defined as

\begin{equation}
\mathsf{A}^{\mathrm{loc}}=\bigcup_{\Omega}\mathsf{A}(\Omega)\hspace{3pt} \big/ \thicksim
\end{equation}

Moreover, since $\mathsf{A}(\Omega)$ for every finite set $\Omega\subseteq \mathbb Z^s$ is
a normed space with the uniform operator norm $\|\cdot\|_\infty$, and
$\|O\otimes I\|_\infty=\|O\|_\infty$, the norm of $O\in\mathsf A_{\Omega_1}$ when embedded
in $\mathsf{A}(\Omega)$ as in Eq. (<ref>) is the same as that of $O$ seen as an
element of $\mathsf A_{\Omega_1}$. We can then make also $\mathsf{A}^\mathrm{loc}$ into a
normed space by defining the norm of an equivalence class as the norm of any of its
representatives which is indeed independent of the chosen representative.

We can then define an equivalence relation for Cauchy sequences, setting $\{\mathsf A_{n}\}_{n=0}^\infty \simeq \{\mathsf B_{n}\}_{n=0}^\infty$ if

\begin{equation}
\forall \epsilon>0 \hspace{5pt} \exists n_0 \hspace{3pt} \mbox{s.t.}\hspace{3pt} \lVert \mathsf A_{k}-\mathsf B_{k}\rVert_{\infty} < \epsilon \hspace{10pt} \forall k \geq n_0.
\end{equation}

We can then complete the local algebra by the standard procedure of defining the algebra of equivalence classes of Cauchy sequences. As a result of this procedure, we obtain
the quasi-local algebra $\mathsf A(\mathbb Z^s)$. The detailed definition follows.

Let $\mathcal{C}(\mathsf{A}^\mathrm{loc})$ denote the space of Cauchy sequences over
The quasi-local algebra $\mathsf{A}(\mathbb{Z}^s)$ is defined as

\begin{equation}
\mathsf{A}(\mathbb{Z}^s)=\mathcal{C}(\mathsf{A}^\mathrm{loc}) \big / \simeq
\end{equation}

Intuitively speaking, this algebra contains all the operators that can be arbitrarily well approximated by local operators in $\mathsf{A}^\mathrm{loc}$. We remark that $\mathsf{A}^\mathrm{loc}\subset\mathsf A(\mathbb Z^s)$.

§ UNIQUENESS OF THE MARGOLUS PARTITIONING SCHEME

Let $M'_1$ and $M'_2$ be a pair of unitary operators such that
eq. (<ref>) is satisfied. Then we must have

\begin{align}
\resizebox{0.8\hsize}{!}{
\tikzfig{MargInd1}=\tikzfig{MargInd12}},
\end{align}

which implies that

\begin{align}
\resizebox{0.8\hsize}{!}{
\tikzfig{M1id}=\tikzfig{M2id}},
\end{align}

The two different factorisations imply that both diagrams must be equal to a factorised unitary of the form

\begin{align*}
\resizebox{0.8\hsize}{!}{
\tikzfig{M1id}=\tikzfig{M1unit}},
\end{align*}

and this shows that

\begin{align}
M'_1=(U\otimes V)M_1, \quad M'_2=M_2(V^\dag\otimes U^\dag).
\label{eq:unimarg}
\end{align}

§ PROOF OF PROPOSITION
$\MATHSF{K} = \MATHCAL{A} \OTIMES \MATHCAL{A} $

To prove the proposition, we start showing that if Eq.(<ref>) holds then $(\phi=0)\lor (n_x=n_y=0)\lor (n_z=0)$,
which means that either $C_\phi=I$, or $U$ is either diagonal or antidiagonal.
Let  then $\{ \ket{\mu_i} \}_{i=0,1}$ be an orthonormal
basis such that
$\mathcal{A} :=
\langle
\ketbra{\mu_0}{\mu_0}
\cup
\ketbra{\mu_1}{\mu_1}
\rangle$.
If Equation (<ref>) holds,
we have

\begin{align}\label{eq:Gfact}
\begin{aligned}
P &= \sum_{i,j} c_{i,j} \ket{\mu_i}\bra{\mu_i}\otimes\ket{\mu_j}\bra{\mu_j}\\
& G^\dag (\ket{\mu_i}\bra{\mu_i}\otimes\ket{\mu_j}\bra{\mu_j})G=\ket{\tilde\mu_i}\bra{\tilde\mu_i}\otimes\ket{\tilde\mu_j}\bra{\tilde\mu_j},
\end{aligned}
\end{align}

where $c_{i,j} \in \{0,1\} $ and
$\{ \ket{\tilde{\mu}_i} \}_{i=0,1}$
is another orthonormal basis. Clearly, we have
$\tilde{\mathcal{A}} :=
\langle
\ketbra{\tilde{\mu}_0}{\tilde{\mu}_0}
\cup
\ketbra{\tilde{\mu}_1}{\tilde{\mu}_1}
\rangle$. We now find a convenient form to express G that acts as above.

If eq.(<ref>) holds, then we can write G as:

\begin{align}\label{eq:vvf}
&G=(V\otimes V) F\\
&V=\begin{pmatrix}\lvert a\rvert & b\\ -b^* & \lvert a\rvert\end{pmatrix} &F=\begin{pmatrix}e^{i\theta_{00}}&0&0&0\\0&1&0&0\\
\end{align}

Let us now define a unitary operator $V$ such that

\begin{align}
\ket{\tilde{\mu_i}}\coloneqq V\ket{\mu_i},\quad i=0,1.
\end{align}

Then, from Equation (<ref>)
we have

\begin{align*}
\begin{aligned}
\ket{\tilde{\mu}_i}\bra{\mu_i}\otimes
\ket{\tilde{\mu}_j}\bra{\mu_j}
=(V\otimes V)F, \\
&F := \sum_{i,j}e^{i\theta(i,j)}
\ket{{\mu}_i}\bra{\mu_i}\otimes
\ket{{\mu}_j}\bra{\mu_j}
\end{aligned}
\end{align*}

We remark that invariance of $G$ under conjugation by the swap implies that also $EFE=F$,
and thus $\theta_{01}=\theta_{10}$, i.e. $F$ has a degenerate eigenspace with dimension $d\geq 2$, with a 2-dimensional subspace spanned by $\{\ket0\ket1,\ket1\ket0\}$. In particular, since we are not interested in global phases, we can set F to be:

\begin{equation}\label{eq:F}
\end{equation}

Moreover, if we write V as:

\begin{align*}
&a=\lvert a\rvert e^{i\phi}, b\in \mathbb{C},
\end{align*}

we have

\begin{align*}
&V= \begin{pmatrix}a&b\\-b^*&a^*\end{pmatrix}
=\begin{pmatrix}\lvert a\rvert&\tilde{b}\\-\tilde{b}^*&\lvert a\rvert\end{pmatrix}
%\otimes \begin{pmatrix}\lvert a\rvert&\tilde{b}\\-\tilde{b}^*&\lvert a\rvert\end{pmatrix}
\begin{pmatrix}e^{i\phi}&0\\0&e^{-i\phi}\end{pmatrix}
\end{align*}

\begin{align*}
\tilde V\coloneqq\begin{pmatrix}\lvert a\rvert&\tilde{b}\\-\tilde{b}^*&\lvert a\rvert\end{pmatrix},\qquad R_\phi\coloneqq\begin{pmatrix}e^{i\phi}&0\\0&e^{-i\phi}\end{pmatrix}
\end{align*}

Thus we have:

\begin{equation*}
G=(V\otimes V) F = (\tilde{V}\otimes\tilde{V}) \tilde{F} ,
\end{equation*}

where $\tilde{F}\coloneqq(R_\phi\otimes R_\phi)F$ is:

\begin{equation*}
\tilde{F}=
\begin{pmatrix}e^{i\tilde\theta_{00}}&0&0&0\\
\end{equation*}

\begin{align*}
\tilde\theta_{00}\coloneqq\theta_{00}+\phi,\quad\tilde\theta_{11}\coloneqq\theta_{11}-\phi.
\end{align*}

We then have the thesis.

As a consequence of the above result, we clearly have

\begin{equation}
\label{eq:spcomm}
\end{equation}

Inserting the above decomposition of $G$ in $[G^2,P]=0$, we have

\begin{equation}
[(V\otimes V)F(V\otimes V)F,P]=0,
\end{equation}

and considering eq.$(\ref{eq:spcomm})$ we have

\begin{equation}\label{eq:blackmagic}
[(V\otimes V)F(V\otimes V),P]=0
\end{equation}

or, in other words,

\begin{equation}\label{eq:commmyst}
(V\otimes V)F(V\otimes V)P=P(V\otimes V)F(V\otimes V)
\end{equation}

Notice that eq. (<ref>) also implies

\begin{equation}\label{eq:commystort}
(V\otimes V)F(V\otimes V)\bar P=\bar P(V\otimes V)F(V\otimes V),
\end{equation}

with $\bar P\coloneqq I-P$, thus the operator $(V\otimes V)F(V\otimes V)$ is block-diagonal in the basis $\{\ket\mu\ket\nu\}$, i.e.

\begin{align*}
R\coloneqq(V\otimes V)F(V\otimes V)=\begin{pmatrix}
\end{pmatrix},
\end{align*}

where $R_{00}$ and $R_{11}$ are unitary.

If we consider the projection

\begin{equation*}
P= I\otimes \ket{\mu}\bra{\mu},
\end{equation*}

then either $G=U\otimes U$ or $V=U$ is diagonal or antidiagonal.

From the above considerations, we can write :

\begin{align}
F=(V^\dag\otimes V^\dag)R(V^\dag\otimes V^\dag)=
\begin{pmatrix}
\end{pmatrix},
\end{align}

with blocks

\begin{align*}
&F_{00}=a^2V^\dag R_{00} V^\dag-\lvert b\rvert^2V^\dag R_{11} V^\dag,\\
&F_{01}=- ab(V^\dag R_{00} V^\dag+V^\dag R_{11} V^\dag),\\
&F_{10}=ab^*(V^\dag R_{00} V^\dag+V^\dag R_{11} V^\dag),\\
&F_{11}=-\lvert b\rvert^2 V^\dag R_{00} V^\dag+ a^2 V^\dag R_{11} V^\dag.
\end{align*}

Since $F$ is block-diagonal, we must have $F_{01}=F_{10}=0$, that is,
(upon multiplying by $V$ on both sides)

\begin{align}
\begin{cases}
ab( R_{00} + R_{11} ) =0,\\
ab^*( R_{00} + R_{11}) =0.
\end{cases}
\end{align}

We have now two possibilities: i) $R_{00}\propto R_{11}$, which however implies
$F=e^{i\theta Z}\otimes e^{i\theta Z}$ and $G=U\otimes U$; ii) $ab=0$  that implies that $V$ is either diagonal or off-diagonal, and this concludes the proof.

We want now to consider the case where

\begin{equation*}
P=\ket{\mu}\bra{\mu}\otimes\ket{\nu}\bra{\nu} +\ket{\mu\oplus 1}\bra{\mu\oplus 1}\otimes\ket{\nu\oplus 1}\bra{\nu\oplus 1}.
\end{equation*}

It is convenient to define

\begin{align}
&\delta\coloneqq \frac{\theta_{00}-\theta_{11}}{2},\\
%&U\eqqcolon \begin{pmatrix}\cos\gamma&\sin\gamma\\-\sin\gamma&\cos\gamma\end{pmatrix},\\
&U\eqqcolon e^{i\alpha_1 \sigma_z}e^{i\gamma \sigma_y}e^{i\alpha_2\sigma_z},\label{eq:euler}\\
&\chi\coloneqq 2\alpha-\phi,
\end{align}

where in (<ref>) we used the representation of $\mathbb{SU}(2)$ matrices in terms of Euler angles. We can impose preliminary constraints on G by computing the determinant and the trace of $G=(V\otimes V) F$ and $G=C_\phi (U\otimes U) C_\phi$ and imposing the equality between the two forms. The constraints are summarised in the following Lemma.

Considering the form of G in eq.(<ref>) and the one in eq.(<ref>) it should hold:

\begin{align}\label{eq:conditionphases}
\begin{cases}
\end{cases}
\end{align}

\begin{align*}
\det(G)=\det(F)=\det(C_\phi)^2,
\end{align*}

and remembering that $\det(U)=\det(V)=1$ we get to:

\begin{align}\label{eq:thetaphi}
\end{align}

Moreover, considering $G=(V\otimes V)F$,

\begin{align*}
\Tr[G]=a^2[2+2e^{i\frac{\theta_{00}+\theta_{11}}2}\cos\delta],%\quad\delta\coloneqq\frac{\theta_{00}-\theta_{11}}2,
\end{align*}

while, for $G=C_\phi(U\otimes U)C_\phi$, we have

\begin{align*}
\Tr[G]=\cos^2\gamma[2+2e^{i\phi}\cos\chi],
\end{align*}

Taking $(\theta_{00}+\theta_{11})/2=\phi+n\pi$, with $n\in\{0,1\}$, as from Eq. (<ref>), we obtain

\begin{align}\label{eq:systemF}
a^2[1+e^{i\phi}\cos\delta]=\cos^2\gamma[1+(-1)^n e^{i\phi}\cos\chi],
\end{align}

and equating the real and imaginary parts of both sides gives the thesis:

\begin{align*}
\begin{cases}
\end{cases}
\end{align*}

Now, the cases are the following

* $\phi=0$, which implies that $G=U\otimes U$.

$\phi=\pi$, that we will analyse as the last.

$\phi\neq n\pi$ for $n\in\mathbb N$, in which case

\begin{align}\label{eq:coschi}
\end{align}

In case <ref>, condition (<ref>) can be substituted in (<ref>) to obtain

\begin{align*}
\end{align*}

leading to $a^2=\cos^2\gamma$. Since the sign of $a$ is irrelevant, we can take
$a=\cos\gamma$. Moreover, either $a=0$, which leads to the case where $U=i\mathbf n\cdot\boldsymbol\sigma$, or, from (<ref>), $\cos\delta=(-1)^n\cos\chi$, i.e.

\begin{align*}
\begin{cases}
\frac{\theta_{00}-\theta_{11}}2=s(2\alpha-\phi)+n\pi,\\
\frac{\theta_{00}+\theta_{11}}2=\phi+n\pi,
\end{cases}
\end{align*}

with $s\in\{+1,-1\}$. Finally, we get to

\begin{align*}
\end{align*}

If $s=+1$, then

\begin{align*}
\end{align*}

while if $s=-1$, then

\begin{align*}
\end{align*}

Now, since $a=\cos\gamma$, we can write

\begin{align*}
&V=e^{-i\beta Z}e^{i\gamma Y}e^{i\beta Z},
\end{align*}

where where $X,Y,Z$ represent the Pauli matrices in the basis where $F$ is diagonal, and
$b=|b|e^{-2i\beta}$. Moreover, since $\alpha=\alpha_1+\alpha_2$, if $s=1$ we can write

\begin{align*}
&F=(e^{i\alpha Z}\otimes e^{i\alpha Z})\tilde C_{2\phi},
\end{align*}

where $\tilde C_{2\phi}$ represents a controlled-phase diagonal in the same basis as $F$.
Now, considering that

\begin{align*}
G&=(e^{-i\beta Z}e^{i\gamma Y}e^{i(\alpha+\beta) Z})^{\otimes 2}\tilde C_{2\phi}\\
&=(e^{-i(\beta+\alpha_1) Z}e^{i\alpha_1 Z}e^{i\gamma Y}e^{i\alpha_2 Z}e^{i(\beta+\alpha_1) Z})^{\otimes 2}\tilde C_{2\phi}\\
&=(e^{-i(\beta+\alpha_1) Z})^{\otimes2}(e^{i\alpha_1 Z}e^{i\gamma Y}e^{i\alpha_2 Z})^{\otimes 2}\tilde C_{2\phi}(e^{i(\beta+\alpha_1) Z})^{\otimes2},
\end{align*}

we can choose

\begin{align*}
&V=e^{-i(\beta+\alpha_1) Z}(e^{i\alpha_1 Z}e^{i\gamma Y}e^{i\alpha_2 Z})e^{i(\beta+\alpha_1) Z},\\
&F=(e^{-i(\beta+\alpha_1) Z})^{\otimes2}\tilde C_{2\phi}(e^{i(\beta+\alpha_1) Z})^{\otimes2}.
\end{align*}

On the other hand, if $s=-1$ we can write

\begin{align*}
%&\hat V=e^{i\alpha_1Z} X e^{i\alpha_1Z}e^{i\gamma Y}e^{i\alpha_2Z}X e^{-i\alpha_1Z},\\
&F=(Xe^{i\alpha Z}\otimes Xe^{i\alpha Z})\tilde C_{2\phi}(X\otimes X).
\end{align*}

In this case, considering that

\begin{align*}
G&=(e^{-i\beta Z}e^{i\gamma Y}e^{i\beta Z}Xe^{i\alpha Z})^{\otimes 2}\tilde C_{2\phi}X^{\otimes 2}\\
&=X^{\otimes 2}(e^{i\beta Z}e^{-i\gamma Y}e^{-i\beta Z}e^{i\alpha Z})^{\otimes 2}\tilde C_{2\phi}X^{\otimes 2}\\
&=X^{\otimes 2}(e^{i(\beta+\frac\pi2) Z}e^{i\gamma Y}e^{-i(\beta+\frac\pi2) Z}e^{i\alpha Z})^{\otimes 2}\tilde C_{2\phi}X^{\otimes 2}\\
&=X^{\otimes 2}(e^{i\tilde\beta Z}e^{i\alpha_1 Z}e^{i\gamma Y}e^{i\alpha_2 Z}e^{-i\tilde\beta Z})^{\otimes 2}\tilde C_{2\phi}X^{\otimes 2}\\
&=(Xe^{i\tilde\beta Z})^{\otimes2}(e^{i\alpha_1 Z}e^{i\gamma Y}e^{i\alpha_2 Z})^{\otimes 2}\tilde C_{2\phi}(e^{-i\tilde\beta Z}X)^{\otimes 2},
\end{align*}

with $\tilde\beta\coloneqq(\beta+\tfrac\pi2-\alpha_1)$, we can choose

\begin{align*}
&V=Xe^{i\tilde\beta Z}(e^{i\alpha_1 Z}e^{i\gamma Y}e^{i\alpha_2 Z})e^{-i\tilde\beta Z}X,\\
&F=(Xe^{i\tilde\beta Z})^{\otimes2}\tilde C_{2\phi}(e^{-i\tilde\beta Z}X)^{\otimes 2}.
\end{align*}

Thus, in both cases, for a suitable special unitary $W$,

\begin{align*}
V=WUW^\dag,\quad F=(W\otimes W)C_{\phi}^2(W^\dag\otimes W^\dag).
\end{align*}

Eq. (<ref>) and  (<ref>) imply that the operator $R$ has the form

\begin{align*}
&R=\begin{pmatrix} R_{00} & R_{01}\\ R_{10}& R_{11}\end{pmatrix},\\
\end{align*}

with $R_{00}$ and $R_{11}$ diagonal, and $R_{01}$ and $R_{10}$ anti-diagonal.
To impose this form, it is convenient to consider the basis given by triplet and singlet states:

\begin{align}
\end{align}

It is easy to see that:

\begin{align*}
\end{align*}

Thus, $R$ must be block diagonal in the above basis.

Moreover, we have:

\begin{align*}
\dket{I},\quad E\dket{\sigma_z}=\dket{\sigma_z},\quad E\dket{\sigma_x}=\dket{\sigma_x},\\
\end{align*}

Reminding that, for $V$ with unit determinant,

\begin{align*}
(V\otimes V)\dket{\sigma_y}=\dket{\sigma_y},
\end{align*}

and by direct inspection of the matrix form of $F$

\begin{align*}
\end{align*}

we have

\begin{equation*}
\end{equation*}

Thus, being $R$ block diagonal,

and being $\dket{\sigma_y}$ necessarily an eigenvector, it must hold that

\begin{equation}\label{eq:omegax}
R\dket{\sigma_x}=\omega \dket{\sigma_x}, \hspace{10pt} \lvert\omega\rvert=1.
\end{equation}

Moreover, since

\begin{align*}
(W\otimes W)(U\otimes U)C_\phi^2(W^\dag\otimes W^\dag)\ket\mu\ket\nu=e^{i\theta_{\mu\nu}}\ket\mu\ket\nu,
\end{align*}

and since the unique tensorised basis that is mapped to a tensorised basis by $C_\gamma$ for $\gamma\neq k\pi$, $k\in\mathbb Z$, is the computational basis, we must have

\begin{align*}
(W^\dag\otimes W^\dag)\dket{ \sigma_\mu}=(e^{iZ\chi}\otimes e^{iZ\chi})\dket{M},
\end{align*}

where $M=I$ for $\mu=0$, and $M=X,Y,Z$ for $\mu=x,y,z$, respectively, and $\dket M$
represents the four Pauli operators in the computational basis (as opposed to $\dket{\sigma_\mu}$ that represent them in the eigenbasis of $P$).

\begin{align*}
(U\otimes U)C_\phi^2(U\otimes U)\dket{X}=\omega\dket{X}.
\end{align*}

Equivalently, we can write

\begin{align}\label{eq:eigenX}
C_\phi^2\dket{UXU^T}=\omega\dket{U^\dag XU^*}.
\end{align}

We can now explicitly calculate

\begin{align*}
&UX U^T=
\begin{pmatrix}
\end{pmatrix}\\
&U^\dag XU^*=
\begin{pmatrix}
\end{pmatrix}\,.
\end{align*}

This allows us to write the vectors in eq. (<ref>), upon suitable redefinition of $b$ by multiplication by a phase factor as

\begin{align*}
&\dket{U X U^T}=2abe^{i\alpha}\ket{00}-2ab^*e^{-i\alpha}\ket{11}+(a^2-|b|^2)\dket{ X},\\
&\dket{U^\dag X U^*}=2ab^*e^{-i\alpha}\ket{11}-2abe^{i\alpha}\ket{00}+(a^2-|b|^2)\dket{ X},
\end{align*}

and after applying $C_{\phi}^2=C_{2\phi}$ to the first one we can rewrite eq. (<ref>) as

\begin{align*}
&2abe^{i\alpha}\ket{00}-2ab^*e^{i(2\phi-\alpha)}\ket{11}+(a^2-|b|^2)\dket{ X}\\
&=\omega(-2abe^{-i\alpha}\ket{00}+2ab^*e^{i\alpha}\ket{11}+(a^2-|b|^2)\dket{ X})
\end{align*}

If $a-|b|^2\neq0$, we must have $\omega=1$, and thus

\begin{align*}
\end{align*}

which admits a solution for $ab=0$—we then have either $U=e^{i\alpha\sigma_z}$ or $U=i\mathbf n\cdot\boldsymbol\Sigma$ with $\mathbf n=(n_x,n_y,0)$ and $\boldsymbol\Sigma=(X,Y,Z)$—or for $\alpha=(2k+1)\pi/2$ and $\phi=n\pi$, which falls under case <ref> that we will treat separately. If $a=|b|=1/\sqrt2$, one has

\begin{align*}
\end{align*}

which implies $2\alpha-\phi=n\pi$. In this case, we have

\begin{align*}
(U\otimes U)C_\phi^2=(V_y\otimes V_y) F^s_{\phi},
\end{align*}

where, up to conjugation by $e^{-i\alpha_1\sigma_z}$ on every factor, we have

\begin{align*}
&V_y=\frac{1}{\sqrt 2}(I+ i\sigma_y),\\
& F^s_{\phi}=\begin{pmatrix}
s e^{i\phi}&0&0&0\\
0&0&0&s e^{i\phi}
\end{pmatrix}=(e^{i\alpha\sigma_z}\otimes e^{i\alpha\sigma_z})C_{2\phi}.
\end{align*}

Where $s=e^{in\pi}\in\{-1,1\}$. We thus end up having:

\begin{align*}
&(V_y\otimes V_y) F^s_\phi= (W^\dag \otimes W^\dag) C_\phi (U\otimes U )C_\phi (W\otimes W),\\
&W\otimes W\dket{M}=\dket{\sigma_\mu}.
\end{align*}

We can decompose $C_\phi (U\otimes U) C_\phi$ as

\begin{align*}
&C_\phi (e^{i\alpha_1\sigma_z}V_ye^{i\alpha_2\sigma_z}\otimes e^{i\alpha_1\sigma_z}V_ye^{i\alpha_2\sigma_z})C_\phi=\\
&=(e^{i\alpha_1\sigma_z}\otimes e^{i\alpha_1\sigma_z}) C_\phi (V_y\otimes V_y)\tilde{C}^s_\phi (e^{-i\alpha_1\sigma_z}\otimes e^{-i\alpha_1\sigma_z})\\
&\tilde C^s_\phi=\begin{pmatrix}s e^{i\phi} & 0& 0& 0\\
0&0&0&s \end{pmatrix}.
\end{align*}

Then, writing:

\begin{align*}
&C_\phi=(e^{-i\frac{\phi}{4}\sigma_z}\otimes e^{-i\frac{\phi}{4}\sigma_z}) F^+_{\frac{\phi}{2}}\\
&\tilde{C}^s_\phi=F^{s}_\frac{\phi}{2}( e^{i\frac{\phi}{4}\sigma_z}\otimes e^{i\frac{\phi}{4}\sigma_z}),
\end{align*}

we get to the equality:

\begin{align*}
(V_y\otimes V_y) F^s_\phi= (\tilde{W}^\dag\otimes \tilde{W}^\dag) F_{\frac{\phi}{2}}^+ (V_y\otimes V_y) F_{\frac{\phi}{2}}^s (\tilde{W}\otimes \tilde{W}),
\end{align*}

where $\tilde{W}=e^{i\frac{\phi}{4}\sigma_z}e^{-i\alpha_1\sigma_z}W$. In order to find the
values of $\phi$ that satisfy this equality, let us compute eigenvalues and eigenvectors
of the two matrices. Computing $(V_y\otimes V_y) F^s_\phi$ in the basis

ordered as
$\{\dket{\sigma_0},\dket{\sigma_y},\dket{\sigma_x},\dket{\sigma_z}\}$ we get to:

\begin{align*}
(V_y\otimes V_y )F^s_\phi=\begin{pmatrix}s e^{i\phi}&0&0&0\\
0&0&0&-s e^{i\phi}\\
\end{align*}

This has eigenvalues $\{s e^{i\phi},1,(\frac{s+1}{2}i+\frac{s-1}{2})e^{i\frac{\phi}{2}},-(\frac{s+1}{2}i+\frac{s-1}{2})e^{i\frac{\phi}{2}}\}$. To ease the notation we introduce the function $f:\{-1,1\}\to\{i,1\}$ defined as follows:

\begin{align*}
&f(1)=i && f(-1)=1
\end{align*}

with the property that $f(s)^2=-s$.
With this notation the spectrum of the above matrix reads: $\{s e^{i\phi},1,f(s)e^{i\frac{\phi}{2}},-f(s)e^{i\frac{\phi}{2}}\}$.
On the other hand, computing $F_{\frac{\phi}{2}}^+ (V_y\otimes V_y) F_{\frac{\phi}{2}}^s $ in the computational basis $\dket{M}$ ordered as $\{\dket{I},\dket{Y},\dket{X},\dket{Z}\}$ we have:

\begin{align*}
F_{\frac{\phi}{2}}^+ (V_y\otimes V_y) F_{\frac{\phi}{2}}^s=\begin{pmatrix}s e^{i\phi}&0&0&0\\
0&0&0&-s e^{i\frac{\phi}{2}}\\
0&0&e^{i\frac{\phi}{2}}&0\end{pmatrix} .
\end{align*}

This has the same spectrum $\{s e^{i\phi},1,f(s)e^{i\frac{\phi}{2}},-f(s)e^{i\frac{\phi}{2}}\}$. Let us now compute the eigenvectors. If $\phi\neq n\pi$, there is no degeneracy and it must be $\dket{\sigma_0}=e^{i\gamma_0}\dket{I}$, thus:

\begin{align*}
\tilde{W}\otimes \tilde{W}\dket{I}=e^{i\gamma_0}\dket{I},
\end{align*}

or, in other words

\begin{align*}
\tilde W\tilde W^T=e^{i\gamma_0}I.
\end{align*}

This means that $e^{-i\gamma_0/2}\tilde W\in O(2)$. However, since $\det(\tilde W)=1$, it must be $e^{-i\gamma_0}=1$, i.e. $\gamma_0=0$. Moreover, the singlet state is invariant under local transformations with unit determinant, so $\dket{Y}=\dket{\sigma_y}$.
Then the matrix form of $\tilde W$ is

\begin{align*}
c_0I+ic_1\sigma_y=c_0I+ic_1Y,\quad c_0,c_1\in\mathbb R,\ c_0^2+c_1^2=1.
%\tilde W=\begin{pmatrix} c_{00} & -c_{01}\\ c_{01} & c_{00}\end{pmatrix},\quad c_{ij}\in \mathbb{R},\quad c_{00}^2+c_{01}^2=1.
\end{align*}

Since $\tilde W$ is special, the remaining eigenvalues of $\tilde W\otimes\tilde W$ must be $\{e^{i\gamma},e^{-i\gamma}\}$.
The other two eigenvectors of $(V_y\otimes V_y) F_\phi^2$ are given by linear combinations of
$\dket{\sigma_x}$ and $\dket{\sigma_z}$. In particular, restricting to this two dimensional subspace, we have the two equations:

\begin{align*}
\begin{pmatrix}0&-se^{i\phi}\\1&0\end{pmatrix}\dket{U}=f(s)e^{i\frac{\phi}{2}}\dket{U},\\
\begin{pmatrix}0&-se^{i\phi}\\1&0\end{pmatrix}\dket{V}=-f(s)e^{i\frac{\phi}{2}}\dket{V}
\end{align*}

This gives:

\begin{align*}
\dket{U}=\frac{1}{\sqrt{2}}(e^{-i\frac{\phi}{4}}\dket{\sigma_z}+f(s)e^{i\frac{\phi}4}\dket{\sigma_x}),\\
\dket{V}=\frac{1}{\sqrt{2}}(e^{-i\frac{\phi}{4}}\dket{\sigma_z}-f(s)e^{i\frac{\phi}{4}}\dket{\sigma_x}).
\end{align*}

In the same way, we can compute the eigenvectors $\dket{\tilde{U}},\dket{\tilde{V}}$ in the $\dket{X},\dket{Z}$ basis. We have:

\begin{align*}
\dket{\tilde{U}}=\frac{1}{\sqrt{2}}(\dket{Z}+f(s)\dket{X})\\
\dket{\tilde{V}}=\frac{1}{\sqrt{2}}(\dket{Z}-f(s)\dket{X})\\
\end{align*}

Finally, we have to impose:

\begin{align*}
&\tilde{W}\otimes\tilde{W}\dket{\tilde{U}}=\dket{\tilde W\tilde U \tilde W^T}=e^{i\gamma}\dket{\tilde U},\\
&\tilde{W}\otimes\tilde{W}\dket{\tilde{V}}=\dket{\tilde W\tilde V \tilde W^T}=e^{-i\gamma}\dket{\tilde V}.
\end{align*}

We have:

\begin{align*}
&\dket{\tilde W\tilde U \tilde W^T}=\\
&=\frac{1}{\sqrt{2}}(\dket{\tilde W Z\tilde W^\dag}-f(s)\dket{\tilde W X\tilde W^\dag})=\\
&=\frac{1}{\sqrt{2}}(\dket{\tilde W^2 Z}-f(s)\dket{\tilde W^2 X}),\\
&\dket{\tilde W\tilde V \tilde W^T}=\\
&=\frac{1}{\sqrt{2}}(\dket{\tilde W Z\tilde W^\dag}+f(s)\dket{\tilde W X\tilde W^\dag})=\\
&=\frac{1}{\sqrt{2}}(\dket{\tilde W^2 Z}+f(s)\dket{\tilde W^2 X}).
%&=\frac{1}{\sqrt{2}}\begin{pmatrix}c_{00}^2-c_{01}^2+2f(s)c_{00}c_{01} & 2c_{01}c_{00} - f(s)(c_{00}^2-c_{01}^2)\\
%2c_{01}c_{00}-f(s)(c_{00}^2-c_{01}^2) & -(c^2_{00}-c_{01}^2)-2f(s)c_{00}c_{01}\end{pmatrix},
\end{align*}

Considering that $\tilde W^2=(c_0^2-c_1^2)I+2ic_0c_1Y$, we finally have

\begin{align*}
&\dket{\tilde W\tilde U \tilde W^T}\\
&=\frac1{\sqrt2}[(c_0^2-c_1^2-2f(s)c_0c_1)\dket Z\\
&-f(s)(c_0^2-c_1^2-2sf(s)c_0c_1)\dket X],\\
&\dket{\tilde W\tilde V \tilde W^T}\\
&=\frac1{\sqrt2}[(c_0^2-c_1^2+2f(s)c_0c_1)\dket Z\\
&+f(s)(c_0^2-c_1^2+2sf(s)c_0c_1)\dket X]
%&=\frac{1}{\sqrt{2}}\begin{pmatrix}c_{00}^2-c_{01}^2+2f(s)c_{00}c_{01} & 2c_{01}c_{00} - f(s)(c_{00}^2-c_{01}^2)\\
%2c_{01}c_{00}-f(s)(c_{00}^2-c_{01}^2) & -(c^2_{00}-c_{01}^2)-2f(s)c_{00}c_{01}\end{pmatrix},
\end{align*}

This yields

\begin{align*}
\end{align*}

Clearly, l.h.s. of the above equations is a real number, thus
$e^{i\gamma}=e^{-i\gamma}=\pm1$. This implies that

\begin{align*}
&\tilde W\otimes\tilde W\dket X=\pm\dket X,\\
&\tilde W\otimes\tilde W\dket Z=\pm\dket Z,
\end{align*}

and consequently

\begin{align*}
\begin{cases}
\tilde W=(iY)&e^{i\gamma}=-1,\\
\tilde W=I&e^{i\gamma}=1.
\end{cases}
\end{align*}

\begin{align*}
&f(s)e^{i\frac\phi4}\sigma_x=\frac1{\sqrt2}(U-V)=\pm X,\\
&e^{-i\frac\phi4}\sigma_z=\frac1{\sqrt2}(U+V)=\pm Z.
\end{align*}

If $s=-1$ (and $f(s)=1$), it must be $\phi=0$ and we end up with a completely factorised
QCA, that has been already treated. If $s=1$ (and $f(s=1)=i$), on the other hand, it must

\begin{align*}
\end{align*}

which is impossible.

Let us then finally analyse case <ref>, i.e. $\phi=\pi$. In this case, by eq. (<ref>), we have

\begin{align*}
C_\pi(U\otimes U)C_\pi= (V\otimes V)F,
\end{align*}

and now the determinant of r.h.s. is 1, so we must have $\theta_{11}=2n\pi-\theta_{00}$, that leads to $F=(e^{i\theta\sigma_z})^{\otimes2}$, that is $G=W\otimes W$. We only need to determine
what are the $U$ that allow for this condition. Now, the first case that we consider is $W^2=I$, that is $U^2=I$, and then either $U=I$ or $U=i\bvec n\cdot\boldsymbol\sigma$. In the latter situation one has

\begin{align*}
&C_\pi(U\otimes U)C_\pi=\sum_{i,j=0,1}U_{ij}\ketbra ij\otimes \sigma_z^iU\sigma_z^j\\
U_{01}\ketbra{0}{1}\otimes U\sigma_z+U_{10}\ketbra 10\otimes \sigma_zU\\
&=(U_{01}\ketbra 01-U_{10}\ketbra10)\otimes (n_x\sigma_y-n_y\sigma_x),
\end{align*}

thus $C_\pi(U\otimes U)C_\pi=W\otimes W$ if and only if $U=i\sigma_j$ with $j=x,y$. We remain with the case $W^2\neq I$, which implies that $W\otimes W$ has the same eigenspaces as $W^2\otimes W^2$, and then $[G,P]=0$. In this case one has

\begin{align*}
&(U\otimes U)C_\pi\ket\mu\ket\nu=e^{i\theta_{\mu\nu}}C_\pi\ket\mu\ket\nu,\\
\end{align*}

and then

\begin{align}
\end{align}

where $\{\ket{\tilde0},\ket{\tilde 1}\}$ is the eigenbasis of $U$. However, this is possible if and only if $\ket{\tilde\mu}=\ket\mu$ for $\mu=1,0$ is the computational basis. Then eq. (<ref>) becomes

\begin{align*}
U\otimes U\dket{\sigma_x}=\omega\dket{\sigma_x},
\end{align*}

or equivalently

\begin{align*}
V\otimes V\dket{\sigma_x}=\omega\dket{\sigma_x},
\end{align*}

that is

\begin{align*}
\end{align*}

The solutions are i) $ab=0$ and $\omega=1$, ii) $a^2=|b|^2=1/2$ and $\omega=-1$. In the case (i), we have $V=U=I$, or $V=i\sigma_x$ and $U=i\sigma_y$, or $V=i\sigma_y$ and $U=i\sigma_x$, which contradict the hypothesis. In case (ii) we have, without loss of generality, $V=H$, the Hadamard gate. However, $C_\pi(H\otimes H)C_\pi$ is not factorised, and thus it cannot be accepted as a solution.

§ RENORMALISED EVOLUTION

Considering eq. (<ref>) it is easy to see that the renormalised evolution of the single cell algebra $\mathsf{B}_0$ over the periodic lattice $\mathcal{L'}$ is:

\begin{equation}
\mathcal{S}(B)\coloneqq (\tT^2)_{r}(B)=\tJ\circ \tT^{2}_{w} \circ \tV (B),\quad\forall B\in\mathsf B_0.
\label{eq:Sev}
\end{equation}

Since the evolution $\mathcal{S}$ consists in a single step of a nearest neighbours automaton, the minimum regular lattice $\mathcal{L'}$ is made of four cells, i.e. $\mathcal{L'}=\{-1,0,1,2\}$, while for the evolution $\tT^2_{\mathcal{L}}$ we need $\lvert\mathcal{L}\rvert =8$. However, the following Lemma tells us that the renormalised local rule can be computed over a lattice with $\lvert\mathcal{L}\rvert =6.$

The matrix implementing the renormalised local rule is

\begin{equation}
V_{\mathcal{S}}=\left(\bigotimes_{x\in\mathcal{L'}}\tilde{J}^\dag_{\Lambda_x}\right)\tilde{U}^2_{\tT}\left(\bigotimes_{x\in\mathcal{L'}}\tilde{J}_{\Lambda_x}\right), \label{eq:Vtilderen}
\end{equation}

\begin{equation*}
\tilde{J}_{\Lambda_x}\coloneqq M_1J_{\Lambda_x}.
\end{equation*}

To compute this rule, we can use a lattice $\mathcal{L}$ with $\lvert\mathcal{L}\rvert =6.$

If the evolution $\tT$ is implemented by the unitary $U_\tT$, eq. (<ref>) reads:

\begin{align}
&\mathcal{S}(B)=V_{\mathcal{S}}B_0 V_{\mathcal{S}}^\dag \\
\end{align}

Then repeating the same manipulations on the evolution as in eq.$(\ref{eq:evmod})$, we can define the operator $\tilde{J}_{\Lambda_x}$ as:

\begin{equation}
\begin{split}
&\tilde{J}^\dag_{\Lambda_x}\coloneqq J^\dag_{\Lambda_x}M_1^\dag\eqqcolon\tikzfig{Rdnew} \\
&\tilde{J}_{\Lambda_x}\coloneqq M_1J_{\Lambda_x}\eqqcolon\tikzfig{Rnew} \\
&\tilde{J}_{\Lambda_x}\tilde{J}_{\Lambda_x}^\dag=\tikzfig{RRdagnew}_{\Lambda_x}=\tikzfig{Piseparated}_{\Lambda_x}=P_{\Lambda_x} 	\\
\label{eq:Jtildeop}
\end{split}
\end{equation}

With those definitions we get to the diagrammatic equation:

\begin{equation}
\mathcal{S}(B)=\tikzfig{Renev}
\label{eq:sbzero}
\end{equation}

where the numbers label the cells in $\mathcal{L}$, the letters the cells of the
coarse-grained lattice $\mathcal{L'}$, and the half $G$-transformations are meant to act
on the $(-1,0)$ and $(5,6)$ cell, where possibly $-1\equiv7$. This allows us to express eq. (<ref>) using the evolution with $G$ operators as in eq. (<ref>). Since our constraints are expressed in terms of G, this is amenable for a direct application of our results. Calling $\tilde{U}^2_\tT$ the operator implementing the evolution  (<ref>),i.e.

\begin{equation}
\tilde{U}^{\dag 2}_\tT\left(\bigotimes_{x\in\mathcal{L'}}P_x\right)(\tilde{U}^2_\tT)=\tikzfig{Gev},
\end{equation}

eq. (<ref>) reads

\begin{equation}
\end{equation}

Exploiting eq.$(\ref{eq:tilde})$ we have

\begin{equation}
\mathcal{S}(B)=\tikzfig{Renevconj}
\end{equation}

Since there are no interaction between the cells $5-6$ nor $-1-0$, this equation reduces to a local expression for the evolution $\mathcal{S}({B})$ on a lattice $\mathcal{L}=\{0,1,2,3,4,5\}$.

Thus , in the following, we will compute the evolution using eq.(<ref>) over only three projections.

§.§ Renormalised Qubit automata

We now explicitly calculate the renormalised evolution for the above case of study of qubit cellular automata.

Let us start from the case where we can choose $P$ to have factorised eigenvectors, i.e.

\begin{equation}
\begin{split}
&P_{\Lambda_x}: \mathsf{A}(\Lambda_x)\to\mathsf{A}(\Lambda_x)
\end{split}
\label{eq:cgproj}
\end{equation}

where $l,j$ are functions $\{0,1\}\to\{0,1\}$, and $\{\ket{0},\ket{1}\}$ are a basis of the single cell algebra isomorphic to $\mathbb{C}^2$. In the same way as in Eq. (<ref>) the choice of a basis for the space $(\mathsf{A}_r)_x\simeq \mathbb{C}^2$ allows us to define the operator $J_{\Lambda_x}$ corresponding to $\Pi_{x}$, we can define the operator $\tilde{J}_{\Lambda_x}$ in Eq. (<ref>) corresponding to $P_{\Lambda_x}$ as well, i.e.

\begin{equation}
\tilde{J}_{\Lambda_x}=\ket{0}_r\bra{\psi_0}+\ket{1}_r\bra{\psi_1},
\label{eq:tildeJ}
\end{equation}

that for the choice of the projection in eq. (<ref>) becomes

\begin{equation}
\tilde{J}_{\Lambda_x}=\ket{0}_r\bra{l(0)}\bra{j(0)}+\ket{1}_r\bra{l(1)}\bra{j(1)}.
\end{equation}

Here the subscript $r$ simply indicates that

\begin{equation}
\tilde{J}_{\Lambda_x}: \mathsf{A}(\Lambda_x)\to(\mathsf{A}_r)_x.
\end{equation}

Let us consider for the remainder a minimal coarse-grained lattice $\mathcal L'$, i.e. with four cells. Eq. (<ref>) states that the evolution of the renormalised CA has eigenvalues equal to those of two layers of $G$, corresponding to eigenvectors of the form

\begin{equation}
\ket{\Psi_\mathbf k}\coloneqq\ket{\psi_{k_0}}\ket{\psi_{k_1}}\ket{\psi_{k_2}}\ket{\psi_{k_3}}.
\end{equation}

The corresponding eigenvector is then given by

\begin{equation}
\ket{\mathbf k}\coloneqq\ket{k_0}_r\ket{k_1}_r\ket{k_2}_r\ket{k_3}_r.
\end{equation}

Let us begin computing the case corresponding to $G$ factorised, i.e. $G=U\otimes U$. In this case, in order to compute the renormalised evolution it is enough to specify the action over the single $\ket{\psi_k}$. In the basis identified by $P$, we have

\begin{equation}
U^2=\begin{pmatrix} e^{i\lambda}& 0\\
0 & e^{-i\lambda}\end{pmatrix}\ ,
\end{equation}

whose action on $\ket{\psi_{k}}=\ket{l(k)}\ket{j(k)}$ is

\begin{equation}
(U^2\otimes U^2)\ket{\psi_k}=e^{i[(-1)^{l(k)}+(-1)^{j(k)}]\lambda}\ket{\psi_k}.
\end{equation}

Thus the renormalised evolution will be a local unitary with eigenstates given by the basis chosen in $(\ref{eq:cgproj})$, whose diagonal form is

\begin{equation}
V=\begin{pmatrix} e^{i\delta_{l(0),j(0)}(-1)^{l(0)}2\lambda} & 0\\
0& e^{i\delta_{l(1),j(1)}(-1)^{l(1)}2\lambda} \end{pmatrix}.
\end{equation}

Notice that, since the renormalised evolution have phases proportional to an integer multiple of $\lambda$, if $\lambda$ is an irrational number, the iteration of the renormalisation will reach a fixed point (the identity CA) only if one chooses
$l(k)=j(k)\oplus1$ for both $k=0,1$.

Let us now consider the case of $G$ of the form

\begin{equation}
G=C_\phi (R_z(\theta)\otimes R_z(\theta)) C_\phi=\begin{pmatrix} e^{2i\theta} & 0 &0 & 0\\
0& 1 & 0 & 0\\
0& 0 & 1 & 0\\
0& 0 & 0 & e^{-2i\theta+2i\phi}\end{pmatrix}\,.
\end{equation}

Every $G$ in the first layer of $\tilde{U}^2_{\tT}$ will act on the second qubit of a cell (say $\alpha$) and the first one of the next cell ($\alpha\oplus1$).

It is clear that these operators represent commuting gates between neighbouring cells in the lattice $\mathcal L'$, thus we can artificially split them in two layers, e.g. $(\tilde G_{12}\otimes\tilde G_{30})(\tilde G_{01}\otimes \tilde G_{23})$ where

\begin{align}
&\tilde G\ket{k_\alpha}\ket{k_{\alpha\oplus 1}}=\omega(k_\alpha,k_{\alpha\oplus1})\ket{k_\alpha}\ket{k_{\alpha\oplus 1}},\\
&\omega(k_\alpha,k_{\alpha\oplus1})\coloneqq e^{i\{[ (-1)^{j(k_\alpha)}+ (-1)^{l(k_{\alpha\oplus1})}]\theta +l(k_{\alpha\oplus1})j(k_\alpha)2\phi\}}.
\end{align}

After the application of these gates, the vector $\ket{\mathbf k}$ acquires a phase

\begin{align*}
\omega_1(\mathbf k)=\prod_{\alpha=0}^3\omega(k_\alpha,k_{\alpha\oplus1}).
\end{align*}

Now, the second layer of $G$ operators will act on the two qubits in the same cell, and can be interpreted as a layer of local gates acting on the single cells $\alpha$ as

\begin{align}
&\tilde R\ket{k_\alpha}=\nu(k_\alpha)\ket{k_\alpha},\\
&\nu(k_\alpha)\coloneqq e^{i\{[ (-1)^{j(k_\alpha)}+ (-1)^{l(k_{\alpha})}]\theta +l(k_{\alpha})j(k_\alpha)2\phi\}}.
\end{align}

After the application of these gates, the vector $\ket{\mathbf k}$ acquires a phase

\begin{align*}
\omega_2(\mathbf k)=\prod_{\alpha=0}^3\nu(k_\alpha).
\end{align*}

The final phase $\omega_1(\mathbf k)\omega_2(\mathbf k)$ can have different values depending on the functions $l$ and $j$. Let us consider the various cases, using the following equalities holding for $l\in\{0,1\}$

\begin{align*}
(-1)^l=-(2l-1),\quad l\oplus1=1-l.
\end{align*}

* $l(k)=j(k)=k$. In this case, neglecting an overall phase factor $e^{i16\theta}$, we have

\begin{align}
\omega_1(\mathbf k)\omega_2(\mathbf k)=\prod_{\alpha=0}^3e^{i[k_\alpha(2\phi-8\theta)+k_\alpha k_{\alpha\oplus 1}2\phi}]
\end{align}

This evolution corresponds to a QCA obtained with two layers of controled-phase gates $C_{\phi'}$ and one layer of local unitary gates given by $\exp(-i\sigma_z\theta')$, with

\begin{align}
\begin{cases}
\phi'=2\phi,\\
\theta'=\phi-4\theta.
\end{cases}
\end{align}

* $l(k)=j(k)=k\oplus 1$. In this case, neglecting an overall phase $e^{i16(\phi-\theta)}$, we have

\begin{align}
\omega_1(\mathbf k)\omega_2(\mathbf k)=\prod_{\alpha=0}^3e^{i[k_\alpha(8\theta-6\phi)+k_\alpha k_{\alpha\oplus 1}2\phi}].
\end{align}

This evolution corresponds to a QCA obtained with two layers of controled-phase gates $C_{\phi'}$ and one layer of local unitary gates given by $\exp(-i\sigma_z\theta')$, with

\begin{align}
\begin{cases}
\phi'=2\phi,\\
\theta'=4\theta-3\phi.
\end{cases}
\end{align}

* $l(k)=j(k)\oplus 1$. In this case, we have

\begin{align}
\omega_1(\mathbf k)\omega_2(\mathbf k)=\prod_{\alpha=0}^3e^{i[k_\alpha2\phi-k_\alpha k_{\alpha\oplus 1}2\phi}].
\end{align}

This evolution corresponds to a QCA obtained with two layers of controled-phase gates $C_{\phi'}$ and one layer of local unitary gates given by $\exp(-i\sigma_z\theta')$, with

\begin{align}
\begin{cases}
\phi'=-2\phi,\\
\theta'=\phi.
\end{cases}
\end{align}

* $l(k)=c_1$ or $j(k)=c_1$ constant. In this case, the other function will be either $k$ or $k\oplus1$, that we can express as $1/2+{s_2}(1/2-k)$ with $s_2=\pm1$, and we have, up to an irrelevant phase factor,

\begin{align}
\omega_1(\mathbf k)\omega_2(\mathbf k)=\prod_{\alpha=0}^3e^{i[s_2k_\alpha4(\theta+c_1\phi)]}.
\end{align}

This evolution corresponds to a QCA obtained one layer of local unitary gates given by $\exp(-i\sigma_z\theta')$, with

\begin{align}
\theta'=2s_2(\theta+c_1\phi).
\end{align}

Finally, consider the case

\begin{align*}
G=C_\phi (R_z(\theta)\vc{n}\cdot\vc{\sigma} R_z(\epsilon))\otimes(R_z(\theta)\vc{n}\cdot\vc{\sigma} R_z(\epsilon)) C_\phi.
\end{align*}

Remembering that $C_\phi$ is diagonal in the basis of eigenvectors of $\sigma_z$, we can always choose the $\sigma_y$ and $\sigma_x$ in such a way that $(R_z(\theta)\vc{n}\cdot\vc{\sigma} R_z(\epsilon))=\sigma_y$ and:

\begin{align*}
G=C_\phi \sigma_y\otimes\sigma_y C_\phi.
\end{align*}

Moreover, we can insert $\sigma_y\sigma_y=I$ on the left and get:

\begin{align}
G=\sigma_y\otimes\sigma_y(\sigma_y\otimes\sigma_y C_\phi \sigma_y\otimes\sigma_y)C_\phi.
\end{align}

We then have:

\begin{align*}
&\sigma_y\otimes\sigma_y C_\phi \sigma_y\otimes\sigma_y=\begin{pmatrix}e^{i\phi}&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix},\\
&\tilde{C}_\phi\coloneqq (\sigma_y\otimes\sigma_y C_\phi \sigma_y\otimes\sigma_y)C_\phi=\begin{pmatrix}e^{i\phi}&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&e^{i\phi}\end{pmatrix}.
\end{align*}

Thus, we can write $G$ as:

\begin{equation}
G=\sigma_y\otimes\sigma_y \tilde{C}_\phi=\begin{pmatrix}0&0&0&e^{i(\phi+\pi)}\\0&0&1&0\\0&1&0&0\\e^{i(\phi+\pi)}&0&0&0\end{pmatrix}.
\end{equation}

Following the steps of the previous calculation and considering the gates $\tilde{G}$ in $\mathcal{L'}$, we can write the action of the single $\tilde{G}$ on $\ket{k_\alpha}\ket{k_{\alpha\oplus 1}}$ as:

\begin{align}
&\tilde G\ket{k_\alpha}\ket{k_{\alpha\oplus 1}}=\omega(k_\alpha,k_{\alpha\oplus1})\ket{k_\alpha\oplus 1}\ket{k_{\alpha\oplus 1}\oplus 1},\\
&\omega(k_\alpha,k_{\alpha\oplus1})\coloneqq e^{i\{\phi+\pi\}\delta_{j(k_\alpha),l(k_{\alpha\oplus 1})}}.
\end{align}

Conversely to the previous case, we can see as $\tilde G$ changes the vector $\ket{k_\alpha}\ket{k_{\alpha\oplus 1}}$ to $\ket{k_{\alpha}\oplus 1}\ket{k_{\alpha\oplus 1}\oplus 1}$. Thus, we have to evaluate the action of the second layer of $\tilde G$ over the new vectors $\ket{k_{\alpha}\oplus 1}\ket{k_{\alpha\oplus 1}\oplus 1}$. Again, this second layer will act on the two qubits in the same cells, and thus we can interpret it as a layer of local gates. This gives:

\begin{align}
&\tilde R\ket{k_\alpha\oplus 1}=\nu(k_\alpha)\ket{k_\alpha},\\
&\nu(k_\alpha)\coloneqq e^{i\{\phi+\pi\}\delta_{j(k_\alpha)\oplus 1,l(k_{\alpha})\oplus 1}}= e^{i\{\phi+\pi\}\delta_{j(k_\alpha),l(k_{\alpha})}}.
\end{align}

We can then define the phases:

\begin{align}
&\omega_1(\mathbf{k})\coloneqq \prod_{\alpha=0}^3\omega(k_\alpha,k_{\alpha\oplus 1})\\
&\omega_2(\mathbf{k})\coloneqq \prod_{\alpha=0}^3\nu(k_\alpha).
\end{align}

This gives the final phase:

\begin{align}\label{eq:omegadelta}
\omega_1(\mathbf{k})\omega_2(\mathbf{k})=\prod_{\alpha=0}^3 e^{i\{\phi+\pi\}\delta_{j(k_\alpha),l(k_{\alpha})}}e^{i\{\phi+\pi\}\delta_{j(k_\alpha),l(k_{\alpha\oplus 1})}}.
\end{align}

Notice that the cases $j(k)=l(k)=k$ and $j(k)=l(k)=k\oplus 1$ give the same results. Moreover, the term $\omega_2(\mathbf k)$ contributes only if $j(k)=c$ (or equivalently if $l(k)=c$). Indeed, it is easy to see that we have:

\begin{align}
&\omega_2(\mathbf k)=1 && \mbox{if } j(k)\neq l(k)\\
&\omega_2(\mathbf k)=e^{i4(\pi+\phi)} && \mbox{if} j(k)=l(k).
\end{align}

We can now consider the different cases exploiting the equality:

\begin{align}
\delta_{ij}=1+2ij-i-j.
\end{align}

* $l(k)=j(k)$. We can consider without loss of generality the case $l(k)=k$. In this case, neglecting an overall phase factor $e^{i8\phi}=e^{i8\{\phi+\pi\}}$, we have

\begin{align}
\omega_1(\mathbf k)\omega_2(\mathbf k)=\omega_1(\mathbf{k})=\prod_{\alpha=0}^3e^{-2i\phi k_\alpha}e^{2i\phi k_\alpha k_{\alpha\oplus1}}
\end{align}

This evolution corresponds to a QCA obtained with two layers of controled-phase gates $C_{\phi'}$ and one layer of local unitary gates given by $\exp(-i\sigma_z\theta')$, with

\begin{align}
\begin{cases}
\phi'=2\phi,\\
\theta'=-\phi.
\end{cases}
\end{align}

* $l(k)=j(k)\oplus 1$. In this case,neglecting an overall phase factor $e^{i4\phi}=e^{i4\{\phi+\pi\}}$, we have

\begin{align}
\omega_1(\mathbf k)\omega_2(\mathbf k)= \omega_1(\mathbf k)=\prod_{\alpha=0}^3e^{2i\phi k_\alpha}e^{-2i\phi k_\alpha k_{\alpha\oplus1}}.