# Exact Quantum Algorithms for Quantum Phase Recognition:
Renormalization Group and Error Correction

Ethan Lake  Department of Physics, Massachusetts Institute of Technology,
Massachusetts Institute of Technology, Cambridge, MA 02139, USA  Shankar
Balasubramanian  Department of Physics, Massachusetts Institute of Technology,
Massachusetts Institute of Technology, Cambridge, MA 02139, USA  Center for
Theoretical Physics, Massachusetts Institute of Technology, Massachusetts
Institute of Technology, Cambridge, MA 02139, USA  Soonwon Choi  Department of
Physics, Massachusetts Institute of Technology, Massachusetts Institute of
Technology, Cambridge, MA 02139, USA  Center for Theoretical Physics,
Massachusetts Institute of Technology, Massachusetts Institute of Technology,
Cambridge, MA 02139, USA

###### Abstract

We explore the relationship between renormalization group (RG) flow and error
correction by constructing quantum algorithms that exactly recognize 1D
symmetry-protected topological (SPT) phases protected by finite internal
Abelian symmetries. For each SPT phase, our algorithm runs a quantum circuit
which emulates RG flow: an arbitrary input ground state wavefunction in the
phase is mapped to a unique minimally-entangled reference state, thereby
allowing for efficient phase identification. This construction is enabled by
viewing a generic input state in the phase as a collection of coherent
‘errors’ applied to the reference state, and engineering a quantum circuit to
efficiently detect and correct such errors. Importantly, the error correction
threshold is proven to coincide exactly with the phase boundary. We discuss
the implications of our results in the context of condensed matter physics,
machine learning, and near-term quantum algorithms.

††preprint: MIT-CTP/5498 Figure 1:  Phase recognition and RG flow. a. A
schematic of a phase diagram drawn as a function of two arbitrary parameters
$\lambda_{1,2}$. Our goal is to determine whether or not a state
$|\psi\rangle$ drawn from the phase diagram belongs to a given target phase,
e.g. $\mathsf{SPT}_{2}$ above. Each $|\psi\rangle$ can be written as a finite-
depth symmetric quantum circuit $\mathcal{U}$ acting on a universal state
$|\Psi\rangle$, which serves as the representative wavefunction for the target
phase. We design a quantum circuit $\mathcal{Q}$ which ‘undoes’ the action of
$\mathcal{U}$ for all $|\psi\rangle$ in the target phase, by inducing an RG
flow from $|\psi\rangle$ to $|\Psi\rangle\otimes|\phi_{an}\rangle$, where
$|\Psi\rangle$ is an RG fixed-point reference state, and $|\phi_{an}\rangle$
encodes the non-universal correlations in $|\psi\rangle$. b. $\mathcal{Q}$ is
built from a hierarchical array of unitary operators $\mathcal{C}$, chained
together in a way reminiscent of MERA. Each $\mathcal{C}$ acts on three sites:
the center output leg of $\mathcal{C}$ is a ‘renormalized’ degree of freedom
that is passed on to the next layer of the circuit, while the remaining
‘ancilla’ legs store the non-universal information in $|\psi\rangle$, and do
not participate in subsequent layers. This divides the output of each layer of
$\mathcal{Q}$ into two subspaces: renormalized legs $\mathcal{H}_{re}$ on
which $\mathcal{Q}$ imprints the result of the phase identification algorithm,
and ancilla legs $\mathcal{H}_{an}$, which contain the data that distinguishes
different wavefunctions in the target phase.

##  I Introduction

The renormalization group (RG) is one of the most important concepts to arise
in theoretical physics over the past century [1, 2, 3, 4]. Given a microscopic
description of a many-body system, the framework of RG provides a systematic
way of extracting the universal features capturing the system’s low-energy
physics. RG is an indispensable tool in condensed matter physics, where it is
used to classify phases of matter.

It is interesting to note that there is an important concept in information
theory which shares many parallels with RG, namely that of error correction
(EC). Writ large, EC is a class of techniques developed to protect information
(both classical and quantum) from the effects of noise. The key idea of EC is
to hide a small amount of important logical information redundantly in a
larger number of physical degrees of freedom, and it shares with RG the
ability to separate universal information from unimportant details. Due to
this conceptual similarity, there have been several works drawing connections
between RG and EC from a variety of perspectives, ranging from the theory of
quantum channels to the physics of black holes [5, 6, 7, 8, 9, 10, 11, 12, 13,
14]. However, these connections are often heuristic, based on empirical
findings, or else appear in highly formalized settings.

In this work, we establish an explicit connection between RG and EC by
presenting a class of quantum circuit algorithms that solve quantum phase
recognition (QPR) problems. Given a ground state wavefunction $|\psi\rangle$
and a phase of matter $\mathsf{P}$, the QPR problem asks whether or not
$|\psi\rangle$ belongs to $\mathsf{P}$. Our quantum circuits efficiently solve
this problem for a large class of gapped 1D symmetry-protected topological
(SPT) and symmetry-breaking phases. We do this by implementing a simple form
of error correction in a hierarchical multi-scale way, in a manner which
emulates RG flow (Fig. 1a). We show that the convergence of this RG flow
coincides exactly with the phase boundary of $\mathsf{P}$, implying that our
algorithm faithfully recognizes input wavefunctions even very close to phase
boundaries. Our circuit is built from 3-local gates with a depth of at most
$O(\log(L))$, and has a substantially smaller sample complexity compared to
more conventional approaches that directly measure order parameters, making it
a practical solution for near-term quantum hardware.

Our RG quantum circuits are inspired by the quantum convolutional neural
network (QCNN) architecture introduced in [13] and experimentally demonstrated
in [15], and have some conceptual similarities with the measurement-based
approach of Refs. [16, 17]. For our purposes, a QCNN is a unitary circuit
$\mathcal{Q}$ built from layers of local unitaries chained together in a
hierarchical fashion, similar to the multiscale entanglement renormalization
ansatz (MERA) [18, 19] and tree tensor networks. The hierarchical nature of
$\mathcal{Q}$ originates from an iterative filtering of the Hilbert space
which occurs at each layer of the circuit. At a given layer, $\mathcal{Q}$
effectively separates the system’s Hilbert space into two subspaces,
$\mathcal{H}_{re}$ and $\mathcal{H}_{an}$. The renormalized subspace
$\mathcal{H}_{re}$ contains error-corrected degrees of freedom that are
further renormalized in subsequent layers, while the ancilla subspace
$\mathcal{H}_{an}$ stores detailed microscopic information about the detected
errors, and the degrees of freedom therein do not participate in further
layers (Fig. 1b).

The nontrivial task we address in this paper is to design a single universal
circuit $\mathcal{Q}$ that performs phase recognition on all input states
$|\psi\rangle$. We accomplish this by addressing three challenges: (i)
constructing a local EC protocol that isolates non-universal information
present in $|\psi\rangle$ and deposits it in $\mathcal{H}_{an}$, (ii) ensuring
any input state in $\mathsf{P}$ flows under our circuit to a unique fixed
point $|\Psi_{\mathsf{P}}\rangle$, while simultaneously ensuring that any
state outside of $\mathsf{P}$ does not flow to $|\Psi_{\mathsf{P}}\rangle$,
and (iii) efficiently performing phase recognition given the converged fixed
point wavefunction. As we show, these desiderata can be all satisfied by a
simple analytic construction that does not require any numerical optimization
or training.

We emphasize that in the scenario under consideration, the input to the QPR
problem is a quantum wavefunction $|\psi\rangle$ — which may be handed to us
from a physical experiment — rather than a tensor network or other efficient
classical description thereof. This means that we are not allowed to perform
any nonlinear data processing that requires a classical description of an
input state, such as probing the state’s entanglement structure, or performing
tensor-network renormalization [20, 21, 22, 23, 24]. While a classical
description can always be obtained using quantum state tomography, such an
approach will generically require a large sample complexity, and is
conceptually distinct from the RG-inspired treatment we propose.

##  II Recognizing 1D Symmetry-Protected Topological phases

###  II.1 Overall strategy

Before presenting technical results, we briefly review the definition of
gapped phases in 1D, establish notation, and summarize the overall strategy of
our approach.

Two gapped local Hamiltonians are said to be in the same phase if and only if
their ground states $|\psi\rangle$ and $|\psi^{\prime}\rangle$ are related by
a constant-depth local circuit $\mathcal{U}$ satisfying
$|\psi^{\prime}\rangle=\mathcal{U}|\psi\rangle$ up to negligible corrections
[25]. Each gapped phase $\mathsf{P}$ can be thus defined as an equivalence
class with a representative element $|\Psi_{\mathsf{P}}\rangle$, where all
other ground states in $\mathsf{P}$ can be written as
$|\psi\rangle=\mathcal{U}_{\psi}|\Psi_{\mathsf{P}}\rangle$ for some constant-
depth circuit $\mathcal{U}_{\psi}$ that depends on the microscopic details
contained in $|\psi\rangle$. Here we focus on a class of Hamiltonians
possessing an internal unitary Abelian symmetry $G$, which is unbroken in
their ground states 111A similar approach is possible for cases in which $G$
is spontaneously broken; see App. G for the details.. In this restricted
setting, symmetric local circuits similarly define distinct gapped phases of
matter, called symmetry-protected topological (SPT) phases [26, 27, 28, 29].

The classification of SPT phases in 1D has by now been fully worked out, and
can be understood from the entanglement structure of the ground state
wavefunction. Consider acting with a symmetry transformation on some subregion
$A$. In non-trivial SPT phases, the wavefunction remains unchanged on the
interior of $A$, but the quantum correlations between $A$ and its complement
become ‘twisted’ near the boundaries of $A$, creating a pair of excitations
that cannot be eliminated locally in a symmetry-preserving way. Each of these
excitations individually transform under a projective representation
$V^{(\omega)}_{g}$ of $G$. While $V^{(\omega)}_{g}$ is in general not a linear
representation of $G$, the combined symmetry action on both excitations, i.e.
$V^{(\omega)*}_{g}\otimes V^{(\omega)}_{g}$, is always a linear
representation. Thus, the excitation associated with $V^{(\omega)}_{g}$ can be
loosely thought of as carrying a ‘fractionalized’ symmetry charge. The
distinct choices of $V^{(\omega)}_{g}$ are determined by algebraic objects
$\omega$ known as second cohomology classes of $G$, and these in turn
enumerate the distinct SPT phases, which we denote by $\mathsf{SPT}_{\omega}$.

Given a symmetry $G$ and a target phase $\mathsf{SPT}_{\omega}$, we construct
our phase recognition algorithm in three steps:

Step 1: we choose a specific reference state $|\Psi_{\omega}\rangle$ for
$\mathsf{SPT}_{\omega}$. This reference state can be constructed directly
using the matrices $V^{(\omega)}_{g}$ and satisfies a number of desired
conditions, to be elaborated on below.

Step 2: we identify a set of indicator observables
$\mathcal{S}^{(\omega)}_{g}$ that exactly recognize the desired reference
state $|\Psi_{\omega}\rangle$, while rejecting reference states for other
phases:

${\langle\Psi_{\omega}}|\mathcal{S}^{(\omega^{\prime})}_{g}|\Psi_{\omega}\rangle=\delta_{\omega,\omega^{\prime}}.$
(1)

In the present setting, the indicator observables can be chosen to be an
appropriate set of string order parameters [21].

Step 3: we construct a hierarchical unitary circuit $\mathcal{Q}_{\omega}$
(Fig. 1b) such that after a sufficiently large number of layers, applying
$\mathcal{Q}_{\omega}$ to any input state in the target phase
$|\psi\rangle\in\mathsf{SPT}_{\omega}$ yields
$|\Psi_{\omega}\rangle\otimes|\phi_{an}\rangle\in\mathcal{H}_{re}\otimes\mathcal{H}_{an},$
where $|\phi_{an}\rangle$ stores the non-universal information present in
$|\psi\rangle$. In essence, the role of $\mathcal{Q}_{\omega}$ is to
approximately ‘undo’ the action of the circuit $\mathcal{U}_{\psi}$ appearing
in $|\psi\rangle=\mathcal{U}_{\psi}|\Psi_{\omega}\rangle$, and to do so
without explicit knowledge of $\mathcal{U}_{\psi}$ (Fig. 1a, red arrows). Note
that under our circuit, all such $|\psi\rangle\in\mathsf{SPT}_{\omega}$ flow
to the fixed point $|\Psi_{\omega}\rangle$ without violating unitarity: this
is made possible by the presence of $\mathcal{H}_{an}$, which serves as a bath
that stores all non-universal information about the input state. At the same
time, we design $\mathcal{Q}_{\omega}$ such that for all input states in
distinct phases
$|\psi_{\omega^{\prime}}\rangle\in\mathsf{SPT}_{\omega^{\prime}}$ with
$\omega^{\prime}\neq\omega$, the output state on $\mathcal{H}_{re}$ never
flows to $|\Psi_{\omega}\rangle$, thus preventing ‘false positives’ from
occurring.

Combined together, our goal is to ensure that
$\langle\psi|\mathcal{Q}_{\omega}^{\dagger}(\mathcal{S}^{(\omega)}_{g}\otimes\mathbf{1}_{an})\mathcal{Q}_{\omega}|\psi\rangle$
is asymptotically close to $1$ if $|\psi\rangle\in\mathsf{SPT}_{\omega}$, and
asymptotically close to zero otherwise. If this is achieved, the sharp
difference in the value of the indicator observable in the two cases enables
us to efficiently answer the QPR problem with high confidence, using only a
small number of measurements. In other words, running the circuit
$\mathcal{Q}_{\omega}$ and subsequently measuring $\mathcal{S}^{(\omega)}_{g}$
constitutes an exact quantum algorithm to recognize the phase
$\mathsf{SPT}_{\omega}$, and it does so with low sample complexity.

We should note that one could always simply directly measure the indicator
observables in the input state, without first acting with the circuit
$\mathcal{Q}_{\omega}$. While in principle such an approach will generically
work, the number of measurements required to get sufficiently good statistics
can be very large, especially when input states lie close to phase boundaries
(where the expectation values of $\mathcal{S}^{(\omega)}_{g}$ often become
vanishingly small). Our algorithm (namely the application of the RG circuit
$\mathcal{Q}_{\omega}$) eliminates this problem.

The success of our approach hinges on the construction of
$\mathcal{Q}_{\omega}$, which we perform using ideas inspired by error
correction. Specifically, we take the viewpoint that any input state in
$\mathsf{SPT}_{\omega}$ should be thought of as a collection of coherent
‘errors’ applied to the reference state. The precise types of errors that
arise are identified in Theorem 1 below, which provides the foundation needed
to design $\mathcal{Q}_{\omega}$. Intuitively, our Theorem states that for
ground states of SPT phases, the errors can be represented as collections of
operators that create pairs of (virtual) fractionalized excitations (this
perspective is closely related to the operational viewpoint on topological
phases adopted in Refs. [30, 31]). As a single local error results in a pair
of such excitations, one can leverage this redundancy as a primitive for error
correction. Specifically, by detecting fractionalized excitations supported on
parts of a system, one can identify occurrences of local errors, and correct
for their effects in the remaining system. Our RG circuit
$\mathcal{Q}_{\omega}$ is constructed based on this inuition while still
evolving the wavefunction in a unitary way.

###  II.2 Reference states and indicator observables

Our main technical idea is to utilize tensor network methods to construct both
$|\Psi_{\omega}\rangle$ and $\mathcal{Q}_{\omega}$. For concreteness, let us
consider a periodic 1D chain consisting of $L$ qudits. As inputs to the QPR
problem, we are given the symmetry group $G$, its unitary representation
$R_{g}$, $g\in G$, a target phase $\mathsf{SPT}_{\omega}$, and the phase’s
associated projective representation $V^{(\omega)}_{g}$. To simplify our
presentation, we will focus on a subclass of phases whose projective
representations are maximally non-commutative, meaning that for all $g\neq
e\in G$, $V_{g}^{(\omega)}$ fails to commute with at least one
$V_{h}^{(\omega)}$ [32, 33, 34]. Most familiar SPT phases satisfy this
property (such as the Haldane phase); an example of one which does not is the
nontrivial SPT phase protected by $G=\mathbb{Z}_{4}\times\mathbb{Z}_{2}$ [33].
The generalization of our construction to arbitrary Abelian $G$-SPT phases
requires adding an extra step prior to running our circuit but does not
involve any qualitatively new ideas; the details are given in App. K. Finally,
to simplify notation we will also assume that the local Hilbert space
$\mathcal{H}$ has dimension $\dim(\mathcal{H})=|G|$ and is enumerated by a set
of basis states $|g\rangle,g\in G$. Under these assumptions, $R_{g}$ is always
isomorphic to the tensor product $V^{(\omega)*}_{g}\otimes V^{(\omega)}_{g}$,
which makes the pattern of symmetry fractionalization manifest.

Figure 2:  Diagrammatic representations of the reference state and tensor
identities. a. The reference state $|\Psi_{\omega}\rangle$ can be written as
an infinite MPS formed by contracting tensors $A$ (gray boxes). b. Symmetry
fractionalization: a local action of the symmetry $R_{g}$ ‘pushes through’ the
MPS tensor to become two projective actions at the virtual level. c. Zero
correlation length: the transfer matrix of the reference MPS is a trivial
rank-1 projector, i.e. the MPS is both left- and right-canonical.

A particularly nice choice of reference states $|\Psi_{\omega}\rangle$ can be
written down in a matrix product state (MPS) form as

$|\Psi_{\omega}\rangle=\sum_{\\{g_{i}\\}}\text{Tr}[A^{[g_{1}]}\cdots
A^{[g_{L}]}]|g_{1},\cdots,g_{L}\rangle,$ (2)

where each $g_{i}$ runs over all $|G|$ basis states, and $A^{[g]}$ is a
$\sqrt{|G|}\times\sqrt{|G|}$ matrix which implements the isomorphism between
$R_{g}$ and $V^{(\omega)*}_{g}\otimes V^{(\omega)}_{g}$. $A^{[g]}$ is fully
determined by $R_{g}$ and $V_{g}^{(\omega)}$:

$A^{[g]}=V^{\dagger}_{\sigma(g)},$ (3)

where $\sigma$ is a permutation on the group elements of $G$ defined through
the relation $\langle
h|R_{\sigma(g)}|h\rangle=\text{Tr}[V_{h}V_{g}V_{h}^{\dagger}V_{g}^{\dagger}]/\sqrt{|G|}$
for all $g,h\in G$.

This choice of $A$ has the merit of satisfying two important properties: (i)
zero correlation length:
$\sum_{g}A^{[g]}_{\alpha\beta}(A^{[g]}_{\alpha^{\prime}\beta^{\prime}})^{*}=\delta_{\alpha\alpha^{\prime}}\delta_{\beta\beta^{\prime}}$;
and (ii) symmetry fractionalization:
$\sum_{k}(R_{g})_{hk}A^{[k]}=(V_{g}^{(\omega)})^{\dagger}A^{[h]}V_{g}^{(\omega)}$
as proven in App C. These two identities are illustrated graphically in Fig.
2.

$|\Psi_{\omega}\rangle$ satisfies a number of additional properties that make
it a natural choice for serving as a reference wavefunction. First, the
conditions (i) and (ii) imply that $|\Psi_{\omega}\rangle$ can be understood
as a minimally-entangled fixed-point wavefunction in the sense of Ref. [35].
Second, one can find a frustration-free parent Hamiltonian of
$|\Psi_{\omega}\rangle$ consisting only of mutually commuting nearest
neighboring interactions [28]. Finally, $|\Psi_{\omega}\rangle$ is a
simultaneous eigenstate of a collection of the aforementioned string operators
$\mathcal{S}^{(\omega)}_{g;i\rightarrow j}$, which implement the action of
$R_{g}$ between the sites $i,j$ and perform a projective action of $g$ at
sites $i,j$:

$\mathcal{S}^{(\omega)}_{g;i\rightarrow
j}=S^{R}_{g,i}\otimes\bigotimes_{l=i+1}^{j-1}R_{g,l}\otimes S^{L}_{g,j},$ (4)

where the explicit form of the matrices $S^{L/R}_{g,i}$ — which decorate the
string ends with projective symmetry actions — depends on $\omega$, and can be
found in App. C. This allows us draw a connection with stabilizer quantum
error correcting codes: $|\Psi_{\omega}\rangle$ is the unique logical state
stabilized by the string operators, which therefore serve as a natural choice
of indicator observables. With these choices, the reference states for
distinct SPT phases satisfy the desired selection rule Eq. (1) [21, 36, 37].

Figure 3:  SPT ground states:  Any input state
$|\psi\rangle\in\mathsf{SPT}_{\omega}$ can be written as
$\mathcal{U}|\Psi_{\omega}\rangle$ for a constant-depth symmetric local
circuit $\mathcal{U}$. The action of $\mathcal{U}$ on $|\Psi_{\omega}\rangle$
can be decomposed as a linear combination of local symmetry actions (colored
circles; inset), which we view as ‘errors’ acting on $|\Psi_{\omega}\rangle$.

###  II.3 Constructing the RG circuits

Having determined the representative wavefunction and indicator observables,
we turn to the most non-trivial step in our construction: finding the RG
circuit $\mathcal{Q}_{\omega}$. To do so, we first show that any
$|\psi\rangle\in\mathsf{SPT}_{\omega}$ can be understood as
$|\Psi_{\omega}\rangle$ locally deformed by a collection of ‘errors’, which
take the form of products of local symmetry actions applied at each site (see
Fig. 3):

######  Theorem 1.

A generic ground state wavefunction $|\psi\rangle\in\mathsf{SPT}_{\omega}$ may
be written as

$|\psi\rangle=\sum_{\mathbf{g}\in
G^{L}}C_{\mathbf{g}}R_{\mathbf{g}}|\Psi_{\omega}\rangle,\qquad
R_{\mathbf{g}}\equiv\bigotimes_{i}R_{g_{i}},$ (5)

where the complex coefficients $C_{\mathbf{g}}$ characterize the amplitude for
a collection of errors labeled by the string of group elements
$\mathbf{g}=(g_{1},\dots,g_{L})$ to occur, with the errors being correlated
over a finite distance set by the correlation length $\xi$ of $|\psi\rangle$.

This Theorem strongly constrains the types of errors that our circuits need to
correct, namely only those errors caused by local symmetry operators $R_{g}$.
Since all of the $R_{g}$ commute in our case, the error correction process we
will design will be essentially classical in nature: this is made possible by
the presence of the symmetry $G$, which prevents ‘bit flip’ errors ($i.e.$
those off-diagonal in our choice of basis) from arising.

The proof of this Theorem proceeds by first studying the general structure of
symmetric finite-depth quantum circuits $\mathcal{U}_{\psi}$ and finding an
appropriate basis of operators in which to decompose the action of
$\mathcal{U}_{\psi}$ on $|\Psi_{\omega}\rangle$; the symmetric nature of
$\mathcal{U}_{\psi}$ and the special fixed-point properties of
$|\Psi_{\omega}\rangle$ guarantee that only $R_{\mathbf{g}}$ operators appear
in the resulting decomposition. The precise statement of our Theorem and
details of the full proof can be found in App. D.

Since quantum circuits are linear, we can focus our attention on correcting
each term in the sum Eq. (5) separately. We will also restrict our attention
to distributions of errors which are generic, meaning that there are no fine-
tuned degeneracies among the coefficients $C_{\mathbf{g}}$. Adversarially
chosen wavefunctions for which errors associated with distinct group elements
occur with exactly equal probabilities will be able to fool our RG circuits,
but since such wavefunctions constitute a set of measure zero in the space of
all SPT ground states, we will not be concerned with this issue.

Figure 4:  a. The elementary unitary $\mathcal{C}$ is designed to detect and
correct errors (cyan circles), which it filters out by way of a majority-vote
scheme. $\mathcal{C}$ consists of six MPS tensors chained together in a ring-
like configuration (which detects the errors) together with a control gate EC
(which corrects them). $\mathcal{C}$ is designed such that when it acts on a
region containing three symmetry actions $R_{g,h,k}$, the renormalized output
(middle leg) retains its original MPS form together with a symmetry action
$R_{\mathsf{maj}(g,h,k)}$ of the majority vote, while the ancilla outputs
(left and right legs) become decoupled from the rest of the system. b. The
error detection stage is accomplished in two steps. First, the errors
$R_{g,h,k}$ are fractionalized into projective representations (yellow
circles) using Fig. 2b. In the next step, the zero-correlation length property
is used (Fig. 2c) to decouple the renormalized leg from the ancilla legs. The
renormalized leg incurs an error determined by
$V_{g}^{(\omega){\dagger}}\otimes V_{k}^{(\omega)}$, while the ancilla legs
store the ‘domain wall’ variables $g-h,h-k$ that are used to diagnose the
error.

A circuit $\mathcal{Q}_{\omega}$ which corrects generic errors can in fact
easily be constructed; see Fig. 1b for a sketch of the overall architecture.
Each layer of $\mathcal{Q}_{\omega}$ consists of parallel applications of a
certain 3-qudit unitary gate $\mathcal{C}$ (Fig. 1b, blue boxes).
$\mathcal{C}$ consists of two components, which ‘detect’ and ‘correct’ errors
respectively, as shown in Fig. 4a. The ‘detect’ portion of $\mathcal{C}$ is
constructed by chaining together a ring of six reference-state MPS tensors
$A^{[g]}$. Fig. 4b illustrates diagrammatically how the ring of six $A^{[g]}$
tensors performs error detection. By using the symmetry fractionalization
property of $A^{[g]}$ (Fig. 2b), a trio of errors $R_{g}\otimes R_{h}\otimes
R_{k}$ (cyan circles) can be ‘pushed up’ into the ring, where they split into
pairs of projective representations (yellow circles). Using the zero
correlation length property (Fig.2c), one finds that the left and right output
qudits then become isolated from the central (renormalized) qudit, which
remains entangled with its neighbors. By measuring only the left and right
qudits, one can then determine how to eliminate the errors remaining on the
center leg. Specifically, under the error $R_{g}\otimes R_{h}\otimes R_{k}$,
the action by $\mathcal{C}$ leaves the ancilla legs in a product state
$\approx|g-h\rangle\otimes|h-k\rangle$ determined by the ‘domain wall’
variables $g-h,h-k$, while the state of the renormalized leg incurs an action
by the operator $V^{(\omega){\dagger}}_{g}\otimes V_{k}^{(\omega)}$.

As a simple example, consider the case where $g=h=k$ are all identical. In
this case the action of $R_{g}\otimes R_{h}\otimes R_{k}$ is locally
indistinguishable from that of a global symmetry operation, which should
accordingly not be treated as a local error. Indeed, the action of
$\mathcal{C}$ leaves the ancilla legs in the state
$|0\rangle\otimes|0\rangle$, indicating that no EC needs to be performed. The
renormalized leg on the other hand incurs an action of
$V_{g}^{(\omega){\dagger}}\otimes V^{(\omega)}_{g}$, which by the symmetry
fractionalization property is equivalent to an action by $R_{g}$. This
property in turn implies that our circuit is symmetric, in the sense that a
global symmetry action passes through $\mathcal{C}$ to become a symmetry
action on only $\mathcal{H}_{re}$: $\mathcal{C}R_{g}^{\otimes
3}=(R_{g}\otimes\mathbf{1}_{an})\mathcal{C}$.

Now consider what happens when an error occurs, $i.e.$ when not all of $g,h,k$
are equal. In this case, we correct the error by way of a majority voting
scheme. This is performed by a control gate denoted by the gate marked ‘EC’ in
Fig. 4a. This gate, whose explicit form is given in App. E, performs an action
controlled by the ancilla state $|g-h\rangle\otimes|h-k\rangle$, and results
in the renormalized leg being left in a state acted on by
$R_{\mathsf{maj}(g,h,k)}$, where $\mathsf{maj}(g,h,k)$ is the majority vote of
$g,h,k$ (which we define to equal $h$ in the case of ties).

Taking the system size $L=3^{l}$, a single layer of $\mathcal{C}$ unitaries
consequently act as

$\mathcal{C}^{\otimes
3^{(l-1)}}R_{\mathbf{g}}|\Psi_{\omega}\rangle_{l}=R_{\mathsf{maj}(\mathbf{g})}|\Psi_{\omega}\rangle_{l-1}\otimes|\phi_{an}(\mathbf{g})\rangle,$
(6)

where $|\Psi_{\omega}\rangle_{l}$ denotes the reference state on a system of
size $3^{l}$,
$\mathsf{maj}(\mathbf{g})=(\mathsf{maj}(g_{1},g_{2},g_{3}),\mathsf{maj}(g_{3},g_{4},g_{5}),\dots)$,
and $|\phi_{an}(\mathbf{g})\rangle$ stores information about the errors
detected by $\mathcal{C}^{\otimes 3^{l-1}}$.

###  II.4 Diagnosing convergence of the RG flow

For a given depth $d$, our RG circuit $\mathcal{Q}_{\omega}^{(d)}$ is
constructed by applying $d$ successive layers of $\mathcal{C}$ unitaries to
the renormalized degrees of freedom in a hierarchical fashion, as indicated in
Fig. 1b. Subsequent rounds of majority voting dilute the concentration of
errors present in the renormalized wavefunction, so that the density of errors
decays exponentially when $d\gtrsim\log_{3}(\xi)$, with $\xi$ the correlation
length of $|\psi_{\omega}\rangle$ (more detailed arguments establishing this
will be given below). For sufficiently large $d$ the renormalized wavefunction
will thus converge to one in which no errors occur. In this limit a single
layer of the RG circuit simply disentangles the ancilla qubits from the
renormalized ones, thereby mapping $|\Psi_{\omega}\rangle$ to a smaller copy
of itself, tensored with the trivial product state $|0\cdots 0\rangle$ —
precisely the behavior desired from a fixed-point reference state. On the
other hand, if the input wavefunction $|\psi_{\omega^{\prime}}\rangle$ is not
drawn from $\mathsf{SPT}_{\omega}$, the expectation value of the indicator
observable in the state $\mathcal{Q}_{\omega}|\psi_{\omega^{\prime}}\rangle$
will exactly vanish. This is a simple consequence of the selection rule in Eq.
(1) and the fact that our circuits are symmetric; see App. F for the proof.
Thus, no ‘false positives’ occur, and our circuit faithfully performs phase
recognition for this class of SPT phases.

The convergence of the RG flow can be summarized by saying that
$\mathcal{Q}_{\omega}^{(d)}$ flows any
$|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$ to a copy of the reference
state $|\Psi_{\omega}\rangle$ supported on the renormalized Hilbert space
$\mathcal{H}_{re}^{(d)}$, tensored with a non-universal state on the ancilla
space:

$\mathcal{Q}_{\omega}^{(d)}|\psi_{\omega}\rangle\langle\psi_{\omega}|\mathcal{Q}_{\omega}^{(d){\dagger}}\approx|\Psi_{\omega}\rangle\langle\Psi_{\omega}|\otimes\rho_{an}$
(7)

with the approximation becoming an equality in the limit of large depth $d$.
We will find it helpful to define a renormalized density matrix obtained by
tracing out $\mathcal{H}_{an}$ as

$\rho_{re,\omega}^{(d)}\equiv\text{Tr}_{\mathcal{H}_{an}}[\mathcal{Q}^{(d)}_{\omega}\rho^{(0)}\mathcal{Q}^{(d){\dagger}}_{\omega}],$
(8)

where $\rho^{(0)}$ is the initial density matrix. The convergence of the RG
flow means that
$\rho_{re,\omega}^{(d\rightarrow\infty)}=|\Psi_{\omega}\rangle\langle\Psi_{\omega}|$
if $\rho^{(0)}$ is a ground state in the target SPT phase. The fact that
$\mathcal{Q}_{\omega}^{(d)}$ can be written as a tree tensor network (i.e. as
a tensor product of unitaries supported on blocks of size $3^{d}$) implies
that $\rho_{re,\omega}^{(d)}$ is obtained from $\rho_{re,\omega}^{(d-1)}$
through LOCC, where the ‘local’ in LOCC is defined with respect to the sites
of $\mathcal{H}_{re}^{(d)}$. This means that any mixed-state entanglement
measure (negativity, distillable entanglement, etc.) is monotonically
decreasing with $d$, as entanglement measures monotonically decrease under
LOCC by definition (note that this holds regardless of the input state
$\rho^{(0)}$). This concretely establishes the sense in which our RG flow
successively eliminates non-universal entanglement.

We note in passing that while our focus until now has been on recognizing
ground states, the initial state $\rho^{(0)}$ need not be pure, and our
circuit also recognizes mixed states with well-defined patterns of symmetry
fractionalization. More precisely, $\rho^{(d)}_{re,\omega}$ flows to the fixed
point $|\Psi_{\omega}\rangle\langle\Psi_{\omega}|$ for any input states of the
form

$\rho^{(0)}=\sum_{a,b}c_{a,b}|{\psi_{\omega,a}}\rangle\langle{\psi_{\omega,b}}|,$
(9)

where the $c_{a,b}$ are complex coefficients, and for all $a$,
$|\psi_{\omega,a}\rangle\in\mathsf{SPT}_{\omega}$. This follows as a simple
consequence of Eq. (7).

A more direct approach to diagnose the convergence of the RG flow is to
measure the distribution of errors detected at each layer of the RG circuit.
Let $\mathcal{H}^{(d)}_{an}$ denote the degrees of freedom which become part
of the ancilla space at layer $d$ of the circuit. As in Eq. (8), we define the
density matrix of these degrees of freedom as

$\rho_{an,\omega}^{(d)}=\text{Tr}_{\mathcal{H}\setminus\mathcal{H}^{(d)}_{an}}[\mathcal{Q}^{(d)}_{\omega}\rho^{(0)}\mathcal{Q}^{(d){\dagger}}_{\omega}].$
(10)

If $\rho^{(0)}$ is a ground state in $\mathsf{SPT}_{\omega}$ (or a mixed state
of the form Eq. (9)), then $\rho_{an,\omega}^{(d)}$ will approach the pure
state $|0\cdots 0\rangle\langle 0\cdots 0|$ at large $d$, after the errors
present in $\rho^{(0)}$ have been corrected away. For all other $\rho^{(0)}$,
$\rho_{an,\omega}^{(d)}$ at sufficiently large $d$ will instead be an equal
weight mixture of all $|g\rangle$ at each site. We can quantify this by
defining

$\mathcal{F}^{(d)}\equiv\frac{1}{\log_{|G|}\dim\mathcal{H}_{an}^{(d)}}\sum_{i}\frac{\text{Tr}[\rho_{an}^{(d)}\Pi_{0,i}]-1/|G|}{1-1/|G|},$
(11)

where $\Pi_{0,i}$ is the projector onto the state $|0\rangle$ at site $i$. For
large $d$, $\mathcal{F}^{(d)}$ will approach 1 in the target phase and vanish
outside of it (thus faithfully performing phase recognition),and in a
subsequent section we will demonstrate numerically that this indeed holds.
Note that since $\mathcal{F}^{(d)}$ is obtained from the expectation value of
a single-site operator, it has the advantage of being simpler to measure than
the string operators, which are necessarily supported on multiple sites.
However, unlike for the string operators, there is no selection rule enforcing
$\mathcal{F}^{(d)}$ to exactly vanish outside of the target phase for all $d$.

###  II.5 Convergence of iterated majority vote

We now give an intuitive explanation for why errors are generically quickly
diluted under successive rounds of majority voting. For the purposes of this
discussion we will assume that the errors have finite correlation length and
are distributed in a way which is statistically translation-invariant on long
scales, an assumption which may fail for distributions of errors that break
translation only in thermodynamically large scales ($e.g.$ errors obtained by
applying a symmetry operator on one half of the system).

With this assumption we are able to rigorously prove that the density of
errors is monotonically decreasing with $d$, and provide strong evidence that
the convergence is exponentially fast when $d>\log_{3}(\xi)$. Let
$p_{d}(\mathbf{g})$ be the probability for an error $R_{\mathbf{g}}$ to occur
at depth $d$ of the RG flow. We claim that
$p_{d\rightarrow\infty}(\mathbf{g})=\prod_{i}\delta_{g_{i},g_{*}}$ for some
fixed group element $g_{*}\in G$, which is equivalent to the statement that
the iterative majority vote process converges to a definite ‘winner’ $g_{*}$.

To argue this, we first note that the treelike structure of
$\mathcal{Q}^{(d)}$ means that as long as $3^{d}\gg\xi$, the probability
distribution at depth $d$ approximately factorizes,
$p_{d}(\mathbf{g})\approx\prod_{i}p_{d}(g_{i})$, where $p_{d}(g)$ are the
single-site marginals of $p_{d}(\mathbf{g})$. Intuitively, this can be seen by
a simple geometric argument. After $d$ rounds of majority voting on a given
length-$3^{d}$ string of group elements $\mathbf{g}$, the majority
$\mathsf{maj}^{d}(\mathbf{g})$ will on average not be sensitive to changing a
small ($\ll 3^{d}$) number of the $g_{i}$. Consider then the two-site marginal
distribution $p_{d}(g_{i},g_{i+1})$. If $\xi\ll 3^{d}$, this distribution can
be computed approximately by ignoring the group elements located within a
distance $\xi$ of the joining point between the two depth-$d$ majority-vote
trees used to compute $g_{i},g_{i+1}$. Doing so then leads to the distribution
factorizing as $p_{d}(g_{i},g_{i+1})\approx p_{d}(g_{i})p_{d}(g_{i+1})$, and
other marginals can be shown to factorize by similar arguments. To prove
convergence we can therefore focus on distributions in which errors occur
independently on each site. The proof from this starting point is
straightforward, as it is easy to show that the difference between the largest
and second-largest values of $p_{d}(g)$ is monotonically increasing with $d$,
reaching a value of $1-\varepsilon$ in a number of layers going roughly as
$\log(1/\varepsilon)$.

A more direct proof is possible if one makes an additional (reasonable)
assumption about the three-site marginals $p_{d}(g,h,k)$. Let $g_{1}$
($g_{2}$) be the element with the largest (second-largest) single-site
marginal probability $p_{d}(g)$. Define the function

$f_{d}(g)\equiv\sum_{h\in G}(p_{d}(g,h,g)-p_{d}(h,g,h)).$ (12)

It is then straightforward to show that the difference $\delta_{d}\equiv
p_{d}(g_{1})-p_{d}(g_{2})$ satisfies
$\delta_{d+1}-\delta_{d}=f_{d}(g_{1})-f_{d}(g_{2}).$ Thus if we assume that
$f_{d}(g_{1})>f_{d}(g_{2})$, then $\delta_{d}$ is monotonically increasing
with $d$, implying convergence of the majority vote. This essentially amounts
to assuming that for two configurations of errors with the same number of
domain walls, the one with more instances of $g_{1}$ has higher probability of
occurring (this can be viewed as an assumption that the majority vote is not
‘Gerrymandered’). The full details are given in App. F.

###  II.6 Numerical demonstration and sample complexity

Figure 5:  Expectation value $\langle\mathcal{S}^{(d)}\rangle$ of a length
$L/2$ string operator for the group element $g=(1,0)$, taken in the ground
state of the $\mathbb{Z}_{3}^{2}$ cluster state model Eq. (13) on an $L=162$
length chain and with $\lambda_{2}=0.5$. Different curves indicate different
layer depths $d$, increasing from $d=0$ (lightest) to $d=3$ (darkest). Grey
crosses indicate the correlation length, demonstrating that
$\langle\mathcal{S}^{(d)}\rangle$ becomes a sharper diagnostic of the true
phase boundary as $d$ is increased. Inset: number of samples needed for phase
recognition for $\lambda_{1}=0.4$ taken near the transition, plotted on a
semi-log scale. The solid line is a fit to $\\#\,{\rm samples}\propto
e^{-1.76d}$.

To assess the performance of our algorithm, we numerically implement our RG
circuits by using them to perform QPR on ground states of a $\mathbb{Z}_{N}$
cluster state Hamiltonian [38], perturbed by onsite and nearest-neighbor
longitudinal fields with strengths $\lambda_{1},\lambda_{2}$:

$H_{\omega}=-\sum_{g\in\mathbb{Z}_{N};i}\left(Z_{i}^{-s_{i}\omega
g}X^{g}_{i+1}Z_{i+2}^{s_{i}\omega
g}+\lambda_{1}X_{i}^{g}+\lambda_{2}X^{g}_{i}X^{g}_{i+1}\right),$ (13)

where $Z=\sum_{g}e^{{2\pi}ig/N}|g\rangle\langle
g|,X=\sum_{g}|{g+1}\rangle\langle{g}|$ are the usual $\mathbb{Z}_{N}$ clock
and shift matrices, $s_{i}\equiv(-1)^{i}$, and $\omega\in\mathbb{Z}_{N}$
labels the different SPT phases protected by the symmetry group
$G=\mathbb{Z}_{N}^{2}$. For large $\lambda_{1,2}$ the ground state is in the
trivial phase, while for small field strengths it is in a nontrivial SPT
phase.

Figure 6:  a. Error densities for the same ground states and parameter values
as considered in Fig. 5. $\mathcal{F}^{(d)}$ denotes the expectation value Eq.
(11) of the projector onto the error-free subspace of the ancilla qudits at
depth $d$ of the circuit, which equals unity at the fixed point
$|\Psi_{\omega}\rangle$ (where no errors occur), and vanishes in the maximally
mixed state (where all errors occur with equal probability). b. As in the left
panel, but with a single disorder realization of the depth-1 circuit Eq. (14)
applied to the ground state.

Taking $N=3,\omega=1$ as an example, we numerically solve for the ground state
using DMRG with bond dimension $\chi=200$, to which we directly apply our RG
circuit. At each depth $d$ we measure the string operator
$\mathcal{S}^{(d)}_{(1,0);i\rightarrow j}$, where $|i-j|$ is a third of the
coarse-grained system size. The results are shown in Fig. 5, where we see that
our circuit does a good job of correctly identifying the phase boundary as $d$
is increased. In the inset we plot the sample complexity, viz. the number of
measurements of the string operator needed to determine the phase with high
confidence (see App. J for the precise statement). As a function of $d$ we see
an exponential improvement in the sample complexity as compared to directly
measuring the string operators in the ground state ($d=0$), which is
consistent with analytical predictions.

As discussed above near Eq. (10), an alternate way of diagnosing convergence
of our RG flow is to measure the distribution of errors detected at each step.
In our numerics we measure the error density by directly calculating the
quantity $\mathcal{F}^{(d)}$ defined in Eq. 11, which we show in Fig. 6a for
the same ground states as in Fig. 5. $\mathcal{F}^{(d)}$ is seen to approach a
step function with increasing $d$, confirming that $\mathcal{F}^{(d)}$
provides a good indicator function for the target phase.

Our approach also does well at handling error distributions with larger error
densities and spatial disorder. More specifically, we note that the ground
states of Eq. (13) have rather simple error distributions, with the error
density being low everywhere except near the phase boundary. In contrast, we
can also consider states with a larger density of errors, with one simple way
of producing such states being to act on ground states of Eq. (13) with a
random short-depth symmetric circuit. To analyze this numerically, we choose
the simple circuit

$\mathcal{U}=\bigotimes_{i=1}^{L}{\rm
diag}(e^{i\phi_{i}},\,e^{i\phi_{i}},\,e^{-2i\phi_{i}}),$ (14)

where the angles $\phi_{i}$ at each site are drawn uniformly from $[0,{2\pi})$
(recall that we are working in a basis which diagonalizes the onsite symmetry
action). The result for a single disorder realization is shown in Fig. 6b. We
see that the additional random errors significantly reduce $\mathcal{F}^{(d)}$
in the SPT phase, but that the error density decreases quickly with increasing
layer depth, demonstrating the robustness of our phase recognition algorithm.

###  II.7 Universal multiscale string operators

As discussed above, the string operators serve as a set of ‘indicator
observables’ that distinguish the different reference states
$|\Psi_{\omega}\rangle$. The convergence of our RG circuits can thus be
summarized in the equation

$\langle\psi_{\omega}|\mathcal{Q}_{\omega}^{(d){\dagger}}(\mathcal{S}^{(\omega^{\prime})}_{g;i\rightarrow
j}\otimes\mathbf{1}_{an})\mathcal{Q}_{\omega}^{(d)}|\psi_{\omega}\rangle\xrightarrow{d\gg\log_{3}(\xi)}\delta_{\omega,\omega^{\prime}}$
(15)

for any $|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$ (which we saw borne
out in the numerics of Fig. 5). In the ‘Schrödinger’ picture, Eq. (15)
measures the expectation value of a bare string operator
$\mathcal{S}^{(\omega^{\prime})}_{g;i\rightarrow j}$ in the renormalized state
$\mathcal{Q}_{\omega}^{(d)}|\psi_{\omega}\rangle$. It is however also helpful
to change to the ‘Heisenberg’ picture, where Eq. (15) can be viewed as the
expectation value of a renormalized string operator with respect in the
original ‘UV’ state $|\psi_{\omega}\rangle$ [14]. This is formalized by
defining the mutliscale string operator [13] (MSO) as

$\widetilde{\mathcal{S}}^{(\omega,d)}_{g;i\rightarrow
j}\equiv\mathcal{Q}_{\omega}^{(d){\dagger}}(\mathcal{S}_{g;i\rightarrow
j}^{(\omega)}\otimes\mathbf{1}_{an})\mathcal{Q}_{\omega}^{(d)}.$ (16)

Owing to the hierarchical structure of $\mathcal{Q}^{(d)}$, the MSO is a
linear combination of a number of terms that grows doubly-exponentially in
$d$, with each term given by a product of elementary string operators [13, 14]
(see App. E for a recursion relation that explicitly constructs the MSOs).

Since we have shown that our RG circuit accurately performs phase
identification, expectation values of the MSOs serve as a sharp diagnostic of
the target SPT phase. That this is possible is rather remarkable, as the MSOs
are constructed solely from the algebraic data that characterize the target
SPT phase (a priori, one might expect that the renormalized string operators
would depend on microscopic details of the specific state to be recognized).
This construction provides a physically transparent way of revealing the
universal order present in SPT ground states, since the MSOs implement
(arbitrarily accurate) projections onto the space of all ground state
wavefunctions in a target phase. This approach is complementary to other
protocols which disentangle the SPT [36], directly measure the projective
symmetry action using swap gates [39], or use symmetry twists to create MSO-
like operators in theories with $U(1)$ symmetry [40, 41].

##  III Discussion and implications

The goal of this work has been to advocate that renormalization group (RG)
flow and error correction (EC) should really be viewed as two sides of the
same coin.222Note that we are not trying to protect any logical information
beyond that required to recognize a given phase. Whether or not we can $e.g.$
guarantee that the logical information contained in the degenerate SPT edge
modes can always be preserved throughout the RG flow is a question we leave to
the future. We arrived at this perspective by implementing RG flow in a
unitary way, via the action of a certain class of quantum circuits. This is
rather distinct from conventional approaches to RG, which is usually viewed as
an irreversible flow performed on Hamiltonians and Lagrangians. Nevertheless,
the mechanics of our construction is quite similar in spirit to the original
block spin approach of Kadanoff [1], which in some sense we simply embed into
a larger operational framework that allows unitarity to be preserved and
enables us to identify phases that lack local order parameters.

Since we are interested in making rigorous statements, we have restricted our
attention to 1D gapped phases of matter with Abelian internal symmetries,
which can be analyzed using powerful group-theoretic and tensor network
methods. In the main text we have focused on SPT phases, but as shown in App.
G a similar treatment is also possible for the (simpler) case of symmetry-
breaking orders. Our belief is however that the general connection between RG
and EC extends well beyond these examples, bringing with it a diverse array of
implications across multiple fields of physics. We describe some of these
implications and discuss future directions below.

Quantum matter: From the quantum matter perspective, the most important
implication of our work is the existence of the multiscale string operators
(MSOs): operators that recognize all wavefunctions belonging to the same phase
(see Sec. II.7). Another consequence of our work stems from our circuit’s
ability to function as a universal variational ansatz for ground state
wavefunctions. The basic idea is to turn EC on its head, by running our RG
circuit $\mathcal{Q}$ ‘in reverse’. We do this by starting from a variational
family of errors—parametrized by a wavefunction $|\phi_{an}\rangle$—which we
then encode into a variational wavefunction by acting with
$\mathcal{Q}^{\dagger}$ on $|\Psi\rangle\otimes|\phi_{an}\rangle$. This
performs a reversed RG flow from the IR to the UV, and generates a state in
the target SPT phase whose pattern of local entanglement is controlled by the
choice of $|\phi_{an}\rangle$. Crucially, our results imply that choices of
$|\phi_{an}\rangle$ are in one-to-one correspondence with ground state
wavefunctions in the target phase (up to a set of measure zero). The
hierarchical construction of this encoding map shares many parallels with that
of the Multiscale Entanglement Renormalizaton Ansatz (MERA) [18], but is
distinguished by having features native to the target phase ‘hard-coded’ into
the ansatz. The EC machinery has the added benefit of explicitly separating
out the universal degrees of freedom $(|\Psi\rangle)$ from the non-universal
ones ($|\phi_{an}\rangle$).

Quantum simulation: From a practical point of view, our circuits provide a way
of performing phase recognition even very close to critical points, where
signals from conventional order parameters are often smeared out due to strong
quantum fluctuations (or long correlation lengths). This problem is
particularly acute in near-term quantum simulators, which typically have
rather modest system sizes [15]. Furthermore, our protocol for performing RG
involves applying a circuit whose depth is at most logarithmic in the system
size, making it suitable for implementation on near-term quantum devices.

As discussed in Sec. II.7, our phase recognition can be effected in practice
in two different ways: a) first acting on the input state $|\psi\rangle$ with
a $d$-layer RG circuit $\mathcal{Q}_{\omega}^{(d)}$ and then measuring the
expectation value of the elementary string operator
$\mathcal{S}_{g}^{(\omega)}$, or b) directly measuring the expectation value
$\langle\psi|\widetilde{\mathcal{S}}^{(\omega,d)}_{g}|\psi\rangle$ of the MSO
in the input state. The advantage of b) is that no unitary gates are needed:
the form of the MSOs implies that their expectation values can be
reconstructed from simultaneous measurements of all of the exponentially many
(in $d$) mutually-commuting elementary string operators (each supported only
on two sites). Together with classical post-processing, this allows estimating
the MSOs at arbitrary depth $d$ without applying $\mathcal{Q}_{\omega}^{(d)}$.
This feature enables the immediate implementation of our approach in
experiments, as already done in two different quantum simulation platforms
[15, 14], prior to our rigorous theoretical understanding. On the other hand,
an advantage of approach a) is its robustness against experimental
imperfections that could arise in future digital fault-tolerant quantum
computers. This is due to the exponential decrease with $d$ in the size of
operators that need to be measured, meaning that approach a) is exponentially
less sensitive to final readout errors than approach b). In essence, our
circuit $\mathcal{Q}$ concentrates important and universal information about
the input state onto a small number of output qubits.

Complexity of QPR: A key performance metric for an algorithm solving the QPR
problem is the sample complexity [42], namely the number of copies of a given
state $|\psi\rangle$ needed to confidently decide if $|\psi\rangle$ belongs to
the target phase. Our multiscale string operators (MSOs) take on a value
asymptotically close to unity everywhere in the target phase (and vanish
outside of it), implying that measurements of the string operators performed
after acting with our RG circuits lead to nearly deterministic outcomes, and
correspondingly to low sample complexities for a fixed system size. This low
sample complexity is particularly desirable from the perspective of near-term
quantum simulators, where finite-size effects are often quite large.333Note
that on a system of size $L$, the number of well-separated string operators
with size $\gg\xi$ diverges as $L\rightarrow\infty$, giving a trivial sample
complexity in the thermodynamic limit. Thus this reduction in sample
complexity is only well-defined for finite systems. It would be interesting to
see if one could provide a fundamental lower bound on the sample complexity
needed in this context, and if so, to check whether or not our algorithm
saturates it.

Machine learning: There has recently been a concerted effort to tackle the
phase recognition problem using machine learning (ML) methods [43, 41, 44, 45,
46, 47]. In this context, our MSOs suggest that our circuits may serve as a
good reference point from which to benchmark such heuristic approaches. At the
same time, our circuit provides a good starting point for numerical
optimization schemes in QCNN-based ML approaches [13]. Furthermore, the
existence of MSOs has implications on the rigorous performance guarantee of
classical shadow-based ML approaches to QPR problems. In previous work [41],
the performance guarantee for recognizing SPT phases was limited to the case
of a 1D $\mathbb{Z}_{2}^{2}$ SPT phase with enhanced $O(2)$ symmetry. Our work
extends these results to a broader class of phases: all 1D SPT phases with
Abelian internal symmetries. Relatedly, we also note that while we have
focused on performing phase recognition by measuring expectation values of
observables, our RG circuits may also allow for the efficient extraction of
other universal (potentially non-linear) properties of the quantum phase in
question.

Intrinsic topological phases: A clear next step is to rigorously characterize
circuit architectures that recognize phases with intrinsic topological order
(perhaps in a way which builds on string-net tensor network methods [48, 23,
22, 24] or RG-inspired decoders [49]), with first steps recently being taken
in [14, 50]. Given the recent realization of topologically ordered states in
quantum simulators [51, 52] and measurement-based protocols for preparing
topological orders [53, 54], addressing this question is of immediate
practical importance. Since the local unitary circuits (in the language of EC,
the ‘errors’) which relate different wavefunctions in a topological phase can
be completely generic — as opposed to the symmetric local circuits relevant
for SPT phases — we expect that the EC procedure in this case must be one of
quantum error correction. Whether or not the EC threshold in these phases can
be made to coincide with the phase boundary is an outstanding question for the
future.

More broadly, connections between EC and RG may have implications for the
design of useful RG schemes in contexts very different from those considered
in this paper. While the particular RG scheme we have employed incorporates
spatial coarse-graining, the connection between RG and EC may be deeper than
this, and approaching RG from the perspective of EC may give us fresh insights
into systems for which there is no useful real-space RG scheme, such as
(non)-Fermi liquids [55] and fracton-inspired models with UV/IR mixing [56,
57, 58].

In a different context, it is natural to ask whether the integration of EC
into the MERA framework provides any new lessons for tensor network approaches
to holography [59, 60, 61], or for the role that EC plays in quantum gravity
more generally [8, 9, 10, 11]. This direction seems especially promising given
that the layout of our RG quantum circuits resembles the geometry of
holographic tensor networks and that our elementary MPS tensor $A$ is perfect,
potentially allowing for more general constructions of holographic error
correcting codes [9].

## Acknowledgements

The authors thank Iris Cong, Jeongwan Haah, Iman Marvian, Hannes Pichler,
David Stephen, Ruben Verresen, and Ashvin Vishwanath for helpful discussions,
and are particularly grateful to Iris Cong, Sarang Gopalakrishnan, and Nishad
Maskara for detailed feedback and a careful reading of a draft version. E.L.
was supported by the Fannie and John Hertz Foundation and by NSF grant
DMR-2206305. S.B. was supported by the National Science Foundation Graduate
Research Fellowship under Grant No. 1745302.

## References

  * Kadanoff [1966] L. P. Kadanoff, Physics Physique Fizika 2, 263 (1966).
  * Wilson and Fisher [1972] K. G. Wilson and M. E. Fisher, Physical Review Letters 28, 240 (1972).
  * Wilson [1975] K. G. Wilson, Reviews of modern physics 47, 773 (1975).
  * Gell-Mann and Low [1954] M. Gell-Mann and F. E. Low, Physical Review 95, 1300 (1954).
  * Furuya et al. [2022] K. Furuya, N. Lashkari, and S. Ouseph, Journal of High Energy Physics 2022, 1 (2022).
  * Furuya et al. [2021] K. Furuya, N. Lashkari, and M. Moosa, arXiv preprint arXiv:2112.05099 (2021).
  * Gómez [2021] C. Gómez, Fortschritte der Physik 69, 2000094 (2021).
  * Almheiri et al. [2015] A. Almheiri, X. Dong, and D. Harlow, Journal of High Energy Physics 2015, 1 (2015).
  * Pastawski et al. [2015] F. Pastawski, B. Yoshida, D. Harlow, and J. Preskill, Journal of High Energy Physics 2015, 1 (2015).
  * Kim and Kastoryano [2017] I. H. Kim and M. J. Kastoryano, Journal of High Energy Physics 2017, 1 (2017).
  * Yang et al. [2016] Z. Yang, P. Hayden, and X.-L. Qi, Journal of High Energy Physics 2016, 1 (2016).
  * Chen et al. [2022] L. Chen, H.-C. Zhang, K.-X. Ji, C. Shen, R.-s. Wang, X.-d. Zeng, and L.-Y. Hung, arXiv preprint arXiv:2210.12127 (2022).
  * Cong et al. [2019] I. Cong, S. Choi, and M. D. Lukin, Nature Physics 15, 1273 (2019).
  * Cong et al. [2022] I. Cong, N. Maskara, M. Tran, H. Pichler, G. Semeghini, S. Yelin, S. Choi, and M. Lukin, arXiv preprint arXiv:2209.12428 (2022).
  * Herrmann et al. [2021] J. Herrmann, S. M. Llima, A. Remm, P. Zapletal, N. A. McMahon, C. Scarato, F. Swiadek, C. K. Andersen, C. Hellings, S. Krinner, et al., arXiv preprint arXiv:2109.05909 (2021).
  * Bartlett et al. [2010] S. D. Bartlett, G. K. Brennen, A. Miyake, and J. M. Renes, Physical review letters 105, 110502 (2010).
  * Miller and Miyake [2015] J. Miller and A. Miyake, Physical review letters 114, 120506 (2015).
  * Vidal [2008] G. Vidal, Physical review letters 101, 110501 (2008).
  * Aguado and Vidal [2008] M. Aguado and G. Vidal, Physical review letters 100, 070404 (2008).
  * Pollmann et al. [2010] F. Pollmann, A. M. Turner, E. Berg, and M. Oshikawa, Physical review b 81, 064439 (2010).
  * Pollmann and Turner [2012] F. Pollmann and A. M. Turner, Physical review b 86, 125441 (2012).
  * Gu and Wen [2009] Z.-C. Gu and X.-G. Wen, Physical Review B 80, 155131 (2009).
  * Levin and Nave [2007] M. Levin and C. P. Nave, Physical review letters 99, 120601 (2007).
  * Evenbly and Vidal [2015] G. Evenbly and G. Vidal, Physical review letters 115, 180405 (2015).
  * Albash and Lidar [2018] T. Albash and D. A. Lidar, Reviews of Modern Physics 90, 015002 (2018).
  * Chen et al. [2013] X. Chen, Z.-C. Gu, Z.-X. Liu, and X.-G. Wen, Physical Review B 87, 155114 (2013).
  * Huang et al. [2015] Y. Huang, X. Chen, et al., Physical Review B 91, 195143 (2015).
  * Schuch et al. [2011] N. Schuch, D. Pérez-García, and I. Cirac, Physical review b 84, 165139 (2011).
  * Senthil [2015] T. Senthil, Annu. Rev. Condens. Matter Phys. 6, 299 (2015).
  * Jamadagni and Weimer [2022a] A. Jamadagni and H. Weimer, Physical Review B 106, 085143 (2022a).
  * Jamadagni and Weimer [2022b] A. Jamadagni and H. Weimer, Physical Review B 106, 115133 (2022b).
  * Else et al. [2012] D. V. Else, I. Schwarz, S. D. Bartlett, and A. C. Doherty, Physical review letters 108, 240505 (2012).
  * Stephen [2017] D. T. Stephen, _Computational power of one-dimensional symmetry-protected topological phases_ (2017).
  * Stephen et al. [2017] D. T. Stephen, D.-S. Wang, A. Prakash, T.-C. Wei, and R. Raussendorf, Physical review letters 119, 010504 (2017).
  * Verstraete et al. [2005] F. Verstraete, J. I. Cirac, J. I. Latorre, E. Rico, and M. M. Wolf, Physical review letters 94, 140601 (2005).
  * Else et al. [2013] D. V. Else, S. D. Bartlett, and A. C. Doherty, Physical Review B 88, 085114 (2013).
  * de Groot et al. [2021] C. de Groot, A. Turzillo, and N. Schuch, arXiv preprint arXiv:2112.04483 (2021).
  * Tsui et al. [2015] L. Tsui, H.-C. Jiang, Y.-M. Lu, and D.-H. Lee, Nuclear Physics B 896, 330 (2015).
  * Haegeman et al. [2012] J. Haegeman, D. Pérez-García, I. Cirac, and N. Schuch, Physical review letters 109, 050402 (2012).
  * Tasaki [2018] H. Tasaki, Physical Review Letters 121, 140604 (2018).
  * Huang et al. [2021] H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill, arXiv preprint arXiv:2106.12627 (2021).
  * Haah et al. [2017] J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, IEEE Transactions on Information Theory 63, 5628 (2017).
  * Aaronson [2007] S. Aaronson, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 463, 3089 (2007).
  * Carleo and Troyer [2017] G. Carleo and M. Troyer, Science 355, 602 (2017).
  * Wang [2016] L. Wang, Physical Review B 94, 195105 (2016).
  * Carrasquilla and Melko [2017] J. Carrasquilla and R. G. Melko, Nature Physics 13, 431 (2017).
  * Carleo et al. [2019] G. Carleo, I. Cirac, K. Cranmer, L. Daudet, M. Schuld, N. Tishby, L. Vogt-Maranto, and L. Zdeborová, Reviews of Modern Physics 91, 045002 (2019).
  * Levin and Wen [2005] M. A. Levin and X.-G. Wen, Phys. Rev. B 71, 045110 (2005).
  * Bravyi and Haah [2011] S. Bravyi and J. Haah, arXiv preprint arXiv:1112.3252 (2011).
  * Cian et al. [2022] Z.-P. Cian, M. Hafezi, and M. Barkeshli, arXiv preprint arXiv:2209.14302 (2022).
  * Satzinger et al. [2021] K. Satzinger, Y.-J. Liu, A. Smith, C. Knapp, M. Newman, C. Jones, Z. Chen, C. Quintana, X. Mi, A. Dunsworth, et al., Science 374, 1237 (2021).
  * Semeghini et al. [2021] G. Semeghini, H. Levine, A. Keesling, S. Ebadi, T. T. Wang, D. Bluvstein, R. Verresen, H. Pichler, M. Kalinowski, R. Samajdar, et al., Science 374, 1242 (2021).
  * Verresen et al. [2021] R. Verresen, N. Tantivasadakarn, and A. Vishwanath, arXiv preprint arXiv:2112.03061 (2021).
  * Tantivasadakarn et al. [2022] N. Tantivasadakarn, A. Vishwanath, and R. Verresen, arXiv preprint arXiv:2209.06202 (2022).
  * Shankar [1994] R. Shankar, Reviews of Modern Physics 66, 129 (1994).
  * You and Moessner [2021] Y. You and R. Moessner, arXiv preprint arXiv:2106.07664 (2021).
  * Gorantla et al. [2021] P. Gorantla, H. T. Lam, N. Seiberg, and S.-H. Shao, Physical Review B 104, 235116 (2021).
  * Lake [2022] E. Lake, Physical Review B 105, 075115 (2022).
  * Swingle [2012] B. Swingle, Physical Review D 86, 065007 (2012).
  * Jahn and Eisert [2021] A. Jahn and J. Eisert, Quantum Science and Technology 6, 033002 (2021).
  * Hayden et al. [2016] P. Hayden, S. Nezami, X.-L. Qi, N. Thomas, M. Walter, and Z. Yang, Journal of High Energy Physics 2016, 1 (2016).
  * Raussendorf et al. [2017] R. Raussendorf, D.-S. Wang, A. Prakash, T.-C. Wei, and D. T. Stephen, Physical Review A 96, 012302 (2017).
  * Berkovich and Zhmud_ [1998] I. G. Berkovich and E. Zhmud_, _Characters of finite groups_ , vol. 2 (American Mathematical Soc., 1998).
  * Karpilovsky [1994] G. Karpilovsky, _Group representations_ , vol. 3 (Elsevier, 1994).
  * Brown [2012] K. S. Brown, _Cohomology of groups_ , vol. 87 (Springer Science & Business Media, 2012).
  * Cirac et al. [2021] J. I. Cirac, D. Perez-Garcia, N. Schuch, and F. Verstraete, Reviews of Modern Physics 93, 045003 (2021).
  * Raussendorf et al. [2019] R. Raussendorf, C. Okay, D.-S. Wang, D. T. Stephen, and H. P. Nautrup, Physical review letters 122, 090501 (2019).
  * Friedman et al. [2022] A. J. Friedman, C. Yin, Y. Hong, and A. Lucas, arXiv preprint arXiv:2206.09929 (2022).
  * Perez-Garcia et al. [2006] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, arXiv preprint quant-ph/0608197 (2006).
  * Prakash and Wei [2014] A. Prakash and T.-C. Wei, arXiv preprint arXiv:1410.0974 (2014).

## Guide to appendices

For the reader’s conveniece, we list below a brief description of the
technical appendicies to follow:

  * •

Appendix A: Group theory details, introducing notation.

  * •

Appendix B: Representation theory details for finite Abelian groups $G$.

  * •

Appendix C: MPS techniuqes and construction of the canonical reference states.

  * •

Appendix D: General representation of SPT ground states in terms of ‘errors’
acting on the canonical reference states.

  * •

Appendix E: The details of our circuit architecture.

  * •

Appendix F: Proof that the RG implemented by our RG circuit converges.

  * •

Appendix G: How to construct RG circuits for spontaneous symmetry breaking.

  * •

Appendix H: Error correction with measurements and classical post-processing.

  * •

Appendix I: How to deal with generic $G$-representations.

  * •

Appendix J: Detailed analysis of sample complexity.

  * •

Appendix K: Modified quantum circuits for cohomology classes which are not
maximally non-commutative.

##  Appendix A Mathematical preliminaries

In this appendix, we provide some of the background group theory details used
in this work.

Let $G$ be a finite Abelian group. We will let $R_{g}$ denote the local
symmetry action of $g\in G$, which until App. I we take to be in the regular
representation, acting on a Hilbert space of dimension $|G|$. Explicitly,

$R_{g}=\sum_{h\in G}\chi_{h}(g)|h\rangle\langle h|.$ (17)

Let $V^{(\omega)}_{g}$ be a projective representation of $G$ with factor set
$\omega:G\times G\rightarrow U(1)$, so that

$V^{(\omega)}_{g}V^{(\omega)}_{h}=\omega_{g,h}V^{(\omega)}_{g+h}.$ (18)

For ease of notation, we will omit the dependence of $V_{g}$ on $\omega$ when
there is no cause for confusion.

Since the $V_{g}$ are only defined up to $g$-dependent phases, $\omega_{g,h}$
is equivalent to $\omega_{g,h}\alpha_{g}\alpha_{h}/\alpha_{g+h}$ for some set
of phases $\alpha_{g}$. For all of the cases we will be interested in,
$\omega$ can always be chosen to satisfy

$\omega_{g,h}=\omega_{-g,h}^{*}=\omega_{g,-h}^{*}.$ (19)

We define the function

$\lambda_{\omega}(g,h)\equiv\frac{\omega_{g,h}}{\omega_{h,g}},$ (20)

which determines the group commutators of the $V_{g}$ via

$V_{g}V_{h}=\lambda_{\omega}(g,h)V_{h}V_{g}.$ (21)

Note that $\lambda_{\omega}$ is invariant under transforming $\omega_{g,h}$ by
the phases $\alpha_{g}$, and due to the cocycle condition on $\omega$, it is a
homomorphism in both of its arguments:

$\lambda_{\omega}(g+k,h)=\lambda_{\omega}(g,h)\lambda_{\omega}(k,h),$ (22)

and similarly for $\lambda_{\omega}(g,h+k)$. $\lambda_{\omega}$ furthermore
obeys the identities

$\lambda_{\omega}(g,e)=\lambda_{\omega}(g,-g)=1,\qquad\lambda_{\omega}(g,h)=\lambda_{\omega}^{*}(h,g)=\lambda_{\omega}^{*}(g,-h)=\lambda_{\omega}(-g,-h),$
(23)

from which one sees that Hermitian conjugates commute in the same way:
$V_{g}^{\dagger}V_{h}^{\dagger}=\lambda_{\omega}(g,h)V_{h}^{\dagger}V_{g}^{\dagger}$.

We will also make use of the function

$\varsigma_{g}\equiv\omega(g,g)$ (24)

which can be used to convert between $V_{g}$ and $V_{-g}^{\dagger}$ via

$\varsigma_{g}V_{-g}=V_{g}^{\dagger}.$ (25)

######  Definition 1.

The projective center [37] $C_{\omega}$ is defined to contain all those
elements which are projectively represented by scalars:

$C_{\omega}\equiv\\{g\in G\,:\,\lambda_{\omega}(g,h)=1\,\forall\,h\in G\\}.$
(26)

We furthermore define a maximally non-commutative factor set [36] as one in
which no nontrivial elements are projectively represented by scalars:

######  Definition 2.

A maximally non-commutative factor set is one with trivial projective center,
viz. one for which $C_{\omega}=\\{e\\}$.

For a given factor set, we may construct a homomorphism $\Lambda$ as

$\displaystyle\Lambda_{\omega}$ $\displaystyle:G\rightarrow G^{*}$ (27)
$\displaystyle g$ $\displaystyle\mapsto\lambda_{\omega}(\cdot,g)$

where $G^{*}$ denotes the group of characters. Then by definition,

$C_{\omega}=\ker(\Lambda_{\omega}).$ (28)

Since $\Lambda_{\omega}(g):G\rightarrow U(1)$, it can always be identified
with some nontrivial character of $G$. We will write the map which associates
$g$ to the appropriate character as $\Gamma_{\omega}$, with
$\Gamma_{\omega}(g)$ thus satisfying

$\chi_{h}(\Gamma_{\omega}(g))=\lambda_{\omega}(h,g)\,\,\forall\,\,h\in G.$
(29)

The element $\Gamma_{\omega}(g)$ can be identified explicitly using character
orthogonality as

$|\Gamma_{\omega}(g)\rangle=\int_{k}\chi_{h}^{*}(k)\lambda_{\omega}(h,g)|k\rangle,$
(30)

where $\int_{k}\equiv\frac{1}{|G|}\sum_{k\in G}$.

If $\omega$ is a maximally non-commutative factor set, then $\Lambda_{\omega}$
and $\Gamma_{\omega}$ are injective. Thus since $|G^{*}|=|G|$,
$\Lambda_{\omega}$ and $\Gamma_{\omega}$ are isomorphisms iff $\omega$ is
maximally non-commutative. This means that the knowledge of
$\lambda_{\omega}(g,h)$ for all $h$ is sufficient to uniquely determine the
group element $g$ iff $\omega$ is maximally non-commutative. This property
greatly simplifies the error correcting technology used in the construction of
our RG circuits (and also simplifies the analysis of SPT phases as resource
states for measurement-based quantum computation [32, 62]), and is the reason
why we choose to restrict our attention to maximally non-commutative
cohomology classes throughout most of this work.

We now state some useful math facts that we will not go through the trouble of
proving; proofs can be extracted from [63], [64]:

######  Proposition 1.

The following facts hold:

  * •

Maximally non-Abelian factor sets exist iff $G=G^{\prime}\times G^{\prime}$ is
a square.

  * •

All projective representations with factor set $\omega$ have dimension
$\sqrt{|G|/|C_{\omega}|}$.

  * •

Distinct projective irreps with factor set $\omega$ are enumerated by the
linear characters of the group $C_{\omega}$; there are thus $|C_{\omega}|$
distinct projective irreps. In particular, if $\omega$ is maximally non-
commutative, there is only a single projective irrep up to isomorphism.

One result that we could not find in the literature is the grand orthogonality
theorem for projective representations:

######  Theorem 2 (Schur orthogonality for projective representations).

For $V^{\mu}$ and $V^{\nu}$ any two projective irreps of $G$,

$\int_{g}[(V^{\mu}_{g})^{\dagger}]_{ij}[V^{\nu}_{g}]_{kl}=\frac{1}{\dim(V^{\mu})}\delta_{il}\delta_{jk}\delta_{\mu\nu}.$
(31)

###### Proof.

The proof is straightforward and mimicks the linear case: we construct an
intertwiner with the map

$F_{ij}^{\mu\nu}=\int_{g}(V^{\mu}_{g})^{\dagger}E_{ij}V_{g}^{\nu},$ (32)

which satisfies

$\displaystyle V^{\mu}_{h}F_{ij}^{\mu\nu}$
$\displaystyle=\int_{g}\varsigma_{g}\omega(h,-g)V^{\mu}_{-g+h}E_{ij}V_{g}^{\nu}$
(33)
$\displaystyle=\int_{g}\varsigma_{g}\varsigma_{-g+h}^{*}\omega_{h,-g}(V^{\mu}_{g-h})^{\dagger}E_{ij}V_{g-h+h}^{\nu}$
$\displaystyle=\int_{g}\varsigma_{g}\varsigma_{-g+h}^{*}\omega_{h,-g}\omega_{g-h,h}^{*}((V^{\mu}_{g-h})^{\dagger}E_{ij}V_{g-h}^{\nu})V_{h}^{\nu}.$

Crucially, the factor

$\varsigma_{g}\varsigma_{-g+h}^{*}\omega_{h,-g}\omega_{g-h,h}^{*}=1$ (34)

due to the cocycle condition $\delta\omega=1$, which expanded out is simply

$\omega(g_{1},g_{2})\omega(g_{1}+g_{2},g_{3})=\omega(g_{2},g_{3})\omega(g_{1},g_{2}+g_{3}).$
(35)

Therefore $[F^{\mu\nu}_{ij}]_{kl}=\delta_{\mu,\nu}\delta_{k,l}\lambda_{i,j}$
for some constant factor $\lambda_{i,j}$. This can be identified by computing

$\lambda_{i,j}=\frac{\text{Tr}[F_{ij}^{\mu\mu}]}{\dim(V^{\mu})}=\frac{\delta_{i,j}}{\dim(V^{\mu})},$
(36)

thereby proving the claim.

∎

######  Corollary 1.

If $V_{g}$ is a projective irrep and $\omega$ is maximally non-commutative,
then

${\rm Tr}[V_{g}]=\delta_{g,e}\sqrt{|G|}.$ (37)

In particular, the only nonzero character of $V_{g}$ is the trivial character.

###### Proof.

We use Shur orthogonality to write

$\displaystyle\int_{g}|\text{Tr}[V_{g}]|^{2}$
$\displaystyle=\sum_{i,j}\int_{g}[V^{\dagger}_{g}]_{ii}[V_{g}]_{jj}=1.$ (38)

Since $\int_{g}=\frac{1}{|G|}\sum_{g\in G}$ we must have

$\sum_{g\in G}|\text{Tr}[V_{g}]|^{2}=|G|,$ (39)

analogously to the case of linear representations. Now if $\omega$ is
maximally non-commutative, then $\dim(V)=\sqrt{|G|}$. Since
$V_{e}=\mathbf{1}_{\sqrt{|G|}}$, the above sum is then fully saturated by
$g=e$, proving the claim. ∎

##  Appendix B Representation theory data for finite Abelian $G$

In this appendix we provide explicit expressions for some of the
representation theory data employed in the main text. We first focus on the
case of $G=\mathbb{Z}_{N}\times\mathbb{Z}_{N}$, and later show how this can be
generalized.

###  B.1 $G=\mathbb{Z}_{N}\times\mathbb{Z}_{N}$

The second cohomology classes of $G$ form the group
$H^{2}(\mathbb{Z}_{N}\times\mathbb{Z}_{N};U(1))=\mathbb{Z}_{N}$. Writing group
elements $g\in\mathbb{Z}_{N}\times\mathbb{Z}_{N}$ as $\bm{g}=(g_{1},g_{2})$,
we may always choose a gauge in which the factor sets are given by [63]

$\omega_{g,h}=\zeta^{\omega g_{2}h_{1}},$ (40)

where $\zeta\equiv e^{2\pi i/N}$ and where we have abused notation slightly by
letting $\omega$ in the exponent denote the element of $\mathbb{Z}_{N}$
corresponding to the cohomology class $\omega$. The commutator function
$\lambda_{\omega}$ is correspondingly

$\lambda_{\omega}(g,h)=\zeta^{-\omega\mathbf{g}\times\mathbf{h}}=\zeta^{-\omega(g_{1}h_{2}-g_{2}h_{1})}.$
(41)

With the standard choice of character
$\chi_{g}(h)=\zeta^{\mathbf{g}\cdot\mathbf{h}}$, we then have

$\Gamma_{\omega}((g_{1},g_{2}))=\omega\cdot(-g_{2},g_{1}),\qquad\varsigma((g_{1},g_{2}))=\zeta^{\omega
g_{1}g_{2}}.$ (42)

Explicit linear and projective representations consistent with the above
choice of factor set are afforded by

$R_{g}=Z^{g_{1}}\otimes Z^{g_{2}},\qquad V_{g}^{\omega}=X^{g_{1}}Z^{\omega
g_{2}},$ (43)

where

$X\equiv\sum_{a}|{a+1}\rangle\langle{a}|,\qquad
Z\equiv\sum_{a}\zeta^{a}|a\rangle\langle a|$ (44)

are the usual $\mathbb{Z}_{N}$ clock and shift matrices, satisfying $ZX=\zeta
XZ$.

By attempting to invert $\Gamma_{\omega}$, we see that $\omega$ is maximally
non-commutative iff $\omega$ is invertible in $\mathbb{Z}_{N}$, i.e. iff
$\omega$ and $N$ are relatively prime [36], in which case
$\Gamma_{\omega}^{-1}((g_{1},g_{2}))=\frac{1}{\omega}(g_{2},-g_{1})$ (note
that $\omega$ is always maximally non-commutative if $N$ is prime). By the
results of App. A, all possible projective representations are then gauge-
equivalent to the $V^{\omega}_{g}$ written above.

###  B.2 General Abelian groups

Let $G=\prod_{i=1}^{M}\mathbb{Z}_{N_{i}}$, and write elements in $G$ as
$M$-component vectors $(g_{1},\dots,g_{M})$. The calculation of
$H^{2}(G;U(1))$ can be accomplished by repeated use of the Kunneth formula
[65]

$0\rightarrow\bigoplus_{k=0}^{n}H^{k}(G;\mathbb{Z})\otimes_{\mathbb{Z}}H^{n-k}(K;\mathbb{Z})\rightarrow
H^{n}(G\times K;\mathbb{Z})\rightarrow\bigoplus_{k=0}^{n+1}{\rm
Tor}[H^{n+1-k}(G;\mathbb{Z}),H^{k}(K;\mathbb{Z})]\rightarrow 0,$ (45)

together with use of $H^{k}(G)\equiv H^{k}(G;U(1))=H^{k+1}(G;\mathbb{Z})$,
$\mathbb{Z}_{N}\otimes_{\mathbb{Z}}\mathbb{Z}_{M}=\mathbb{Z}_{(N,M)}$ (with
$(N,M)\equiv\gcd(N,M)$), and the fact that

$H^{k}(\mathbb{Z}_{N};\mathbb{Z})=\begin{dcases}\mathbb{Z}_{N}\qquad&k\in
2\mathbb{N}\\\ 0\qquad&k\in 2\mathbb{N}+1\\\ \mathbb{Z}&k=0\end{dcases}.$ (46)

Putting these together, we obtain

$H^{2}(G;U(1))=\prod_{j<k}^{M}\mathbb{Z}_{(N_{j},N_{k})}.$ (47)

As a straightforward generalization of the $\mathbb{Z}_{N}^{2}$ case,
representatives for the distinct factor sets are provided by

$\omega_{g,h}=\prod_{1\leq i<j\leq
M}\zeta_{(N_{i},N_{j})}^{\hat{\omega}_{ij}g_{i}h_{j}},$ (48)

where $\hat{\omega}$ is now a symmetric matrix with entries
$\hat{\omega}_{ij}\in\mathbb{Z}_{(N_{i},N_{j})}$. The commutator function is
consequently

$\lambda_{\omega}(g,h)=\prod_{1\leq i<j\leq
M}\zeta_{(N_{i},N_{j})}^{\hat{\omega}_{ij}(g_{i}h_{j}-h_{i}g_{j})},$ (49)

from which $\omega$ is seen to be maximally non-commutative if
$\hat{\omega}_{ij}$ is relatively prime to $(N_{i},N_{j})$ for all $i,j$.
Explicit forms for the projective representations with maximally non-
commutative $\omega$ can be constructed by taking appropriate products of the
expressions in the $\mathbb{Z}_{N}\times\mathbb{Z}_{N}$ case.

##  Appendix C MPS techniques and the construction of $|\Psi_{\omega}\rangle$

In this section we describe how to construct the canonical reference states
$|\Psi_{\omega}\rangle$ for each SPT phase, and prove some relations involving
the shift operators $S^{L/R}_{g}$ introduced in the main text.

###  C.1 MPS tensors

In all of what follows, we take the physical indices of our MPS tensors to be
indexed by elements of $G$, with the physical onsite Hilbert space
$\mathcal{H}$ having dimension $|G|$. We will always choose a basis in which
the onsite symmetry action $R_{g}$ is diagonal, with

$R_{g}=\sum_{h\in G}\chi_{g}(h)|h\rangle\langle h|,$ (50)

where $\chi_{g}(\cdot)$ is the linear character on $G$ dual to the element
$g$.

Since the physical indices of our MPS states are indexed by $G$, an arbitrary
MPS tensor $A$ may be written

$A=\sum_{g\in G}|g\rangle A^{g},$ (51)

where $A^{g}$ is a $\chi\times\chi$ matrix in ${\rm
End}(\mathcal{H}_{\text{virt}})$, with $\mathcal{H}_{\text{virt}}$ the
$\chi$-dimensional virtual space of the MPS. All MPS tensors descrbing MPS
wavefunctions in $\mathsf{SPT}_{\omega}$ must be such that the symmetry pushes
from a linear action on the physical leg to a projective action on the virtual
legs [66], with

$\sum_{h\in G}R_{g}|h\rangle A^{h}=\sum_{h\in
G}|h\rangle(V^{\dagger}_{g}A^{h}V_{g})$ (52)

for some $\chi$-dimensional projective representation $V_{g}$ of $G$ with
factor set $\omega$ (which neccessitates that $\chi\geq\sqrt{|G|}$ if $\omega$
is nontrivial). We will find it helpful to use notation where matrices acting
on the left of $A$ denote an action on $A$’s physical index, while matrices of
the form $(X\otimes Y)$ which act on the right of $A$ denote an action on
$A$’s left virtual index by $X$ and right virtual index by $Y$. In this
notation Eq. (52) reads

$R_{g}A=A(V_{g}^{\dagger}\otimes V_{g}).$ (53)

Graphically,

(54)

where the grey box denotes an MPS tensor whose physical leg is indicated by a
doubled line (since in the present MNC case,
$\dim\mathcal{H}=(\dim\mathcal{H}_{virt})^{2}$). In our notation MPS tensors
with downward-pointing physical legs will tacitly assumed to be complex
conjugated; thus $R_{g}$ pushes ‘up’ through MPS tensors as

(55)

Since there is no spontaneous symmetry breaking (SSB) in the models we are
considering, all MPS tensors will be required to be injective [66], meaning
that some integer number $n$ of $A$ tensors can be blocked together so that
the MPS tensor $\sum_{\mathbf{g}\in G^{n}}|\mathbf{g}\rangle(A^{g_{1}}\cdots
A^{g_{n}})$ defines an isometry on $\mathcal{H}_{\text{virt}}^{\otimes 2}$.

We now discuss the construction of the canonical reference states
$|\Psi_{\omega}\rangle$. The MPS tensors that appear in our definition of
$|\Psi_{\omega}\rangle$ will in fact satisfy a much stronger property than
injectivity:

######  Definition 3 (perfect MPS).

An MPS tensor $A$ is said to be perfect if it is a perfect tensor when viewed
as a map $\mathcal{H}_{virt}^{\otimes 2}\rightarrow\mathcal{H}$. That is, $A$
is perfect if both

${\rm Tr}[(A^{g})^{\dagger}A^{h}]\propto\delta_{g,h}$ (56)

(isometry when virtual legs are contracted), and

$\sum_{g\in G}[A^{g}]_{ij}[A^{g}]^{*}_{kl}\propto\delta_{ik}\delta_{jl}$ (57)

(isometry when physical legs are contracted).

Graphically, Eq. (56) means (from now on all grey boxes drawn will indicate
canonical MPS tensors $A_{\omega}$, unless indicated otherwise)

(58)

while Eq. (57) means

(59)

We will refer to a translation-invariant MPS wavefunction constructed from
perfect MPS tensors as a ‘perfect MPS’. Note that by Eq. (57), a perfect MPS
tensor is automatically injective without the need for any blocking.

It is very easy to write down an explicit expression for a perfect MPS tensor
in the maximally non-commutative case:

######  Proposition 2 (maximally non-commutative MPS tensors).

For maximally non-commutative $\omega$, one may always construct a perfect MPS
with bond dimension $\sqrt{|G|}$ and MPS tensors

$A_{\omega}=\sum_{g\in G}|g\rangle
V_{\Gamma_{\omega}^{-1}(g)}^{\dagger}=\sum_{g\in G}\varsigma_{g}|g\rangle
V_{-\Gamma_{\omega}^{-1}(g)}.$ (60)

Note that $A_{\omega}$ has the smallest allowable bond dimension, and thus
defines a state in $\mathsf{SPT}_{\omega}$ with the smallest possible
entanglement. The fact that the bond dimension of $A_{\omega}$ is the square
root of the physical dimension of $A_{\omega}$ is the reason for indicating
physical legs with doubled lines in our graphical notation.

That the above choice of $A_{\omega}$ works is proven by noticing that the
phases generated when commuting $V_{g}$s past one another can always be
transformed into the linear character $\chi_{g}(h)$ appearing in the action of
$R_{g}$:

###### Proof.

Injectivity of $A_{\omega}$ can be checked using Schur orthogonality (31):

$\sum_{g\in G}(A^{g}_{\omega})^{\dagger}\otimes
A_{\omega}^{g}=|G|\int_{g}\sum_{ijkl}|{ij}\rangle\langle{kl}|[V_{g}]_{ij}[V_{g}]^{*}_{lk}=\sqrt{|G|}\sum_{ij}|{ij}\rangle\langle{ij}|=\sqrt{|G|}\mathbf{1}_{\text{virt}}^{\otimes
2}.$ (61)

That $A_{\omega}$ is perfect then follows from the fact that

$\text{Tr}[(A_{\omega}^{g})^{\dagger}A_{\omega}^{h}]|{g}\rangle\langle{h}|=|{g}\rangle\langle{h}|\text{Tr}[V^{\dagger}_{\Gamma^{-1}_{\omega}(g)}V_{\Gamma^{-1}_{\omega}(h)}]=\sqrt{|G|}\delta_{g,h}$
(62)

We then verify the pull-through property (52). Conjugating the
$V_{\Gamma^{-1}_{\omega}(g)}$ by $V_{h}$s at the cost of a $\lambda_{\omega}$
term, we have

$\displaystyle R_{h}A_{\omega}=\sum_{g\in
G}|g\rangle\frac{\chi_{h}(g)}{\lambda_{\omega}(h,\Gamma^{-1}_{\omega}(g))}V_{h}^{\dagger}V_{\Gamma_{\omega}^{-1}(g)}^{\dagger}V_{h}.$
(63)

But by definition of the map $\Gamma_{\omega}$ (29), we have

$\lambda_{\omega}(h,\Gamma_{\omega}^{-1}(g))=\chi_{h}(g),$ (64)

and thus we have $R_{h}A_{\omega}=A_{\omega}(V_{h}^{\dagger}\otimes V_{h})$ as
desired. ∎

We define the canonical representative of the phase $\mathsf{SPT}_{\omega}$
using these MPS tensors:

######  Definition 4 (canonical reference state of an SPT phase).

For a given maximally non-commutative cohomology class $\omega$, the canonical
reference state of the phase $\mathsf{SPT}_{\omega}$ is defined as

$|\Psi_{\omega}\rangle\equiv\sum_{\mathbf{g}\in G^{L}}{\rm
Tr}[A^{g_{1}}_{\omega}\cdots A_{\omega}^{g_{L}}]|\mathbf{g}\rangle,$ (65)

where $A_{\omega}$ are the MPS tensors of (60).

A useful fact we will employ later, which follows easily from the injectivity
of $A_{\omega}$ and $\text{Tr}[V_{g}]\propto\delta_{g,e}$, is

$\langle\Psi_{\omega}|R_{\mathbf{g}}|\Psi_{\omega}\rangle=\prod_{i}\delta_{g_{i},e}.$
(66)

###  C.2 Shift operators and parent Hamiltonians

We now define the right and left shift operators employed in the main text,
and show how they can be used to construct a Hamiltonian whose ground state is
$|\Psi_{\omega}\rangle$.

######  Definition 5 (right shift operator).

We define the right shift operator as

$S^{R}_{g}=\sum_{h\in
G}\omega(g,\Gamma^{-1}_{\omega}(h)+g)\varsigma_{-g}^{*}|{h+\Gamma_{\omega}(g)}\rangle\langle{h}|=\sum_{h\in
G}\omega(g,\Gamma^{-1}_{\omega}(h))\varsigma_{-g}^{*}|{h}\rangle\langle{h-\Gamma_{\omega}(g)}|.$
(67)

This operator is designed to satisfy

$\displaystyle A_{\omega}(\mathbf{1}\otimes V_{g})$ $\displaystyle=\sum_{h\in
G}|h\rangle
V_{\Gamma^{-1}_{\omega}(h)}^{\dagger}V_{-g}^{\dagger}\varsigma^{*}_{-g}$ (68)
$\displaystyle=\sum_{h\in G}|h+\Gamma_{\omega}(g)\rangle
V_{\Gamma^{-1}_{\omega}(h)}^{\dagger}\omega(-g,\Gamma^{-1}_{\omega}(h)+g)^{*}\varsigma^{*}_{-g}$
$\displaystyle=S^{R}_{g}A_{\omega}.$

Graphically,

$\vbox{\hbox{\includegraphics[width=151.76964pt]{figures/right_shift}}}.$ (69)

Given that $S_{R}$ is unitary, $(S^{R}_{g})^{\dagger}$ can be used to correct
for an ‘error’ of $V_{g}$ occurring on the right virtual leg of $A_{\omega}$,
via

$(S_{g}^{R})^{\dagger}A_{\omega}(1\otimes V_{g})=A_{\omega}.$ (70)

Note that the $S^{R}_{g}$ obey the same fusion rule as the projective
representations themselves,

$S^{R}_{g}S^{R}_{h}=\omega_{g,h}S^{R}_{g+h},$ (71)

so that

$S^{R}_{g}S^{R}_{h}=\lambda_{\omega}(g,h)S^{R}_{h}S^{R}_{g}.$ (72)

Furthermore, $S^{R}_{g}$ picks up the same phase as $V_{g}$ under Hermitian
conjugation:

$(S^{R}_{g})^{\dagger}=\varsigma_{g}S^{R}_{-g},$ (73)

and it commutes with the linear symmetry operators as

$S^{R}_{g}R_{h}=\lambda_{\omega}(g,h)R_{h}S^{R}_{g}.$ (74)

These equations can all be proved by evaluating the action of both sides on
$A_{\omega}$; that this is sufficient follows from the fact that $A_{\omega}$
is perfect.

Similarly,

######  Definition 6 (left shift operator).

We define the left shift operator as

$\displaystyle S^{L}_{g}=\varsigma_{g}R_{g}S^{R}_{-g}=\sum_{h\in
G}\omega(g-\Gamma^{-1}_{\omega}(h),g)|{h-\Gamma_{\omega}(g)}\rangle\langle{h}|=\sum_{h\in
G}\omega(\Gamma^{-1}_{\omega}(h),g)^{*}|{h}\rangle\langle{h+\Gamma_{\omega}(g)}|.$
(75)

$S^{L}_{g}$ is designed to satisfy

$\displaystyle A_{\omega}(V_{g}^{\dagger}\otimes\mathbf{1})$
$\displaystyle=R_{g}A_{\omega}(\mathbf{1}\otimes V_{g}^{\dagger})$ (76)
$\displaystyle=\varsigma_{g}R_{g}A_{\omega}(\mathbf{1}\otimes V_{-g})$
$\displaystyle=\varsigma_{g}R_{g}S^{R}_{-g}A_{\omega}$
$\displaystyle=S^{L}_{g}A_{\omega}.$

Graphically,

$\vbox{\hbox{\includegraphics[width=151.76964pt]{figures/left_shift}}}.$ (77)

Therefore an ‘error’ of $V_{g}^{\dagger}$ occurring on the left virtual leg of
$A_{\omega}$ can be corrected by way of

$(S^{L}_{g})^{\dagger}A_{\omega}(V_{g}^{\dagger}\otimes\mathbf{1})=A_{\omega}.$
(78)

The $S^{L}$ operators combine in the opposite way as the projective
representations, since they put the projective representations in ‘reversed’
order on the left legs:

$S^{L}_{g}S^{L}_{h}=\omega_{h,g}^{*}S^{L}_{g+h}.$ (79)

Therefore (c.f. (72))

$S^{L}_{g}S^{L}_{h}=\lambda_{\omega}(h,g)S^{L}_{h}S^{L}_{g},$ (80)

and

$S^{L}_{g}R_{h}=\lambda_{h,g}R_{h}S^{L}_{g}.$ (81)

Note that the $S^{L/R}_{g}$ are designed to ‘fractionalize’ the linear
symmetry action, in that

$R_{g}=S^{L}_{g}S^{R}_{g}.$ (82)

We also see that $\Gamma_{\omega}(g)$ has the meaning of the linear
representation of $G$ that the shift operators transform under the adjoint
action of $G$: indeed, by (74) and (81),

$R_{h}^{\dagger}S^{L}_{g}R_{h}=\chi_{\Gamma_{\omega}(g)}(h)S^{L}_{g},\qquad
R_{h}^{\dagger}S^{R}_{g}R_{h}=\chi^{*}_{\Gamma_{\omega}(g)}(h)S^{R}_{g}.$ (83)

Thus $S^{L}_{g},S^{R}_{g}$ transform in conjugate representations, as
befitting the fact that their product (viz. $R_{g}$) transforms trivially
under the adjoint action, by virtue of $G$ being Abelian.

The left and right shift operators can be used to construct string operators,
as well as a Hamiltonian whose ground state is $|\Psi_{\omega}\rangle$:

######  Proposition 3 (Parent Hamiltonian).

A commuting projector Hamiltonian with ground state $|\Psi_{\omega}\rangle$ is

$H=-\sum_{i}\sum_{g\in G}S_{g,i-1}^{R}S_{g,i}^{L}.$ (84)

###### Proof.

The standard way of constructing $H$ is to write [66]

$H=-\sum_{i}\mathcal{P}_{{\rm span}(AA)},$ (85)

where $\mathcal{P}_{{\rm span}(AA)}$ is the projector onto the subspace
$\mathcal{H}_{AA}$ spanned by the tensor product of two contracted MPS
tensors:

$\mathcal{H}_{AA}={\rm
span}\\{|g,h\rangle\text{Tr}[A_{\omega}^{g}A_{\omega}^{h}X]\,|\,X\in{\rm
Mat}_{\sqrt{|G|}\times\sqrt{|G|}},\,g,h\in G\\}.$ (86)

Since our MPS tensors are injective,
$\dim\mathcal{H}_{AA}=\dim\mathcal{H}=|G|$. We therefore need to find $|G|$
independent operators $\mathcal{P}_{i,i+1}^{g}$ which stabilize the ground
state. Constructing these operators is actually quite straightforward to do if
we make use of the shift operators defined previously; a little reflection
reveals that the expression above works, as it is easily checked to stabilize
the MPS ground state by way of (68) and (76). ∎

The following string operators, which are formed by taking a symmetry action
on a finite interval and decorating the ends with shift operators, play a
fundamental role in our ability to distinguish different SPT phases:

######  Definition 7 (string operators).

For any two sites $j>i$ and any $g\in G$, we define the string operator
$\mathcal{S}_{g,i\rightarrow j}$ as

$\mathcal{S}_{g;i\rightarrow j}\equiv
S^{R}_{g,i}\otimes\bigotimes_{l=i+1}^{j-1}R_{g,l}\otimes S^{L}_{g,j}.$ (87)

Using the pull-through condition (54), these string operators are easily
checked to stabilize $|\Psi_{\omega}\rangle$. Note also that the operators
appearing in the above parent Hamiltonian are simply
$\mathcal{S}_{g,i\rightarrow i+1}$.

Intuitively, the string operators are constructed by acting with the symmetry
over a finite interval, and then decorating the ends of the interval with a
fractionalized action of the symmetry (this terminology being appropriate
since $R_{g}$ fractionalizes into $S^{L}_{g}S^{R}_{g}$). If one were to
decorate the ends of the interval with operators transforming under $G$
according to any irrep other than $\chi_{\Gamma_{\omega}(g)}$ (see (83)), it
is easy to see that the resulting string operator will have vanishing
expectation value throughout the SPT phase [21, 37].

###  C.3 Explicit expressions for $G=\mathbb{Z}_{N}\times\mathbb{Z}_{N}$

We now give expressions for the various tensors defined above in case
considered in the main text, where $G=\mathbb{Z}_{N}\times\mathbb{Z}_{N}$ and
$\omega$ is maximally non-commutative. We will often decompose the physical
Hilbert space into two factors of dimension $N$, writing
$\mathcal{H}=\mathcal{H}_{1}\otimes\mathcal{H}_{2}$ with
$\dim\mathcal{H}_{1}=\dim\mathcal{H}_{2}=N$.

Since $\omega$ is invertible in $\mathbb{Z}_{N}$ by assumption, we may use
(60) to write down the canonical MPS tensors as

$A_{\omega}=\sum_{g\in G}|g\rangle Z^{g_{1}}X^{-g_{2}/\omega}.$ (88)

That $A_{\omega}$ is perfect follows from the fact that the matrices
$X^{a}Z^{b},a,b,\in\mathbb{Z}_{N}$ generate $GL(N)$, together with the
invertibility of $\omega$ in $\mathbb{Z}_{N}$. Note that the canonical MPS
tensors for two maximally non-commutative factor sets $\nu$ and $\omega$ are
linearly related by

$A_{\nu}=\sum_{g\in G}(|g_{1}\rangle\langle g_{1}|\otimes|{\nu
g_{2}/\omega}\rangle\langle{g_{2}}|)A_{\omega},$ (89)

One can further verify that the left and right shift operators are

$S^{L}_{g}=Z^{g_{1}}X^{\omega g_{2}}\otimes X^{-\omega g_{1}},\qquad
S^{R}_{g}=X^{-\omega g_{2}}\otimes X^{g_{1}\omega}Z^{g_{2}}.$ (90)

The Hamiltonian
$H=-\sum_{g,i}S^{R}_{g,i}S^{L}_{g,i+1}\equiv-\sum_{g,i}H_{g,i}$ is
consequently

$H=-\sum_{g,i}\left(X^{-\omega g_{2}}\otimes X^{\omega g_{1}}Z^{g_{2}}\otimes
Z^{g_{1}}X^{\omega g_{2}}\otimes X^{-\omega g_{1}}\right)_{i\rightarrow i+3},$
(91)

where now we are indexing the sites by the individual tensor factors of
dimension $N$.

While the Hamiltonian as written above contains terms acting on 4 consecutive
sites, it can be simplified somewhat as follows. First, for the
$\mathbb{Z}_{2}$ case, we may write

$H_{\mathbb{Z}_{2}^{2}}=-\sum_{i}(IIII+IXZX+XZXI+XYYX)_{i\rightarrow i+3}.$
(92)

The first term in parenthesis is a constant and can be dropped. The last term
is a product of the first two, and as all terms commute it is thus redundant
and can also be dropped, leaving us with the familiar $XZX$ form of the
Hamiltonian.

A similar type of simplification is possible for general $N$ [38]. Note that
$H_{g,i}=H_{(g_{1},0),i}H_{(0,g_{2}),i}$, and that all terms in the
Hamiltonian mutually commute. Therefore terms where both $g_{1},g_{2}$ are
nontrivial will automatically be minimized if the terms where one of
$g_{1},g_{2}$ is trivial are minimized. This means we may get away with only
summing over elements of the form $\\{(g_{1},0),(0,g_{2})\\}$. This gives

$H_{\mathbb{Z}_{N}^{2}}=-\sum_{g\in\mathbb{Z}_{N}}\left(\sum_{i\in
2\mathbb{Z}}X^{-\omega g}_{i}\otimes Z^{g}_{i+1}\otimes X^{\omega
g}_{i+2}+\sum_{i\in 2\mathbb{Z}+1}X^{\omega g}_{i}\otimes Z^{g}_{i+1}\otimes
X^{-\omega g}_{i+2}\right).$ (93)

Note that the alternating placement of daggers on the two sublattices is
actually important to keep track of, and is needed to ensure that all of the
terms in $H_{\mathbb{Z}_{N}^{2}}$ commute.

With this notation the string operators are generated by

$\mathcal{S}_{(1,0);i\rightarrow i+2l}=(I_{i}\otimes
X^{\omega}_{i+1})\bigotimes_{n=2}^{l-2}(Z_{2n}\otimes
I_{2n+1})\otimes(Z_{i+2l-1}\otimes X^{-\omega}_{i+2l})$ (94)

and

$\mathcal{S}_{(0,1);i\rightarrow i+2l}=(X^{-\omega}_{i}\otimes
Z_{i+1})\bigotimes_{n=2}^{l-2}(I_{2n}\otimes
Z_{2n+1})\otimes(X^{\omega}_{i+2l-1}\otimes I_{i+2l}).$ (95)

##  Appendix D General expression for ground states of maximally non-
commutative SPT phases

This section is devoted to proving the following theorem:

######  Theorem 3 (relation between SPT states in the same phase).

Let $|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$ be a ground state in the
SPT phase identified with the maximally non-commutative cohomology class
$\omega$. Then for $|\Psi_{\omega}\rangle$ the canonical reference state
defined in (65), we may always write

$|\psi_{\omega}\rangle=\sum_{\mathbf{g}\in
G^{L}}C_{\mathbf{g}}R_{\mathbf{g}}|\Psi_{\omega}\rangle,$ (96)

for $\bm{g}$ an $L$-component vector of group elements, and where the
$C_{\mathbf{g}}$ are complex coefficients satisfying
$\sum_{\mathbf{g}}|C_{\mathbf{g}}|^{2}=1$ and
$R_{\mathbf{g}}\equiv\bigotimes_{i=1}^{L}R_{g_{i},i}.$

The proof proceeds by finding a convenient operator basis in which to
decompose the action of the unitary circuit relating $|\psi_{\omega}\rangle$
to $|\Psi_{\omega}\rangle$. The overall logic is essentially the same as a
similar result pertaining to the 2D cluster state proven in Ref. [67].

To begin, we need the following lemma:

######  Lemma 4.

For $\omega$ maximally non-commutative, any $n$-site operator
$\mathcal{O}_{n}$ can be decomposed as

$\mathcal{O}_{n}=\sum_{\mathbf{g},\mathbf{h}\in
G^{n}}C_{\mathbf{g},\mathbf{h}}\bigotimes_{i=1}^{n}S^{R}_{g_{i},i}R_{h_{i},i}$
(97)

for some constants $C_{\mathbf{g},\mathbf{h}}$. Furthermore, $\mathcal{O}_{n}$
commutes with the symmetry action iff $\sum_{i}g_{i}=e$.

###### Proof.

The proof proceeds simply by noting that the operators in the above sum form
an orthogonal set which spans $\mathcal{H}^{\otimes n}$. Consider first the
case where $n=1$. Then we have

$\displaystyle\text{Tr}[S^{R}_{g}R_{h}(S^{R}_{g^{\prime}}R_{h^{\prime}})^{\dagger}]$
$\displaystyle=\text{Tr}[S^{R}_{g}(S^{R}_{g^{\prime}})^{\dagger}R_{h-h^{\prime}}]$
(98) $\displaystyle=|G|\delta_{g,g^{\prime}}\delta_{h,h^{\prime}}.$

Since there are $|G|^{2}=\dim\text{End}(\mathcal{H})$ such operators, they
form a basis for all single-site unitaries. Tensoring $n$ copies of them
together then gives a basis for the unitaries on $\mathcal{H}^{\otimes n}$.

Requiring that a given operator is symmetric means that it must commute with
$R_{k}^{\otimes n}$ for all $k\in G$. Now

$\displaystyle\mathcal{O}_{n}R_{k}^{\otimes n}$ $\displaystyle=R_{k}^{\otimes
n}\sum_{\mathbf{g},\mathbf{h}\in
G^{n}}C_{\mathbf{g},\mathbf{h}}\bigotimes_{i=1}^{n}\lambda_{\omega}(k,g_{i})S^{R}_{g_{i},i}R_{h_{i},i}$
(99) $\displaystyle=R_{k}^{\otimes n}\sum_{\mathbf{g},\mathbf{h}\in
G^{n}}C_{\mathbf{g},\mathbf{h}}\chi_{k}(\Gamma^{-1}_{\omega}(\sum_{j}g_{j}))\bigotimes_{i=1}^{n}S^{R}_{g_{i},i}R_{h_{i},i}.$

The RHS is equal to $R_{k}^{\otimes n}\mathcal{O}_{n}$ iff $\sum_{j}g_{j}=e$,
and so any symmetric operator must indeed be of the form claimed. ∎

Since $S^{R}_{-g}=S^{L}_{g}R_{-g}\varsigma_{-g}$, we can equivalently replace
$S^{R}_{-g_{i},i}$ operators appearing in the decomposition of a given
$\mathcal{O}_{n}$ with $S^{L}_{g_{i},i}$ operators, at the cost of modifying
the values of the $C_{\mathbf{g},\mathbf{h}}$. The combination of
$S^{R/L}_{g_{i},i}$ operators appearing in the decomposition of any symmetric
operator can thus always be manipulated so that it consists only of tensor
products of pairs $S^{R}_{g,i}\otimes S^{L}_{g,j>i}$. These give the endpoints
of a $g$ string operator, and hence by shifting the $R_{h_{i},i}$, any
symmetric operator may be written in terms of single-site symmetry actions and
string operators as

$\mathcal{O}^{\text{sym}}=\sum_{\mathbf{g},\mathbf{h}\in
G^{n}}\bigotimes_{i=1}^{n}R_{h_{i},i}\sum_{j>i}C^{\prime}_{\mathbf{g},\mathbf{h};j}\mathcal{S}_{g_{i},i\rightarrow
j}$ (100)

where the $C^{\prime}_{\mathbf{g},\mathbf{h};j}$ are complex numbers
determinable in principle from the $C_{\mathbf{g},\mathbf{h}}$.

We can use the above fact to prove theorem 3. By definition, all states
$|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$ can be related to one another
via the action of a constant-depth local444Strictly speaking the correct
adjective is ‘quasilocal’, allowing for the gates appearing in $\mathcal{U}$
to have arbitrarily large support, so long as operators with large support are
given exponentially small weights. Keeping track of the distinction between
local and quasilocal will not be important for the issues that concern us
here. unitary circuit $\mathcal{U}_{\psi}$, where each gate in
$\mathcal{U}_{\psi}$ commutes with the symmetry action $R_{g}^{\otimes L}$. By
(100), all of the gates in $\mathcal{U}_{\psi}$ can be decomposed in terms of
the onsite symmetry generators $R_{g_{i},i}$ and string operators
$\mathcal{S}_{g_{i},i\rightarrow j}$ — this leads to the picture shown in Fig
3. We can then move all $\mathcal{S}_{g_{i},i\rightarrow j}$ operators
appearing in the circuit to the ‘bottom’ of the circuit, so that they act
directly on $|\Psi_{\omega}\rangle$; this can be done merely at the cost of
picking up various unimportant complex phases. However, all string operators
act trivially on (i.e. stabilize) $|\Psi_{\omega}\rangle$ and hence may be
eliminated from $\mathcal{U}_{\psi}$, leaving behind only the $R_{\mathbf{h}}$
operators. The $R_{\mathbf{h}}$ then form of depth-1 circuit, and
$|\psi_{\omega}\rangle$ can indeed be written in the form of (96).
∎

##  Appendix E The circuit architecture

Figure 7:  Definition of the coarse-graining unitary $\mathcal{C}$. Grey boxes
denote canonical MPS tensors $A_{\omega}$, the $T$ denotes transpose, and the
controlled gates $CS^{L/R}$, $CCR$ are defined in the text.

In this appendix we elaborate on the on the properties of the tensors used to
build the coarse-graining convolution unitary $\mathcal{C}$, and demonstrate
that $\mathcal{C}$ performs error correction by implementing the recursive
majority function. The explicit form of $\mathcal{C}$ is repeated in Fig. 7
for convenience. The ring of six MPS tensors serves to coarse-grain the input
wavefunction; when acting on $|\Psi_{\omega}\rangle$ this part of
$\mathcal{C}$ simply produces a coarse-grained (by a factor of 3) version of
$|\Psi_{\omega}\rangle$, tensored with a product state of $|0\rangle$s on the
remaining sites. The controlled gates activate when nontrivial ‘errors’ act on
$|\Psi_{\omega}\rangle$, and these gates serve to correct the errors by re-
directing the action of the errors away from the renormalized leg $r$, and
onto the measurement legs $m_{L},m_{R}$.

Specifically, we introduce the controlled left-shift operator as

$\displaystyle CS^{L}$ $\displaystyle\equiv\sum_{g\in
G}|\Gamma_{\omega}(g)\rangle\langle\Gamma_{\omega}(g)|\otimes(S^{L}_{g})^{\dagger}\otimes\mathbf{1}$
(101)

where we have written the operator in the basis
$\mathcal{H}_{m_{L}}\otimes\mathcal{H}_{r}\otimes\mathcal{H}_{m_{R}}$ (see
Fig. 7). Similarly, we define the controlled right-shift operator as

$CS^{R}\equiv\sum_{g\in
G}\varsigma_{g}^{*}\mathbf{1}\otimes(S^{R}_{g})^{\dagger}\otimes|\Gamma_{\omega}(-g)\rangle\langle\Gamma_{\omega}(-g)|.$
(102)

Finally, the double-controlled gate $CCR$ is defined to perform a linear
action of the symmetry if the left and right legs are in opposite states, and
to act as the identity otherwise:

$\displaystyle CCR$
$\displaystyle\equiv\sum_{g}|\Gamma_{\omega}(-g)\rangle\langle\Gamma_{\omega}(-g)|\otimes
R_{g}^{\dagger}\otimes|\Gamma_{\omega}(g)\rangle\langle\Gamma_{\omega}(g)|+\sum_{g\neq
g^{\prime}}|\Gamma_{\omega}(-g)\rangle\langle\Gamma_{\omega}(-g)|\otimes\mathbf{1}\otimes|\Gamma_{\omega}(g^{\prime})\rangle\langle\Gamma_{\omega}(g^{\prime})|$
(103)
$\displaystyle=\sum_{g,g^{\prime}}|\Gamma_{\omega}(-g)\rangle\langle\Gamma_{\omega}(-g)|\otimes((R_{g}^{\dagger}-\mathbf{1})\delta_{g,g^{\prime}}+\mathbf{1})\otimes|\Gamma_{\omega}({g^{\prime}})\rangle\langle\Gamma_{\omega}({g^{\prime}})|.$

To understand the utility of these gates, consider first how a single-site
error passes through $\mathcal{C}$:

######  Proposition 4.

$\mathcal{C}$ corrects all single-site $R_{g}$ errors acting on
$|\Psi_{\omega}\rangle$. That is, for an error of the form $R_{g}\otimes
R_{h}\otimes R_{k}$ where only one of $g,h,k\neq e$,

$\mathcal{C}(R_{g}\otimes R_{h}\otimes R_{k})A_{\omega}^{\otimes
3}=|\Gamma_{\omega}(h-g)\rangle\otimes
A_{\omega}\otimes|\Gamma_{\omega}(k-h)\rangle.$ (104)

In the above, we have used notation where tensor products are in physical
space, with virtual indices being implicitly contracted as appropriate. Thus
e.g. $A^{\otimes 3}_{\omega}=\sum_{\mathbf{g}\in G^{3}}|\mathbf{g}\rangle
A_{\omega}^{g_{1}}A_{\omega}^{g_{2}}A_{\omega}^{g_{3}}$ is a tensor valued in
$\mathcal{H}_{\text{virt}}\otimes\mathcal{H}^{\otimes
3}\otimes\mathcal{H}_{\text{virt}}$.

###### Proof.

We demonstrate this simply by explicitly computing the action of $\mathcal{C}$
in all situations where a single error is present. Suppose an error of $g$
occurs on the leftmost input site $i_{l}$. Understanding how this error
travels through $\mathcal{C}$ can be done graphically as follows:

(105)

where the cyan and yellow circles stand for linear and projective
representations respectively, and where in the second step we have used the
injectivity condition (59). The states of the measurement legs $m_{L/R}$ can
be worked out using

$\sum_{h\in
G}|h\rangle\text{Tr}[A^{h}_{\omega}V_{g}]=\vbox{\hbox{\includegraphics[width=86.72267pt]{figures/ttensor}}}=\sqrt{|G|}|\Gamma_{\omega}(g)\rangle$
(106)

since $\text{Tr}[V_{g}^{\dagger}V_{h}]=\sqrt{|G|}\delta_{g,h}$. Thus in this
case, the left leg $m_{L}$ is in the state $|\Gamma_{\omega}(g)\rangle$, and
the right leg $m_{R}$ is in the state $|e\rangle$. The job of the control
gates $CS^{L/R},CCR$ is to use the information contained in these states to
correct for the action of $S^{L}_{g}$ that has been applied to the
renormalized leg $r$ (due to the $V_{g}^{\dagger}$ projective rep appearing in
the last panel of (105)). In this case, since $m_{R}$ is in the state
$|e\rangle$, only the $CS^{L}$ gate activates. This gate applies
$(S^{L}_{g})^{\dagger}$ to the renormalized leg, which cancels the $S^{L}_{g}$
error. Thus indeed,

$\mathcal{C}(R_{g}\otimes\mathbf{1}\otimes\mathbf{1})A_{\omega}^{3}=|\Gamma_{\omega}(g)\rangle\otimes
A_{\omega}\otimes|e\rangle.$ (107)

Similarly, consider what happens when an error $R_{k}$ occurs on the rightmost
site $c$. Similar arguments show that the right measurement module is left in
the state $\varsigma_{k}|\Gamma_{\omega}(-k)\rangle$, the left module in the
sate $|\Gamma_{\omega}(k)\rangle$, and that renormalized leg incurrs an error
of $S^{R}_{k}$. Only the $CS^{R}$ gate activates, which applies a corrective
action of $(S^{R}_{k})^{\dagger}$ to the renormalized leg, cancelling the
error. Therefore

$\mathcal{C}(\mathbf{1}\otimes\mathbf{1}\otimes R_{k})A_{\omega}^{\otimes
3}=|e\rangle\otimes A_{\omega}\otimes|\Gamma_{\omega}(-k)\rangle.$ (108)

Finally, consider an error of $R_{h}$ applied to the central leg. This leaves
the left module in the state $\varsigma_{h}|\Gamma_{\omega}(-h)\rangle$, the
right module in the state $|\Gamma_{\omega}(h)\rangle$, and leads to no error
on the renormalized leg. Both the $CS^{L/R}$ gates activate, and conseuqnetly
the renormalized leg is acted on by
$\varsigma_{h}\varsigma_{-h}^{*}(S^{L}_{-h})^{\dagger}(S^{R}_{-h})^{\dagger}=\lambda_{\omega}(-h,h)(R_{-h})^{\dagger}=R_{h}$.
We see that the $CCR$ gate has been chosen to exactly compensate for this
action; thus

$\mathcal{C}(\mathbf{1}\otimes R_{h}\otimes\mathbf{1})A_{\omega}^{\otimes
3}=|\Gamma_{\omega}(-h)\rangle\otimes
A_{\omega}\otimes|\Gamma_{\omega}(h)\rangle.$ (109)

∎

We also have the necessary property that $\mathcal{C}$ preserves the global
symmetry action:

######  Proposition 5.

The global symmetry commutes with $\mathcal{Q}_{\omega}$, in the sense that
the global symmetry operator $R_{g}^{\otimes L}$ is mapped to $R_{g}^{\otimes
L^{\prime}}\otimes\mathbf{1}_{M}$ upon commuting with $\mathcal{Q}_{\omega}$,
where $L^{\prime}=L/3$ and $\mathbf{1}_{M}$ denotes the identity on the
subspace spanned by the measured legs.

###### Proof.

The proof is straightforward, and does not require us to project onto states
generated by $A_{\omega}$. Without loss of generality, we can focus on the
commutation relation between $R_{g}^{\otimes 3}$ and a single convolution
module $\mathcal{C}$. First, we see that $R_{g}^{\otimes 3}$ passes through
the layer below the control gates in $\mathcal{C}$ unchanged. Since the
controls occur in the $R_{g}$ basis, we just need to compute how $R_{g}$ on
the renormalized leg passes through the $CS^{L/R}$ gates. For the $CS^{L}$
gate,

$\displaystyle CS^{L}(\mathbf{1}\otimes R_{g}\otimes\mathbf{1})$
$\displaystyle=\sum_{h\in
G}|\Gamma_{\omega}(h)\rangle\langle\Gamma_{\omega}(h)|\otimes(S^{L}_{h})^{\dagger}R_{g}\otimes\mathbf{1}$
(110) $\displaystyle=\sum_{h\in
G}\chi_{g}(\Gamma_{\omega}(h))|\Gamma_{\omega}(h)\rangle\langle\Gamma_{\omega}(h)|\otimes
R_{g}(S^{L}_{h})^{\dagger}\otimes\mathbf{1}$
$\displaystyle=(R_{g}^{\dagger}\otimes R_{g}\otimes\mathbf{1})CS^{L},$

where we used
$(S^{L}_{h})^{\dagger}R_{g}=\lambda_{\omega}(-g,h)R_{g}(S^{L}_{h})^{\dagger}=\chi_{-g}(\Gamma_{\omega}(h))R_{g}(S^{L}_{h})^{\dagger}$.
One can similarly verify that

$CS^{R}(\mathbf{1}\otimes R_{g}\otimes\mathbf{1})=(\mathbf{1}\otimes
R_{g}\otimes R_{g}^{\dagger})CS^{R}.$ (111)

Therefore when the $R_{g}$ on the renormalized leg passes through the control
gates, it cancels the two applications of $R_{g}$ on the measurement legs.
Thus

$\mathcal{C}R_{g}^{\otimes 3}=(\mathbf{1}\otimes
R_{g}\otimes\mathbf{1})\mathcal{C}$ (112)

at the level of operators (i.e. not just when acting on states generated by
the MPS tensors $A_{\omega}$).

∎

To define the action of $\mathcal{C}$ on general errors of the form
$R_{g}\otimes R_{h}\otimes R_{k}$, we define a majority vote function as
follows:

######  Definition 8 (majority vote rule).

The function $\mathsf{maj}:G^{3}\rightarrow G$ is defined to implement
majority vote on $G$. In the case of ties, $\mathsf{maj}$ selects out the
center element of the tuple $(g,h,k)\in G^{3}$. Explicitly,

$\mathsf{maj}(g,h,k)\equiv\begin{dcases}g\quad&{\rm if}\,\,(h=g)\vee(k=g)\\\
h\quad&{\rm if}\,\,(g=h)\vee(k=h)\\\ k\quad&{\rm if}\,\,(g=k)\vee(h=k)\\\
h\quad&{\rm else}\end{dcases}$ (113)

The previous two propositions then lead to

######  Corollary 2.

$\mathcal{C}$ implements the majority vote rule on $R_{\mathbf{g}}$ operator
strings which act on the canonical ground state $|\Psi_{\omega}\rangle$. That
is,

$\mathcal{C}(R_{g}\otimes R_{h}\otimes R_{k})A_{\omega}^{\otimes
3}=|\Gamma_{\omega}(h-g)\rangle\otimes
R_{\mathsf{maj}(g,h,k)}A_{\omega}\otimes|\Gamma_{\omega}(k-h)\rangle.$ (114)

Graphically,

(115)

Note that this property is not satisfied by the QCNN used in [13] to study the
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ cluster state.

###### Proof.

Since the global symmetry pushes through $\mathcal{C}$ and since single errors
are corrected, this property obviously holds in the 3:0 situation when
$g=h=k$. When we are in a 2:1 vote situation, we have e.g.

$\mathcal{C}(R_{g}\otimes R_{g}\otimes R_{h})A_{\omega}^{\otimes
3}=(\mathbf{1}\otimes
R_{g}\otimes\mathbf{1})\mathcal{C}(\mathbf{1}\otimes\mathbf{1}\otimes
R_{h-g})A_{\omega}^{\otimes 3}=|e\rangle\otimes
R_{g}A_{\omega}\otimes|\Gamma_{\omega}(h-g)\rangle,$ (116)

and likewise for the two other 2:1 vote configurations. Since $R_{g}$ acts on
the renormalized leg in all cases, the 2:1 vote works in the way claimed.

Consider then the case of a tie, where $g\neq h\neq k$. In this case the
$R_{g}^{\dagger}$ part of the $CCR$ gate will be unactivated as $g\neq k$. On
the other hand, both the $CS^{L/R}$ gates will activate. In this case, the
left measurement module is left in the state
$\varsigma_{h}\omega_{g,-h}|\Gamma_{\omega}(g-h)\rangle$, the right module is
left in the state $\varsigma_{k}\omega_{h,-k}|\Gamma_{\omega}(h-k)\rangle$,
and the renormalized leg incurs an error of $V_{g}^{\dagger}\otimes V_{k}$.
After the $CS^{L/R}$ gates activate, we get a combined action on the
renormalized leg of

$\displaystyle\varsigma_{h}\varsigma_{k}\varsigma^{*}_{k-h}\omega_{g,-h}\omega_{h,-k}(S^{L}_{g-h})^{\dagger}(S^{R}_{k-h})^{\dagger}$
$\displaystyle=R_{h}(S^{L}_{g})^{\dagger}(S^{R}_{k})^{\dagger},$ (117)

where we used
$(S^{R}_{k-h})^{\dagger}=\omega_{k,-h}(S^{R}_{-h})^{\dagger}(S^{R}_{k})^{\dagger}$,
$(S^{L}_{g-h})^{\dagger}=\omega^{*}_{g,-h}(S^{L}_{-h})^{\dagger}(S^{L}_{g})^{\dagger}$,
and where we made use of the fact that $\omega$ is a bicharacter to write
$\varsigma_{h}\varsigma_{k}\varsigma_{k-h}^{*}=\omega_{k,h}\omega_{h,k}$. The
action of the suriving shift operators cancels the error on the renormalized
leg, and so in this case,

$\mathcal{C}(R_{g}\otimes R_{h}\otimes R_{k})A_{\omega}^{\otimes
3}=|\Gamma_{\omega}(h-g)\rangle\otimes
R_{h}A_{\omega}\otimes|\Gamma_{\omega}(k-h)\rangle.$ (118)

∎

Note that the above majority-vote property is not true at the level of
operators; it relies projecting onto the space generated by the MPS tensors
$A_{\omega}$.

From the above, we know that $R_{g}$ operators on renormalized legs push
‘down’ through $\mathcal{C}$ to become $R_{g}^{\otimes 3}$. To determine how
an arbitrary operator on a renormalized leg pushes down through $\mathcal{C}$,
we need only determine what happens to $S^{L}_{g}$. We do this with the
following proposition:

######  Proposition 6.

The left shift operator $S^{L}_{g}$ pushes ‘down’ through the circuit as
(recall $\int_{h}\equiv\frac{1}{|G|}\sum_{h\in G}$)

$\displaystyle\mathcal{C}^{\dagger}(\mathbf{1}\otimes
S^{L}_{g}\otimes\mathbf{1})\mathcal{C}$ $\displaystyle=R_{g}\otimes
S^{L}_{g}\otimes\mathbf{1}+\left(S^{L}_{g}\otimes\mathbf{1}\otimes\mathbf{1}-R_{g}\otimes
S^{L}_{g}\otimes\mathbf{1}\right)\int_{k}S^{R}_{k}\otimes R_{k}\otimes
S^{L}_{k}.$ (119)

###### Proof.

$S^{L}_{g}$ moves through the $CS^{R}$ gate for free (as $S^{L}_{g},S^{R}_{h}$
commute), and pushes through the $CS^{L}$ gate as

$\displaystyle(\mathbf{1}\otimes S^{L}_{g}\otimes\mathbf{1})CS^{L}$
$\displaystyle=\sum_{h\in
G}|\Gamma_{\omega}(h)\rangle\langle\Gamma_{\omega}(h)|\otimes
S^{L}_{g}(S^{L}_{h})^{\dagger}\otimes\mathbf{1}$ (120)
$\displaystyle=\sum_{h\in
G}\chi_{g}(\Gamma_{\omega}(h))|\Gamma_{\omega}(h)\rangle\langle\Gamma_{\omega}(h)|\otimes(S^{L}_{h})^{\dagger}S^{L}_{g}\otimes\mathbf{1}$
$\displaystyle=CS^{L}(R_{g}\otimes S^{L}_{g}\otimes\mathbf{1})$

where in the first line we used
$S^{L}_{g}(S^{L}_{h})^{\dagger}=\lambda_{\omega}(-h,g)(S^{L}_{h})^{\dagger}S^{L}_{g}=\chi_{g}(\Gamma_{\omega}(h))(S^{L}_{h})^{\dagger}S^{L}_{g}$.
Now we pull $R_{g}\otimes S^{L}_{g}\otimes\mathbf{1}$ through the $CCR$ gate:

$\displaystyle(R_{g}\otimes S^{L}_{g}\otimes\mathbf{1})CCR$
$\displaystyle=CCR\Big{(}\sum_{h\in
G}R_{g}^{\dagger}|\Gamma_{\omega}(-h)\rangle\langle\Gamma_{\omega}(-h)|\otimes\mathbf{1}\otimes|\Gamma_{\omega}(h)\rangle\langle\Gamma_{\omega}(h)|$
(121) $\displaystyle\qquad+\sum_{h\neq h^{\prime}\in
G}|\Gamma_{\omega}(-h)\rangle\langle\Gamma_{\omega}(-h)|\otimes\mathbf{1}\otimes|\Gamma_{\omega}(h^{\prime})\rangle\langle\Gamma_{\omega}(h^{\prime})|\Big{)}(R_{g}\otimes
S^{L}_{g}\otimes\mathbf{1})$

where we similarly used
$S^{L}_{g}R_{h}^{\dagger}=\chi_{g}(\Gamma_{\omega}(h))R^{\dagger}_{h}S^{L}_{g}$.
The second gate on the RHS has the structure of a controlled-$R_{g}^{\dagger}$
gate acting on the first $\otimes$ factor, with the third $\otimes$ factor
acting as the control. To simplify this, we use

$|g\rangle\langle
g|=\int_{h}R_{h}\chi_{h}^{*}(g)\implies|\Gamma_{\omega}(g)\rangle\langle\Gamma_{\omega}(g)|=\int_{h}R_{h}\lambda_{\omega}^{*}(h,g),$
(122)

which allows us to replace the double control gate with a sum over $R_{h}$
operators. This then lets us write the expression in parenthesis on the RHS of
the above equation as

$\displaystyle|G|\int_{h,h^{\prime}}$
$\displaystyle(\delta_{h,h^{\prime}}(R_{g}^{\dagger}-\mathbf{1})+\mathbf{1})|\Gamma_{\omega}(-h)\rangle\langle\Gamma_{\omega}(-h)|\otimes\mathbf{1}\otimes|\Gamma_{\omega}(h^{\prime})\rangle\langle\Gamma_{\omega}(h^{\prime})|$
(123)
$\displaystyle=|G|^{2}\int_{h,h^{\prime},k,k^{\prime}}\lambda_{\omega}(k,h)\lambda_{\omega}(k^{\prime},-h^{\prime})((R_{g}^{\dagger}-\mathbf{1})\delta_{h,h^{\prime}}+\mathbf{1})(R_{k}\otimes\mathbf{1}\otimes
R_{k^{\prime}})$
$\displaystyle=\int_{k}R_{k}(R_{g}^{\dagger}-\mathbf{1})\otimes\mathbf{1}\otimes
R_{k}+\mathbf{1}^{\otimes 3}.$

While it is not completely obvious in this presentation, the RHS is indeed
unitary as required.

Pushing $\mathbf{1}\otimes S^{L}_{g}\otimes\mathbf{1}$ through the control
gates in $\mathcal{C}$ thus generates the operator
$(\int_{k}(R_{g}^{\dagger}-\mathbf{1})R_{k}\otimes\mathbf{1}\otimes
R_{k}+\mathbf{1}^{\otimes 3})(R_{g}\otimes S_{g}^{L}\otimes\mathbf{1})$. Now
we push these terms through the ring of six MPS tensors in $\mathcal{C}$. This
can be done by noting that $R_{g}\otimes S^{L}_{g}\otimes\mathbf{1}$ pushes
through the ring unchanged,
$R_{g}^{\dagger}\otimes\mathbf{1}\otimes\mathbf{1}$ pushes through to
$S^{R}_{-g}\otimes S^{L}_{-g}\otimes\mathbf{1}$, while
$R_{k}\otimes\mathbf{1}\otimes R_{k}$ pushes through to a 3-site $k$ string
operator:

$R_{k}\otimes\mathbf{1}\otimes R_{k}\rightarrow S^{R}_{k}\otimes R_{k}\otimes
S^{L}_{k}.$ (124)

Therefore as claimed,

$\displaystyle\mathcal{C}^{\dagger}(\mathbf{1}\otimes
S^{L}_{g}\otimes\mathbf{1})\mathcal{C}$ $\displaystyle=R_{g}\otimes
S^{L}_{g}\otimes\mathbf{1}+\left(S^{L}_{g}\otimes\mathbf{1}\otimes\mathbf{1}-R_{g}\otimes
S^{L}_{g}\otimes\mathbf{1}\right)\int_{k}S^{R}_{k}\otimes R_{k}\otimes
S^{L}_{k},$ (125)

where we used $S^{R}_{-g}R_{g}\otimes
S^{L}_{-g}S^{L}_{g}=S^{L}_{g}\varsigma_{g}^{*}\otimes\varsigma_{-g}\mathbf{1}=S^{L}_{g}\otimes\mathbf{1}$.
This expression may also be written more explicitly as

$\displaystyle\mathcal{C}^{\dagger}(\mathbf{1}\otimes
S^{L}_{g}\otimes\mathbf{1})\mathcal{C}$ $\displaystyle=R_{g}\otimes
S^{L}_{g}\otimes\mathbf{1}(1-1/|G|)+\frac{1}{|G|}S^{L}_{g}\otimes\mathbf{1}\otimes\mathbf{1}+\frac{1}{|G|}R_{g}\otimes
R_{g}\otimes S^{L}_{g}$ (126)
$\displaystyle\qquad+\frac{1}{|G|}(S^{L}_{g}\otimes\mathbf{1}\otimes\mathbf{1}-R_{g}\otimes
S^{L}_{g}\otimes\mathbf{1})\sum_{G\ni k\neq e,g}S^{L}_{k}\otimes R_{k}\otimes
S^{L}_{k}-\frac{1}{|G|}R_{g}S^{R}_{g}\otimes S^{L}_{g}R_{g}\otimes S^{L}_{g}$

∎

The point of this rather messy expression is to show that $S^{L}_{g}$ pushes
through the RG circuit to become a renormalized operator which still carries
the same irrep under the adjoint $G$-action as $S^{L}_{g}$ itself (an
analogous calculation for $S^{R}_{g}$ shows that it pushes through to
something where the ‘net’ shift is by $S^{R}_{g}$ for all terms). Note
furthermore that this symmetry-property means that all of the terms on the RHS
of (119) mutually commute with each other; this can be easily demonstrated
explicitly using the commutation relations (81) and (74). Finally, note that
upon iterating this map $d$ times, the number of terms appearing in the
resulting linear combination is doubly-exponential in $d$ — but due to the
symmetry, all such terms transform under the adjoint action in the same way
that $S^{L}_{g}$ itself does.

##  Appendix F Convergence of the RG circuits

In this section we will discuss the convergence of our circuits when run on a
generic state $|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$. We will first
prove that the error correction procedure always succeeds in the limit of
large circuit layer depth $d$, so that the error correction threshold can be
identified exactly with the SPT phase boundary (up to a set of measure zero
where fine-tuned degeneracies prevent convergence). A subsequent section
contains a numerical study of the convergence for a few types of random error
models. In the final section, we show that the circuit does not ‘over-correct’
and produce false-positives.

A note on notation: in this section, we will write
$\mathcal{Q}_{\omega}(\rho)$ for the action of the RG circuit on the density
matrix $\rho$ followed by a tracing out of the ancilla degrees of freedom:

$\mathcal{Q}_{\omega}(\rho)=\text{Tr}_{an}[\mathcal{Q}_{\omega}\rho\mathcal{Q}_{\omega}^{\dagger}].$
(127)

###  F.1 Analytic arguments: convergence of majority vote

Recall that $|\psi_{\omega}\rangle$ can always be written as

$|\psi_{\omega}\rangle=\sum_{\mathbf{g}}C_{\mathbf{g}}R_{\mathbf{g}}|\Psi_{\omega}\rangle,$
(128)

where $\sum_{\mathbf{g}}|C_{\mathbf{g}}|^{2}=1$. 555Note that on a closed
ring, the normalization condition is actually
$\sum_{\mathbf{g},\mathbf{g}^{\prime}}\sum_{h\in
G}\delta_{\mathbf{g},\mathbf{g}^{\prime}+h}C_{\mathbf{g}}^{*}C_{\mathbf{g}^{\prime}}=1,$
(129) where $\mathbf{g}^{\prime}+h$ means adding $h$ to each component of
$\mathbf{g}^{\prime}$. This is just because the global symmetry operator
stabilizes $|\Psi_{\omega}\rangle$. However, we can wolog assume that no two
$C_{\mathbf{g}}$ differ by a constant factor of $h$ on every site, since
$C_{\mathbf{g}}$ and $C_{\mathbf{g}+h}$ act identically on
$|\Psi_{\omega}\rangle$. . As usual, for convenience we will let
$|\psi_{\omega}\rangle$ be defined on a chain of length $L=3^{l}$. Let
$|\Psi_{\omega}^{(d)}\rangle$ denote the canonical representative of
$\mathsf{SPT}_{\omega}$ defined on a chain of length $3^{l-d}$.

######  Proposition 7.

After $d$ applications of $\mathcal{Q}_{\omega}$ on the initial state
$|\psi_{\omega}\rangle\langle\psi_{\omega}|$, the probability
$p_{d}(\mathbf{g})$ that a given error $R_{\mathbf{g}}$ acts on the state
$\mathcal{Q}_{\omega}^{d}(|\psi_{\omega}\rangle\langle\psi_{\omega}|)$ is

$p_{d}(\mathbf{g})=\langle\Psi_{\omega}^{(d)}|R_{\mathbf{g}}^{\dagger}\mathcal{Q}_{\omega}^{d}(|\psi_{\omega}\rangle\langle\psi_{\omega}|)R_{\mathbf{g}}|\Psi_{\omega}^{(d)}\rangle=\sum_{\mathbf{h}\in
G^{L}}\delta(\mathsf{maj}^{d}(\mathbf{h})-\mathbf{g})|C_{\mathbf{h}}|^{2}.$
(130)

###### Proof.

$d$ applications of $\mathcal{Q}_{\omega}$ on
$|\psi_{\omega}\rangle\langle\psi_{\omega}|$ produce the state

$\mathcal{Q}_{\omega}^{d}(|\psi_{\omega}\rangle\langle\psi_{\omega}|)=\sum_{\mathbf{h},\mathbf{h}^{\prime}\in
G^{L}}C_{\mathbf{h}}C_{\mathbf{h}^{\prime}}^{*}R_{\mathsf{maj}^{d}(\mathbf{h})}|\Psi_{\omega}^{(d)}\rangle\langle\Psi_{\omega}^{(d)}|R^{\dagger}_{\mathsf{maj}^{d}(\mathbf{h}^{\prime})}\text{Tr}[|\mathcal{M}_{d}(\mathbf{h})\rangle\langle\mathcal{M}_{d}(\mathbf{h}^{\prime})|]$
(131)

where $|\mathcal{M}_{d}(\mathbf{h})\rangle$ are the measurement outcomes
generated by $d$ layers of the circuit. The probability $p_{d}(\mathbf{g})$ of
getting an error is then found by taking the overlap with the state
$R_{\mathbf{g}}|\Psi^{(d)}_{\omega}\rangle$, giving by way of (66)

$\displaystyle p_{d}(\mathbf{g})$
$\displaystyle=\sum_{\mathbf{h},\mathbf{h}^{\prime}\in
G^{L}}C_{\mathbf{h}}C_{\mathbf{h}^{\prime}}^{*}\langle\Psi_{\omega}^{(d)}|R_{\mathsf{maj}^{d}(\mathbf{h})-\mathbf{g}}|\Psi_{\omega}^{(d)}\rangle\langle\Psi_{\omega}^{(d)}|R_{\mathsf{maj}^{d}(\mathbf{h}^{\prime})-\mathbf{g}}^{\dagger}|\Psi_{\omega}^{(d)}\rangle\delta_{\mathcal{M}_{d}(\mathbf{h})_{M},\mathcal{M}_{d}(\mathbf{h}^{\prime})_{M}}$
(132) $\displaystyle=\sum_{\mathbf{h},\mathbf{h}^{\prime}\in
G^{L}}C_{\mathbf{h}}C^{*}_{\mathbf{h}^{\prime}}\delta_{\mathcal{M}_{d}(\mathbf{h}),\mathcal{M}_{d}(\mathbf{h}^{\prime})}\delta_{\mathbf{g},\mathsf{maj}^{d}(\mathbf{h})}\delta_{\mathsf{maj}^{d}(\mathbf{h}),\mathsf{maj}^{d}(\mathbf{h}^{\prime})}$
$\displaystyle=\sum_{\mathbf{h}\in
G^{L}\,:\,\mathsf{maj}^{d}(\mathbf{h})=\mathbf{g}}|C_{\mathbf{h}}|^{2},$

which is positive and satisfies $\sum_{\mathbf{g}\in
G^{L/3^{d}}}p_{d}(\mathbf{g})=1$. ∎

The probability distribution of errors thus flows under application of the RG
circuit according to recursive majority voting. To understand this flow, we
need to know a bit more about the initial distribution
$p_{0}(\mathbf{g})=|C_{\mathbf{g}}|^{2}$.

First, we will assume that $p_{0}(\mathbf{g})$ is translation-invariant,
meaning that e.g. the single-site marginal probability $p_{0}(g_{i})$ of
finding a $g$ error on site $i$ is independent of $i$. This assumption is made
purely for simplicity of presentation, and is not essential. Second, since
$C_{\mathbf{g}}$ can be identified with the MPO of $R_{\mathbf{g}}$ operators
that relates $|\Psi_{\omega}\rangle$ to $|\psi_{\omega}\rangle$,
$p_{0}(\mathbf{g})$ will have a finite correlation length $\xi$. Letting

$p_{d}(g_{i_{1}},\dots,g_{i_{n}})=\sum_{\\{g_{j}\\}\,:j\,\not\in\\{i_{1},\dots,i_{n}\\}}p_{d}(\mathbf{g})$
(133)

denote the $n$-site marginals of $p_{d}(\mathbf{g})$, this means that
$p_{0}(g_{i},g_{j})\approx p_{0}(g_{i})p_{0}(g_{j})$ when $|i-j|>\xi$. In fact
in the approximation where $|\psi_{\omega}\rangle$ is obtained from
$|\Psi_{\omega}\rangle$ from a constant-depth local (as opposed to quasilocal)
circuit — which is good enough for our purposes — $p_{0}(g_{i},g_{j})$ exactly
factorizes for all $|i-j|>\xi$, by causality.

Finally, we will assume that $p_{0}(\mathbf{g})$ is generic, meaning that
there are no accidental degeneracies among the single-site marginals
$p_{0}(g)$. More specifically, we will assume that for all $g\neq h$,
$|p_{0}(g)-p_{0}(h)|$ is nonzero and independent of system size (e.g. does not
vanish as $1/L$). Situations where this assumption fails are measure zero in
the space of possible probability distributions generated by the circuits
relating $|\psi_{\omega}\rangle$ to $|\Psi_{\omega}\rangle$, and hence will be
ignored.

Our goal in the following is to prove the following claim, which ensures
$\mathcal{Q}_{\omega}^{d\rightarrow\infty}(|\psi_{\omega}\rangle\langle\psi_{\omega}|)=|\Psi_{\omega}\rangle\langle\Psi_{\omega}|,\,\,\,\forall\,\,|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$,
so that the RG flow converges on the correct reference state:

######  Claim 1 (convergence of majority vote).

For a generic translation-invariant starting probability distribution
$p_{0}(\mathbf{g})$ with finite correlation length, the sequence of
distributions $\\{p_{d}(\mathbf{g})\\}$ converges as $d\rightarrow\infty$ to
the product distribution
$p_{d\rightarrow\infty}(\mathbf{g})=\prod_{i}\delta_{g_{i},g_{*}}$, for some
fixed $g_{*}\in G$.

Claim 1 follows easily if one makes an additional (reasonable) assumption
about the initial distribution of errors.

######  Definition 9 (dominance property).

For a probability distribution $p(\mathbf{g})$, let $g_{1}$ be the element for
which the single-site marginal probability $p(g)$ is maximized; $p(g)\leq
p(g_{1})\,\,\forall\,g\in G$. Let $p(g,h,k)=p(g_{i},h_{i+1},k_{i+2})$ denote
the 3-site marginal probability, for arbitrary $i$. The distribution $p(g)$ is
said to be dominant if for all $G\ni g\neq g_{1}$,

$\sum_{h\in G}(p(g_{1},h,g_{1})-p(h,g_{1},h))>\sum_{h\in
G}(p(g,h,g)-p(h,g,h)).$ (134)

This property essentially means that if the single-site marginals $p(g)$ are
maximized on $g_{1}$, then for two strings $\mathbf{g}$ with the same number
of domain walls (occurrences of adjacent non-identical group elements in
$\mathbf{g}$), the one with more occurrences of $g_{1}$ is the one with the
higher probability. To see this, we note that the difference between the LHS
and RHS of (134) can be written as

$\displaystyle\sum_{h\in G}[(p(g_{1},h,g_{1})-p(g,h,g))-(p(h,g_{1},h)$
$\displaystyle-p(h,g,h))]=2(p(g_{1},g,g_{1})-p(g,g_{1},g))$ (135)
$\displaystyle+\sum_{G\ni h\neq
g_{1},g}[(p(g_{1},h,g_{1})-p(g,h,g))-(p(h,g_{1},h)-p(h,g,h))].$

We expect the RHS of (135) to be positive for distributions associated with
ground states of all ‘reasonable’ Hamiltonians. Indeed, the first term
proportional to $p(g_{1},g,g_{1})-p(g,g_{1},g)$ will be positive if for two
configurations with the same number of domain walls, the one with more
instances of $g_{1}$ has higher probability. If this property holds, the
differences
$d_{1}(h)=p(g_{1},h,g_{1})-p(g,h,g),\,d_{2}(h)=p(h,g_{1},h)-p(h,g,h)$ for
$h\neq g_{1},g$ will also be positive. The RHS of (135) will then be positive
if $d_{1}(h)>d_{2}(h)$, which is reasonable since more instances of $g_{1}$s
appear in $d_{1}(h)$.

To see why distributions which are dominant converge as in claim 1, we note
that under majority vote, the single-site marginals at layer $d+1$ are
obtained from the single- and three-site marginals at layer $d$ as

$\displaystyle p_{d+1}(g)$ $\displaystyle=\sum_{h\in
G}p_{d}(g,h,g)+\sum_{h,k\in G}p(h,g,k)-\sum_{h\in G}p(h,g,h)$ (136)
$\displaystyle=p_{d}(g)+\sum_{h\in G}(p_{d}(h,g,h)-p_{d}(g,h,g)).$

Let $\\{g_{a}\\},\,a=1,\dots,|G|$ be an ordering of the elements of $G$ sorted
by decreasing probability, so that $a\leq b\implies p_{d}(g_{a})\geq
p_{d}(g_{b})$. Define the gap

$\delta_{d}\equiv p_{d}(g_{1})-p_{d}(g_{2})$ (137)

to be the difference in probabilities between the most likely and second-most
likely group elements. The gap then evolves under $\mathsf{maj}$ as

$\delta_{d+1}-\delta_{d}=\sum_{h\in
G}[(p_{d}(h,g_{1},h)-p_{d}(g_{1},h,g_{1}))-(p_{d}(h,g_{2},h)-p_{d}(g_{2},h,g_{2}))].$
(138)

If $p_{d}(\mathbf{g})$ obeys the dominance property, the gap clearly
monotonically increases with $d$. A generic initial distribution satisfying
the dominance property thus flows until the gap reaches the maximal size of
$\delta_{d\rightarrow\infty}=1$, implying that all of the probability is
concentrated on a single group element, and that the RG flow converges.

We have to work a bit harder when the initial distribution is not dominant,
because in this case $\delta_{d}$ needn’t be monotonically increasing with
$d$. Indeed, it is possible to construct examples in which $\delta_{d}$
changes nonmonotonically. These examples are rather contrived, but do not
appear to be measure-zero in the space of distributions. We refer to this
phenomenon as Gerrymandering, for obvious reasons:

######  Definition 10.

A series of distributions $p_{d}(\mathbf{g}),d\in\mathbb{N}$ related by
recursive majority voting is said to Gerrymander if there is some $d_{*}$ for
which the single-site marginal $p_{d>d_{*}}(g)$ attains its maximum on
$g_{>}$, while $p_{d\leq d_{*}}(g)$ attains its maximum on $g_{<}\neq g_{>}$.

Any Gerrymandering distribution cannot be dominant, and as we will see
shortly, can also not be iid. It is however possible to construct translation-
invariant Gerrymandered distributions using inter-site correlations. For
example, we may construct a distribution whose initial 3-site marginals are

$p_{0}(g,h,k)=\left(1-(\delta_{h,g_{*}}\delta_{k,g_{*}}+\delta_{k,g_{*}}\delta_{g,g_{*}}+\delta_{h,g_{*}}\delta_{g,g_{*}})+2\delta_{h,g_{*}}\delta_{k,g_{*}}\delta_{g,g_{*}}\right)\left(\alpha\frac{\delta_{g_{*}\in\\{g,h,k\\}}}{3(|G|-1)^{2}}+(1-\alpha)\frac{1-\delta_{g\in\\{g,h,k\\}}}{(|G|-1)^{3}}\right),$
(139)

where $0<\alpha<1$ and $\delta_{a\in\\{g,h,k\\}}$ is unity if
$a\in\\{g,h,k\\}$, and zero else. The first factor in (139) is to ensure that
no two $g_{*}$s occur within a distance of 3 from one another in a way
consistent with translation invariance, implying $p_{1}(g_{*})=0$. However, by
increasing the value of $\alpha$ one can arrange for $p_{0}(g)$ to be
maximized at $g_{*}$ as long as $|G|>2$ ($\alpha<1$ is needed for translation
invariance, which is spontaneously broken at $\alpha=1$). This phenomenon is
robust with respect to relaxing the hard-core constraint on the distribution
of $g_{*}$s, and thus we expect Gerrymandering to occupy a set of nonzero
measure in parameter space.

We now argue that a general distribution (even if it Gerrymanders) will still
converge in the manner of claim 1. We argue in two stages: first, we prove
that if $p_{d}(\mathbf{g})$ is iid for some $d$, meaning that
$p_{d}(\mathbf{g})=\prod_{i}p_{d}(g_{i})$, then
$p_{d\rightarrow\infty}(\mathbf{g})$ converges in the way claimed. Secondly,