# Subsystem symmetries, quantum cellular automata, and computational phases of
quantum matter

David T. Stephen  Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße
1, 85748 Garching, Germany  Hendrik Poulsen Nautrup  Institut für Theoretische
Physik, Universität Innsbruck, Technikerstr. 21a, A-6020 Innsbruck, Austria
Juani Bermejo-Vega  Dahlem Center for Complex Quantum Systems, Freie
Universität Berlin, 14195 Berlin, Germany Jens Eisert  Dahlem Center for
Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
Robert Raussendorf  Department of Physics and Astronomy, University of British
Columbia, Vancouver, British Columbia V6T 1Z1, Canada  Stewart Blusson Quantum
Matter Institute, University of British Columbia, Vancouver, British Columbia,
V6T 1Z4, Canada

(August 27, 2024)

###### Abstract

Quantum phases of matter are resources for notions of quantum computation. In
this work, we establish a new link between concepts of quantum information
theory and condensed matter physics by presenting a unified understanding of
symmetry-protected topological (SPT) order protected by subsystem symmetries
and its relation to measurement-based quantum computation (MBQC). The key
unifying ingredient is the concept of quantum cellular automata (QCA) which we
use to define subsystem symmetries acting on rigid lower-dimensional lines or
fractals on a 2D lattice. Notably, both types of symmetries are treated
equivalently in our framework. We show that states within a non-trivial SPT
phase protected by these symmetries are indicated by the presence of the same
QCA in a tensor network representation of the state, thereby characterizing
the structure of entanglement that is uniformly present throughout these
phases. By also formulating schemes of MBQC based on these QCA, we are able to
prove that most of the phases we construct are computationally universal
phases of matter, in which every state is a resource for universal MBQC.
Interestingly, our approach allows us to construct computational phases which
have practical advantages over previous examples, including a computational
speedup. The significance of the approach stems from constructing novel
computationally universal phases of matter and showcasing the power of tensor
networks and quantum information theory in classifying subsystem SPT order.

The fields of study of quantum phases of matter and of quantum computation
have been evolving alongside each other for over a decade, such that they are
now deeply intertwined. This is on the one hand because many instances of non-
trivial quantum order are key to storing or processing quantum information, an
idea that has stimulated a plethora of theoretical and experimental research
in both fields. Perhaps the most familiar example is the idea of topological
quantum computation which leverages the anyonic excitations of topologically
ordered systems to perform error-resilient quantum computation [1, 2, 3]. A
complementing approach to topological quantum computation uses Majorana
fermions located at the edges of one-dimensional (1D) chains with symmetry-
protected topological (SPT) order [4, 5, 6]. On the other hand, quantum states
exhibiting SPT order can be used as resources for instances of measurement-
based quantum computation [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22] – an insight most relevant to the present work. Various further
examples can be found [23, 24, 25]; indeed, every time a new type of quantum
order is discovered, it is not long before its uses in notions of quantum
computation are being investigated.

Figure 1: Interrelation between symmetry-protected topological (SPT) order,
measurement-based quantum computation (MBQC), and quantum cellular automata
(QCA). By framing both subsystem SPT order and MBQC in terms of QCA, we
develop a new framework for characterizing subsystem SPT order and
constructing computationally universal phases of matter.

The most intriguing aspect of this joint development, however, is that the
intertwinement of the two fields goes both ways. Often, in-depth
characterizations of quantum phases of matter are spurred by the desire to
understand their computational properties [1, 26, 3, 27, 28, 29, 10]. In
extreme cases of this, novel notions of quantum order have been defined in
such a way that they are tailor-made for specific computational tasks [7, 11,
18, 21]. One such example can be found in Ref. [21] in which the authors
define a new two-dimensional (2D) SPT phase referred to as the “cluster
phase”, whose defining symmetries had also been suggested in earlier works [7,
11]. This phase is designed to be useful for measurement-based quantum
computation (MBQC), a scheme of quantum computation that is performed by local
measurements only on initially entangled states [30, 31], avoiding any
physical implementation of coherent quantum gates. In the context of MBQC, a
many-body quantum state is called a universal resource state if the circuit
model of quantum computation can be efficiently simulated by performing local
measurements on the state. Hence, identifying and classifying universal
resources is an important open problem in the study of MBQC. Recently,
significant progress in this direction has been made thanks to a link between
MBQC and SPT order: Many known MBQC resource states exhibit SPT order and, in
some cases, their usefulness as resources persists throughout the entire SPT
phase in which they lie. This link has nearly completely been established in
1D [7, 8, 9, 10, 12, 13, 14, 15], but to a much lesser extent in 2D [16, 17,
18, 19, 20, 22]. The aforementioned cluster phase has been the first example
of a computationally universal phase of matter, one in which every state is a
universal resource for MBQC.

What distinguishes the cluster phase from other candidates for computationally
universal phases? This answer lies in the structure of the symmetries that
define it: While conventional SPT phases are defined by global on-site
symmetries [32, 33, 34, 35, 36, 37] or crystalline symmetries [38, 39, 40],
the symmetries in the cluster phase act rather on rigid 1D lines spanning the
2D lattice. It is the first example of a subsystem SPT phase, which is any SPT
phase protected by symmetries that act on rigid lower-dimensional structures,
such as lines [41, 42], planes [43], or even fractals of non-integer dimension
[44, 45, 46, 22], see Fig. 2 for an example111Subsystem symmetries should be
distinguished from _higher-form_ symmetries which act on deformable lower-
dimensional subsystems, are related to higher-form gauge theories [47], and
have recently appeared in the context of quantum memories and quantum error
correction [48, 46, 29, 49].. For such phases the total symmetry group, and
therefore the dimension of the symmetry-protected edge states in which logical
information is encoded and processed via MBQC, grows with system size. This is
the key feature of subsystem SPT phases that enables their computational
universality. Independent from their use in MBQC, subsystem symmetries have
recently garnered interest in condensed matter physics thanks to their
relation to fracton topological order [50, 51, 52, 53] (and, much earlier,
topological order [54, 55]). It has been shown that, via generalized gauging
procedures, certain states with subsystem symmetry can be transformed to
states exhibiting fracton topological order [53, 44, 46, 43, 56, 57]. Thus, it
is high time to develop a framework for constructing and characterizing
subsystem SPT phases.

Figure 2: Two of the roles played by QCA in our results. a) Example of a
fractal symmetry operator defined by QCA that emerges from our framework. The
operator is a tensor product of local Pauli-$X$ operators arranged on a square
lattice in the pattern shown. b) We define tensor network states from QCA,
such that measuring a block of spins results in a quantum circuit living in
the virtual space of the tensor network. The circuit, which forms the backbone
of our MBQC scheme, consists of global applications of the QCA interspersed by
single qubit rotations determined by the bases in which spins are measured.
This structure appears within every state in the corresponding subsystem SPT
phase, leading to uniform computational power across the phase.

Historically, an important tool for developing the link between quantum phases
of matter and quantum computation is the language of tensor networks [58]. In
this language, the pure quantum state is decomposed into a network of local
tensors associated to each site in the lattice. Remarkably, properties of a
state that are inherently non-local, such as topological degeneracy [59] or
string order [60], can be understood locally in terms of symmetries of the
local tensors. Studying these symmetries leads to an extremely powerful
approach to detect and even classify topological order [59, 61, 62], SPT order
[34, 33, 32, 63, 64, 65], and others [66, 67, 68, 69]. The same symmetries
also aid in understanding a quantum state’s usefulness for quantum
computation. This is especially true when considering SPT order and MBQC,
wherein the group of tensor symmetries that define 1D SPT order is essentially
the only ingredient needed to construct a scheme of MBQC, and hence the
possible MBQC schemes inherit the same algebraic structure that classifies 1D
SPT order [14, 15]. In Ref. [21] as well, it is shown that the cluster phase
is characterized by a set of symmetries of the local tensor, and these
symmetries were used to derive the computational scheme therein. Using similar
methods, the same result has recently been shown for a pair of subsystem SPT
phases protected by fractal symmetries [22]. These results therefore point
towards the possibility of a unified understanding of subsystem SPT order and
its relation to MBQC via tensor networks.

In the present work, we provide such a unified framework by viewing both
subsystem SPT order and MBQC in terms of underlying quantum cellular automata
(QCA), thereby exposing a tight-knit relation between the three concepts, see
Fig. 1. The QCA are the new ingredient that becomes essential for the
description of MBQC in SPT phases in dimensions higher than 1, see Fig. 2 for
illustrations. More precisely, we use QCA to define tensor network states that
exhibit SPT order with respect to either rigid line-like or fractal subsystem
symmetries, and we then characterize the corresponding subsystem SPT phases
and their computational capabilities.

Our first result shows that non-trivial subsystem SPT order under the
symmetries we consider is characterized by the presence of the QCA within the
tensor network, which is persistent throughout the corresponding phase. This
is akin to the behavior seen in the cluster phase, as the single-tensor
symmetries that characterize the cluster phase can be used to derive the
presence of a QCA in the tensor network [21]. This means the patterns of
entanglement found in these phases are characterized in part by QCA,
demonstrating the possible use of tensor networks in obtaining a
classification of subsystem SPT order. Interestingly, our framework treats
line-like symmetries and fractal symmetries on the same footing, showing that
different types of subsystem symmetries are more similar than one would think
based on their structure. Indeed, we find that the 2D cluster state has
subsystem SPT order under both types of symmetries.

We then turn to investigating the computational capability of the constructed
phases. Using the above characterization, we show that every phase we
construct is computationally universal in the same way as the cluster phase,
except for those defined by non-entangling QCA. Hence, our framework gives a
systematic way to identify computationally universal phases of matter which,
up until now, have remained elusive outside a select few cases [21, 22]. The
computational schemes we develop are strictly tied to the QCA that define the
phases (see Fig. 2), further strengthening the connection between quantum
computation and SPT phases in 2D.

Our perspective on MBQC based on QCA has the additional feature that, by
choosing different QCA, the set of gates executable in a single step can be
tailored to suit the problem at hand. In particular, our framework allowed us
to uncover a particular class of subsystem SPT phases for which the
corresponding computational schemes enjoy a quadratic reduction in the number
of measurements per gate versus the number of logical qubits, as compared to
previous schemes [21, 22]. One such phase is built around a modified cluster
state with additional qubits placed on the horizontal edges. We briefly
discuss the implications that this result and our general framework may have
on related tasks such as blind quantum computation [70, 71], quantum
computation with global control [72, 73, 74], and in experimental
demonstrations of quantum computational advantage [75, 76].

This work is organized as follows. In Sec. 1, we begin with a review the basic
properties of QCA. In Sec. 2, we use QCA to define tensor network states and
show that they have non-trivial SPT order under certain subsystem symmetries.
Then, in Sec. 3, we investigate the properties of the corresponding SPT phases
in a quasi-1D picture before moving to a genuine 2D picture in Sec. 4. In Sec.
5, we classify these phases by their computational power in measurement-based
quantum computing. Finally, in Sec. 6, we discuss possible applications and
extensions of our results.

##  1 Quantum cellular automata

In this section, we present a review of _quantum cellular automata (QCA)_ for
qubit systems, as described in Refs. [77, 78, 79], as they will be central to
our description of symmetry protected topological order with respect to
subsystem symmetries. A 1D QCA is a translationally-invariant locality-
preserving unitary acting on a 1D chain of qubits [77]. That is, a QCA maps
any locally supported operator to another locally supported operator, with the
size of the support increased by an amount independent of the size of the
original support. In Ref. [80], it was shown that QCA acting on 1D systems are
equivalent to _matrix product unitaries (MPU)_ , in that every QCA can be
represented as an MPU with finite bond dimension, and every MPU is a QCA. An
MPU is a matrix product operator defined by a local tensor $\mathcal{T}$,
which generates a unitary $T$ on a ring of arbitrary length $N$. Graphically,
the MPU can be represented by the tensor network

$T=\includegraphics[scale={1},valign={c}]{mpu.pdf}.$ (1)

Here, the dotted lines represent the virtual indices of the MPU. All QCA
described in this paper act on systems with periodic boundary conditions. Note
that we use the graphical language of tensor networks extensively throughout
this work, see Ref. [58] for a review of the relevant notation and concepts.

In what follows, we will focus on _Clifford quantum cellular automata (CQCA)_
[78, 79], which are QCA that map products of Pauli operators to products of
Pauli operators. For reasons of simplicity of notation, we focus on the Pauli
Clifford group for qubits, even though the formalism laid out here could be
applied larger dimensions as well [81, 82]. On a finite chain of $N$ qubits,
we can define the Pauli group $\mathcal{P}_{N}$ as the group generated by all
local Pauli operators $X_{i}$, $Y_{i}$, and $Z_{i}$ acting on qubit $i$, where
$i$ is defined modulo $N$ and can take negative values giving, for example,
$X_{-1}=X_{N-1}$. A CQCA is a QCA that is also an automorphism of
$\mathcal{P}_{N}$, defined by a unitary transition function $T$ such that
$P\mapsto T(P):=T^{\dagger}PT$ for any $P\in\mathcal{P}_{N}$.

CQCA have been studied extensively in Refs. [78, 79] which introduced a
compact representation of CQCA. Firstly, a CQCA $T$ is completely specified by
the images $T(X_{0})$ and $T(Z_{0})$. To see this, note that the QCA is
translationally invariant, and that $X_{i}$ and $Z_{i}$ generate the whole
Pauli group up to phases, which contains a basis of the space of all
$2^{N}\times 2^{N}$ matrices. Next, we represent elements of
$\mathcal{P}_{N}$, up to phases, by $2N$-component binary strings
$\bm{\xi}=(\bm{\xi}^{X},\bm{\xi}^{Z})$ such that

$V(\bm{\xi})=\bigotimes_{i=1}^{N}X_{i}^{\xi^{X}_{i}}Z_{i}^{\xi^{Z}_{i}}\in\mathcal{P}_{N}.$
(2)

These strings form the group $\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$, for
which $\bm{\xi}\mapsto V(\bm{\xi})$ forms a faithful irreducible projective
representation. Note that we ignore all complex phases in front of Pauli
operators throughout, since they do not affect the symmetries or phases of
matter we define. We further condense the notation using the language of
Laurent polynomials [78]. We map $\bm{\xi}$ onto a vector of polynomials of a
variable $u$ as

$\begin{pmatrix}\bm{\xi}^{X}\\\
\bm{\xi}^{Z}\end{pmatrix}\mapsto\begin{pmatrix}\sum_{i}(u^{i})^{\xi^{X}_{i}}\\\
\sum_{i}(u^{i})^{\xi^{Z}_{i}}\end{pmatrix}.$ (3)

The purpose of the variable $u$ is the keep track of the moving and spreading
of local Pauli operators under $T$. For example, the operator
$X_{1}Z_{0}X_{-1}$ is represented as

$\bm{\xi}=\begin{pmatrix}u+u^{-1}\\\ 1\end{pmatrix}.$ (4)

We use the symbol $\bm{\xi}$ to represent both the binary and polynomial
representations of an element of $\mathcal{P}_{N}$ interchangeably.

Finally, we can represent the CQCA $T$ as a $2\times 2$ matrix $t$ of
polynomials by arranging

$T(X_{0}):=t\begin{pmatrix}1\\\
0\end{pmatrix},\,\,T(Z_{0}):=t\begin{pmatrix}0\\\ 1\end{pmatrix}$ (5)

into columns of a matrix. For a concrete example, consider the CQCA $T_{g}$
defined by the relations

$T_{g}(X_{i})=X_{i-1}Z_{i}X_{i+1}\,,T_{g}(Z_{i})=X_{i}.$ (6)

This CQCA is the QCA of the 2D cluster state [31], and it has appeared several
times already in the context of quantum computation [72, 75, 83]. The
subscript $g$ refers to the term glider which we shall introduce shortly. In
the polynomial representation, this CQCA becomes

$t_{g}=\begin{pmatrix}u+u^{-1}&1\\\ 1&0\end{pmatrix}.$ (7)

Every CQCA $T$ can be represented as a 2 $\times$ 2 matrix $t$ whose entries
are Laurent polynomials over $\mathbb{Z}_{2}$, up to phase factors [78]. We
further restrict to CQCA for which the images $T(X_{i})$, $T(Z_{i})$ are
symmetric about site $i$, meaning there is no translation in the CQCA222In
Refs. [84, 80], QCA are assigned an index according to the amount of
information flow to the left or right. Our restriction is to QCA with index 0.
As shown in Ref. [78], this corresponds to the matrix $t$ having unit
determinant. We make this restriction only because translation will not be
particularly interesting for our purposes. With this restriction, we have that
all entries in $t$ are symmetric Laurent polynomials, meaning that $u^{-k}$
appears whenever $u^{k}$ does, for all $k$. Finally, we implement the periodic
boundary conditions by taking all polynomials modulo the relation $u^{N}=1$.

CQCA can be split into three classes depending on their trace [79].

  * •

Periodic CQCA. When $\mathrm{Tr}(t)=0$ or 1 the CQCA has periodic behavior.

  * •

Glider CQCA. When $\mathrm{Tr}(t)=u^{c}+u^{-c}$ for some positive integer $c$,
the CQCA supports gliders. These are operators on which the CQCA acts as
translation by $\pm c$ sites.

  * •

Fractal CQCA. If neither of these conditions hold, the CQCA will display self-
similar fractal behavior.

The CQCA in Eq. (6) is of glider type, with $\mathrm{Tr}(t_{g})=u+u^{-1}$.
Indeed, we can check that $T_{g}(X_{i}Z_{i-1})=X_{i+1}Z_{i}$, and
$T_{g}(Z_{i+1}X_{i})=Z_{i}X_{i-1}$.

The Laurent polynomial representation allows us to uncover an identity which
will be useful at several points throughout this work. Namely, due to the
Cayley-Hamilton theorem, we obtain [79]

$t^{2}=\mathrm{Tr}(t)t+\mathbb{I},$ (8)

where we have used our assumption that $\det(t)=1$, and the fact that the
polynomials are defined over the field $\mathbb{Z}_{2}$, so addition and
subtraction are equivalent. This useful equation allows us to reduce any power
of $t$ to a linear combination of $t$ and $\mathbb{I}$.

##  2 Defining PEPS from QCA

Now we use the correspondence between QCA and MPU to define _projected
entangled pair states (PEPS)_ [85]. Given a CQCA $T$, we first represent it as
an MPU with local tensor $\mathcal{T}$, as described in Ref. [80]. We then
define the PEPS in terms of $\mathcal{T}$ by a local tensor $A_{T}$ whose
components are given by,

$\includegraphics[scale={1},valign={c},raise={0.13cm}]{qcapeps_plus.pdf}:=\includegraphics[scale={1},valign={c}]{qcapeps_I.pdf}\quad,\quad\includegraphics[scale={1},valign={c},raise={0.13cm}]{qcapeps_minus.pdf}:=\includegraphics[scale={1},valign={c}]{qcapeps_Z.pdf}.$
(9)

Given ${\cal T}$, the PEPS tensors $A_{T}$ for local qubit dimension can be
uniquely defined in this way, the vectors $\\{\ket{\pm}\\}$ constituting a
basis. The resulting PEPS may not be rotationally invariant; the dimension of
the virtual indices along the horizontal and vertical directions may not even
match. Since we will be mainly treating these PEPS as quasi-1D systems, in a
way that will be explained subsequently, we will not worry about this property
of our construction here. We call the PEPS constructed in Eq. (9) “fixed-
point” PEPS because they will appear as special points within SPT phases, such
as the AKLT state [86] within the 1D Haldane phase. However, they are not
fixed-points of any renormalization transformation defined here.

It is important to stress how the term quasi-1D system will be used here: The
mapping to a quasi-1D system occurs by putting our PEPS on a long, skinny
torus of dimensions $N\times M$ ($M\gg N$), and blocking tensors $A_{T}$ into
rings along the skinny direction of the torus. This gives rise to an
effectively one-dimensional system,

$\includegraphics[scale={1},valign={c}]{ringblock_a.pdf}:=\includegraphics[scale={1},valign={c},raise={0.12cm}]{ringblock_b.pdf}\quad.$
(10)

Therein, the contracted virtual legs correspond to the dotted red legs in Eq.
(9). The resulting ring tensor, denoted by $\mathcal{A}_{T}$, becomes the
tensor of a _matrix product state (MPS)_ [87] representation of a quasi-1D
system. For clarity, we use thicker lines when graphically representing MPS
tensors like $\mathcal{A}_{T}$ which represent blocked tensors. We stress
that, although we use a quasi-1D approach, the subsystem SPT phases that we
construct can be distinct from stacks of 1D SPT chains, as will be discussed
in Sec. 4.

If we contract the physical (upwards-directed) leg of the tensor
$\mathcal{A}_{T}$ with the $N$-qubit state vector
${|\mathbf{j}\rangle}={|j_{1},j_{2},\dots,j_{N}\rangle}$, the result is a
$2^{N}\times 2^{N}$ matrix acting in the virtual space of the tensor network,
denoted $\mathcal{A}_{T}^{\mathbf{j}}$. The state vector of the fixed-point
PEPS is then written as

${|\psi_{T}\rangle}=\sum_{\mathbf{j}_{1},\dots\mathbf{j}_{M}}\mathrm{Tr}\left(\mathcal{A}_{T}^{\mathbf{j}_{1}}\mathcal{A}_{T}^{\mathbf{j}_{2}}\dots\mathcal{A}_{T}^{\mathbf{j}_{M}}\right){|\mathbf{j}_{1},\mathbf{j}_{2},\dots,\mathbf{j}_{M}\rangle}.$
(11)

As is common in the description of quantum many-body systems with tensor
networks [33, 34, 10, 11, 12, 15, 14], throughout this work we consider
quantum states that can be captured as exact tensor network states, which is
meaningful as they approximate general states arbitrarily well [88, 89]. We
also assume that our MPS can be constructed with injective MPS tensors
$\mathcal{A}_{T}$. This condition means that, for sufficiently large $l$, the
set of products
$\\{\mathcal{A}_{T}^{\mathbf{j}_{1}}\dots\mathcal{A}_{T}^{\mathbf{j}_{l}}\\}_{\mathbf{j}_{1},\dots,\mathbf{j}_{l}}$
spans the space of all $2^{N}\times 2^{N}$ matrices [87]. Physically,
injectivity is equivalent to the state vector ${|\psi_{T}\rangle}$ having a
finite correlation length in the long direction, which is true throughout the
phases we consider.

In principle, we could have chosen to define our PEPS by replacing the Pauli
$Z$ in the $|-\rangle$-component of $A_{T}$ with an $X$ or $Y$. It turns out
that these cases are already included in the current definition. For example,
replacing the $Z$ with an $X$ is equivalent to conjugating $T$ by Hadamard
gates on every leg, represented as $t\mapsto hth^{-1}$ where

$h=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}.$ (12)

Similarly, exchanging $Z$ with $Y$ is equivalent to conjugation by phase
gates, $t\mapsto sts^{-1}$, where

$s=\begin{pmatrix}1&0\\\ 1&1\end{pmatrix}.$ (13)

Were we to also include a Pauli operator in the $|+\rangle$-component of
$A_{T}$, this would be equivalent to one of the three cases discussed above,
up to rephasing of $T$, which is unimportant to us. Hence, we can use the
definition of $A_{T}$ given by Eq. (9) without loss of generality.

For the time being, we restrict our attention to simple CQCA, which we define
to be CQCA that have the form

$t=\begin{pmatrix}\mathrm{Tr}(t)&1\\\ 1&0\end{pmatrix}.$ (14)

We make this restriction based on the fact that only simple CQCA define MPS
tensors $\mathcal{A}_{T}$ that are injective for all $N$, as proven in
Appendix B. In Sec. 5 we will slightly alter the way in which we construct
PEPS from CQCA, and in this construction we will no longer need to impose any
restriction on the choice of CQCA.

As follows straightforwardly from its definition (Eqs. (9,10)), the tensor
$\mathcal{A}_{T}$ has the symmetries

$\displaystyle=\includegraphics[scale={1},valign={c},raise={0.17cm}]{ringsymm_b.pdf}\
,$
$\displaystyle=\includegraphics[scale={1},valign={c},raise={0.1cm}]{ringsymm_d.pdf}.$
(15)

That is, a Pauli $Z$ acting in the virtual space passes through each ring
freely and is transformed by the QCA $T$, while a virtual $X$ passes through
with the help of a physical $X$ operator. Now, if $T$ represents a CQCA,
$T(Z_{i})$ and $T(X_{i})$ are products of Pauli operators. Hence, they can be
pushed through the next ring of tensors as well, possibly with the application
of more physical $X$ operators. Since we impose periodic boundary conditions,
the CQCA will have a finite period $L$ such that $t^{L}=\mathbb{I}$. In
general, $L$ is a complicated function of the circumference $N$ of the torus,
a point which we return to in Sec. 5.1. If we push any Pauli operator in the
virtual space through $L$ rings of the PEPS, it will be mapped to itself,
leading to the symmetry

=
$\displaystyle\includegraphics[scale={1},valign={c}]{qcacyclesymm_b.pdf},$
(16)

for all $\bm{\xi}\in\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$, where

$u(\bm{\xi}):=\bigotimes_{i=1}^{N}X_{i}^{\xi^{X}_{i}},$ (17)

and $V(\bm{\xi})$ is defined in Eq. (2). Hence, if we set $M=kL$,
$k\in\mathbb{N}$, our state satisfies

$U_{T}(\bm{\xi})^{\otimes k}{|\psi_{T}\rangle}={|\psi_{T}\rangle}$ (18)

where the symmetry representation $\bm{\xi}\mapsto U_{T}(\bm{\xi})^{\otimes
k}$ is defined as

$U_{T}(\bm{\xi}):=u(\bm{\xi})\otimes u(t\bm{\xi})\otimes\dots\otimes
u(t^{L-1}\bm{\xi}).$ (19)

As shown in Appendix B, $\bm{\xi}\mapsto U_{T}(\bm{\xi})$ is a faithful
representation of $\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$ when $T$ is
simple.

The unitary $U_{T}(\bm{\xi})$ is more general than the usual global on-site
symmetry operator. Rather than acting the same way on each site in the
lattice, the representation “cycles” with a period $L$. Such symmetries have
been called _$L$ -cycle symmetries_ in Ref. [90]. If we block our PEPS into
large blocks of size $N\times L$, $U_{T}(\bm{\xi})^{\otimes k}$ becomes a
standard global symmetry that acts in the same way on each block. In this way,
we can look at the conventional 1D SPT order protected by $U_{T}(\bm{\xi})$.
Since $\xi\mapsto V(\bm{\xi})$ forms a projective representation of
$\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$, the fixed-point PEPS have non-
trivial quasi-1D SPT order with respect to this symmetry [32, 34, 33]. As
discussed in Sec. 4, this means they also have non-trivial 2D SPT order with
respect to the same symmetries.

Examples. Let us study some examples of the fixed-point PEPS we have
constructed. First, consider the CQCA $T_{g}$ from Eq. (6). In this case, the
fixed-point PEPS defined by Eq. (9) represents the 2D cluster state (see
Appendix A for a proof of this and of the following examples). The
corresponding $L$-cycle symmetry has the form of cone-like operators with
$L=N$, as pictured in Fig. 3. The SPT phase defined by these symmetries is
exactly the cluster phase considered in Ref. [21].

For an example using a CQCA with fractal behavior, consider the CQCA $T_{f}$
defined by the relations

$T_{f}(X_{i})=X_{i-1}Y_{i}X_{i+1}\,,T_{f}(Z_{i})=X_{i}.$ (20)

The corresponding fixed-point PEPS turns out to be the cluster state again,
with the phase gate

$S=\begin{pmatrix}1&0\\\ 0&i\end{pmatrix}$ (21)

applied to each site. The $L$-cycle symmetries also have a fractal structure,
see Fig. 2 for an example with $N=512$, $L=\frac{3}{2}N=768$. This shows that
the cluster state also has SPT order under fractal symmetries that are tensor
products of Pauli-$Y$ operators (since $SXS^{\dagger}=Y$).

For a periodic CQCA, we choose $T_{p}$ defined as

$T_{p}(X_{i})=Z_{i}\,,T_{p}(Z_{i})=X_{i}.$ (22)

That is, $t_{p}=h$ where $h$ is as defined in Eq. (12). This corresponds to a
stack of decoupled 1D cluster states, and the $L$-cycle symmetries are simple
horizontal lines.

These examples are all states that can be defined by a local stabilizer group
[91], which is a feature common for any fixed-point PEPS constructed by Eq.
(9), as is demonstrated in Appendix A. In fact, the fixed-point PEPS defined
by simple CQCA are graph states [92], see Appendix B. Hence, every state
constructed by Eq. (9) is the unique ground state of a gapped, exactly
solvable Hamiltonian.

Figure 3: Two generators of the symmetries of the cluster phase defined by the
CQCA $T_{g}$ (Eq. (6)) on a torus of circumference $N=6$. The other generators
are vertical translates. The corresponding virtual representations for each
generator are shown at the edges. Note that a Pauli $X$ operator drawn inside
a PEPS tensor acts on the physical leg of the tensor, which is not explicitly
shown.

##  3 SPT order with $L$-cycle symmetries

Above, we have used CQCA to define fixed-point PEPS with quasi-1D SPT order
protected by $L$-cycle symmetries. We would now like to investigate the
corresponding SPT phases that surround these fixed-points. It is important to
note that these are indeed gapped phases of matter, since the fixed-point PEPS
have gapped parent Hamiltonians [33] (with a uniform gap $\Delta>0$ that is
independent of the system size, see Appendix A).

To begin, we first need a better understanding of $L$-cycle symmetries in 1D
systems. In general, we consider a (quasi) 1D chain of $d$-level systems with
length $M=kL$ which is invariant under $L$-cycle symmetries of the form
$U(g)^{\otimes k}{|\psi\rangle}={|\psi\rangle}$ where

${|\psi\rangle}=\sum_{j_{1},\dots,j_{M}=1}^{d}\mathrm{Tr}\left(\mathcal{A}^{j_{1}}\dots\mathcal{A}^{j_{M}}\right){|j_{1},\dots,j_{M}\rangle},$
(23)

and

$U(g):=u(g)\otimes u(\phi(g))\otimes\dots\otimes u(\phi^{L-1}(g)),$ (24)

with $g\mapsto u(g)$ being a $d$-dimensional unitary representation of a group
$G\ni g$, and $\phi$ an automorphism of $G$ with $\phi^{L}=\mathbb{I}$.
$g\mapsto u(g)$ alone need not be a faithful representation, but the whole
cycle $U(g)$ should be faithful (otherwise $G$ should be redefined such that
$U(g)$ becomes faithful). The symmetries found in the previous section fall
under this definition.

Again, we can block $L$ consecutive sites into one larger site such that
$U(g)^{\otimes k}$ acts in the same way on each block. If our state vector
${|\psi\rangle}$ is invariant under this symmetry, it is well-known that the
blocked MPS tensors must satisfy the relation [93],

=
$\displaystyle\includegraphics[scale={1},valign={c}]{blockcyclesymm_b.pdf}.$
(25)

Therein, $g\mapsto V(g)$ is a projective representation of the group $G$,
satisfying $V(g)V(h)=\omega(g,h)V(gh)$ for a cocycle $\omega$ [33]. The SPT
order of ${|\psi\rangle}$ with respect to the symmetry $U(g)$ can be
determined by $\omega$ [33]. For finite Abelian groups, which we will focus on
here, there is a particularly important type of SPT phase called a maximally
non-commutative phase [10]. These phases satisfy the property

$\displaystyle\\{g|\omega(g,h)=\omega(h,g)\ \forall h\in G\\}=\\{e\\},$ (26)

and they have the largest edge-mode degeneracy of all phases for a given $G$
[94]. Another important property of these phases is that the decomposition of
$V(g)$ into irreducible representations is made of up many copies of a single
irrep $\widetilde{V}(g)$, such that we have the decomposition

$\displaystyle V(g)=\mathbb{I}\otimes\widetilde{V}(g)$ (27)

$\forall g\in G$ [95]. Our first technical result is the following theorem.

######  Theorem 1 (Normal form of MPS in maximally non-commutative SPT phase).

Any state vector ${|\psi\rangle}$ on a ring of length $kL$ that is in a
maximally non-commutative SPT phase with respect to an $L$-cycle symmetry
representation (Eq. (24)) of a finite Abelian group $G$ admits an MPS
representation of the form

$\mathcal{A}_{[l]}^{j}=B_{[l]}^{j}\otimes(C^{j}\Phi),$ (28)

for suitable tensors $B_{[l]}^{j}$. Therein, $[l]$ is a site index such that
$[l]=[l+L]$, $\Phi$ is uniquely defined by the relation
$\widetilde{V}(g)=\Phi^{\dagger}\widetilde{V}(\phi(g))\Phi$, and
$C^{j}=\widetilde{V}(g_{j})$ for some $g_{j}\in G$. Throughout the phase,
$C^{j}$ and $\Phi$ remain constant, while $B^{j}_{[l]}$ varies.

This result is the essentially analogous to that given in Ref. [10] when
extended to $L$-cycle symmetries. $\Phi$ and $C^{j}$ are hence protected by
the symmetry $g\mapsto U(g)$, in that they are present in a subspace of the
virtual space of the MPS representation of all states in the phase. $C^{j}$
are completely defined by the on-site representation $g\mapsto u(g)$ of Eq.
(24), while the transformation $\Phi$ contains the information about the
structure of the $L$-cycle symmetry. Hence, the same patterns that define the
$L$-cycle symmetry also appear in the entanglement structure.

Proof. We now sketch the proof of Theorem 1, with full details given in
Appendix C. The first step is to use the results of Ref. [96] to show that the
symmetries of the block tensor (Eq. (3)) imply the following symmetries of the
single tensor,

$\includegraphics[scale={1},valign={c},raise={0.25cm}]{singletenscycle_a.pdf}\
\propto\includegraphics[scale={1},valign={c}]{singletenscycle_b.pdf}.$ (29)

Using the fact that the SPT phase is maximally non-commutative, we can then
rewrite this equation as

$\includegraphics[scale={1},valign={c},raise={0.25cm}]{singletenscycle_a.pdf}\
=\includegraphics[scale={1},valign={c}]{singletenscycle3_b.pdf},$ (30)

where $\Lambda$ is a matrix that encodes the proportionality constant that
hides in Eq. (29), which it is not consistent throughout the phase. From this,
we can continue as in Ref. [10] to constrain the matrices $\mathcal{A}^{j}$
into the form

$\mathcal{A}^{j}=B^{j}\otimes(C^{j}\Lambda\Phi).$ (31)

Finally, we get rid of the non-universal $\Lambda$, at the cost of partially
losing translation invariance of our MPS representation, and we are left with
Eq. (28). $\Box$

We can now apply Theorem 1 to the constructions found in the previous section.
Given a CQCA $T$, we get a fixed-point PEPS which is in a non-trivial quasi-1D
SPT phase with respect to the $L$-cycle symmetry $\bm{\xi}\mapsto
U_{T}(\bm{\xi})$ for $\bm{\xi}\in\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$.
Since $V(\bm{\xi})$ are $N$-qubit Pauli operators, it follows that this SPT
phase is maximally non-commutative. Hence, Theorem 1 applies, and if we
consider an arbitrary state within this SPT phase, it admits a quasi-1D MPS
representation of the form Eq. (28), which in this case reads

$\mathcal{A}^{\mathbf{j}}_{[l]}=B^{\mathbf{j}}_{[l]}\otimes(C^{\mathbf{j}}T),$
(32)

where $\mathbf{j}=(j_{1},j_{2},\dots,j_{N})$ denotes the state of the $N$
spins along a ring with $j=0$ (1) corresponding to the vectors ${|+\rangle}$
(${|-\rangle}$), and $C^{\mathbf{j}}=\bigotimes_{i=1}^{N}(Z_{i})^{j_{i}}$.
Notice that setting $B^{\mathbf{j}}_{[l]}=1$ leaves us with
$\mathcal{A}^{\mathbf{j}}_{[l]}=C^{\mathbf{j}}T$, which is the fixed-point
PEPS defined in Eq. (9).

Thus, when CQCA are used to define subsystem symmetries, the presence of non-
trivial SPT order under those symmetries is equivalent to the presence of the
CQCA on the virtual level of the tensor network. This shows that the same
structure appearing in the subsystem symmetry also appears in the entanglement
structure found throughout the phase. This correspondence between QCA and SPT
order protected by subsystem symmetries is the first major result of this
work.

##  4 Relation to subsystem SPT order

In this section, we re-cast our phases, which are so far only defined in the
quasi-1D picture, as genuine 2D phases of matter protected by subsystem
symmetries. We then show that, for phases defined by glider CQCA, the full
$L$-cycle symmetry group is not necessary to protect the phase, and a subgroup
of rigid line-like symmetries is sufficient.

###  4.1 From quasi-1D to 2D

Let us be clear about what is meant by quasi-1D SPT order and how it differs
from a genuine 2D SPT order. The difference is in the notion of locality. SPT
order can be defined as equivalence classes of states under finite depth
quantum circuits which respect the symmetry [35]; two states are in the same
SPT phase if they can be transformed into each other by such a circuit, which
corresponds to a quasi-adiabatic evolution along a path of gapped, local
Hamiltonians [97]. Here, ‘local’ depends on the dimensionality of the system.
For our quasi-1D scenario, the evolution must be local between different rings
of the torus (the long direction of the torus), but it may be non-local along
the rings (the skinny direction around the torus). When we promote to a true
2D scenario, we enforce locality in both directions. It is important to stress
that the new 2D scenario again constitutes a proper gapped phase of matter, in
that it embodies all states that can be reached from the gapped fixed point
states via local quantum circuits that respect the symmetry. Using the
techniques of Refs. [33, 98, 99], one can show a lower bound to the gap of the
parent Hamiltonian in a vicinity of the fixed point model. Indeed, one can
perturb the local tensors up to a constant error in the operator norm and
remain in the same phase of matter.

From each fixed-point PEPS, we define the corresponding quasi-1D (2D) SPT
phase as all states that can be reached from the fixed-point PEPS via
symmetric finite depth quantum circuits which are local in the quasi-1D (2D)
sense. Note that, since any circuit that is local in the 2D sense is also
local in the quasi-1D sense, the 2D SPT phases are contained within the
quasi-1D SPT phases. Therefore, the results on quasi-1D phases derived in the
previous section, Eq. (32) in particular, also hold throughout the
corresponding 2D phase defined by the same symmetries. One implication of this
is the presence of zero-energy edge modes of dimension $2^{N}$ [94] throughout
the phase. This exponentially growing edge degeneracy was noted in Refs. [41,
45] as a signature of subsystem SPT phases. In Sec. 5, we encode logical
information in these protected edge modes for the purposes of computation.

We note an important distinction between the quasi-1D and 2D scenarios. As
mentioned in Sec. 3, 1D SPT phases are classified by a symmetry group $G$, a
representation $g\mapsto U(g)$, and a cocycle $\omega$. Often, the
representation is not considered important to the classification of 1D SPT
phases [33, 34, 100] because one can construct a path of Hamiltonians that
smoothly interpolates between any two local symmetry representations without
closing the gap. So 1D SPT phases that only differ by the symmetry
representation defining them are often said to be equivalent. This is
precisely the case for the SPT phases considered here: When regarded as
quasi-1D SPT phases, they differ only by the $L$-cycle symmetry representation
$\bm{\xi}\mapsto U_{T}(\bm{\xi})$. Therefore, as quasi-1D phases, they may all
be seen as equivalent. This argument breaks down in the 2D scenario, since the
interpolation can act non-locally on blocks of size $N\times L$, violating the
2D notion of locality. So SPT phases defined by different CQCA can be distinct
in the genuine 2D scenario. Indeed, as we saw above, defining the symmetry by
the CQCA $T_{p}$ (Eq. (22)) leads to an SPT phase built around a stack of
decoupled 1D cluster states, while the phase defined by the CQCA $T_{g}$ (Eq.
(6)) is built around the 2D cluster state. These two phases are physically
distinct, as discussed in the next subsection.

###  4.2 Line-like symmetries protect glider CQCA

In the case of glider CQCA, promoting to a 2D notion of locality allows us to
equivalently define our phases in terms of rigid line-like symmetries acting
on 1D subsystems. In general, the symmetries defined by glider CQCA are shaped
like cones. This follows from Eq. (8) which, for glider CQCA, takes the form
$t^{2}=(u^{c}+u^{-c})t+\mathbb{I}$. Thus, if we apply $T$ to any single-qubit
Pauli $P_{i}$, we find

$T(T(P_{i}))=T^{2}(P_{i})=T(P_{i-c})P_{i}T(P_{i+c}).$ (33)

We can continue in this fashion to see that powers of $T$ can be expressed as
cones which expand until they wrap all the way around the torus, after which
they contract back to a point (see Fig. 4 for the case $P_{i}=Z_{i}$).

$T(Z)$ $Z$ $T(Z)$ $Z$ $T(Z)$ $Z$ $Z$ $T(Z)$ $Z$ $T(Z)$ $Z$ $T(Z)$ $Z$ $T(Z)$
$Z$ $T(Z)$ $Z$ $T(Z)$ $Z$

$T(Z)$ $Z$ $T(Z)$ $Z$ $T(Z)$ $Z$ $T(Z)$ $Z$ $T(Z)$ $Z$ $T(Z)$ $Z$ $T(Z)$ $Z$

Figure 4: Representation of the general appearance of cones (a) and lines (b)
in glider CQCA, for $c=1$. Each column represents a product of Pauli operators
on $N=6$ qubits with periodic boundaries, and advancing to the right is
equivalent to one application of $T$. After $6$ steps, any operator returns to
itself.

This picture also gives us an easy way to understand the existence of gliders,
see Fig. 4. The gliders lead to line-like symmetries of the state, as pictured
in Fig. 5. The line symmetries can be generated as products of the cone
symmetries, but the converse is not true on a finite torus. Indeed, the line
symmetries form a $\mathbb{Z}_{2}^{2(N-1)}$ subgroup of the full
$\mathbb{Z}_{2}^{2N}$ symmetry group of cones in the cluster phase.

Figure 5: The gliders of a CQCA define line-like symmetries of the PEPS, as
pictured here for the CQCA $T_{g}$ of Eq. (6) which defines the cluster phase.
The corresponding representation in the virtual space is shown on the edges.

The claim is that, when a 2D notion of locality is enforced, the line
symmetries defined by gliders are sufficient to protect the SPT order. Fig. 4
shows that the operator $T(Z_{i})Z_{i-1}$ defines a glider and hence a line
symmetry. Likewise, $Z_{i}T(Z_{i-1})$ defines a glider moving in the opposite
direction. Now, for any even integer $k$, we can write

$\displaystyle Z_{i}\otimes Z_{i-k}=$
$\displaystyle(Z_{i}T(Z_{i-1}))(T(Z_{i-1})Z_{i-2})\dots(T(Z_{i-k+1})Z_{i-k}).$
(34)

That is, we can write a product of non-neighbouring $Z$’s as a product of
gliders. Since $Z_{i}$ in the virtual space corresponds to a cone symmetry in
the physical space, we see that we can create pairs of cone symmetries with
products of line symmetries. The same argument can be repeated for $X_{i}$ in
place of $Z_{i}$.

If we separate these cones sufficiently far from each other, then each local
gate in the finite depth quantum circuit will see only one of the cones. So a
local gate that is symmetric under the line symmetries is also symmetric under
the cone symmetries. Since we require in the definition of SPT order that each
local gate of the finite depth quantum circuit commutes with the symmetry,
this implies that a circuit which is symmetric under the line symmetries is
also symmetric under the cone symmetries. Therefore, the 2D phase defined by
line symmetries in contained within the quasi-1D phase defined by the cone
symmetries.

Definitions of 2D SPT order with symmetries acting on 1D lines have also been
suggested in Refs. [11, 21, 41, 42]. In Refs. [41] and [42], the authors make
a distinction between strong and weak subsystem SPT order under line-like
symmetries. Therein, a phase is called weak if it can be trivialized by adding
1D SPT chains along the direction of the symmetry operators, while strong
subsystem SPT phases are genuine 2D phases of matter that cannot be viewed as
stacks of 1D SPT chains. For simple, periodic CQCA, the fixed-point states we
construct are themselves stacks of 1D chains, so periodic CQCA correspond to
weak subsystem SPT phases. On the other hand, phases defined by simple, glider
CQCA are strong. This has been shown in Ref. [42] for the 2D cluster phase.
For phases defined by other simple glider CQCA, one can use the stabilizer
representation of the fixed-point PEPS (Appendix A) to see that they
correspond to stacks of 2D cluster states. Since the subsystem symmetry group
acts independently on each cluster state, the resulting system is still in a
strong subsystem SPT phase. Finally, for fractal CQCA, there are no line-like
symmetries [79], and we must treat the fractal symmetries themselves as
fundamental. This leads to a definition of 2D phases via fractal symmetry
operators, as in Refs. [45, 46]. Whether there exists a notion of strong
versus weak phases under fractal symmetry remains unknown [42].

##  5 Computational power of the QCA phases

Now that we have defined 2D SPT phases via CQCA, and we have understood some
basic properties of these phases, we move on to characterizing their
computational power in measurement-based quantum computing.

Before we can state our second main result, we need to define another class of
CQCA, entangling CQCA. We call a CQCA $T$ entangling if one or more of the
entries of the matrix $t$ is not 0 or 1. In other words, entangling CQCA are
CQCA that spread information. All glider and fractal CQCA are entangling, but
not all periodic CQCA are. In particular, non-entangling CQCA are those for
which $t$ can be expressed as a product of $h,h^{-1}$ and $s,s^{-1}$ as
defined in Eq. (12) and Eq. (13), respectively. For this class of CQCA, we
will prove our second main result:

######  Theorem 2 (Computational phases of matter).

For every entangling CQCA, there exists a 2D SPT phase in which every state is
a resource for universal MBQC, except for a possible subset of zero measure.
Furthermore, the universal circuit model is simulated with polynomial
overhead.

We begin with an outline of the main ideas that are needed to use an SPT phase
as a resource for MBQC [14, 15]. There are three key features of the
constructions which are relevant to the current work:

  1. 1.

Logical qubits are encoded in the virtual space of the tensor network [101,
26]. Specifically, $N$ qubits are encoded in the $2^{N}$-dimensional subspace
of Eq. (32) which is uniform throughout the corresponding SPT phase. One time-
step of the computation is enacted by individually measuring every qubit in a
block of size $N\times L$ consisting of $L$ consecutive rings around the
torus, where $L$ is the period of the CQCA (to be determined in Sec. 5.1).
Information can be initialized into this space and subsequently read-out by
appropriate measurement patterns on blocks.

  2. 2.

Logical gates are performed by measuring a single qubit in a block in a
perturbed basis

$\\{{|+\rangle}+id\alpha{|-\rangle},{|-\rangle}-id\alpha{|+\rangle}\\},$ (35)

with $|d\alpha|\ll 1$, and measuring the rest of the qubits in a block in the
basis $\\{{|+\rangle},{|-\rangle}\\}$. According to Eq. (32), and the
computational scheme of Ref. [15], if the qubit measured in the perturbed
basis is located at site $(i,l)$ in the block, the corresponding logical gate
is, up to second order in $d\alpha$,

$R_{(i,l)}(d\alpha)=\exp(2id\alpha\nu_{(i,l)}T^{L-l+1}(Z_{i})),$ (36)

where $\\{\nu_{(i,l)}\\}$ is a set of constants that characterize the part of
the state that is not uniform within the SPT phase. That is, they are defined
in terms of the $B^{\mathbf{j}}_{[l]}$ from Eq. (32). These constants can be
easily measured before computation, again using local measurements only.
Therefore, they may be accounted for by adjusting $d\alpha$ accordingly. If
one of $\nu_{(i,l)}$ is equal to $0$, which only occurs for a subset of states
of zero measure, the computation fails. The gate $R_{(i,l)}(d\alpha)$
represents an infinitesimal rotation generated by $T^{L-l+1}(Z_{i})$. By
composing these gates in the appropriate order, we can achieve any rotation
generated by elements of the Lie algebra $\mathcal{O}_{T}$ which is generated
by the set $\\{T^{l}(Z_{i})|i=1,\dots,N,l=1,\dots,L\\}$ with linear
combinations and the matrix commutator. Thus our full set of gates is given by
the Lie group $\mathcal{L}_{T}=\exp(i\mathcal{O}_{T})$. $\mathcal{L}_{T}$ is
the same for every state in the SPT phase defined by the CQCA $T$ (to be
investigated in Sec. 5.2).

  3. 3.

Every non-trivial gate must be followed up by measuring a large number of
blocks of qubits in the $\\{{|+\rangle},{|-\rangle}\\}$ basis. The number of
blocks measured is on the order of the correlation length of the system (in
the long direction), which is finite by the assumption of injectivity. This
serves to decouple the two virtual subspaces in Eq. (32), which become
slightly entangled after each logical gate.

###  5.1 Period of the CQCA

We first determine the period $L$ of our CQCA, which determines the length of
a single step of computation. We recall the matrix representation $t$ of the
CQCA. The task is to determine the smallest $L$ such that $t^{L}=\mathbb{I}$,
which we do by invoking Eq. (8). Since the trace of the CQCA appears here, the
analysis now splits into three parts, depending on whether the CQCA is of
periodic, glider, or fractal type.

Periodic CQCA. For periodic CQCA, we have $\mathrm{Tr}(t)=a$, where $a=0,1$.
Using Eq. (8), it is easy to check that the period is then $L=a+2$ [79]. Note
that this period is independent of the circumference $N$. In particular, the
CQCA is periodic even on an infinite chain, while the glider and fractal CQCA
have a finite period only when periodic boundary conditions are enforced. This
is the reason why only these CQCA are called “periodic”.

Glider CQCA. For CQCA that support gliders, the period can be determined from
the cone structure in Fig. 4. For $c=1$ and $N$ even, this cycle takes $N$
steps (for odd $N$, it takes $2N$ steps, but we only consider even $N$). For
$c>1$, the above is still true, but there may be a smaller number $L$ also
satisfying $t^{L}=\mathbb{I}$. We ignore this possibility for simplicity.
Thus, the period of a glider CQCA on a ring of circumference $2N$ can always
be taken to be $L=2N$.

Fractal CQCA. The case is more complicated for CQCA with fractal behaviour.
Indeed, due to their fractal nature, the period $L$ of these CQCA can be a
wildly fluctuating function of $N$. In fact, $L(N)$ can appear to have
exponentially growing behavior (see Appendix D for an example). This would
pose a significant problem to computation. Since $N$ is essentially the number
of qubits, and $L$ controls the duration of a single step of computation, an
exponential relationship implies that computation time scales exponentially
with the number of qubits. Thus, we could not call the resulting computational
scheme universal, even if we have a full set of gates. Luckily, it turns out
that this problem can be avoided. Indeed, although $L(N)$ may have an
exponential envelope, it turns out that there is a subsequence of system sizes
for which the relationship in linear. Specifically, when $N=2^{k}$, we have
either $L=2^{k}=N$ or $L=2^{k}+2^{k-1}=\frac{3}{2}N$, as proven in Appendix D.

###  5.2 Determining gate set

We must now determine the Lie group of gates $\mathcal{L}_{T}$. We will show
that we can construct a universal set of gates as long as $T$ is simple and
entangling, which implies that $T$ is of glider or fractal type. We construct
arbitrary single-qubit gates and a non-trivial two-qubit entangling gate,
which together form a full gate set [102, 103, 104]. The single-qubit gates
follow from the fact that $T$ is a simple CQCA, which implies that
$T(Z_{i})=X_{i}$. Then, if we set $l=1$ in Eq. (36), we get all $Z$-rotations
on a single qubit, while setting $l=L$ gives all $X$-rotations. Together,
these give a full set of single qubit gates.

To construct an entangling gate, we generalize the technique from Ref. [21],
in which a two-qubit gate was constructed from a three-qubit gate by
initializing one qubit into a particular eigenstate on which the three-qubit
gate acts trivially. Consider $T^{2}(Z_{i})$ for any $i$. If $T$ is
entangling, this operator must act non-trivially outside of site $i$. Then
$T^{2}(Z_{i})$ will be a product of Pauli operators supported on the interval
$[i-n,i+n]$, for some minimal $n\neq 0$, which is symmetric about site $i$.
The trick now is to make every $2n$-th qubit a logical qubit, and initialize
the qubits in between each logical qubit into the +1 eigenstate of the middle
$2n-1$ operators in $T^{2}(Z_{i})$. This initialization can always be done
since we have all single qubit gates at our disposal, as described in Ref.
[21]. Then, $T^{2}(Z_{i})$ will act as a two-qubit gate on logical qubits at
positions $i-n$ and $i+n$ while leaving the qubits in between unchanged.
Hence, by setting $l=L-1$ in Eq. (36), we get a non-trivial two-qubit
entangling gate on all neighbouring pairs of logical qubits which, together
with the single-qubit gates, form a universal set.

For an explicit example, consider the CQCA from Eq. (6) with
$T_{g}^{2}(Z_{i})=X_{i-1}Z_{i}X_{i+1}$. We initialize every even numbered
qubit in the ${|0\rangle}$ eigenstate and use only odd-numbered qubits as
logical qubits. Then the gate $\exp(2id\alpha
T_{g}^{2}(Z_{2i}))=\exp(2id\alpha X_{2i-1}Z_{2i}X_{2i+1})$ reduces to
$\exp(2id\alpha X_{2i-1}X_{2i+1})$, which is an entangling gate on the logical
qubits.

###  5.3 Proving computational universality

We have now all ingredients needed for the proof of Theorem 2 for simple,
entangling CQCA. Next we show how to modify the above scheme such that we can
drop the condition that our CQCA is simple and instead apply it to any
entangling CQCA. One advantage of using simple QCA is that they allow us to
easily construct a full set of single-qubit gates. For arbitrary CQCA that are
not simple, this is not as straightforward. To address this issue, we modify
the way in which we construct fixed-point PEPS from CQCA.

The new fixed-point PEPS are defined in terms of a two-qubit unit cell,
labeling the two qubits within a unit cell by $a$ and $b$. The local tensor
$A^{\prime}_{T}$ has components given by,

$\displaystyle\includegraphics[scale={1},valign={c},raise={0.24cm}]{qcapeps_plusplus.pdf}:=\includegraphics[scale={1},valign={c}]{qcapeps_I.pdf}\qquad,\quad\includegraphics[scale={1},valign={c},raise={0.24cm}]{qcapeps_minusplus.pdf}:=\includegraphics[scale={1},valign={c}]{qcapeps_X.pdf},$
$\displaystyle\includegraphics[scale={1},valign={c},raise={0.24cm}]{qcapeps_plusminus.pdf}:=\includegraphics[scale={1},valign={c}]{qcapeps_Z.pdf}\,\,,\quad\includegraphics[scale={1},valign={c},raise={0.24cm}]{qcapeps_minusminus.pdf}:=\includegraphics[scale={1},valign={c}]{qcapeps_XZ.pdf},$
(37)

where $\mathcal{T}$ is again the MPU representation of the CQCA. The choice of
CQCA in this definition is completely free, as opposed to the previous
sections where we required $T$ to be simple CQCA.

Figure 6: The modified line and cone symmetries arising from the cluster CQCA
$T_{g}$ of Eq. (6) when using the two qubit per-site construction. $A$ ($B$)
denotes the Pauli-X operator acting on qubit $a$ ($b$) on a given site, while
operators on the edges show the corresponding virtual representation. Note
that the analysis in Sec. 4 still holds in this case: the line symmetries,
although widened, are still sufficient to protect the phase.

The tensors $A^{\prime}_{T}$ can be used to define the ring tensor
$\mathcal{A}^{\prime}_{T}$ as in Eq. (10). Proceeding from here in the same
way as the qubit case, we can construct an $L$-cycle symmetry representation

$\bm{\xi}\mapsto U^{\prime}_{T}(\bm{\xi})=u^{\prime}(\bm{\xi})\otimes
u^{\prime}(t\bm{\xi})\otimes\dots\otimes u^{\prime}(t^{L-1}\bm{\xi})$ (38)

of $\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$, where the on-site
representation is defined by

$u^{\prime}(\bm{\xi})=\bigotimes_{i=1}^{N}{X^{a}_{i}}^{\xi^{X}_{i}}{X^{b}_{i}}^{\xi^{Z}_{i}},$
(39)

where $X^{a}_{i}$, $X^{b}_{i}$ denotes the Pauli-X matrix acting on the qubit
$a$ and $b$ at site $i$, respectively (see Fig. 6). It can be easily verified
that $\bm{\xi}\mapsto U^{\prime}_{T}(\bm{\xi})$ is a faithful representation
of $\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$ as before. The virtual
representation $\bm{\xi}\mapsto V(\bm{\xi})$ is again the Pauli
representation, so the resulting state has non-trivial SPT order under this
$L$-cycle symmetry. We can thus prove that Eq. (32) holds throughout the
corresponding SPT phase, where $C^{\mathbf{j}}$ can now be any $N$-qubit
Pauli, not just a product of $Z$’s.

We can briefly compare this two-qubit construction to the original one-qubit
construction of Eq. (9). As shown in Appendix B, every PEPS defined by Eq. (9)
with a simple CQCA $T$ is equivalent to the PEPS defined by Eq. (5.3) with
CQCA $T^{2}$. So this new construction includes all fixed-point PEPS, and
hence all SPT phases, considered in the previous sections. Since we no longer
restrict to simple CQCA, we also get new fixed-point states and phases. In
particular, all fixed-point states in the previous sections were graph states,
while this is not generally the case for states defined by Eq. (5.3). They are
nevertheless still stabilizer states (see Appendix A), and so they are again
unique ground states of gapped, local Hamiltonians.

The important distinction between the two constructions appears in their use
for MBQC. Because of the different $C^{\mathbf{j}}$ appearing in Eq. (32), the
set of logical gates that we can execute in one step is enlarged. The
computational scheme is almost identical to that described above for the
single-qubit unit cell, except that we now have a choice to measure either
qubit $a$ or $b$ at a given site in a perturbed basis for a logical gate. The
logical gates we can execute now have the form,

$R^{\prime}_{(i,l)}(d\alpha)=\exp(2id\alpha\nu_{(i,l)}T^{L-l+1}(P_{i})),$ (40)

where $P_{i}$ is either $Z_{i}$ or $X_{i}$, depending on whether qubit $a$ or
$b$ is measured in the perturbed basis, respectively. Therefore, setting $l=1$
in Eq. (40) already gives a full set of single-qubit rotations. We can then
construct an entangling gate in a way exactly analogous to the previous case.
Again, this construction can fail only if $T$ is not entangling.

With this, we have constructed a full set of gates for all CQCA $T$ which are
entangling. So we can finally complete the proof of Theorem 2,

Proof of Theorem 2. Based on the above discussions, we see that a) $N$ can
always be scaled in such a way that the period $L$ is linear in $N$ or
constant, and b) we can construct a universal set of gates on $q=\lfloor
N/{2n}\rfloor$ qubits for a fixed $n$, i.e. $SU(2^{q})\subset\mathcal{L}_{T}$.
Finally, the computational scheme of Refs. [14, 15, 21] which we employ here
has polynomial overhead for logical gates. Thus, overall, we can simulate the
circuit model of quantum computation on $q$ logical qubits in $poly(q)$ time,
as stated in the theorem. $\Box$

Within each phase, the computational power remains uniform and hence they
truly constitute computational phases of matter. However, it is important to
note that the measurement protocol needed for gates depends on certain details
about the specific point within the phase, namely the constants $\nu_{(i,l)}$,
as in similar schemes from previous works [14, 15, 21, 22]. This means that
our schemes are not necessarily robust against unknown small deformations
within the phase, as would be the case in fault-tolerant schemes for quantum
computing. However, the constants $\nu_{(i,l)}$ can be readily obtained via
local measurements, in a small pre-computation before the actual quantum
computation [15], giving rise to uniform computational power across the phase.
These constants are the same for each block of computation, as we have assumed
translational invariance throughout.

###  5.4 Periodic, entangling CQCA as universal resources for MBQC

Theorem 2 does not apply to every periodic CQCA, and there are examples of
periodic CQCA which do not lead to universal phases: consider again the CQCA
$T_{p}$ in Eq. (22), which is periodic and describes decoupled 1D chains. Such
a system cannot be a universal resource for measurement-based quantum
computation with our methods, since we cannot create entangling gates with
local measurements. This shows that the presence of zero-energy edge modes of
dimension $2^{N}$ is not sufficient for universal MBQC, and that some
additional structure is needed to allow entangling gates. However, periodic
CQCA can also be entangling and hence computationally universal as stated in
Theorem 2. Surprisingly, in such cases being periodic is not a bug but rather
a feature that we now investigate.

Periodic, entangling CQCA have a computational advantage over glider or
fractal CQCA due to a quadratic reduction in the number of measurements per
gate. This improvement stems from the constant period $L$ of periodic CQCA in
contrast to a period that scales linearly in $N$ for glider or fractal CQCA
(see Sec. 5.1). As an example, consider the following periodic, entangling
CQCA,

$t_{e}=ht_{g}=\begin{pmatrix}1&0\\\ u+u^{-1}&1\end{pmatrix}.$ (41)

The corresponding fixed-point state defined via Eq. (5.3) is a dressed cluster
state which features additional qubits along horizontal lines (see Fig. 7).
The CQCA has a period of $2$ since $t_{e}^{2}=\mathbb{I}$. Nevertheless, it is
entangling since $T(X_{i})=Z_{i-1}X_{i}Z_{i+1}$ spreads information. According
to our computational scheme $T(X_{i})$ can be used as an entangling gate on
qubits $i-1$ and $i+1$ while single qubit gates come for free in the two-qubit
construction. The advantage of the periodic CQCA comes from the fact that our
scheme requires all the qubits within a block to be measured in order to
perform a single gate. Since the block size is $N\times L$ with $L=2$ for
$t_{e}$, we gain a computational advantage over glider and fractal CQCA which
require at least $N\times N$ measurements per block.

Figure 7: The dressed cluster state as defined by the CQCA $t_{e}$ in Eq.
(41). Each circle represents a qubit. Representative graph state stabilizers
are depicted in blue. One symmetry generator is depicted by red and green $X$
operators acting on the $A$ and $B$ sublattice, respectively. Since $t_{e}$ is
periodic, symmetries act along horizontal lines. However, because $t_{e}$ is
also entangling, the width of some horizontal lines is larger than one.

##  6 Discussion

In this work, we have used quantum cellular automata to define subsystem
symmetries and, correspondingly, SPT phases of matter. With this, we developed
a new framework for identifying computationally universal phases of matter,
and also for characterizing subsystem SPT order. We have determined which of
the resulting phases of matter are computationally universal from the
perspective of measurement-based quantum computation. The relation we
uncovered between QCA and SPT order protected by subsystem symmetries in
tensor networks should aid in the understanding and classification of these
relatively novel phases of matter.

Our general framework of building MBQC schemes based on CQCA remains
relatively unexplored. In particular, we can choose different CQCA in order to
tailor the elementary logical gate set towards the problem at hand, a fact
that we did not take advantage of in our general proof of universality. For
example, when two-qubit nearest neighbour gates are sufficient, periodic CQCA
can be employed for a computational speedup as shown in the previous section.
On the other hand, altering the elementary gate set in MBQC to include higher
order entangling gates is possible in our framework, and can lead to depth-
savings in gate synthesis [105]. Also, as pointed out in Ref. [22], the self-
similar nature of fractal CQCA can lead to the possibility of entangling far-
separated qubits in a single step. It is therefore worthwhile to explore the
different computational properties bestowed by different CQCA.

The flexibility of our framework could also have implications for other
related protocols of quantum computation that are partially based around QCA.
One example is that of secure delegated quantum computation: some protocols
for universal blind quantum computation [70, 71] employ schemes for MBQC that
only make use of measurements in a single plane. This requirement is naturally
fulfilled by our scheme. The same requirement has also recently appeared in
proposals to demonstrate superior quantum computational power in near-term
devices [75, 76]. Also related is quantum computation restricted to
translationally invariant operations [72, 73], which is particularly useful
for quantum computing architectures that are restricted to global control
[74]. There are examples of all of the above protocols that are based on the
cluster state QCA $T_{g}$. It would be interesting to investigate whether our
general framework can be adapted to these settings, and in particular whether
the speedup identified in Sec. 5.4 carries over to advantages in any of the
above protocols.

In the direction of classifying subsystem SPT order, one future path would
make further use of the tensor network language. In Ref. [21], it was shown
that the subsystem SPT order of the cluster phase is associated with a set of
symmetries of a single tensor. Likewise, the symmetries of a ring of tensors
considered here can be used to determine the symmetries of the single tensor.
Examining the symmetries of a single tensor has proven useful for classifying
phases of matter and their physical properties in the past [34, 33, 59, 63,
65], so it is likely this will be the case for subsystem symmetries as well.

Finally, while we only considered QCA acting as Clifford circuits on chains of
qubits, it is possible to generalize beyond this scenario. First, we could
extend our analysis to systems of arbitrary local dimension $d$. In this case,
we could realize systems with subsystem symmetry groups of the form $(G\times
G)^{N}$ for an arbitrary finite Abelian group $G$ with $|G|=d$, and our
analysis would be in terms of generalized Pauli and Clifford operators [82].
Our general formalism in Sec. 3 is already equipped to handle this extension,
which would lead to new computationally universal phases, and may be useful
for the classification of subsystem SPT phases. Similarly, we can extend our
results to higher dimensions using the same mapping to a quasi-1D system. In
particular, moving to 3D opens up the study of fracton topological order [50,
51, 53] and fault-tolerant MBQC [106, 107]. Finally, with some modifications,
our framework should also be able to handle non-Clifford QCA, although in this
case the resulting subsystem symmetries would likely not be simple products of
local operators.

This work is supported by the NSERC (DTS, RR), Cifar (RR), the Stewart Blusson
Quantum Matter Institute (RR), the European Union through the ERC grants TAQ
(JBV, JE) and WASCOSYS (DTS), the DFG CRC 183 (JE), and the Austrian Science
Fund FWF within the DK-ALM: W1259-N27 (HPN). DTS thanks N. Schuch for
discussions, and H. Dreyer for discussions and help in preparation of the
manuscript. RR thanks the American Institute of Mathematics for their
hospitality during the workshop “Arithmetic golden gates” in 2017.

##  Appendix A Stabilizers for fixed-point PEPS

In Sec. 2, we build SPT phases around special fixed-point PEPS as defined by
Eq. (9). In order to gain a better intuition and to construct gapped parent
Hamiltonians, we show in this section that the fixed-point PEPS are also
stabilizer states with local stabilizer groups.

To start, notice that the fixed-point PEPS defined by Eq. (9) have more
symmetries than those shown in Eq. (2). They also have the following
symmetries,

$\includegraphics[scale={1},valign={c}]{ringsymm_c.pdf}=\includegraphics[scale={1},valign={c},raise={0.16cm}]{fixedptsymm.pdf}=\includegraphics[scale={1},valign={c},raise={.08cm}]{ringsymm_d.pdf}.$
(42)

Note that these symmetries exist only at the fixed-point, and they do not
persist throughout the corresponding SPT phase. In addition to these
symmetries, we also need the identity from Eq. (8). In general, we have
$\mathrm{Tr}(t)=\sum_{k=1}^{m}\alpha_{k}(u^{k}+u^{-k})+\beta$ for
$\alpha_{k},\beta\in\\{0,1\\}$. Stated in terms of operators, Eq. (8) tells
us,

$T^{2}(Z_{i})=Z_{i}\bigotimes_{k=1}^{m}\left[T(Z_{i-k})T(Z_{i+k})\right]^{\alpha_{k}}T(Z_{i})^{\beta}.$
(43)

Using Eqs. (2), (42) and (43), we can now determine the form of the
stabilizers for our states,

$\displaystyle=\includegraphics[scale={1},valign={c},raise={0.15cm}]{stab2.pdf}$
$\displaystyle=\includegraphics[scale={1},valign={c},raise={0.3cm}]{stab3.pdf}$
$\displaystyle=\includegraphics[scale={1},valign={c},raise={0.3cm}]{stab4.pdf}.$
(44)

In the first equality, we have used Eq. (42). In the second, we have employed
Eq. (2) (note that $Z_{i}$ is represented as the polynomial vector
$(0,u^{i})$). In the third equality, we have used Eq. (43), and Eq. (42) to
pull the $Z_{i}$ and
$\bar{Z}:=\bigotimes_{k=1}^{m}\left[Z_{i-k}Z_{i+k}\right]^{\alpha_{k}}Z_{i}^{\beta}$
onto the physical legs. Since $u(\xi)$ is a localized product of $X$ operators
and $\bar{Z}$ is a localized product of $Z$ operators, we have derived a local
stabilizer operator. We can derive an independent stabilizer $K_{i}$ for any
site $i$ in the lattice. One can easily check that, due to the reflection
symmetry of the stabilizers, all stabilizers commute as needed. So the fixed-
point PEPS is the unique ground state of the Hamiltonian,

$H=-\sum_{i}K_{i},$ (45)

which is a local Hamiltonian with a uniform spectral gap.

We can now verify the claimed examples in Section 2. If we construct the
stabilizers for the fixed-point PEPS defined by the CQCA $T_{g}$ in Eq. (6),
then we find that they have the following form,

$\displaystyle Z$ $\displaystyle K_{i}=Z\ $ $\displaystyle X_{i}\ Z,$
$\displaystyle Z$ (46)

which is indeed the familiar form of the cluster stabilizer [31]. If we use
the CQCA $T_{f}$ in Eq. (20), we find

$\displaystyle Z$ $\displaystyle K_{i}=Z\ $ $\displaystyle Y_{i}\ Z,$
$\displaystyle Z$ (47)

which corresponds to the cluster state with the operator $S$ (Eq. (21))
applied to every site. Finally, with the CQCA $T_{p}$ of Eq. (22), we get
stabilizers with the simple form,

$K_{i}=ZX_{i}Z,$ (48)

which does indeed correspond to a stack of uncoupled 1D cluster states.

The fixed-point PEPS defined with respect to a two-qubit unit cell in Eq.
(5.3) are also stabilizer states with a local stabilizer group, as can be
straightforwardly shown in the same way as above. Hence, these fixed-point
PEPS are also ground states of uniformly gapped Hamiltonians.

##  Appendix B Simple CQCA

In this section we show that, when using the single-qubit unit cell
construction of fixed-point PEPS (Eq. (9)), it is sufficient to consider
simple CQCA, which we define to be any CQCA of the following form,

$t=\begin{pmatrix}\mathrm{Tr}(t)&1\\\ 1&0\end{pmatrix}.$ (49)

We then describe some properties of fixed-point PEPS defined by simple CQCA.

###  B.1 Injectivity of fixed-point states

Consider the $N$-qubit MPS tensor $\mathcal{A}_{T}$ defined by Eqs. (9),(10).
Note that $\mathcal{A}_{T}$ is a different MPS tensor for each $N$. In
particular, whether or not $\mathcal{A}_{T}$ is injective can depend on $N$.
In this section only, we make the $N$ dependence explicit by using the
notation $\mathcal{A}_{T,N}$ to indicate that $\mathcal{A}_{T}$ is defined on
a ring of circumference $N$. We now prove the following result.

######  Proposition 1.

$\mathcal{A}_{T,N}$ is injective for all $N$ if and only if $t_{12}=1$, where
$t$ is the polynomial matrix representation of the CQCA $T$.

The proof follows directly from the following two lemmas:

######  Lemma 1.

$\mathcal{A}_{T,N}$ is injective if and only if the set of operators $Z_{i}$
and $T(Z_{i})$, $i=1,\dots,N$, and their products forms a basis for all
$2^{N}\times 2^{N}$ matrices.

###### Proof.

Recall that injectivity means that, for sufficiently large $l$, the set of
products
$\\{\mathcal{A}_{T,N}^{\mathbf{j}_{1}}\dots\mathcal{A}_{T,N}^{\mathbf{j}_{l}}\\}_{\mathbf{j}_{1},\dots,\mathbf{j}_{l}}$
spans the space of all $2^{N}\times 2^{N}$ matrices. Since we have
$\mathcal{A}^{\mathbf{j}}_{T,N}=C^{\mathbf{j}}_{N}T$ with
$C^{\mathbf{j}}_{N}:=\bigotimes_{i=1}^{N}(Z_{i})^{j_{i}}$, we can rewrite this
set as $\\{C_{N}^{\mathbf{j}_{1}}T(C_{N}^{\mathbf{j}_{2}})\dots
T^{l-1}(C_{N}^{\mathbf{j}_{l}})T^{l}\\}_{\mathbf{j}_{1},\dots,\mathbf{j}_{l}}$
where $T^{k}(C_{N}^{\mathbf{j}})=T^{k}C_{N}^{\mathbf{j}}T^{\dagger k}$. When
checking for injectivity, the $T^{l}$ at the end can be ignored, since it does
not affect the rank of the span. Using Eq. (8), we can always reduce powers of
$T$, such that $T^{k}(C_{N}^{\mathbf{j}})$ can always be expressed as a
product of $C_{N}^{\mathbf{j}}$, $T(C_{N}^{\mathbf{j}})$ and their
translations. Therefore, injectivity in the present scenario means that the
operators $Z_{i}$, $T(Z_{i})$ and their products form a basis. ∎

In particular, Lemma 1 says that $\mathcal{A}_{T,N}$ is injective if and only
if it is possible to obtain the operator $X_{0}$ as a product of $Z_{i}$ and
$T(Z_{i})$, with $X_{i}$ for $i\neq 0$ following from translation invariance.

To facilitate the rest of the proof, let us move to the Laurent polynomial
notation. Recall that, when considering a ring of circumference $N$, we
identify $u^{N}=1$. We also work over the field $\mathbb{Z}_{2}$, so all
coefficients of the polynomials will be taken modulo 2. In what follows, we
use congruency ($\equiv$) to indicate equality subject to these
identifications.

The condition that we can express $X_{0}$ as a product of $Z_{i}$ and
$T(Z_{i})$ translates into the existence of Laurent polynomials $\bm{\xi}^{Z}$
and $\bm{\zeta}^{Z}$ such that

$\begin{pmatrix}0\\\ \bm{\xi}^{Z}\end{pmatrix}+t\begin{pmatrix}0\\\
\bm{\zeta}^{Z}\end{pmatrix}\equiv\begin{pmatrix}1\\\ 0\end{pmatrix}.$ (50)

In particular, we have,

$t_{12}\bm{\zeta}^{Z}\equiv 1.$ (51)

That is, $t_{12}$ is invertible subject to the identification $u^{N}=1$, which
we call $N$-invertible. This can only be true for all $N$ in the trivial case,
as stated by the next Lemma,

######  Lemma 2.

A symmetric Laurent polynomial $p(u)$ with coefficients in $\mathbb{Z}_{2}$ is
$N$-invertible for all $N$ if and only if $p(u)=1$.

###### Proof.

Clearly, $p(u)=1$ is $N$-invertible for all $N$. For the converse we use Ref.
[108], which shows that a polynomial $p(u)$ over $\mathbb{Z}_{2}$ is
$N$-invertible if and only if no $N$-th root of unity $\omega$ is a root of
$p(u)$, i.e. $p(\omega)\equiv 0$. To finish the proof, We will first show that
$p(u)$ has such a root on the unit circle. Then, we will show that it must be
an $N$-th root of unity for some $N$.

By assumption, $p(u)$ is a symmetric Laurent polynomial over $\mathbb{Z}_{2}$,
meaning it can be written in the following form,

$p(u)=\beta+\sum_{k}\alpha_{k}(u^{k}+u^{-k})$ (52)

for some $\beta,\alpha_{k}\in\\{0,1\\}$. If $\beta=0$, then $p(1)\equiv 0$,
and therefore 1 is trivially a root, so assume $\beta=1$. If we write
$u=e^{i\phi}$ for some angle $\phi$, then we have,

$p(e^{i\phi})=1+2\sum_{k}\alpha_{k}\cos(k\phi).$ (53)

Let $K$ denote the number of non-zero $\alpha_{k}$ (which is finite), giving
$p(1)=2K+1$. Let $\theta=\frac{\pi}{k}$ for some $k$ with $\alpha_{k}\neq 0$,
giving $p(e^{i\theta})\leq 2K-1$. Then, since $p(e^{i\phi})$ is continuous,
there must exist some $\psi\in(0,\theta)$ such that $p(e^{i\psi})=2K\equiv 0$.
Calling $\omega=e^{i\psi}$, we have a root on the unit circle.

Next, notice that $p(u^{2^{n}})\equiv p(u)^{2^{n}}$ for any $n\in\mathbb{N}$.
This holds because our coefficients are in $\mathbb{Z}_{2}$, so the cross
terms cancel out each time $p(u)$ is squared. Hence we have
$p(\omega^{2^{n}})=p(\omega)^{2^{n}}\equiv 0$, so $\omega^{2^{n}}$ is also a
root for all $n\in\mathbb{N}$. But there are only a finite number of roots on
the unit circle (since $p(u)$ is bounded on it), so we must have
$\omega^{2^{n}}=\omega^{2^{m}}$ for some $m<n$. Thus $\omega$ is an $N$-th
root of unity for $N=k(2^{n}-2^{m})$ for any $k\in\mathbb{N}$, and therefore
$p(u)$ is not $N$-invertible. ∎

Applying this Lemma to $t_{12}$, which is by definition a symmetric Laurent
polynomial, we see that if we want $\mathcal{A}_{T,N}$ to be injective for all
$N$, we need to fix $t_{12}=1$. By examining the stabilizer representation of
our fixed-point PEPS derived in Appendix A, it is clear that the PEPS depends
only on $t_{12}$ and $\mathrm{Tr}(t)$. Hence, if we set $t_{12}=1$, the only
meaningful degree of freedom left is $\mathrm{Tr}(t)$, which we can obtain by
setting $t_{11}=\mathrm{Tr}(t)$ and $t_{22}=0$. Finally, our condition that
$t$ has unit determinant enforces $t_{21}=1$, and we are left with Eq. (49).

###  B.2 Properties of fixed-point PEPS with simple CQCA

Here we note some properties of fixed-point PEPS defined by simple CQCA.

(i) The PEPS correspond to graph states defined by some underlying graph [92],
up to global application of the unitary $S$ (Eq. (21)). This can be clearly
seen by examining the stabilizer representation of the state derived in
Appendix A.

(ii) The $L$-cycle symmetry representation $\bm{\xi}\mapsto U_{T}(\bm{\xi})$
defined by Eqs. (17) and (19) is always a faithful representation of
$\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$. To see this, suppose that
$U_{T}(\bm{\xi})=\mathbb{I}$ for some
$\bm{\xi}\in\mathbb{Z}_{2}^{N}\times\mathbb{Z}_{2}^{N}$. In particular, this
implies that $u(\bm{\xi})=u(t\bm{\xi})=\mathbb{I}$. Since
$u(\bm{\xi})=\bigotimes_{i=1}^{N}X_{i}^{\xi^{X}_{i}}$, we see that
$\xi^{X}_{i}=0$, $\forall i$. Using this and Eq. (49), we have that
$u(t\bm{\xi})=\bigotimes_{i=1}^{N}X_{i}^{\xi^{Z}_{i}}$, which then implies
$\xi^{Z}_{i}=0$, $\forall i$. So $\bm{\xi}=0$ and thus $\bm{\xi}\mapsto
U_{T}(\bm{\xi})$ is a faithful representation.

(iii) In Sec. 5 we introduce an altered construction of fixed-point PEPS from
CQCA that uses a two-qubit unit cell (Eq. (5.3)). This construction subsumes
the original one, in that all fixed-point PEPS defined by Eq. (9) with a
simple CQCA can also be constructed by Eq. (5.3). To see this, note that the
fixed-point PEPS defined by Eq. (9) can be written as an MPS as follows,

${|\psi_{T}\rangle}=\sum_{\mathbf{j}_{1},\dots\mathbf{j}_{M}}\mathrm{Tr}\left(Z^{\mathbf{j}_{1}}T\dots
Z^{\mathbf{j}_{M}}T\right){|\mathbf{j}_{1},\dots,\mathbf{j}_{M}\rangle}.$ (54)

Where $P^{\mathbf{j}}=\bigotimes_{i=1}^{N}(P_{i})^{j_{i}}$ for a Pauli
operator $P=X,Y,Z$. If we commute half of the $Z^{\mathbf{j}}$ past the
neighbouring CQCA $T$ on the right, and we use the fact that
$T(Z^{\mathbf{j}})=X^{\mathbf{j}}$ for simple CQCA, we get

$\displaystyle{|\psi_{T}\rangle}=$
$\displaystyle\sum_{\mathbf{j}_{1}\dots\mathbf{j}_{M}}\mathrm{Tr}\left(X^{\mathbf{j}_{M}}Z^{\mathbf{j}_{1}}T^{2}\dots
X^{\mathbf{j}_{M-2}}Z^{\mathbf{j}_{M-1}}T^{2}\right){|\mathbf{j}_{1},\dots,\mathbf{j}_{M}\rangle}.$
(55)

If we group the $i$-th qubits of columns $2k$ and $2k+1$ together, this state
is exactly the fixed-point PEPS defined by Eq. (5.3) with CQCA $T^{2}$.

##  Appendix C Proof of Theorem 1

Here we show how to constrain the MPS tensors of states which have 1D SPT
order with respect to $L$-cycle symmetries. We begin with a state whose MPS
tensor is injective and satisfies Eq. (3), where $V(g)$ is a projective
representation of a finite Abelian group $G$ with maximally non-commutative
cocycle $\omega$. Using this, we would like to prove Eq. (28).

First, we prove Eq. (29). In general, if a state is invariant under the
$L$-cycle symmetry in Eq. (24), then we have [96],

$\includegraphics[scale={1},valign={c},raise={0.28cm}]{fundtheorem_a.pdf}=\includegraphics[scale={1},valign={c}]{fundtheorem_b.pdf},$
(56)

for some unitaries $W_{l}(g)$ ($l=0,\dots,L$) with $W_{0}(g)=W_{L}(g)$. This
equation, and all others that follow in this section, hold for all $g\in G$.
From Eq. (56), we get,

=
$\displaystyle\includegraphics[scale={0.95},valign={c}]{blockcyclesymm2_b.pdf}.$
(57)

If the tensor is injective, the only way this equation and Eq. (3) can both be
true is if $W_{0}(g)\propto V(g)$. If we connect the relations in Eq. (56) in
a different order, we find,

=
$\displaystyle\includegraphics[scale={0.95},valign={c}]{blockcyclesymm3_b.pdf},$
(58)

where we have used the fact that $\phi^{L}(g)=g$. Now compare this to Eq. (3)
with $g$ replaced by $\phi(g)$. Again, by injectivity, we find that
$W_{1}(g)\propto V(\phi(g))$. So, for some scalar $\lambda(g)$, we have,

$\includegraphics[scale={1},valign={c},raise={0.28cm}]{singletenscycle_a.pdf}=\includegraphics[scale={1},valign={c}]{singletenscycle2_b.pdf}.$
(59)

Now, we would like to use Eq. (59) to prove Eq. (28). This proof is similar to
that of Theorem 1 in Ref. [10], adapted to $L$-cycle symmetries. First, we
invoke maximal non-commutativity of the cocycle $\omega$, which says that
there is only one irreducible representation (irrep) with cocycle $\omega$, up
to unitary equivalence ([95], Theorem 6.39). Calling this irrep
$\widetilde{V}(g)$, this implies that $V(g)$, being a reducible
representation, must have the form $\mathbb{I}\otimes\widetilde{V}(g)$ in some
basis.

Then, if $g\mapsto u(g)$ is a linear representation, and $\widetilde{V}(g)$ is
an irrep with cocycle $\omega$, Eq. (59) tells us that the cocycle of
$\widetilde{V}(\phi(g))$ must be in the same cohomology class as $\omega$.
That is, there exist phases $\gamma(g)$ such that
$\gamma(g)\widetilde{V}(\phi(g))$ has cocycle $\omega$. Hence, by maximal non-
commutativity, we have
$\gamma(g)\widetilde{V}(\phi(g))=\Phi^{\dagger}\widetilde{V}(g)\Phi$ for some
unitary $\Phi$. Then it follows from Eq. (59) that
$g\mapsto\lambda(g)\gamma(g)$ is a 1D representation of $G$. Then, from Ref.
[10], we can find a unitary $\Lambda$ such that
$\overline{\lambda(g)\gamma(g)}\widetilde{V}(g)=\Lambda^{\dagger}\widetilde{V}(g)\Lambda$.

With the above we can now rewrite Eq. (59) as,

$\includegraphics[scale={1},valign={c},raise={0.26cm}]{singletenscycle_a.pdf}\
=\includegraphics[scale={1},valign={c}]{singletenscycle3_b.pdf}.$ (60)

If we multiply each side by $\mathbb{I}\otimes\Phi^{\dagger}\Lambda^{\dagger}$
on the right, then we get a relation for the composite tensor
$\mathcal{A}^{j}(\mathbb{I}\otimes\Phi^{\dagger}\Lambda^{\dagger})$. With this
relation, we can continue as in Theorem 1 of Ref. [10] to obtain,

$\mathcal{A}^{j}(\mathbb{I}\otimes\Phi^{\dagger}\Lambda^{\dagger})=B^{j}\otimes
C^{j},$ (61)

hence,

$\mathcal{A}^{j}=B^{j}\otimes(C^{j}\Lambda\Phi).$ (62)

This expression holds with respect to the basis of physical spins
$\\{|j\rangle\\}$ that diagonalizes $u(g)$, such that
$u(g){|j\rangle}=\chi_{j}(g){|j\rangle}$ where $g\mapsto\chi_{j}(g)$ are 1D
representations of $G$. We then have $C^{j}=\widetilde{V}(g_{j})$ where
$g_{j}$ are defined uniquely by the relation
$\chi_{j}(g)\widetilde{V}(g)=\widetilde{V}(g_{j})^{\dagger}\widetilde{V}(g)\widetilde{V}(g_{j})$.
$B^{j}$ are unconstrained tensors and can vary throughout the SPT phase. Since
$\lambda$ is not uniformly defined throughout the SPT phase, $\Lambda$ can
also vary throughout the phase.

We would like to rewrite Eq. (62) in such a way that we separate the parts
which are universal throughout the phase, namely $\Phi$ and $C^{j}$, from the
rest. We can accomplish this in the following way. On each block of $L$ sites,
we push the matrix $\Lambda$ through the tensors to the end of the block,

$\displaystyle B^{j_{1}}\dots B^{j_{L}}\otimes C^{j_{1}}\Lambda\Phi\dots
C^{j_{L}}\Lambda\Phi=$ $\displaystyle B^{j_{1}}_{[1]}\dots
B^{j_{L}}_{[L]}\otimes C^{j_{1}}\Phi\dots C^{j_{L}}\Phi\Lambda_{*}.$ (63)

$\Lambda$ commutes with all $\widetilde{V}(g_{j})$ up to a phase. So when
$\Lambda$ passes through the tensor $\mathcal{A}^{j}$, it leaves behind a
phase, which is absorbed into the tensor $B^{j}$. The tensors $B^{j}_{[l]}$
are the original tensors $B^{j}$ along with these phases, which are in general
not translationally invariant within a block (We do, however, have
$B^{j}_{[l]}=B^{j}_{[l+L]}$, so the representation is invariant under
translation by $L$ sites). The matrix
$\Lambda_{*}:=\Lambda\Phi^{L-1\dagger}\Lambda\Phi^{L-1}\dots\Phi^{\dagger}\Lambda\Phi$
is a scalar matrix and can thus be removed from the above expression. To see
this, note that Eq. (3) says that $\lambda(g)$ must satisfy the constraint

$\lambda_{*}(g):=\lambda(g)\lambda(\phi(g))\dots\lambda(\phi^{L-1}(g))=1.$
(64)

By definition, we have
$\overline{\lambda_{*}(g)}\widetilde{V}(g)=\Lambda_{*}^{\dagger}\widetilde{V}(g)\Lambda_{*}$.
Since $\lambda^{*}(g)=1$, we have $\Lambda_{*}\propto\mathbb{I}$ by Schur’s
lemma. The proportionality constant can be absorbed into one of the tensors
$B^{j}_{[l]}$ and therefore $\Lambda_{*}$ can be removed from Eq. (C). Hence,
we can represent our state by an MPS of the form

$A_{[l]}^{j}=B_{[l]}^{j}\otimes(C^{j}\Phi),$ (65)

as desired. $\Box$

##  Appendix D Period of fractal CQCA

N | L | N | L | N | L
---|---|---|---|---|---
2 | 3 | 18 | 84 | 34 | 510
4 | 6 | 20 | 60 | 36 | 168
6 | 12 | 22 | 186 | 38 | 1026
8 | 12 | 24 | 48 | 40 | 120
10 | 30 | 26 | 126 | 42 | 2340
12 | 24 | 28 | 36 | 44 | 372
14 | 18 | 30 | 1020 | 46 | 12282
16 | 24 | 32 | 48 | 48 | 96
Table 1: The period $L$ as a function of the circumference $N$ for the fractal
CQCA $T_{f}$ in Eq. (20). For $N=2^{k}$, the relationship is linear. In
general, $L$ appears to grow with an exponential envelope.

Here, we look at the period of fractal CQCA on rings of circumference $N$.
This is in general a difficult problem to solve, and the period $L$ can appear
to grow exponentially with $N$ (see Table 1 for an example). Nevertheless, we
prove that, for certain values of $N$, the period can be shown to have a
linear relation in general. Specifically, we prove that, for a fractal CQCA
$T$ on a ring of circumference $N=2^{k}$, the period is either $L=N=2^{k}$ or
$L=\frac{3}{2}N=2^{k}+2^{k-1}$. Throughout this proof, we will be taking
powers of polynomials like $\sum_{k}c_{k}u^{k}$. As in Appendix B, we can
write $(\sum_{k}c_{k}u^{k})^{2^{n}}=\sum_{k}c_{k}(u^{k})^{2^{n}}$ $\forall
n\in\mathbb{N}$. This simplifies the following calculations significantly.

Let

$\gamma:=\mathrm{Tr}(t)=\beta+\sum_{i}\alpha_{i}(u^{i}+u^{-i}),$ (66)

for $\alpha_{i},\beta\in\\{0,1\\}$. With the periodic boundary conditions, we
identify $u^{-2^{k-1}}$ and $u^{2^{k-1}}$. Then we have

$\gamma^{2^{k-1}}=\beta+\sum_{i}\alpha^{i}((u^{2^{k-1}})^{i}+(u^{-2^{k-1}})^{i})=\beta.$
(67)

The proof now splits into two cases:

Case 1: $\beta=0$. From Eq. (8), we have

$t^{2^{k}}=(t^{2})^{2^{k-1}}=(\gamma
t+\mathbb{I})^{2^{k-1}}=\gamma^{2^{k-1}}t^{2^{k-1}}+\mathbb{I},$ (68)

where cross terms again cancel out. Since $\gamma^{2^{k-1}}=\beta=0$, we have
$t^{2^{k}}=\mathbb{I}$, showing $L=2^{k}=N$. $\Box$

Case 2: $\beta=1$. We need a formula for $t^{2^{k}+2^{k-1}}$. The result,
which we will prove by induction, is

$\displaystyle t^{2^{k}+2^{k-1}}=$
$\displaystyle(1+\gamma^{2^{k}})\gamma^{2^{k-1}-1}t+\left[(1+\gamma^{2^{k}})p_{k}(\gamma)+\gamma^{2^{k-1}}\right]\mathbb{I}.$

Therein, $\gamma=\mathrm{Tr}(t)$, and $p_{k}(\gamma)$ is some polynomial in
$\gamma$. The expression is simple to confirm for $k=1$ using Eq. (8), where
$p_{1}(\gamma)=0$. Now assume it is true for $k$. Then we have

$\displaystyle t^{2^{k+1}+2^{k}}=(t^{2^{k}+2^{k-1}})^{2}=$
$\displaystyle(1+\gamma^{2^{k+1}})\gamma^{2^{k}-2}t^{2}+\left[(1+\gamma^{2k})p_{k}(\gamma)+\gamma^{2^{k-1}}\right]^{2}\mathbb{I}.$

Now, we apply Eq. (8) to find

$\displaystyle t^{2^{k+1}+2^{k}}=$
$\displaystyle(1+\gamma^{2^{k+1}})\gamma^{2^{k}-1}t+\left[(1+\gamma^{2^{k+1}})p_{k+1}(\gamma)+\gamma^{2^{k}}\right]\mathbb{I},$

which is the desired expression where
$p_{k+1}(\gamma)=p^{2}_{k}(\gamma)+\gamma^{2^{k}-2}$. So the formula holds for
all $k$. Now, since $\gamma^{2^{k-1}}=\beta=1$, we get
$t^{2^{k}+2^{k-1}}=\mathbb{I}$, so $L={2^{k}+2^{k-1}}=\frac{3}{2}N$. $\Box$

## References

  * [1] A.Yu. Kitaev “Fault-tolerant quantum computation by anyons” In _Ann. Phys._ 303.1, 2003, pp. 2 –30 DOI: 10.1016/S0003-4916(02)00018-0
  * [2] Michael Freedman, Alexei Kitaev, Michael Larsen and Zhenghan Wang “Topological quantum computation” In _Bull. Amer. Math. Soc._ 40, 2003, pp. 31–38 DOI: 10.1090/S0273-0979-02-00964-3
  * [3] Chetan Nayak, Steven H. Simon, Ady Stern, Michael Freedman and Sankar Das Sarma “Non-Abelian anyons and topological quantum computation” In _Rev. Mod. Phys._ 80 American Physical Society, 2008, pp. 1083–1159 DOI: 10.1103/RevModPhys.80.1083
  * [4] A Yu Kitaev “Unpaired Majorana fermions in quantum wires” In _Physics-Uspekhi_ 44.10S Uspekhi Fizicheskikh Nauk (UFN) Journal, 2001, pp. 131–136 DOI: 10.1070/1063-7869/44/10s/s29
  * [5] Jason Alicea, Yuval Oreg, Gil Refael, Felix Oppen and Matthew P. A. Fisher “Non-Abelian statistics and topological quantum information processing in 1D wire networks” In _Nature Physics_ 7 Nature Publishing Group, 2011, pp. 412–417 DOI: 10.1038/nphys1915
  * [6] R. M. Lutchyn et al. “Majorana zero modes in superconductor-semiconductor heterostructures” In _Nature Reviews Materials_ 3.5, 2018, pp. 52–68 DOI: 10.1038/s41578-018-0003-1
  * [7] Andrew C. Doherty and Stephen D. Bartlett “Identifying Phases of Quantum Many-Body Systems That Are Universal for Quantum Computation” In _Phys. Rev. Lett._ 103 American Physical Society, 2009, pp. 020506 DOI: 10.1103/PhysRevLett.103.020506
  * [8] Akimasa Miyake “Quantum Computation on the Edge of a Symmetry-Protected Topological Order” In _Phys. Rev. Lett._ 105 American Physical Society, 2010, pp. 040501 DOI: 10.1103/PhysRevLett.105.040501
  * [9] Stephen D. Bartlett, Gavin K. Brennen, Akimasa Miyake and Joseph M. Renes “Quantum Computational Renormalization in the Haldane Phase” In _Phys. Rev. Lett._ 105 American Physical Society, 2010, pp. 110502 DOI: 10.1103/PhysRevLett.105.110502
  * [10] Dominic V. Else, Ilai Schwarz, Stephen D. Bartlett and Andrew C. Doherty “Symmetry-Protected Phases for Measurement-Based Quantum Computation” In _Phys. Rev. Lett._ 108 American Physical Society, 2012, pp. 240505 DOI: 10.1103/PhysRevLett.108.240505
  * [11] Dominic V Else, Stephen D Bartlett and Andrew C Doherty “Symmetry protection of measurement-based quantum computation in ground states” In _New Journal of Physics_ 14.11 IOP Publishing, 2012, pp. 113016 DOI: 10.1088/1367-2630/14/11/113016
  * [12] Jacob Miller and Akimasa Miyake “Resource Quality of a Symmetry-Protected Topologically Ordered Phase for Quantum Computation” In _Phys. Rev. Lett._ 114 American Physical Society, 2015, pp. 120506 DOI: 10.1103/PhysRevLett.114.120506
  * [13] Dong-Sheng Wang, David T. Stephen and Robert Raussendorf “Qudit quantum computation on matrix product states with global symmetry” In _Phys. Rev. A_ 95 American Physical Society, 2017, pp. 032312 DOI: 10.1103/PhysRevA.95.032312
  * [14] David T. Stephen, Dong-Sheng Wang, Abhishodh Prakash, Tzu-Chieh Wei and Robert Raussendorf “Computational Power of Symmetry-Protected Topological Phases” In _Phys. Rev. Lett._ 119 American Physical Society, 2017, pp. 010504 DOI: 10.1103/PhysRevLett.119.010504
  * [15] Robert Raussendorf, Dong-Sheng Wang, Abhishodh Prakash, Tzu-Chieh Wei and David T. Stephen “Symmetry-protected topological phases with uniform computational power in one dimension” In _Phys. Rev. A_ 96 American Physical Society, 2017, pp. 012302 DOI: 10.1103/PhysRevA.96.012302
  * [16] Hendrik Poulsen Nautrup and Tzu-Chieh Wei “Symmetry-protected topologically ordered states for universal quantum computation” In _Phys. Rev. A_ 92 American Physical Society, 2015, pp. 052309 DOI: 10.1103/PhysRevA.92.052309
  * [17] Jacob Miller and Akimasa Miyake “Hierarchy of universal entanglement in 2D measurement-based quantum computation” In _npj Quantum Information_ 2, 2016, pp. 16036 DOI: 10.1038/npjqi.2016.36
  * [18] Jacob Miller and Akimasa Miyake “Latent Computational Complexity of Symmetry-Protected Topological Order with Fractional Symmetry” In _Phys. Rev. Lett._ 120 American Physical Society, 2018, pp. 170503 DOI: 10.1103/PhysRevLett.120.170503
  * [19] Tzu-Chieh Wei and Ching-Yu Huang “Universal measurement-based quantum computation in two-dimensional symmetry-protected topological phases” In _Phys. Rev. A_ 96 American Physical Society, 2017, pp. 032317 DOI: 10.1103/PhysRevA.96.032317
  * [20] Yanzhu Chen, Abhishodh Prakash and Tzu-Chieh Wei “Universal quantum computing using ${({\mathbb{Z}}_{d})}^{3}$ symmetry-protected topologically ordered states” In _Phys. Rev. A_ 97 American Physical Society, 2018, pp. 022305 DOI: 10.1103/PhysRevA.97.022305
  * [21] Robert Raussendorf, Cihan Okay, Dong-Sheng Wang, David T. Stephen and Hendrik Poulsen Nautrup “Computationally Universal Phase of Quantum Matter” In _Phys. Rev. Lett._ 122 American Physical Society, 2019, pp. 090501 DOI: 10.1103/PhysRevLett.122.090501
  * [22] Trithep Devakul and Dominic J. Williamson “Universal quantum computation using fractal symmetry-protected cluster phases” In _Phys. Rev. A_ 98 American Physical Society, 2018, pp. 022332 DOI: 10.1103/PhysRevA.98.022332
  * [23] Sagar Vijay, Timothy H. Hsieh and Liang Fu “Majorana Fermion Surface Code for Universal Quantum Computation” In _Phys. Rev. X_ 5 American Physical Society, 2015, pp. 041038 DOI: 10.1103/PhysRevX.5.041038
  * [24] Arpit Dua, Boris Malomed, Meng Cheng and Liang Jiang “Universal quantum computing with parafermions assisted by a half fluxon”, 2018 URL: https://arxiv.org/abs/1803.05886
  * [25] Bela Bauer et al. “Topologically protected braiding in a single wire using Floquet Majorana modes”, 2018 URL: https://arxiv.org/abs/1808.07066
  * [26] D. Gross, J. Eisert, N. Schuch and D. Perez-Garcia “Measurement-based quantum computation beyond the one-way model” In _Phys. Rev. A_ 76 American Physical Society, 2007, pp. 052315 DOI: 10.1103/PhysRevA.76.052315
  * [27] H. Bombin and M. A. Martin-Delgado “Family of non-Abelian Kitaev models on a lattice: Topological condensation and confinement” In _Phys. Rev. B_ 78 American Physical Society, 2008, pp. 115421 DOI: 10.1103/PhysRevB.78.115421
  * [28] Beni Yoshida “Gapped boundaries, group cohomology and fault-tolerant logical gates” In _Ann. Phys._ 377, 2017, pp. 387 –413 DOI: 10.1016/j.aop.2016.12.014
  * [29] Sam Roberts, Beni Yoshida, Aleksander Kubica and Stephen D. Bartlett “Symmetry-protected topological order at nonzero temperature” In _Phys. Rev. A_ 96 American Physical Society, 2017, pp. 022306 DOI: 10.1103/PhysRevA.96.022306
  * [30] Robert Raussendorf and Hans J. Briegel “A One-Way Quantum Computer” In _Phys. Rev. Lett._ 86 American Physical Society, 2001, pp. 5188–5191 DOI: 10.1103/PhysRevLett.86.5188
  * [31] Robert Raussendorf, Daniel E. Browne and Hans J. Briegel “Measurement-based quantum computation on cluster states” In _Phys. Rev. A_ 68 American Physical Society, 2003, pp. 022312 DOI: 10.1103/PhysRevA.68.022312
  * [32] Frank Pollmann, Ari M. Turner, Erez Berg and Masaki Oshikawa “Entanglement spectrum of a topological phase in one dimension” In _Phys. Rev. B_ 81 American Physical Society, 2010, pp. 064439 DOI: 10.1103/PhysRevB.81.064439
  * [33] Norbert Schuch, David Pérez-García and Ignacio Cirac “Classifying quantum phases using matrix product states and projected entangled pair states” In _Phys. Rev. B_ 84 American Physical Society, 2011, pp. 165139 DOI: 10.1103/PhysRevB.84.165139
  * [34] Xie Chen, Zheng-Cheng Gu and Xiao-Gang Wen “Classification of gapped symmetric phases in one-dimensional spin systems” In _Phys. Rev. B_ 83 American Physical Society, 2011, pp. 035107 DOI: 10.1103/PhysRevB.83.035107
  * [35] Xie Chen, Zheng-Cheng Gu, Zheng-Xin Liu and Xiao-Gang Wen “Symmetry protected topological orders and the group cohomology of their symmetry group” In _Phys. Rev. B_ 87 American Physical Society, 2013, pp. 155114 DOI: 10.1103/PhysRevB.87.155114
  * [36] T. Senthil “Symmetry-Protected Topological Phases of Quantum Matter” In _Ann. Rev. Cond. Mat. Phys._ 6.1, 2015, pp. 299–324 DOI: 10.1146/annurev-conmatphys-031214-014740
  * [37] A. Nietner, C. Krumnow, E. J. Bergholtz and J. Eisert “Composite symmetry-protected topological order and effective models” In _Phys. Rev. B_ 96 American Physical Society, 2017, pp. 235138 DOI: 10.1103/PhysRevB.96.235138
  * [38] Hao Song, Sheng-Jie Huang, Liang Fu and Michael Hermele “Topological Phases Protected by Point Group Symmetry” In _Phys. Rev. X_ 7 American Physical Society, 2017, pp. 011020 DOI: 10.1103/PhysRevX.7.011020
  * [39] Ryan Thorngren and Dominic V. Else “Gauging Spatial Symmetries and the Classification of Topological Crystalline Phases” In _Phys. Rev. X_ 8 American Physical Society, 2018, pp. 011040 DOI: 10.1103/PhysRevX.8.011040
  * [40] Sheng-Jie Huang, Hao Song, Yi-Ping Huang and Michael Hermele “Building crystalline topological phases from lower-dimensional states” In _Phys. Rev. B_ 96 American Physical Society, 2017, pp. 205106 DOI: 10.1103/PhysRevB.96.205106
  * [41] Yizhi You, Trithep Devakul, F. J. Burnell and S. L. Sondhi “Subsystem symmetry protected topological order” In _Phys. Rev. B_ 98 American Physical Society, 2018, pp. 035112 DOI: 10.1103/PhysRevB.98.035112
  * [42] Trithep Devakul, Dominic J. Williamson and Yizhi You “Classification of subsystem symmetry-protected topological phases” In _Phys. Rev. B_ 98 American Physical Society, 2018, pp. 235121 DOI: 10.1103/PhysRevB.98.235121
  * [43] Yizhi You, Trithep Devakul, F. J. Burnell and S. L. Sondhi “Symmetric Fracton Matter: Twisted and Enriched”, 2018 URL: https://arxiv.org/abs/1805.09800
  * [44] Dominic J. Williamson “Fractal symmetries: Ungauging the cubic code” In _Phys. Rev. B_ 94 American Physical Society, 2016, pp. 155128 DOI: 10.1103/PhysRevB.94.155128
  * [45] Trithep Devakul, Yizhi You, F. J. Burnell and S. L. Sondhi “Fractal Symmetric Phases of Matter” In _SciPost Phys._ 6 SciPost, 2019, pp. 7 DOI: 10.21468/SciPostPhys.6.1.007
  * [46] Aleksander Kubica and Beni Yoshida “Ungauging quantum error-correcting codes”, 2018 URL: https://arxiv.org/abs/1805.01836
  * [47] Davide Gaiotto, Anton Kapustin, Nathan Seiberg and Brian Willett “Generalized global symmetries” In _J. High En. Phys._ 2015.2, 2015, pp. 172 DOI: 10.1007/JHEP02(2015)172
  * [48] Beni Yoshida “Topological phases with generalized global symmetries” In _Phys. Rev. B_ 93 American Physical Society, 2016, pp. 155131 DOI: 10.1103/PhysRevB.93.155131
  * [49] Sam Roberts and Stephen D. Bartlett “Symmetry-protected self-correcting quantum memories”, 2018 URL: https://arxiv.org/abs/1805.01474
  * [50] Jeongwan Haah “Local stabilizer codes in three dimensions without string logical operators” In _Phys. Rev. A_ 83 American Physical Society, 2011, pp. 042330 DOI: 10.1103/PhysRevA.83.042330
  * [51] Beni Yoshida “Exotic topological order in fractal spin liquids” In _Phys. Rev. B_ 88 American Physical Society, 2013, pp. 125122 DOI: 10.1103/PhysRevB.88.125122
  * [52] Sagar Vijay, Jeongwan Haah and Liang Fu “A new kind of topological quantum order: A dimensional hierarchy of quasiparticles built from stationary excitations” In _Phys. Rev. B_ 92 American Physical Society, 2015, pp. 235136 DOI: 10.1103/PhysRevB.92.235136
  * [53] Sagar Vijay, Jeongwan Haah and Liang Fu “Fracton topological order, generalized lattice gauge theory, and duality” In _Phys. Rev. B_ 94 American Physical Society, 2016, pp. 235157 DOI: 10.1103/PhysRevB.94.235157
  * [54] Zohar Nussinov and Gerardo Ortiz “A symmetry principle for topological quantum order” In _Ann. Phys._ 324.5, 2009, pp. 977 –1057 DOI: 10.1016/j.aop.2008.11.002
  * [55] Zohar Nussinov and Gerardo Ortiz “Sufficient symmetry conditions for Topological Quantum Order” In _Proceedings of the National Academy of Sciences_ 106.40 National Academy of Sciences, 2009, pp. 16944–16949 DOI: 10.1073/pnas.0803726105
  * [56] Wilbur Shirley, Kevin Slagle and Xie Chen “Foliated fracton order from gauging subsystem symmetries” In _SciPost Phys._ 6 SciPost, 2019, pp. 41 DOI: 10.21468/SciPostPhys.6.4.041
  * [57] Hao Song, Abhinav Prem, Sheng-Jie Huang and M. A. Martin-Delgado “Twisted fracton models in three dimensions” In _Phys. Rev. B_ 99 American Physical Society, 2019, pp. 155118 DOI: 10.1103/PhysRevB.99.155118
  * [58] Jacob C Bridgeman and Christopher T Chubb “Hand-waving and interpretive dance: an introductory course on tensor networks” In _J. Phys. A_ 50.22 IOP Publishing, 2017, pp. 223001 DOI: 10.1088/1751-8121/aa6dc3
  * [59] Norbert Schuch, Ignacio Cirac and David Perez-Garcia “PEPS as ground states: Degeneracy and topology” In _Ann. Phys._ 325.10, 2010, pp. 2153 –2192 DOI: 10.1016/j.aop.2010.05.008
  * [60] Frank Pollmann and Ari M. Turner “Detection of symmetry-protected topological phases in one dimension” In _Phys. Rev. B_ 86 American Physical Society, 2012, pp. 125441 DOI: 10.1103/PhysRevB.86.125441
  * [61] N. Bultinck et al. “Anyons and matrix product operator algebras” In _Ann. Phys._ 378, 2017, pp. 183 –233 DOI: 10.1016/j.aop.2017.01.004
  * [62] Kasper Duivenvoorden, Mohsin Iqbal, Jutho Haegeman, Frank Verstraete and Norbert Schuch “Entanglement phases as holographic duals of anyon condensates” In _Phys. Rev. B_ 95 American Physical Society, 2017, pp. 235119 DOI: 10.1103/PhysRevB.95.235119
  * [63] Dominic J. Williamson et al. “Matrix product operators for symmetry-protected topological phases: Gauging and edge theories” In _Phys. Rev. B_ 94 American Physical Society, 2016, pp. 205150 DOI: 10.1103/PhysRevB.94.205150
  * [64] Shenghan Jiang and Ying Ran “Anyon condensation and a generic tensor-network construction for symmetry-protected topological phases” In _Phys. Rev. B_ 95 American Physical Society, 2017, pp. 125107 DOI: 10.1103/PhysRevB.95.125107
  * [65] Andras Molnar, Yimin Ge, Norbert Schuch and J. Ignacio Cirac “A generalization of the injectivity condition for projected entangled pair states” In _J. Math. Phys._ 59.2, 2018, pp. 021902 DOI: 10.1063/1.5007017
  * [66] Didier Poilblanc, J. Ignacio Cirac and Norbert Schuch “Chiral topological spin liquids with projected entangled pair states” In _Phys. Rev. B_ 91 American Physical Society, 2015, pp. 224431 DOI: 10.1103/PhysRevB.91.224431
  * [67] Dominic J. Williamson, Nick Bultinck and Frank Verstraete “Symmetry-enriched topological order in tensor networks: Defects, gauging and anyon condensation”, 2017 URL: https://arxiv.org/abs/1711.07982
  * [68] Nick Bultinck, Dominic J Williamson, Jutho Haegeman and Frank Verstraete “Fermionic projected entangled-pair states and topological phases” In _J. Phys. A_ 51.2 IOP Publishing, 2017, pp. 025202 DOI: 10.1088/1751-8121/aa99cc
  * [69] Henrik Dreyer, J. Ignacio Cirac and Norbert Schuch “Projected entangled pair states with continuous virtual symmetries” In _Phys. Rev. B_ 98 American Physical Society, 2018, pp. 115120 DOI: 10.1103/PhysRevB.98.115120
  * [70] Joseph F. Fitzsimons “Private quantum computation: an introduction to blind quantum computing and related protocols” In _npj Quantum Information_ 3, 2017, pp. 23 DOI: 10.1038/s41534-017-0025-3
  * [71] Atul Mantri, Tommaso F. Demarie, Nicolas C. Menicucci and Joseph F. Fitzsimons “Flow Ambiguity: A Path Towards Classically Driven Blind Quantum Computation” In _Phys. Rev. X_ 7 American Physical Society, 2017, pp. 031004 DOI: 10.1103/PhysRevX.7.031004
  * [72] Robert Raussendorf “Quantum computation via translation-invariant operations on a chain of qubits” In _Phys. Rev. A_ 72 American Physical Society, 2005, pp. 052301 DOI: 10.1103/PhysRevA.72.052301
  * [73] Joseph Fitzsimons and Jason Twamley “Globally Controlled Quantum Wires for Perfect Qubit Transport, Mirroring, and Computing” In _Phys. Rev. Lett._ 97 American Physical Society, 2006, pp. 090502 DOI: 10.1103/PhysRevLett.97.090502
  * [74] Joseph Fitzsimons, Li Xiao, Simon C. Benjamin and Jonathan A. Jones “Quantum Information Processing with Delocalized Qubits under Global Control” In _Phys. Rev. Lett._ 99 American Physical Society, 2007, pp. 030501 DOI: 10.1103/PhysRevLett.99.030501
  * [75] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf and Jens Eisert “Architectures for Quantum Simulation Showing a Quantum Speedup” In _Phys. Rev. X_ 8 American Physical Society, 2018, pp. 021010 DOI: 10.1103/PhysRevX.8.021010
  * [76] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz and Jens Eisert “Anticoncentration theorems for schemes showing a quantum speedup” In _Quantum_ 2 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2018, pp. 65 DOI: 10.22331/q-2018-05-22-65
  * [77] B. Schumacher and R. F. Werner “Reversible quantum cellular automata”, 2004 URL: https://arxiv.org/abs/quant-ph/0405174
  * [78] Dirk-M. Schlingemann, Holger Vogts and Reinhard F. Werner “On the structure of Clifford quantum cellular automata” In _J. Math. Phys._ 49.11, 2008, pp. 112104 DOI: 10.1063/1.3005565
  * [79] Johannes Gütschow, Sonja Uphoff, Reinhard F. Werner and Zoltan Zimboras “Time asymptotics and entanglement generation of Clifford quantum cellular automata” In _J. Math. Phys._ 51.1, 2010, pp. 015203 DOI: 10.1063/1.3278513
  * [80] J Ignacio Cirac, David Perez-Garcia, Norbert Schuch and Frank Verstraete “Matrix product unitaries: structure, symmetries, and topological invariants” In _J. Stat. Mech._ 2017.8 IOP Publishing, 2017, pp. 083105 DOI: 10.1088/1742-5468/aa7e55
  * [81] Daniel Gottesman “Fault-Tolerant Quantum Computation with Higher-Dimensional Systems” In _Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications_ Springer, 1998 DOI: 10.1007/3-540-49208-9˙27
  * [82] Juan Bermejo-Vega and Maarten Van Den Nest “Classical Simulations of Abelian-group Normalizer Circuits with Intermediate Measurements” In _Quant. Inf. Comp._ 14.3-4 Paramus, NJ: Rinton Press, Incorporated, 2014, pp. 181–216 DOI: 10.26421/QIC14.3-4
  * [83] Atul Mantri, Tommaso F. Demarie and Joseph F. Fitzsimons “Universality of quantum computation with cluster states and (X, Y)-plane measurements” In _Scientific Reports_ 7 The Author(s) SN -, 2017, pp. 42861 DOI: 10.1038/srep42861
  * [84] D. Gross, V. Nesme, H. Vogts and R. F. Werner “Index Theory of One Dimensional Quantum Walks and Cellular Automata” In _Commun. Math. Phys._ 310.2, 2012, pp. 419–454 DOI: 10.1007/s00220-012-1423-1
  * [85] F. Verstraete, V. Murg and J.I. Cirac “Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems” In _Adv. Phys._ 57.2 Taylor & Francis, 2008, pp. 143–224 DOI: 10.1080/14789940801912366
  * [86] Ian Affleck, Tom Kennedy, Elliott H. Lieb and Hal Tasaki “Rigorous results on valence-bond ground states in antiferromagnets” In _Phys. Rev. Lett._ 59 American Physical Society, 1987, pp. 799–802 DOI: 10.1103/PhysRevLett.59.799
  * [87] D. Perez-Garcia, F. Verstraete, M. M. Wolf and J. I. Cirac “Matrix Product State Representations” In _Quantum Info. Comput._ 7.5 Paramus, NJ: Rinton Press, Incorporated, 2007, pp. 401–430 URL: http://dl.acm.org/citation.cfm?id=2011832.2011833
  * [88] Norbert Schuch, Michael M. Wolf, Frank Verstraete and J. Ignacio Cirac “Entropy Scaling and Simulability by Matrix Product States” In _Phys. Rev. Lett._ 100 American Physical Society, 2008, pp. 030504 DOI: 10.1103/PhysRevLett.100.030504
  * [89] F. Verstraete and J. I. Cirac “Matrix product states represent ground states faithfully” In _Phys. Rev. B_ 73 American Physical Society, 2006, pp. 094423 DOI: 10.1103/PhysRevB.73.094423
  * [90] David Sauerwein, Andras Molnar, J. Ignacio Cirac and Barbara Kraus “Matrix Product States: Entanglement, symmetries, and state transformations”, 2019 URL: https://arxiv.org/abs/1901.07448
  * [91] Daniel Gottesman “Stabilizer codes and quantum error correction”, 1997 URL: https://arxiv.org/abs/quant-ph/9705052
  * [92] M. Hein, J. Eisert and H. J. Briegel “Multiparty entanglement in graph states” In _Phys. Rev. A_ 69 American Physical Society, 2004, pp. 062311 DOI: 10.1103/PhysRevA.69.062311
  * [93] D. Pérez-García, M. M. Wolf, M. Sanz, F. Verstraete and J. I. Cirac “String Order and Symmetries in Quantum Spin Lattices” In _Phys. Rev. Lett._ 100 American Physical Society, 2008, pp. 167202 DOI: 10.1103/PhysRevLett.100.167202
  * [94] Iman Marvian “Symmetry-protected topological entanglement” In _Phys. Rev. B_ 95 American Physical Society, 2017, pp. 045111 DOI: 10.1103/PhysRevB.95.045111
  * [95] I˙A G Berkovich and EM Zhmud “Characters of finite groups” American Mathematical Soc., 1998
  * [96] Andras Molnar, José Garre-Rubio, David Pérez-García, Norbert Schuch and J Ignacio Cirac “Normal projected entangled pair states generating the same state” In _New Journal of Physics_ 20.11 IOP Publishing, 2018, pp. 113017 DOI: 10.1088/1367-2630/aae9fa
  * [97] Xiao-Gang Wen “Colloquium: Zoo of quantum-topological phases of matter” In _Rev. Mod. Phys._ 89 American Physical Society, 2017, pp. 041004 DOI: 10.1103/RevModPhys.89.041004
  * [98] Bruno Nachtergaele “The spectral gap for some spin chains with discrete symmetry breaking” In _Communications in Mathematical Physics_ 175.3, 1996, pp. 565–606 DOI: 10.1007/BF02099509
  * [99] A. S. Darmawan and S. D. Bartlett “Graph states as ground states of two-body frustration-free Hamiltonians” In _New J. Phys._ 16, 2014, pp. 073013 DOI: 10.1088/1367-2630/16/7/073013
  * [100] Ruben Verresen, Roderich Moessner and Frank Pollmann “One-dimensional symmetry protected topological phases and their transitions” In _Phys. Rev. B_ 96 American Physical Society, 2017, pp. 165124 DOI: 10.1103/PhysRevB.96.165124
  * [101] D. Gross and J. Eisert “Novel Schemes for Measurement-Based Quantum Computation” In _Phys. Rev. Lett._ 98 American Physical Society, 2007, pp. 220503 DOI: 10.1103/PhysRevLett.98.220503
  * [102] Adriano Barenco et al. “Elementary gates for quantum computation” In _Phys. Rev. A_ 52 American Physical Society, 1995, pp. 3457–3467 DOI: 10.1103/PhysRevA.52.3457
  * [103] David Deutsch, Adriano Barenco and Artur Ekert “Universality in quantum computation” In _Proc. R. Soc. London A_ 449.1937 The Royal Society, 1995, pp. 669–677 DOI: 10.1098/rspa.1995.0065
  * [104] Michael J. Bremner et al. “Practical Scheme for Quantum Computation with Any Two-Qubit Entangling Gate” In _Phys. Rev. Lett._ 89 American Physical Society, 2002, pp. 247902 DOI: 10.1103/PhysRevLett.89.247902
  * [105] Mariami Gachechiladze, Otfried Gühne and Akimasa Miyake “Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states” In _Phys. Rev. A_ 99 American Physical Society, 2019, pp. 052304 DOI: 10.1103/PhysRevA.99.052304
  * [106] R. Raussendorf, J. Harrington and K. Goyal “A fault-tolerant one-way quantum computer” In _Annals of Physics_ 321.9, 2006, pp. 2242 –2270 DOI: 10.1016/j.aop.2006.01.012
  * [107] R Raussendorf, J Harrington and K Goyal “Topological fault-tolerance in cluster state quantum computation” In _New Journal of Physics_ 9.6 IOP Publishing, 2007, pp. 199–199 DOI: 10.1088/1367-2630/9/6/199
  * [108] Burton Voorhees “A note on injectivity of additive cellular automata” In _Complex Systems_ 8.3 [Champaign, IL, USA: Complex Systems Publications, Inc., c1987-, 1994, pp. 151–160