we argue that for a generic initial distribution $p_{0}(\mathbf{g})$,
$p_{d}(\mathbf{g})$ can be well-approximated as iid for all $d$ sufficiently
greater than $\log_{3}(\xi)$.

######  Proposition 8.

Let $p_{0}(\mathbf{g})$ be iid, with gap $\delta_{0}$. For any
$\varepsilon>0$, there exists a $d_{\varepsilon}$ such that

$\delta_{d_{\varepsilon}}>1-\varepsilon,$ (140)

so that $d_{\varepsilon}$ sets the scale when $p_{d}(g)$ is $\varepsilon$
close to its $d\rightarrow\infty$ limiting value. The scale $d_{\varepsilon}$
is approximately upper bounded by

$d_{\varepsilon}\leq\ln(1/\varepsilon)+|G|\ln(1/\delta_{0}).$ (141)

###### Proof.

We give a rather lowbrow proof that doesn’t make use of any information-
theoretic properties of the flow of $p_{d}$. From (138), in the iid case we
have

$\delta_{d+1}-\delta_{d}=p_{d}(g_{1})^{2}-p_{d}(g_{2})^{2}-\delta_{d}\sum_{h\in
G}p_{d}(h)^{2}=\delta_{d}\left(2p_{d}(g_{1})(1+\delta_{d}-p_{d}(g_{1}))-\delta_{d}(1+\delta_{d})-\sum_{G\ni
h\neq g_{1},g_{2}}p_{d}(h)^{2}\right).$ (142)

Note that the RHS is bounded as

$p_{d}(g_{1})^{2}-p_{d}(g_{2})^{2}-\delta_{d}\sum_{h\in
G}p_{d}(h)^{2}\geq\delta_{d}p_{d}(g_{2})\geq 0,$ (143)

so that the gap grows monotonically with $d$ (with $\delta_{d+1}-\delta_{d}>0$
as long as $p_{d}(g_{2})>0$ and $\delta_{d}>0$); the iid case thus satisfies
the above dominance condition, and is guaranteed to converge when
$d\rightarrow\infty$.

Now we estimate the convergence time. For a fixed $\delta_{d}$, the difference
$\delta_{d+1}-\delta_{d}$ is readily checked to be minimized on the
distribution where all $p_{d}(h\neq g_{1})$ are identical:

$p_{d}(g_{1})=\frac{1-\delta_{d}}{|G|}+\delta_{d},\qquad p_{d}(h\neq
g_{1})=\frac{1-\delta_{d}}{|G|},$ (144)

with the form of this distribution being preserved under $\mathsf{maj}$. This
is also the distribution which minimizes $p_{d}(g_{1})$ for fixed
$\delta_{d}$. While (144) contains non-generic degeneracies among the
$p_{d}(h\neq g_{1})$, we can consequently use it to upper-bound the time
needed for convergence to be achieved for a fixed starting $\delta_{0}$.
Inserting this distribution on the RHS of (142),

$\frac{\delta_{d+1}-\delta_{d}}{\delta_{d}}=\frac{(1-\delta_{d})(1+\delta_{d}(|G|-1))}{|G|}.$
(145)

Given an initially small gap of $\delta_{0}$, we may write the above for small
$d$ as the differential equation $\dot{\delta}_{d}\approx\delta_{d}/|G|$.
Therefore from an initial small value, $\delta_{d}$ will grow to be of order 1
by the scale

$d_{1}\approx|G|\ln\frac{1}{\delta_{0}}.$ (146)

After the flow reaches $d_{1}$, we may expand in small $\eta_{d}\equiv
1-\delta_{d}$. In terms of $\eta_{d}$, we have

$\eta_{d+1}-\eta_{d}=-\eta_{d}(1-\eta_{d})\left((1-\eta_{d})-\frac{\eta_{d}}{|G|-1}\right)=-\eta_{d}+O(\eta_{d}^{2}),$
(147)

and so after reaching $d_{1}$, we will reach the scale $d_{2}$ at which
$\delta_{d}>1-\varepsilon$ for $d_{2}\approx d_{1}+\ln 1/\varepsilon$.
Therefore up to constants, we approach the limiting distribution within a
distance $\varepsilon$ after $d_{2}$ steps, with

$d_{2}=|G|\ln\frac{1}{\delta_{0}}+\ln\frac{1}{\varepsilon}.$ (148)

Since the above analysis was performed in the worst case, where the flow to
$\delta_{d}>1-\varepsilon$ was as slow as possible, the scale
$d_{\varepsilon}$ is upper bounded in the way claimed.

∎

We now need to argue the following:

######  Proposition 9.

Let $p_{0}(\mathbf{g})$ be a generic distribution with finite correlation
length $\xi$. Then for $d\gg\log_{3}(\xi)$, $p_{d}(\mathbf{g})$ is
approximately iid. That is, for any string $\mathbf{g}_{n}$ of length $n\sim
O(1)$ 666We specialize to such strings rather looking at the individual
probabilities for $\mathbf{g}$ with $|\mathbf{g}|=L$, since for the latter
case the accumulated error will depend on $L$, and hence not be small., the
marginal probabilities factor as

$p_{d}(\mathbf{g}_{n})=\prod_{g\in\mathbf{g}_{n}}p_{d}(g)+\cdots,$ (149)

where the $\cdots$ are terms exponentially suppressed in $d/\log_{3}(\xi)$.

Figure 8:  An illustration of why $p_{d}(g,h)$ approximately factors as
$p_{d}(g)p_{d}(h)$ when $d\gg\log_{3}(\xi)$. Each blue triangle represents a
$\mathsf{maj}$ tree of depth $d$. The input variables $\mathbf{g},\mathbf{h}$
(satisfying
$\mathsf{maj}^{d}(\mathbf{g})=g,\mathsf{maj}^{d}(\mathbf{h})=h,|\mathbf{g}|=|\mathbf{h}|=3^{d}$)
are only correlated over the scale $\xi$; thus the only correlations between
$g$ and $h$ arise from the variables within the indicated region of width
$\xi$. Since the variables wihin this region have a vanishingly small
influence on the outcomes of
$\mathsf{maj}^{d}(\mathbf{g}),\mathsf{maj}^{d}(\mathbf{h})$ in the limit
$\xi\ll 3^{d}$, $p_{d}(g,h)$ approximately factorizes.

###### Proof.

As summarized in Figure 8, this is a very reasonable statement. Consider for
simplicity the 2-site marginal probability $p_{d}(g,h)$ (more complicated
marginals are treated in a similar way). For large $d$, $p_{d}(g)$ is
determined by the distribution $p_{0}(\mathbf{g}_{d})$, where $\mathbf{g}_{d}$
has length $|\mathbf{g}_{d}|=3^{d}$ and runs over variables in the
$\mathsf{maj}$ tree of depth $d$ that outputs $g$. Since
$p_{0}(\mathbf{g}_{d})$ is correlated only over the scale $\xi$, when
$3^{d}\gg\xi$ the variables at the bases of two adjancent depth-$d$
$\mathsf{maj}$ trees contributing to $p_{d}(g,h)$ will recieve correlations
only from a region of size $\xi$ located where the bases of the two trees
touch. Since the variables in this region have almost no influence on the
outcomes of the two majority trees, $p_{d}(g,h)$ consequently nearly
factorizes (see Fig. 8).

Now we try to make this inuitive argument more rigorous. As mentioned above,
we can without loss of generality take correlations in the initial
distribution $p_{0}(\mathbf{g})$ to be exactly vanishing on scales greater
than $\xi$. This consequently implies that as soon as $3^{d}>\xi$, the
correlations in $p_{d}(\mathbf{g})$ are purely nearest-neighbor, implying e.g.

$d>\log_{3}(\xi)\implies\sum_{h\in G}p_{d}(g,h,k)=p_{d}(g)p_{d}(k).$ (150)

Let $d_{\xi}=\lceil\log_{3}(\xi)\rceil$ and define $l\equiv d-d_{\xi}$. Then

$\displaystyle p_{d}(g,h)$ $\displaystyle=\sum_{\mathbf{g},\mathbf{h}\in
G^{3^{l}}}p_{d_{\xi}}(\mathbf{g},\mathbf{h})\delta_{\mathsf{maj}^{l}(\mathbf{g}),g}\delta_{\mathsf{maj}^{l}(\mathbf{h}),h}.$
(151)

Because of (150), $p_{d}(g,h)$ would factorize exactly if we were able to
perform an unrestricted sum on the element $g_{3^{l}}$, which is located at
the boundary between the bases of the two depth-$l$ $\mathsf{maj}$ trees
leading to $g$ and $h$. The thing which prevents us from doing so is of course
the factor of $\delta_{\mathsf{maj}^{l}(\mathbf{g}),g}$. However, when
$3^{l}\gg\xi$, we expect the outcome of the majority vote
$\mathsf{maj}^{l}(\mathbf{g})$ to be largely insensitive to the exact value of
$g_{3^{l}}$: in the vast majority of cases, the value of the element
$g_{3^{l}}$ will not by itself be able to sway the outcome of the majority
vote. We thus claim that

$p_{d_{\xi}+l}(g,h)=p_{d_{\xi}+l}(g)p_{d_{\xi}+l}(h)+\cdots,$ (152)

where $\cdots$ is exponentially small in $l$.

We can quantify this expectation by computing the conditional entropy
$H(\mathsf{maj}^{l}(\mathbf{g})|g_{1},\dots,g_{3^{l}-1})$. This entropy
vanishes if $\mathsf{maj}^{l}(\mathbf{g})$ can be determined from
$g_{1},\dots,g_{3^{l}-1}$ alone, without the need to know the value of the
remaining element $g_{3^{l}}$. In general
$H(\mathsf{maj}^{l}(\mathbf{g})|g_{1},\dots,g_{3^{l}-1})$ is nonzero, but is
nevertheless exponentially small in $l$. Indeed, given a scheme for predicting
$\mathsf{maj}^{l}(\mathbf{g})$ from $g_{1},\dots,g_{3^{l}-1}$, we can bound
$H(\mathsf{maj}^{l}(\mathbf{g})|g_{1},\dots,g_{3^{l}-1})$ using Fano’s
inequality as

$H(\mathsf{maj}^{l}(\mathbf{g})|g_{1},\dots,g_{3^{l}-1})\leq
H(p_{e})+p_{e}\ln(|G|-1),$ (153)

where $p_{e}$ is the probability of our prediction scheme giving the wrong
answer, and $H(x)=-x\ln x-(1-x)\ln(1-x)$ is the binary Shannon entropy.

Given $g_{1},\dots,g_{3^{l}-1}$, we can exactly determine the values of all
nodes in the ternary tree computing $\mathsf{maj}^{l}$ except for those on the
tree’s rightmost flank. For example, when $l=2$ we can determine all of the
nodes of the following tree, except those marked in yellow:

(154)

One estimate for $\mathsf{maj}^{l}(\mathbf{g})$ given
$g_{1},\dots,g_{3^{l}-1}$ is to assume that the result of the majority vote on
the last three elements $g_{3^{l}-2},g_{3^{l}-1},g_{3^{l}}$ is just the
central element $g_{3^{l}-1}$ (since the central element wins in the case of
ties), and to then assign the remaining nodes of the majority tree according
to this choice. In order for this estimate to be in error, the choice of
$g_{3^{l}}$ must be able to change the outcomes of every majority vote
occuring on the right flank of the $\mathsf{maj}$ tree (the yellow nodes in
the above figure). Since the probability of changing each of these majority
votes is less than 1, the error probability $p_{e}$ will accordingly be
exponentially small in $l$.

More precisely, in order for this estimate to be incorrect, we first need that
$g_{3^{l}-2}=g_{3^{l}}\neq g_{3^{l}-1}$, so that the value of the ‘deepest’
majority vote on the right flank of the $\mathsf{maj}$ tree, viz.
$\mathsf{maj}(g_{3^{l}-2},g_{3^{l}-1},g_{3^{l}})$, disagrees with our guess of
$g_{3^{l}-1}$. The probability of this disagreement happening is less than 1
unless $p_{d_{\xi}}(g,h,k)\propto\delta_{g,k}$ for all $g,h,k$ — but this is
impossible, as summing over $h$ would produce
$p_{d_{\xi}}(g)p_{d_{\xi}}(k)\propto\delta_{g,k}$, which can be true only if
$p_{d_{\xi}}(g)\neq 0$ only for a single $g$ (in which case $\mathsf{maj}$ has
already converged). A similar argument applies for each node along the right
flank of the majority tree, where the probability of an error occuring given a
change in the rightmost member of a $\mathsf{maj}$ vote is strictly less than
1, unless $\mathsf{maj}$ has already converged. Thus $p_{e}$ is a product of
$l$ numbers less than 1, and consequently is exponentially small in $l$
(unfortunately explicitly calculating $p_{e}$ in terms of
$p_{d_{\xi}}(\mathbf{g})$ is rather complicated). By Fano’s inequality this
implies that $H(\mathsf{maj}^{l}(\mathbf{g})|g_{1},\dots,g_{3^{l}-1})$ is also
exponentially small in $l$, meaning that performing an unrestricted sum over
$g_{3^{l}}$ in (151) can be done while incurring only an exponentially small
error. This then implies (152). ∎

Figure 9:  String order parameters measured at different depths $d$ of an RG
circuit acting on the ground states of a family of $\mathbb{Z}_{2}$ deformed
cluster state Hamiltonians (13). Grey triangles denote the correlation length.
Figure 10:  As in Fig. 9, except with the wavefunction incurring an additional
error (symmetry action) on each site with probability $\sin^{2}(25^{\circ})$
(note the different scale on the $y$-axis).

###  F.2 Numerical tests of convergence

The numerical results in Figure 5 were obtained by running our RG circuit on
the ground states obtained from the simple family of Hamiltonians given by
(13). For this class of Hamiltonians, the initial distribution of errors
$p_{0}(\mathbf{g})$ can be determined straightforwardly within perturbation
theory. The density of errors for these models is low except when one is close
to the boundary of $\mathsf{SPT}_{\omega}$, and thus we expect (and indeed
observe) our circuit to converge rather rapidly in most of parameter space.

One simple way of making the circuit’s life more difficult (with the aim of
performing a more stringent test of the convergence of our RG flow) is to act
on a given input ground state with a depth-1 circuit that performs a symmetric
rotation at each site, as was done in the main text near (14). For the case of
the $\mathbb{Z}_{2}$ version of the perturbed cluster state model (13), this
can be done simply by acting with the unitary
$\bigotimes_{i}(\cos\theta+Z_{i}\sin\theta)$ (where in keeping with the
previous appendicies, we are working in a basis where the symmetry is
generated by $Z_{j}$ operators on each site). Fig. 9 shows how our RG circuit
performs on ground states drawn from a particular cut in the parameter space
of the Hamiltonian (13), and Fig. 10 shows how the performance is altered when
acting on the same ground states with the above unitary. In the latter case
the signals from the string operators are suppressed, but the pattern of
convergence with increasing circuit depth is similar.

To test the flow induced by the majority voting process more explicitly, we
can examine the flow of error probability distributions $p_{0}(\mathbf{g})$
drawn from various ensembles not directly tied to the ground states of any
simple family of Hamiltonians. Continuing to specify to the case of
$\mathbb{Z}_{2}^{2}$ SPT phases, as one example we can consider the error
distribution associated with the consistant depth symmetric circuit

$\mathcal{U}_{\theta}=\bigotimes_{i}\prod_{a=1}^{k}\exp\left(i\theta_{a}\bigotimes_{j=i}^{i+k}Z_{j}\right),$
(155)

where the $\theta_{a}$ are iid random variables drawn from some distribution
on $[0,2\pi)$. This yields the error distribution

$p_{e}(\mathbf{g})=\underset{\\{\theta_{a}\\}}{\mathbb{E}}\left[\langle+|\mathcal{U}_{\theta}^{\dagger}\bigotimes_{i=1}^{L}\left(\frac{1+(-1)^{g_{i}}X_{i}}{2}\right)\mathcal{U}_{\theta}|+\rangle\right],$
(156)

where $|+\rangle=(|0\rangle+|1\rangle)^{\otimes L}$. As another example, we
can take the error probabilities to be generated by sampling from a random MPS
(thereby encorporating a small amount of spatial correlation into the error
distribution); in this case

$p_{e}(\mathbf{g})=\langle\phi_{\chi}|\Pi_{\mathbf{g}}|\phi_{\chi}\rangle,$
(157)

where $|\phi_{\chi}\rangle$ is a translation-invariant MPS wavefunction
constructed from a random MPS tensor of fixed bond dimension $\chi$.

Figure 11:  Convergence of the flow induced by our RG circuit for two
different random error models. Here $\mkern
1.5mu\overline{\mkern-1.5mu\delta\mkern-1.5mu}\mkern 1.5mu_{d}$, the average
gap between the most likely and second most likely single-site marginals, is
plotted as a function of the depth $d$; the flow converges when $\mkern
1.5mu\overline{\mkern-1.5mu\delta\mkern-1.5mu}\mkern 1.5mu_{d}\rightarrow 1$.
In the blue curves, the errors are sampled from random MPS wavefunctions with
bond dimensions $\chi=2,4$, while in the blue curves they are sampled using
the error model of (156) with $k=2,3$.

In Fig. 11 we numerically illustrate the convergence of the majority voting
process under these two error models for errors applied to a system of size
$L=3^{7}=2187$. Let $\bar{\delta}_{d}$ be the average gap at layer $d$ between
the two largest values of the single-site marginals $p_{d}(g)$, as in (137).
We consider ranges $k=2,3$ and bond dimensions $\chi=2,4$, obtaining the
evolution of $\mkern 1.5mu\overline{\mkern-1.5mu\delta\mkern-1.5mu}\mkern
1.5mu_{d}$ shown in the figure. The error model derived from the circuit
$\mathcal{U}_{\theta}$ with $k=3$ displays the smallest expected gap $\mkern
1.5mu\overline{\mkern-1.5mu\delta\mkern-1.5mu}\mkern 1.5mu_{d}$, but still
shows a clear trend towards convergence with increasing $d$.

###  F.3 No false positives

We now show that $\mathcal{Q}_{\omega}$ does not produce false positives, i.e.
that for $\nu\neq\omega$, $\mathcal{Q}_{\omega}$ does not mistakenly converge
to $|\Psi_{\omega}\rangle$ if given $|\psi_{\nu}\rangle$ as input. That this
holds can in fact be argued on general grounds using the results of [37],
wherein it was shown that any quantum channel whose Kraus operators commute
with the symmetry action cannot map
$|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$ to
$|\psi_{\nu}\rangle\in\mathsf{SPT}_{\nu}$ if $\omega\neq\nu$.
$\mathcal{Q}_{\omega}$ enjoys precisely this symmetry-property: from (115) we
see that $(\mathbf{1}\otimes
R_{g}\otimes\mathbf{1})\mathcal{C}=\mathcal{C}R_{g}^{\otimes 3}$, implying
that the symmetry pushes through $\mathcal{Q}_{\omega}$ to operate on just the
renormalized legs:

$\mathcal{Q}_{\omega}[(R_{g}^{\dagger})^{\otimes 3^{l}}\rho\,R_{g}^{\otimes
3^{l}}]=(R_{g}^{\dagger})^{\otimes
3^{l-1}}\mathcal{Q}_{\omega}(\rho)R_{g}^{\otimes 3^{l-1}}$ (158)

for any density matrix $\rho$. This then implies that exactly the desired
condition is satisfied by the Kraus operators of $\mathcal{Q}_{\omega}$, so
that the claim follows.

##  Appendix G Identifying spontaneous symmetry breaking with RG circuits

In this appendix we briefly discuss how to construct an RG circuit which
recognizes phases with and without spontaneous symmetry breaking of an
internal finite Abelian symmetry $G$. As with the SPT case, the RG circuit has
the merit of being able to reduce the sample complexity of phase recognition
near the critical point, and provides a direct link between error correction
and RG flow.

The construction parallels that of the architecture used for recognizing SPT
phases, but as there exists a standard local order parameter for diagnosing
symmetry breaking the construction is much simpler (see [6, 68]). As in the
rest of the paper, the setting will be on a 1d chain of length $L$.

Define the linear symmetry and shift operators as

$R_{g}\equiv\sum_{h\in G}\chi_{g}(h)|h\rangle\langle h|,\qquad
S_{g}\equiv\sum_{h\in G}|{g+h}\rangle\langle{h}|,$ (159)

which obey $R_{g}S_{h}=\chi_{g}(h)S_{h}R_{g}$. We will take the global
symmetry to be generated by the operators $S_{g}^{\otimes L}$ 777In our
discussion of SPT phases we worked in a basis where the symmetry generators
were diagonal, since in that case we were only interested in symmetric phases.
Here we are focused on phases with SSB, and taking the symmetry generators to
be off-diagonal is more natural.. By character orthogonality, any operator can
be expanded in terms of the $R_{g}$ and $S_{h}$; the proof is analogous to
that of (97). While we will not specify a particular Hamiltonian, for
concreteness one could simply take a $G$-generalization of the standard Ising
model, e.g.

$H=-\sum_{i}\sum_{g\in G}\left(R_{-g,i}\otimes R_{g,i+1}+\lambda
S_{g,i}\right)$ (160)

where the real constant $\lambda$ tunes between the symmetric and SSB phases.

Denote the symmetric phase by $\mathsf{PARA}$, and let $\mathsf{SSB}$ denote
the phase where $G$ is spontaneously broken. We take $\mathsf{SSB}$ to be a
direct sum over all superslection sectors, including states where $R_{g}$ has
all nonzero expectation values. Our goal will be to construct a circuit
$\mathcal{Q}_{\omega}$ for classifying whether a given wavefunction is in
$\mathsf{PARA}$, or in $\mathsf{SSB}$. The reason for defining $\mathsf{SSB}$
as a union over all superselection sectors is that we will not require
$\mathcal{Q}_{\omega}$ to correctly reproduce the superselection sector a
given $|\psi\rangle\in\mathsf{SSB}$ belongs to. This is because as in our
analysis of SPT phases, we define phases by equivalence classes of
wavefunctions under symmetric local constant-depth circuits, which can permute
between superselection sectors (consider the depth-1 symmetric local circuit
$S_{g}^{\otimes L}$, for example).

Consider a wavefunction $|\psi\rangle$ drawn from $\mathsf{SSB}$.
$|\psi\rangle$ can be obtained from the product state
$|{\mathbf{0}}\rangle\equiv|0\rangle^{\otimes L}$ by a constant-depth
symmetric circuit built from combinations of $S_{h,i}$ and $R_{h,i}\otimes
R_{-h,j}$ operators, with bounded $|i-j|$. Since the $R_{h}$ operators act as
c-numbers on $|{\mathbf{0}}\rangle$, they can effectively be ignored, and we
may write

$|\psi\rangle=\sum_{\mathbf{g}}C_{\mathbf{g}}|\mathbf{g}\rangle.$ (161)

where the complex coefficients $C_{\mathbf{g}}$ satisfy
$\sum_{\mathbf{g}}|C_{\mathbf{g}}|^{2}=1$ and produce a wavefunction with a
finite correlation length.

Figure 12:  Coarse-graining layer used for performing RG to identify the
symmetry breaking phase of a theory with an Abelian symmetry group $G$.
$g,h,k\in G$, and the $\pm$ signs denote the type of controlled shift gate
applied ($CS_{\pm}$ or $CCS_{\pm}$; in the case $G=\mathbb{Z}_{2}$ these are
just CNOT and CCNOT). The left (right) measurement leg is left in a state
which keeps track of the presence of a domain wall between the first and
second (second and third) input legs, and the renormalized leg becomes the
majority of the inputs.

We now construct a circuit which performs RG on $|\psi\rangle$ simply by
implementing majority vote on the strings $\mathbf{g}$. The convolution module
$\mathcal{C}_{SSB}$ that we use for this purpose is built out of controlled
shift gates $CS_{\pm},CCS_{\pm}$, defined as the $G$-generalizations of CNOT
and Toffoli gates:

$\displaystyle CS_{\pm}$ $\displaystyle\equiv\sum_{g,h\in G}|g\rangle\langle
g|\otimes|{h\pm g}\rangle\langle{h}|,$ (162) $\displaystyle CCS_{\pm}$
$\displaystyle\equiv\sum_{g,h\in G}|g\rangle\langle g|\otimes|g\rangle\langle
g|\otimes|{h\pm g}\rangle\langle{h}|.$

Majority voting on $G$ can be acommplished using the choice of
$\mathcal{C}_{SSB}$ shown in figure 12, which consists of a pair of $CS_{-}$
gates controlled by the central ‘renormalized’ leg, and a single $CCS_{+}$
gate controlled by the two measurement legs. It is straightforward to check
that

$\mathcal{C}_{SSB}(|g\rangle\otimes|h\rangle\otimes|k\rangle)=|g-h\rangle\otimes|\mathsf{maj}(g,h,k)\rangle\otimes|k-h\rangle.$
(163)

The values of the measurement legs thus keep track of domain walls between the
left / right and central tensor factors, while the value of the renormalized
leg is determined by majority vote. Constructing a circuit
$\mathcal{Q}_{\omega}$ from $\mathcal{C}_{SSB}$ in the same way as in the main
text, we see that $\mathcal{Q}_{\omega}$ will converge to a reference product
state $|g\rangle^{\otimes L}$ for some $g\in G$ as long as the recursive
majority vote converges, which it will in the absence of fine tuning, as
argued previously. Note that the value of $g$ which it converges to may not
correpond to the superselection sector in which $|\psi\rangle$ lies, as made
clear by the Gerrymandering example of (139). This however is enough for our
purposes.

Finally, consider the case when $|\psi\rangle$ is drawn from $\mathsf{PARA}$.
$|\psi\rangle$ can then be constructed by applying operators of the form
$R_{g,i}\otimes R_{-g,j}$ to the reference state $|+\rangle^{\otimes L}$,
where $|+\rangle=\frac{1}{\sqrt{|G|}}\sum_{g\in G}|g\rangle$. We claim that
the RG circuit will never incorrectly classify $|\psi\rangle$ as being in
$\mathsf{SSB}$, and that the distribution of group elements measured will
remain uniformly random at all circuit depths. As in the SPT case, this
follows from a symmetry argument. It is easy to check that $\mathcal{C}_{SSB}$
commutes with the symmetry group, in that

$\mathcal{C}_{SSB}(S_{g}\otimes S_{g}\otimes S_{g})=(\mathbf{1}\otimes
S_{g}\otimes\mathbf{1})\mathcal{C}_{SSB}.$ (164)

Consider then the expectation value of $R_{g}$ on an arbitrary site at some
depth $d$ of the circuit. We have

$\displaystyle\text{Tr}[R_{g}\mathcal{Q}_{\omega}^{d}(|\psi\rangle\langle\psi|)]$
$\displaystyle=\chi^{*}_{g}(h)\text{Tr}[(S_{h}^{\dagger})^{\otimes
L/3^{d}}R_{g}S_{h}^{\otimes
L/3^{d}}\mathcal{Q}_{\omega}^{d}(|\psi\rangle\langle\psi|)]$ (165)
$\displaystyle=\chi^{*}_{g}(h)\text{Tr}[R_{g}\mathcal{Q}_{\omega}^{d}((S_{h}^{\dagger})^{\otimes
L}|\psi\rangle\langle\psi|S_{h}^{\otimes L})]$
$\displaystyle=\chi^{*}_{g}(h)\text{Tr}[R_{g}\mathcal{Q}_{\omega}^{d}(|\psi\rangle\langle\psi|)]$

since $|\psi\rangle\in\mathsf{PARA}$ is symmetric. Since this holds for any
$g,h$, the LHS must vanish for all $d$.

##  Appendix H Error correction with measurements and classical post-
processing

We have seen that the RG circuit essentially performs a classical error
correction procedure on an input wavefunction
$|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$. One is naturally then led to
ask: to what extent is the full RG circuit architecture actually needed for
phase identification? As demonstrated above, the whole implementation of the
RG circuit circuit can be effectively replaced by the direct measurement of
the multiscale string order parameters, at least as far as phase
identification is concerned. However, the multiscale string operator is rather
complicated, and contains a very large number of terms. Is there an easier way
out, which lets a collection of simple local measurements bypass the work done
by the RG circuit? In particular, given that the job of the circuit is to
perform a classical error correction of the local symmetry actions, can it
simply be replaced by a simpler one-shot measurement of the local errors,
together with classical data post-processing? In this appendix we argue that
the answer to this question is likely no.

For the purposes of this discussion it will help to introduce the
disentangling operators

$\mathscr{D}_{\omega}\equiv\sum_{\mathbf{g}\in
G^{2L}}\text{Tr}\left[\prod_{i=1}^{L}(A_{\omega}^{g_{2i}})^{*}(A_{\omega}^{g_{2i+1}})^{T}\right]\bigotimes_{j=1}^{L}|{g_{2j}}\rangle\langle{g_{2j+1}}|=\vbox{\hbox{\includegraphics[width=195.12767pt]{figures/disentangler}}}.$
(166)

The disentangler $\mathscr{D}_{\omega}$ gets its name from the fact that it
converts $|\Psi_{\omega}\rangle$ to the product state
$|\Psi_{0}\rangle=|0\rangle^{\otimes L}$ and vice-versa:

$\mathscr{D}_{\omega}|\Psi_{\omega}\rangle=|\Psi_{0}\rangle,$ (167)

as can easily be checked using the perfect tensor condition (59).

The utility of $\mathscr{D}_{\omega}$ is that given
$|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$, it lets us easily sample from
the distribution of errors acting on $|\psi_{\omega}\rangle$. As before, let
the error amplitudes of $|\psi_{\omega}\rangle$ be $C_{\mathbf{g}}$. Using
(57) and (106), we obtain

$\mathscr{D}_{\omega}|\psi_{\omega}\rangle=\sum_{\mathbf{g}\in
G^{L}}C_{\mathbf{g}}\bigotimes_{i=1}^{L}|\Gamma_{\omega}(g_{i+1}-g_{i})\rangle.$
(168)

Applying $\mathscr{D}_{\omega}$ and then measuring in the $R_{g}$ basis thus
lets us directly sample the probability distribution of errors. Indeed,
consider the distribution $p^{\omega}_{e}(\mathbf{g})$, defined by

$p^{\omega}_{e}(\mathbf{g})=\langle\psi_{\omega}|\mathscr{D}_{\omega}^{\dagger}\Pi_{\mathbf{g}}\mathscr{D}_{\omega}|\psi_{\omega}\rangle,$
(169)

with the projector

$\Pi_{\mathbf{g}}\equiv\bigotimes_{i=1}^{L}\int_{h\in
G}\chi^{*}_{h}(g_{i})R_{h,i}.$ (170)

As argued above, at a generic point in $\mathsf{SPT}_{\omega}$, the recursive
majority function $\mathsf{maj}$ applied to samples obtained from the
distribution $p_{e}^{\omega}(\mathbf{g})$ will converge to a fixed point where
$p_{e}^{\omega}(g)$ has support on only a single group element $g_{*}$.
Furthermore, the convergence scale obtained in this way will agree with the
convergence scale of the actual RG circuit. Thus measurements and classical
data processing suffice to determine how ‘far’ $|\psi_{\omega}\rangle$ is from
$|\Psi_{\omega}\rangle$, given the promise that
$|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$.

However, if one is not promised that
$|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$, the full architecture of the
RG circuit cannot simply be replaced by the depth-1 disentangling circuit
$\mathscr{D}_{\omega}$, together with the classical data processing required
to compute $\mathsf{maj}^{d}(p^{\omega}_{e}(\mathbf{g}))$. To see this, define
the distributions

$p_{e}^{\omega,\nu}(\mathbf{g})=\langle\psi_{\nu}|\mathscr{D}_{\omega}^{\dagger}\Pi_{\mathbf{g}}\mathscr{D}_{\omega}|\psi_{\nu}\rangle,$
(171)

where $\psi_{\nu}\in\mathsf{SPT}_{\nu}$ (with $\nu=0$ being the trivial
paramagnetic phase). In order for the phase identification ability of the
circuit to be replaced by the action of $\mathscr{D}_{\omega}$ together with
classical data processing, we require that if $\nu\neq\omega$, then
$\mathsf{maj}^{d}$ does not converge when acting on samples obtained from
$p_{e}^{\omega,\nu}(\mathbf{g})$. That is, for $\omega\neq\nu$, we require
that the marginal distribution $p_{e}^{\omega,\nu}(g)$ be uniformly random on
$G$. This is however not generically true, as we now argue.

Consider first the case where the input wavefunction is the product state
$|\Psi_{0}\rangle$ (we will see in a moment that this case is special). Since
$\mathscr{D}_{\omega}|\Psi_{0}\rangle=|\Psi_{\omega}\rangle$, the marginal
probability for a single-site error is

$p_{e}^{\omega,0}(g)=\langle\Psi_{0}|\mathscr{D}_{\omega}^{\dagger}\Pi_{g}\mathscr{D}_{\omega}|\Psi_{0}\rangle=\int_{h}\chi^{*}_{h}(g)\langle\Psi_{\omega}|R_{h}|\Psi_{\omega}\rangle=\widetilde{f}(g),$
(172)

where $\widetilde{f}(g)$ is the Fourier transform of
$f(g)=\langle\Psi_{\omega}|R_{g}|\Psi_{\omega}\rangle$. For
$\mathsf{maj}^{d}(p_{e}^{\omega,0}(\mathbf{g}))$ to generically fail to
converge, $p_{e}^{\omega,0}(g)$ should be uniformly distributed on $G$. This
is true only if $f(g)\propto\delta_{g,e}$, i.e. only if
$\langle\Psi_{\omega}|R_{g}|\Psi_{\omega}\rangle\propto\delta_{g,e}$. In the
present case this is indeed true, as can easily be checked using the
injectivity of the canonical MPS tensor $A_{\omega}$ and the fact that
$\text{Tr}[V_{g}]=\propto\delta_{g,e}$.

However, while $p^{\omega,0}_{e}(g)$ is uniformly random when
$|\psi_{0}\rangle=|\Psi_{0}\rangle$ is an exact product state, we claim that
$p^{\omega,0}_{e}(g)$ is not generically be uniform throughout the
paramagnetic phase $\mathsf{SPT}_{0}$. Indeed, since $R_{h}$ commutes with the
symmetry action, there is no selection rule which generically enforces
$\langle\psi_{0}|\mathscr{D}_{\omega}^{\dagger}R_{g}\mathscr{D}_{\omega}|\psi_{0}\rangle\propto\delta_{g,e}$,
and the expectation value will generically be nonzero.

More precisely, consider a generic wavefunction
$|\psi_{0}\rangle\in\mathsf{SPT}_{0}$. Since $R_{g,i}$ acts trivially on
$|\psi_{0}\rangle$ for all $i,g$, $|\psi_{0}\rangle$ may be obtained from the
trivial product state $|\Psi_{0}\rangle$ through a circuit of the form

$|\psi_{0}\rangle=\sum_{i>j}\sum_{g\in
G}D_{i-j}(g)S^{L}_{g,i}S^{R}_{g,j}|\Psi_{0}\rangle,$ (173)

where we have without loss of generality chosen a basis of symmetric operators
to be generated by the linear symmetry generators (which act trivially on
$|\Psi_{0}\rangle$) and the shift operators $S^{L/R}_{g}$ for the cohomology
class $\omega$. When we act on this wavefunction with $\mathscr{D}_{\omega}$,
we obtain

$\mathscr{D}_{\omega}|\psi_{0}\rangle=\sum_{\mathbf{g}}D^{\prime}_{\mathbf{g}}R_{\mathbf{g}}|\Psi_{\omega}\rangle,$
(174)

where the coefficients $D^{\prime}_{\mathbf{g}}$ are generically rather
complicated functions of the $D_{i-j}(g)$ 888In the case where the
coefficients $D_{i-j}(g)$ are all 2-local, being nonzero only when $i=j+1$, we
have simply $D^{\prime}_{\mathbf{g}}=\prod_{i}D_{1}(g_{i})$. . The point here
is that $\mathscr{D}_{\omega}|\psi_{0}\rangle$ is simply some generic
wavefunction $|\psi^{\prime}_{\omega}\rangle\in\mathsf{SPT}_{\omega}$. Such a
generic wavefunction will not be such that
$\langle\psi^{\prime}_{\omega}|R_{g}|\psi^{\prime}_{\omega}\rangle$ vanishes
for all $g\neq e$, since there is no symmetry reason for this to be so (that
$\langle\psi^{\prime}_{\omega}|R_{g}|\psi^{\prime}_{\omega}\rangle\neq 0$ for
all $g\neq e$ generically is also confirmed in our numerics).

##  Appendix I Different $G$-representations

In this paper we have focused on the case in which $G$ is represented in the
regular representation (a direct sum of each $G$ irrep, with each irrep
entering with multiplicity one) on a Hilbert space $\mathcal{H}_{reg}$ of
dimension $|G|$:

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

Of course, a given physical system might be in some other representation
$r_{g}$ of $G$ other than the regular representation, with the local Hilbert
space $\mathcal{H}_{r}$ of dimension $\dim\mathcal{H}_{r}\neq|G|$. A prominent
example of such a situation is the Haldane chain. Here a
$G=\mathbb{Z}_{2}^{2}$ symmetry is represented on a spin-1 Hilbert space
$\dim\mathcal{H}_{r^{Hald}}=3$ in a way which does not include the trivial
representation:

$r^{Hald}_{g}=\begin{pmatrix}\chi_{(1,0)}(g)&&\\\ &\chi_{(0,1)}(g)&\\\
&&\chi_{(1,1)}(g)\end{pmatrix},$ (176)

with the elements $(1,0)$ and $(0,1)$ corresponding to $\pi$ rotations about
the ${\mathbf{\hat{x}}}$ and ${\mathbf{\hat{y}}}$ axes, respectively. In
general, the symmetry will be represented as

$r_{g}=\sum_{h\in
G:N_{h}>0}\sum_{\alpha=1}^{N_{h}}\chi_{h}(g)|h,\alpha\rangle\langle
h,\alpha|,$ (177)

where the degeneracies $\\{N_{h}\\}$ are non-negative integers. One choice of
(unnormalized) representative wavefunctions $|\Psi_{\omega}^{r}\rangle$ for an
SPT in which $G$ acts as (177) is999We will continue to specify to maximally
non-commutative $\omega$ throughout this discussion.

$|\Psi^{r}_{\omega}\rangle=\sum_{\\{g_{i}\\}\in
G^{L}:N_{g_{i}}>0\,\forall\,i}\text{Tr}[A^{g_{1}}_{\omega}\cdots
A^{g_{L}}_{\omega}]\bigotimes_{i=1}^{L}\sum_{\alpha_{i}=1,\dots,N_{g_{i}}}|g_{i},\alpha_{i}\rangle,$
(178)

which is uniform in degeneracy space and which otherwise is obtained simply by
restricting the regular representation reference state
$|\Psi_{\omega}^{R}\rangle$ to those group elements such that $N_{g}>0$ (in
the case of the Haldane phase, $|\Psi_{\omega}^{r^{Hald}}\rangle$ is simply
the AKLT state). It is straightforward to check that the symmetry
fractionalizes on $|\Psi^{r}_{\omega}\rangle$ according to the cohomology
class $\omega$. It is also the case that $|\Psi^{r}_{\omega}\rangle$ is
injective for all projectively faithful representations of $G$ (the ones we
care about when doing quantum mechanics), as we prove below in proposition 10.
Thus for each $r,\omega$, $|\Psi^{r}_{\omega}\rangle$ indeed constitutes an
allowed reference state.

From this starting point, and with the symmetry representation fixed to be
$r_{g}$, one approach would be to design an RG circuit acting on the onsite
Hilbert space $\mathcal{H}_{r}$, which maps any input wavefunction in
$\mathsf{SPT}_{\omega}$ to the reference state $|\Psi^{r}_{\omega}\rangle$.
While such a construction is likely possible, it would likely require
developing an architecture distinct from the architecture we developed for the
regular representation, as the MPS tensors of $|\Psi^{r}_{\omega}\rangle$ will
not generically be perfect tensors, and the set of $G$-symmetric local unitary
operators will not generically be generated purely by the set of string
operators and local symmetry actions.

Because of these complications, and because in this work we are primarily
interested in illustrating a proof of principle, we will resort to a different
approach. First, it is always possible to embed a model in which $G$ is
represented as $r_{g}$ on a system with local Hilbert space $\mathcal{H}_{r}$
into a model defined on the local Hilbert space $\mathcal{H}_{reg}$, on which
$G$ acts as the regular representation. This embedding is achieved via a local
symmetric isometry $I=\bigotimes_{i}I_{i}$,
$I_{i}^{\dagger}I_{i}=\mathbf{1}_{i}$, where the isometry at each site maps

$I_{i}:\mathcal{H}_{r}\rightarrow\mathcal{H}_{reg}^{\otimes(n_{r}+1)},\qquad
n_{r}=\lceil\log_{|G|}(\max_{g\in G}N_{g})\rceil.$ (179)

Note that for the case where all of the degeneracies $N_{g}=0,1$, we have
$n_{r}=0$ and we can simply embed $\mathcal{H}_{r}$ into $\mathcal{H}_{reg}$
through the obvious inclusion. The requirement that $I_{i}$ be symmetric means

$r_{g,i}I_{i}=I_{i}R_{g,i}^{\otimes(n_{r}+1)}.$ (180)

Intuitively, the action of a local symmetric isometry such as $I$ preserves
SPT phases, as the notion of an SPT phase should be robust with respect to
adding unentangled ancillae and coupling them to the system through symmetric
local unitaries. Therefore given a wavefunction
$\mathsf{SPT}_{\omega}\ni|\psi_{\omega}^{r}\rangle\in\mathcal{H}_{r}^{\otimes
L}$, the embedded wavefunction
$I|\psi_{\omega}^{r}\rangle\in\mathcal{H}_{reg}^{\otimes L(n_{r}+1)}$ is also
in $\mathsf{SPT}_{\omega}$. This can be proved by looking at the projective
representations obeyed by split symmetry operators (which are left untouched
by the isometry by virtue of (180)), or by thinking about edge states: if the
$|G|$ different edge states cannot be lifted by a symmetric local perturbation
in $\mathcal{H}_{r}^{\otimes L}$, they are also unable to be lifted by a
similar perturbation in the larger Hilbert space $\mathcal{H}_{reg}^{\otimes
L(n_{r}+1)}$.

Since $G$ is represented as the regular representation in the larger Hilbert
space, we can then apply the already-developed RG circuit for this case to
flow the embedded wavefunction $I|\psi_{\omega}^{r}\rangle$ to the canonical
representative $|\Psi_{\omega}\rangle$ of the regular representation. String
operators can then be measured in $|\Psi_{\omega}\rangle$ before using
$I^{\dagger}$ to project back to the original Hilbert space, and the
expectation values of these string operators serve as a diagnostic of whether
or not the original wavefunction $|\psi_{\omega}^{r}\rangle$ is indeed in
$\mathsf{SPT}_{\omega}$. Thus in the present setting, the correct definition
of the multiscale string operators is

$\widetilde{\mathcal{S}}^{(\omega)}_{g}=I^{\dagger}\mathcal{Q}_{\omega}^{\dagger}(\mathcal{S}^{(\omega)}_{g}\otimes\mathbf{1}_{an})\mathcal{Q}_{\omega}I.$
(181)

Note however that in this case, we have only accomplished phase recognition by
the direct measurement of the multiscale string operators, and have not
actually provided a unitary RG circuit which asymptotically maps any
$|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$ to
$|\Psi_{\omega}\rangle\otimes|\phi_{an}\rangle$ (conjugating
$\mathcal{Q}_{\omega}$ with $I$ does not generically work, since
$I^{\dagger}\mathcal{Q}_{\omega}I$ needn’t be unitary). In actual hardware
implementations measuring the multiscale string operators may be impractical,
and ideally one would still be able to construct a unitary circuit where each
individual gate — rather than the entire circuit itself — is able to be
implemented on the particular microscopic Hilbert space one is provded with.
We leave the best way of getting around this issue as a question for the
future.

We close this section with a proof of the proposition referenced above:

######  Proposition 10.

One may always block sites together to form composite sites on which $G$ is
represented by

$r^{block}_{g}=\bigoplus_{h\in G}\chi_{h}(g)^{\oplus N_{h}},$ (182)

where the degeneracies $N_{h}\geq 1$ for all $h\in G$.

For the maximally non-commutative factor sets we are concerned with in this
appendix, the set of matrices $V_{g}$ generate the full matrix algebra of the
virtual space, and thus the above proposition is equivalent to injectivity of
the reference states $|\Psi^{r}_{\omega}\rangle$ given above.

###### Proof.

Suppose that microscopically $G$ acts on each site as

$r_{g}=\bigoplus_{\gamma\in S}\chi_{\gamma}(g),$ (183)

where the $\gamma$ run over some subset $S$ of $G$. Since in quantum mechanics
we mod out by overall phases, any element $g$ for which
$r_{g}\propto\mathbf{1}$ is represented trivially. We will not allow this to
occur, since in this case $G$ is not represented faithfully. Therefore we
require that the $\\{\gamma\\}$ be such that

$\chi_{\gamma}(g)=1\,\,\forall\,\,\gamma\,\implies g=e.$ (184)

We will call a representation obeying the above equation a ‘legit’
representation. As an example, for $G=\mathbb{Z}_{N}$ a legit representation
is

$r_{g}=1\oplus\zeta_{N}^{g}$ (185)

where $\zeta_{N}=e^{{2\pi}i/N}$. For $\mathbb{Z}_{N}^{2}$, one requires at
least three summands, with a legit representation being e.g.

$r_{\mathbf{g}}=1\oplus\zeta_{N}^{g_{1}}\oplus\zeta_{N}^{g_{2}}.$ (186)

Note how we are always taking the first summand to be the trivial
representation; this is done wolog because we can always redefine $r_{g}$ by
an overall $g$-dependent phase. This is what allows us to use 1 on the RHS of
(184).

Let $H$ be the subgroup of $G$ generated by the $\\{\gamma\\}$. We will first
show that if $r_{g}$ is a legit representation, then $H=G$. Indeed, suppose
that $H$ is a proper subgroup of $G$. We claim that this implies that $r_{g}$
is not a legit representation, i.e. that there is some $e\neq g_{*}\in G$ for
which $r_{g_{*}}=\mathbf{1}$. To show this we use the fact that for a subgroup
$H\subset G$, every irrep of $H$ can be extended to an irrep of $G$ in
$|G|/|H|$ different ways, so that in particular, there are $|G|/|H|$ irreps of
$G$ whose characters are trivial when restricted to $H$ (as can be proved
using e.g. Frobenius reciprocity). Thus if $H$ is a proper subgroup of $G$, we
can find $|G|/|H|>1$ different irreps of $G$ whose characters are trivial on
$H$. Since each irrep of $G$ is identified with a group element, there exist
$|G|/|H|$ choices of $g_{*}\in G$ such that $\chi_{\gamma}(g_{*})=1$ for all
$\gamma$. Therefore $r_{g}$ does not generate a legit representation, as
claimed.

Finally, suppose $r_{g}$ is a legit representation. Taking $n$ tensor powers
of $r_{g}$ gives

$r_{g}^{\otimes
n}=\bigoplus_{\\{\gamma_{1},\dots,\gamma_{n}\\}}\chi_{\gamma_{1}+\cdots+\gamma_{n}}(g).$
(187)

Since the $\\{\gamma\\}$ must generate $G$, for large enough $n$ (upper
bounded by $|G|$), $r_{g}^{\otimes n}$ will contain $\chi_{h}(g)$ for all
$h\in G$. Thus as long as $n$ is large enough, all of the degeneracies $N_{h}$
can be made positive, as we wanted to show. ∎

##  Appendix J Sample complexity

In this section we describe how to estimate the sample complexity of phase
recognition using the expectation values of the multiscale string operators
(MSOs) $\mathcal{S}_{g}^{(\omega)}$ defined in the main text. Given an SPT
ground state wavefunction $|\psi\rangle$, the sample complexity
$M_{\delta}^{\psi}$ is defined as the number of measurements of the MSOs in
the state $|\psi\rangle$ needed to conclude whether or not $|\psi\rangle$ is
in the target phase $\mathsf{SPT}_{\omega}$ of interest, given some tolerance
for error $\delta$.

The eigenvalues of any $\mathcal{S}_{g}^{(\omega)}$ are given by the phases
$\chi_{g}(h),h\in G$. This fact can be proven by demonstrating it in the case
where $\mathcal{S}_{g}^{(\omega)}=S^{R}_{g}\otimes R_{g}\otimes S^{L}_{g}$ is
a ‘bare’ 3-site string operator (which can in turn be shown using the
graphical technology developed in previous appendices), and noting that the
eigenvalues of $\mathcal{S}_{g}^{(\omega)}$ do not change under conjugation by
$\mathcal{Q}_{\omega}$. Since $G$ is a finite group, for any $g$ the character
$\chi_{g}(h)$ will be a multiple of some primitive $n$-th root of unity for
all $h$, for some integer $n$ (with $n>1$ if $g\neq e$). We can thus select
out the eigenspace of $\mathcal{S}^{(\omega)}_{g}$ spanned by those
eigenvectors with eigenvalue $\zeta_{n}^{k}$, $k\in\mathbb{Z}_{n}$ (recall
$\zeta_{n}\equiv e^{{2\pi}i/n}$) by forming the projector

$\Pi_{k}^{(\omega,g)}\equiv\frac{1}{n}\sum_{l\in\mathbb{Z}_{n}}\zeta_{n}^{kl}(\mathcal{S}^{(\omega)}_{g})^{l}.$
(188)

If $|\psi\rangle\in\mathsf{SPT}_{\omega}$ is an RG fixed point, then
$|\psi\rangle$ is an eigenstate of $\mathcal{S}^{(\omega)}_{g}$ with
eigenvalue 1, and has support only on the image of $\Pi_{e}^{(\omega,g)}$.
When $|\psi\rangle\in\mathsf{SPT}_{\omega}$ but $|\psi\rangle$ is not a fixed
point, $\langle\psi|\mathcal{S}^{(\omega)}_{g}|\psi\rangle$ will be some
$O(1)$ number which approaches $1$ exponentially fast in the QCNN circuit
depth, but which for small circuit depths and near phase boundaries can still
be rather small, giving nonzero weight to the $\Pi_{k\neq e}^{(\omega,g)}$. On
the other hand, if $|\psi\rangle\not\in\mathsf{SPT}_{\omega}$, then by the
selection rules discussed earlier,
$\langle\psi|\mathcal{S}^{(\omega)}_{g;i\rightarrow j}|\psi\rangle$ will
vanish as $e^{-|i-j|/\xi}$, meaning that the measurements of the
$\Pi_{k}^{(\omega,g)}$ will be very nearly uniformly distributed over all $k$.
When doing numerics, this means that as soon as one sees a
$\langle\psi|\mathcal{S}^{(\omega)}_{g;i\rightarrow j}|\psi\rangle$ whose
value is above machine precision and not exponentially small in the limit
where $|i-j|/\xi\gg 1$, one can be confident that
$|\psi\rangle\in\mathsf{SPT}_{\omega}$. However in an experimental context
there will always be some finite level of noise present in the measurement
process, mandating that a stronger signal be observed before one can be
confident about phase identification.

The criterion we will adopt is as follows. Define the binary random variable
$\xi_{\psi}\in\\{0,1\\}$ to be the outcome of measuring the projector
$\Pi^{(\omega,g_{\bullet})}_{e}$ in the state $|\psi\rangle$, where
$g_{\bullet}$ is some fixed element of maximal order $n$ in $G$. Let
$p\equiv\mathbb{E}[\xi_{\psi}]$. Assuming
$|\psi\rangle\in\mathsf{SPT}_{\omega}$, the sample complexity
$M^{\psi}_{\delta}$ is defined as the number of samples needed so that $p$ is
separated from $1/n$ (which would be the expectation value of $\xi$ if
$|\psi\rangle\not\in\mathsf{SPT}_{\omega}$) by $\delta$ times the standard
deviation of the emperical average of $\xi_{\psi}$ (in practice, one may be
able to do slightly better by using a more sophisticated estimator of the
average [13]). That is, $M^{\psi}_{\delta}$ is the minimum integer satisfying

$p-\delta\frac{\sqrt{p(1-p)}}{\sqrt{M^{\psi}_{\delta}}}>1/n.$ (189)

Thus

$M^{\psi}_{\delta}=\lceil\frac{\delta^{2}p(1-p)}{(p-1/n)^{2}}\rceil.$ (190)

In the setting of the $\mathbb{Z}_{3}\times\mathbb{Z}_{3}$ SPT considered in
Fig. 5 of the main text, we take $g_{\bullet}=(1,0)$, so that $n=3$ and

$p=\frac{1}{3}(1+2S),\qquad S\equiv{\rm
Re}[\langle\psi|\mathcal{S}^{(\omega)}_{g_{\bullet}}|\psi\rangle],$ (191)

giving

$M_{\delta}^{\psi}=\lceil\delta^{2}\frac{(1+2S)(1-S)}{2S^{2}}\rceil.$ (192)

Note that $M^{\psi}_{\delta}=1$ as $S\rightarrow 1$ from below; in this case
one is nearly at the fixed point $|\Psi_{\omega}\rangle$, which can be
recognized immediately. In the opposite limit of $S\rightarrow 0$ the string
operator contains no signal of the SPT order, and $M^{\psi}_{1}$ accordingly
diverges. The inset of Fig. 5 shows $M^{\psi}_{3}$ for $|\psi\rangle$ the DMRG
ground state close to the phase boundary, illustrating the exponential
improvement of the sample complexity with increasing depth $d$.

##  Appendix K The case when $\omega$ is not MNC

In this appendix we explain how the technology used in the construction of our
RG circuit can be generalized to the case when the cohomology class $\omega$
in question is not maximally non-commutative (MNC). This allows us to give a
provable performance guarantee for identifying any SPT phase protected by an
internal finite Abelian symmetry.

A summary of the material contained in this appendix is as follows. We begin
in Sec. K.1 by discussing an alternate way of formulating the tools (reference
states, shift operators, etc.) used to construct the RG circuits
$\mathcal{Q}_{\omega}$ in the MNC case, which will allow us to more easily
generalize to non-MNC $\omega$. In Sec. K.2 we extend this technology to
general $\omega$. The main result of this section is to prove that for any SPT
phase, the protecting symmetry $G$ can always be factored into a ‘MNC part’
and a ‘flavor’ part. The Hilbert space can similarly be factored as
$\mathcal{H}=\mathcal{H}_{MNC}\otimes\mathcal{H}_{flav}$, with $G$ acting
projectively on $\mathcal{H}_{MNC}$ and linearly on $\mathcal{H}_{flav}$. The
degrees of freeom in $\mathcal{H}_{MNC}$ are the ones responsible for the
phase’s protected edge modes, while those in $\mathcal{H}_{flav}$ are in some
sense trivial (in our reference states, the degrees of freedom in
$\mathcal{H}_{flav}$ are frozen out in a product state and unentangled with
the rest of the system).

In Sec. K.3 we discuss how general wavefunctions $|\psi_{\omega}\rangle$ can
be represented in terms of collections of ‘errors’ applied to the reference
states $|\Psi_{\omega}\rangle$ constructed in Sec. K.2. Some errors involve
local actions of the symmetry that act only on $\mathcal{H}_{MNC}$. These
errors can be corrected using the same framework developed above for the case
of MNC $\omega$. Other errors act only on $\mathcal{H}_{flav}$; these errors
are unimportant and can essentially simply be ignored. The main difficulty is
that there exist errors which involve a mixed action on $\mathcal{H}_{MNC}$
and $\mathcal{H}_{flav}$. From the perspective of either one of these
subsystems, these mixed errors look as though they break the symmetry; that
they are in fact symmetric is only seen when both subsystems are considered.
To deal with these errors, the strategy we adopt is to convert them into
errors that act only on $\mathcal{H}_{MNC}$ and to then run an MNC RG circuit
on $\mathcal{H}_{MNC}$, with $\mathcal{H}_{flav}$ being ignored for the
remaineder of phase recognition procedure.

The conversion process is done by measuring the degrees of freedom on
$\mathcal{H}_{flav}$, performing an $O(L)$ amount of classical data processing
on the measurement outcome, and then using the result of this data processing
to construct a certain depth-1 local symmetric circuit $\mathcal{U}$; we will
show that $\mathcal{U}$ can always be chosen to turn mixed errors into errors
that act only on $\mathcal{H}_{MNC}$. After acting with $\mathcal{U}$, the
wavefunction is left in a form amenable to be adressed with an MNC RG circuit
applied to $\mathcal{H}_{MNC}$, and phase recognition proceeds as in the MNC
case developed previously. The upshot is that phases with non-MNC $\omega$ can
be dealt with using more or less the same framework as the MNC case, provided
that one pays an $O(L)$ amount of classical data processing as overhead.

###  K.1 Entangled pairs representation of SPT ground states for MNC $\omega$

Before getting into the construction for general $\omega$, we first discuss an
alternate representation of the symmetry action and reference fixed-point
wavefunctions in the MNC case, which will be helpful to use when we extend our
technology to general $\omega$. This representation can be thought of as a
generalization of the usual representation of the AKLT ground state
wavefunction, where spin-1 degrees of freedom are decomposed into two spin 1/2
sites that are then entangled into Bell pairs between sites. It is based on
the fact [35, 69] that any SPT ground state wavefunction with zero correlation
length can be constructed by applying local isometries to a collection of Bell
pairs. In this representation this construction is made manifest; for this
reason we refer to it as the ‘entangled pairs representation’.

To get started, recall that in all of the previous discussion, we have worked
in a basis in which the local symmetry action $R_{g}$ is diagonal and acts in
the regular representation, viz.

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

There is however another convenient basis in which the symmetry
fractionalization that occurs in SPT phases is made more manifest.

######  Proposition 11 (entangled pair representation, MNC case).

When $\omega$ is MNC, the regular representation $R_{g}$ is unitarily
equivalent to the representation

$\mathcal{R}_{g}=V_{g}^{*}\otimes V_{g},$ (194)

meaning that there exists a local unitary $U$ such that
$U^{\dagger}R_{g}U=\mathcal{R}_{g}$ (as before, $V_{g}$ denotes the projective
representation associated with $\omega$).

Recall that $\omega$ being MNC implies that $G=G^{\prime}\times G^{\prime}$ is
a square and $\dim(V_{g})=|G^{\prime}|$; thus the dimensions in (194) match.

###### Proof.

First, note that $\mathcal{R}_{g}$ is linear over $G$, viz. that
$\mathcal{R}_{g}\mathcal{R}_{h}=\mathcal{R}_{g+h}$, since while
$V_{g}V_{h}\neq V_{g+h}$, $V^{*}_{g}V^{*}_{h}\otimes
V_{g}V_{h}=V_{g+h}^{*}\otimes V_{g+h}$.

We thus only need demonstrate that $R_{g}$ and $\mathcal{R}_{g}$ have
identical eigenvalues. The eigenvalues of $R_{g}$ are of course enumerated by
the characters $\chi_{g}(h),h\in G$. That these agree with the eigenvalues of
$V_{g}^{*}\otimes V_{g}$ can be seen by explicitly constructing the
corresponding eigenvectors, which are

$|v_{h}\rangle\equiv(V_{h}^{*}\otimes\mathbf{1})|\Gamma\rangle,\qquad|\Gamma\rangle\equiv\frac{1}{\sqrt{|G|}}\sum_{g\in
G^{\prime}}|g\rangle\otimes|g\rangle.$ (195)

The eigenvalue of $|v_{h}\rangle$ under $V_{g}^{*}\otimes V_{g}$ is
accordingly

$(V_{g}^{*}\otimes V_{g})|v_{h}\rangle=(V_{g}^{*}V_{h}^{*}\otimes
V_{g})|\Gamma\rangle=\lambda_{\omega}(h,g)(V_{h}^{*}V_{g}^{*}\otimes
V_{g})|\Gamma\rangle=\chi_{h}(\Gamma_{\omega}(g))(V_{h}^{*}\otimes
V_{g}V_{g}^{\dagger})|\Gamma\rangle=\chi_{h}(\Gamma_{\omega}(g))|v_{h}\rangle.$
(196)

Since $\Gamma_{\omega}$ is an automorphism of $G$, the eigenvalues of
$\mathcal{R}_{g}$ are indeed enumerated by the characters $\chi_{g}(h),h\in
G$, as claimed. ∎

In this representation, the left and right shift operators $S^{L/R}_{g}$ are
espeically simple. Indeed, from the fact that the shift operators
‘fractionalize’ the symmetry action into left and right projective parts, it
is not surprising that under the unitary transformation in the above
proposition, they become

$S^{L}_{g}=V^{*}_{g}\otimes\mathbf{1},\qquad S^{R}_{g}=\mathbf{1}\otimes
V_{g},$ (197)

so that $\mathcal{R}_{g}=S^{L}_{g}S^{R}_{g}$, as desired. It is easy to check
that the $S^{L/R}_{g}$ obey all the algebraic relations derived previously.

####  K.1.1 MPS representation of reference states $|\Psi_{\omega}\rangle$

The reference state $|\Psi_{\omega}\rangle$ also takes a rather simple form in
this basis. With the decomposition of the physical space $\mathcal{H}$ into
the two tensor factors as above, the MPS tensors of $|\Psi_{\omega}\rangle$
simply associate the left tensor factor with the left virtual leg, and the
right tensor factor with the right virtual leg:

$|\Psi_{\omega}\rangle=\sum_{\mathbf{g}\in G^{L}}\text{Tr}[A^{g_{1}}\cdots
A^{g_{L}}],\qquad A^{g}=|{g_{1}}\rangle\langle{g_{2}}|.$ (198)

Graphically,

(199)

Chaining these tensors together, it is apparent that in
$|\Psi_{\omega}\rangle$, the right $\otimes$ factor of the physical Hilbert
space at site $i$ forms a maximally entangled pair with the left $\otimes$
factor at site $i+1$, generalizing the usual picture of the AKLT state to
groups beyond $\mathbb{Z}_{2}$.

####  K.1.2 Parent Hamiltonian

The parent Hamiltonian of the reference state $|\Psi_{\omega}\rangle$ has the
same representation as before, viz.

$H=\sum_{i}H_{i},\qquad H_{i}=-\sum_{g\in G}S^{R}_{g,i}S^{L}_{g,i+1}.$ (200)

In the present representation, this is

$H_{i}=-\sum_{g\in G}(\mathbf{1}\otimes
V_{g})_{i}\otimes(V_{g}^{*}\otimes\mathbf{1})_{i+1},$ (201)

with each $H_{i}$ easily being seen to stabilize $|\Psi_{\omega}\rangle$.
Graphically, the action of e.g. $H_{2}$ on $|\Psi_{\omega}\rangle$ looks like

(202)

The existence of $\dim V_{g}=\sqrt{|G|}$ protected edge modes is particularly
transparent in this representation, since $H$ as given above contains no
nontrivial action on the left tensor factor of the leftmost site (straight
line on far left of (202)), nor on the right tensor factor of the rightmost
site (straight line on far right). Thus on a finite chain, $H$ has
$\sqrt{|G|}$ degenerate modes on each edge, corresponding to the $\sqrt{|G|}$
independent states of each free tensor factor. It is easy to check that these
degenerate modes cannot be lifted by any symmetry-preserving perturbation.
Indeed, the symmetry action restricted to the edges is the projective action
$V_{g}$, and $\\{V_{g}\\}$ generate the full matrix algebra on
$L(\mathbb{C}^{\sqrt{|G|}})$ — thus there are no nontrivial terms that can be
added to the Hamiltonian which commute with the symmetry and act locally on
the free tensor factors.

###  K.2 Entangled pairs representation for general $\omega$

We now generalize the formalism of the previous subsection to the case where
$\omega$ is not MNC. We will show that for general $\omega$, all of the tools
involved (projective representations, reference-state MPS wavefunctions, etc.)
can in some sense be split into an MNC part and an extra ‘flavor’ part, with
the latter not playing an essential role in distinguishing one SPT phase from
another. This decomposition is inspired by previous studies of non-MNC SPT
phases [33, 34, 70, 37] and in particular by the masters thesis of David
Stephen [33], in which a general prescription was worked out for constructing
zero correlation length MPS tensors for non-MNC SPT ground states.

####  K.2.1 Mathematical preliminaries

First, recall from App. A that for general $\omega$, the projective center
$C_{\omega}$ is defined as the subgroup of all elements $g$ for which $V_{g}$
is a scalar matrix. This means that $\omega$ is MNC when restricted to the
quotient $\mathcal{G}_{\omega}\equiv G/C_{\omega}$ (which is always non-
trivial; if $C_{\omega}=G$ then there are no nontrivial projective
representations, and hence no nontrivial SPT phases). For future reference, we
will write the relation between $\mathcal{G},G,$ and $C_{\omega}$ as the short
exact sequence

$0\rightarrow
C_{\omega}\xrightarrow{\iota}G\xrightarrow{\pi}\mathcal{G}_{\omega}\rightarrow
0.$ (203)

In what follows we will drop the subscripts on
$\mathcal{G}_{\omega},C_{\omega}$ for simplicity of notation.

Recall from the math facts listed in App. A that MNC cohomology classes exist
for a given finite Abelian group iff that group takes the form
$G^{\prime}\times G^{\prime}$ for some factor $G^{\prime}$. Since $\omega$ is
MNC on $\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{G}\mkern-1.5mu}\mkern
1.5mu$, we thus always have

$\mathcal{G}=G^{\prime}\times G^{\prime}$ (204)

for some $G^{\prime}$. Since the dimension of every projective irrep with
factor set $\omega$ is $\sqrt{|\mathcal{G}|}=|G^{\prime}|$, the projective
irreps will always satisfy $\dim(V)=|G^{\prime}|$ (readers interested in
seeing an explicit example can skip ahead to Sec. K.2.5). Because the number
of topologically protected edge modes is determined by $\dim(V)$ (see e.g.
LABEL:pollmann2010entanglement and the following), their number is thus equal
to $|G^{\prime}|$. While this is the same number of edge modes as a
$\mathcal{G}$-SPT with MNC factor set, the $G$-SPT under consideration is
nevertheless generically physically distinct from a $\mathcal{G}$-SPT with an
‘accidentally’ enlarged symmetry, as we will see explicitly later.

Let us now fix some notation. In situations where confusion could potentially
arise, we will use subscripts to explicitly denote the group in which
operations are being performed, with e.g. $+_{K}$ denoting addition in the
group $K$ (we use ‘$+$’ for the group action since all groups under
consideration are Abelian). Furthermore, we will adopt notation in which bars
denote membership in $\mathcal{G}$, while tildes denote membership in $C$. We
thus will write a general $g\in G$ in terms of the pair
$(\underline{g},\underaccent{\sim}{g})\in\mathcal{G}\times C$ as

$g=\pi^{-1}(\underline{g})+_{G}\iota(\underaccent{\sim}{g}),$ (205)

where the map $\pi^{-1}$ will always be defined using a certain fixed section
of $G$.101010Physicists which find this notation strange can think of $\pi$ as
an isometry: $\pi(\pi^{-1})=\mathbf{1}_{C}$, but
$(\pi^{-1})\pi\neq\mathbf{1}_{G}$. We see that $\underline{g}$ and
$\underaccent{\sim}{g}$ are obtained from $g$ as

$\underline{g}=\pi(g),\qquad\underaccent{\sim}{g}=\iota^{-1}(g-_{G}\pi^{-1}(\pi(g))),$
(206)

where $\underaccent{\sim}{g}$ is well-defined since
$g-\pi^{-1}(\pi(g))\in\ker(\pi)={\rm im}(\iota)$.

Note that when writing elements pairwise like this, the group addition law
acts in a twisted way:

$(\underline{g},\underaccent{\sim}{g})+_{G}(\underline{h},\underaccent{\sim}{h})=(\underline{g}+_{\mathcal{G}}\underline{h},\,\,\underaccent{\sim}{h}+_{C}\underaccent{\sim}{g}+_{C}\underaccent{\sim}{\delta}(\underline{h},\underline{g})),$
(207)

where we have defined the function

$\underaccent{\sim}{\delta}:\mathcal{G}\times\mathcal{G}\rightarrow
C,\quad\underaccent{\sim}{\delta}(\underline{h},\underline{g})=\iota^{-1}(\delta\pi^{-1}(\underline{h},\underline{g})),$
(208)

with

$\delta\pi^{-1}(\underline{h},\underline{g})=\pi^{-1}(\underline{h})+_{G}\pi^{-1}(\underline{g})-_{G}\pi^{-1}(\underline{h}+_{\mathcal{G}}\underline{g}),$
(209)

with $\underaccent{\sim}{\delta}$ well-defined for the same reason as
$\underaccent{\sim}{g}$ in (206). Since $\delta\pi^{-1}$ is a coboundary, its
exterior derivative vanishes, with

$\delta\pi^{-1}(a,b)+\delta\pi^{-1}(a+b,c)=\delta\pi^{-1}(a,b+c)+\delta\pi^{-1}(b,c)=\pi^{-1}(a)+\pi^{-1}(b)+\pi^{-1}(c)-\pi^{-1}(a+b+c).$
(210)

We will also need a way of talking about relations between the characters of
$G,\mathcal{G},$ and $C$, which we will denote respectively as
$\chi,\chi^{\mathcal{G}}$, and $\chi^{C}$. To find the relations between the
characters, we apply the Hom functor to the short exact sequence (203).
Letting $K^{*}\equiv{\rm Hom}(K,U(1))$ denote the group of characters on $K$,
the contravariance of Hom gives the left exact sequence

$1\rightarrow\mathcal{G}^{*}\xrightarrow{\pi_{*}}G^{*}\xrightarrow{\iota_{*}}C^{*},$
(211)

where $\pi_{*},\iota_{*}$ satisfy $\ker(\iota_{*})={\rm im}(\pi_{*})$ and are
defined by pre-composing with $\pi,\iota$, respectively (e.g.
$\pi_{*}(\chi^{\mathcal{G}})(\cdot)=\chi^{\mathcal{G}}(\pi(\cdot)):G\rightarrow
U(1)$).

Since $K^{*}\cong K$ for all finite Abelian groups $K$, just as we could write
any $g\in G$ as the pair
$(\underline{g},\underaccent{\sim}{g})\in\mathcal{G}\times C$, we can perform
a similar decomposition on characters in $G^{*}$, with any $\chi_{*}\in G^{*}$
equivalently being given in terms of a pair $(\chi_{\mkern
1.5mu\overline{\mkern-1.5mug\mkern-1.5mu}\mkern
1.5mu}^{\mathcal{G}},\chi_{\widetilde{g}}^{C})\in\mathcal{G}^{*}\times C^{*}$
— here the group elements $(\bar{g},\widetilde{g})\in\mathcal{G}\times C$
label their respective characters, and we have placed the bars and tildes on
top to distinguish these group elements from
$\underline{g},\underaccent{\sim}{g}$.

This is formalized as the following proposition, which is essentially the dual
of (205):

######  Proposition 12 (decomposition of characters).

Any character $\chi_{g}\in G^{*}$ can be written as

$\chi_{g}=\pi_{*}(\chi^{\mathcal{G}}_{\mkern
1.5mu\overline{\mkern-1.5mug\mkern-1.5mu}\mkern
1.5mu})\iota_{*}^{-1}(\chi^{C}_{\widetilde{g}}),$ (212)

where the map $\iota_{*}^{-1}$ is as usual defined by picking a section of
$G^{*}$.111111Note that it does not simply work by pre-composing by
$\iota^{-1}$, since $\iota$ is not invertible except on $\ker(\pi)$. Here the
characters $\chi^{\mathcal{G}}_{\mkern
1.5mu\overline{\mkern-1.5mug\mkern-1.5mu}\mkern 1.5mu}\in\mathcal{H}^{*}$ and
$\chi^{C}_{\widetilde{g}}\in C^{*}$ are determined from $\chi_{g}$ as

$\chi^{C}_{\widetilde{g}}=\iota_{*}(\chi_{g}),\qquad\chi^{\mathcal{G}}_{\mkern
1.5mu\overline{\mkern-1.5mug\mkern-1.5mu}\mkern
1.5mu}=\pi_{*}^{-1}\left(\frac{\chi_{g}}{\iota^{-1}_{*}(\iota_{*}(\chi_{g}))}\right),$
(213)

where the expression in parenthesis is invertible by $\pi_{*}$ since it is in
$\ker(\iota_{*})$.

We will simplify notation by defining the map

$\theta\equiv\iota_{*}^{-1}$ (214)

and by writing
$G^{*}\ni\theta(\chi^{C}_{\widetilde{g}})\equiv\chi_{\theta(\widetilde{g})}$.
Explicitly, when evaluated on $h\in G$, Prop. 12 reads

$\chi_{g}(h)=\chi^{\mathcal{G}}_{\bar{g}}(\underline{h})\chi_{\theta(\widetilde{g})}(h).$
(215)

Since characters can be identified with group elements, we can also decompose
any $g\in G$ as

$g=\pi_{*}(\bar{g})+_{G}\theta(\widetilde{g}),$ (216)

where by following logic similar to (206),

$\bar{g}=\pi_{*}^{-1}(g-_{G}\theta(\iota_{*}(g))),\qquad\widetilde{g}=\iota_{*}(g).$
(217)

In terms of the pairs $(\mkern 1.5mu\overline{\mkern-1.5mug\mkern-1.5mu}\mkern
1.5mu,\widetilde{g})$, group addition is performed in a way analogous to
(207):

$(\bar{g},\widetilde{g})+_{G}(\bar{h},\widetilde{h})=(\bar{g}+_{\mathcal{G}}\bar{h}+_{\mathcal{G}}\bar{\delta}(\widetilde{g},\widetilde{h}),\widetilde{g}+_{C}\widetilde{h}),$
(218)

where

$\bar{\delta}:C\times C\rightarrow\mathcal{G},\qquad\mkern
1.5mu\overline{\mkern-1.5mu\delta\mkern-1.5mu}\mkern
1.5mu(\widetilde{h},\widetilde{g})=\pi_{*}^{-1}(\delta\theta(\widetilde{h},\widetilde{g})),$
(219)

where we have defined the coboundary

$\delta\theta:C\times C\rightarrow
G,\qquad\delta\theta(\widetilde{h},\widetilde{g})=\theta(\widetilde{h})+\theta(\widetilde{g})-\theta(\widetilde{h}+\widetilde{g}),$
(220)

which also obeys (210).

Example: $G=\mathbb{Z}_{pq}^{2}$

To illustrate the above symbol pushing with an example, consider the case when
$G=\mathbb{Z}_{pq}^{2}$ with $p,q$ prime, and take $\omega=q$. Then

$C=p\mathbb{Z}_{pq}^{2}\cong\mathbb{Z}_{q}^{2},\qquad\mathcal{G}=\mathbb{Z}_{pq}^{2}/p\mathbb{Z}_{pq}^{2}\cong\mathbb{Z}_{p}^{2},$
(221)

giving the SES

$0\rightarrow\mathbb{Z}_{q}^{2}\xrightarrow{\times
p}\mathbb{Z}_{pq}^{2}\xrightarrow{\mod p}\mathbb{Z}_{p}^{2}\rightarrow 0,$
(222)

so that $\iota$ multiplies by $p$ and $\pi$ takes its argument mod $p$, with
$\pi^{-1}$ defined by emedding the elements of $\mathcal{G}$ as those elements
of $G$ which have both factors less than $p$. Letting
$(a+_{x}b)\equiv(a+b)\mod x$, we may then write any $g\in G$ as

$g=\underline{g}+_{pq}p\underaccent{\sim}{g},$ (223)

where
$\underline{g}\in\mathbb{Z}_{p}^{2},\,\underaccent{\sim}{g}\in\mathbb{Z}_{q}^{2},$
and the function $\underaccent{\sim}{\delta}(\underline{g},\underline{h})$ is
simply

$\underaccent{\sim}{\delta}(\underline{g},\underline{h})=\frac{(\underline{g}+_{pq}\underline{h})-(\underline{g}+_{p}\underline{h})}{p}.$
(224)

In this simple setting, it is straightforward to check that taking the dual
merely exchanges $p$ and $q$. Thus the map $\pi_{*}=\times q$ is
multiplication by $q$, while $\iota_{*}$ takes its argument modulo $q$. The
inverse $\theta=\iota_{*}^{-1}$ embedds the elements of $C$ as those elements
of $G$ with both factors less than $q$. We may correspondingly also write any
$g\in G$ as

$g=q\bar{g}+_{pq}\widetilde{g},$ (225)

with

$\bar{\delta}(\widetilde{g},\widetilde{h})=\frac{(\widetilde{g}+_{pq}\widetilde{h})-(\widetilde{g}+_{q}\widetilde{h})}{q}.$
(226)

####  K.2.2 Form of $\mathcal{R}_{g}$

We now generalize the entangled pair representation $\mathcal{R}_{g}$ of the
symmetry operators (194) to the case of general $\omega$. The idea is to split
$\mathcal{R}_{g}$ into a projective action controlled by the part
$\underline{g}$ of $G$ belonging to $\mathcal{G}$, together with an ordinary
linear action controlled by the part $\widetilde{g}$ belonging to $C$. To
facilitate this decomposition, we will break up the $|G|$-dimensional physical
Hilbert space $\mathcal{H}$ at each site as

$\mathcal{H}=\mathcal{H}_{l}\otimes\mathcal{H}_{flav}\otimes\mathcal{H}_{re},$
(227)

where
$\dim\mathcal{H}_{l}=\dim\mathcal{H}_{re}=\sqrt{|\mathcal{G}|}=|G^{\prime}|$
and $\dim\mathcal{H}_{flav}=|C|$. We will refer to
$\mathcal{H}_{l}\otimes\mathcal{H}_{re}$ as the ‘MNC’ subspace
$\mathcal{H}_{MNC}$; it is on this subspace that the symmetry
fractionalization occurs. We will also use the symbols
$\mathcal{H}_{flav},\mathcal{H}_{MNC}$ to refer to the tensor products of the
single-site flavor / MNC Hilbert spaces across all sites; the distinction
between the two should be clear from context.

In order to write down $\mathcal{R}_{g}$, which will split as a tensor product
according to the above decomposition, we need a further definition:

######  Definition 11.

For any $g\in G$, the matrix $\widetilde{R}_{g}\in L(\mathbb{C}^{|C|})$ is
defined as the linear represetation $R_{g}$ restricted to $\theta(C)$ (again
with the same fixed section used to define $\theta$). Explicitly, for
$\\{|\widetilde{h}\rangle\,:\,\widetilde{h}\in C\\}$ a basis of
$\mathcal{H}_{flav}$,

$\widetilde{R}_{g}\equiv\sum_{\widetilde{h}\in
C}\chi_{\theta(\widetilde{h})}(g)|\widetilde{h}\rangle\langle\widetilde{h}|.$
(228)

We can now state the main result of this subsection, which shows that $R_{g}$
can be equivalently written in a form that explicitly separates the symmetry
action into a projective action on $\mathcal{H}_{MNC}$ and a linear action on
$\mathcal{H}_{flav}$:

######  Theorem 5 (entangled pair representation, general case).

For a factor set $\omega$ with projective center $C$, the regular
representation $R_{g}$ is unitarily equivalent to the representation

$\mathcal{R}_{g}=V^{*}_{\underline{g}}\otimes\widetilde{R}_{g}\otimes
V_{\underline{g}}.$ (229)

###### Proof.

It is easy to check that $\mathcal{R}_{g}$ is linear, viz. that
$\mathcal{R}_{g}\mathcal{R}_{h}=\mathcal{R}_{g+_{G}h}$. Thus as with the case
of Prop. 11, it sufficies simply to show that the eigenvalues of $R_{g}$ are
identical to the eigenvalues of $\mathcal{R}_{g}$. Since the eigenvalues of
$V_{\underline{g}}^{*}\otimes\mathbf{1}_{|C|}\otimes V_{\underline{g}}$ are
given by $\chi_{\underline{g}}^{\mathcal{G}}(\mathcal{G})$ by virtue of
$\omega$ being MNC when restricted to $\mathcal{G}$, from the definition of
$\widetilde{R}_{g}$ we have

$\mathsf{Eigvals}(\mathcal{R}_{g})=\\{\chi^{\mathcal{G}}_{\bar{h}}(\underline{g})\chi_{\theta(\widetilde{h})}(g)\,\,|\,\,(\bar{h},\widetilde{h})\in\mathcal{G}\times
C\\}.$ (230)

From the character decomposition formula (215), this set is simply equivalent
to the set $\chi_{g}(G)$, which is indeed equal to the eigenvalues of the
regular representation $R_{g}$. ∎

####  K.2.3 MPS representation of reference states $|\Psi_{\omega}\rangle$

We are finally in the position to apply the above group theory technology to
the problem at hand. Our goal is to construct a wavefunction
$|\Psi_{\omega}\rangle$ that will serve as our chosen RG fixed point for the
phase $\mathsf{SPT}_{\omega}$. $|\Psi_{\omega}\rangle$ should be symmetric,
and should also be stabilized by a collection of string operators.
Furthermore, $|\Psi_{\omega}\rangle$ should reduce to the simple form of the
generalized AKLT state (198) in the MNC case, i.e. in the case when $C$ is
trivial. We claim that the following wavefunction does the job:

$|\Psi_{\omega}\rangle=\sum_{\mathbf{g}\in
G^{L}}\text{Tr}[A^{g_{1}}_{\widetilde{g}_{\bullet}}\cdots
A^{g_{L}}_{\widetilde{g}_{\bullet}}],$ (231)

where the MPS tensors are (writing $g\in G$ as the triple
$(\bar{g}_{1},\widetilde{g},\bar{g}_{2})\in G^{\prime}\times C\times
G^{\prime}$ in accordance with the factorization
$\mathcal{H}_{l}\otimes\mathcal{H}_{flav}\otimes\mathcal{H}_{re}$)

$A^{g}_{\widetilde{g}_{\bullet}}=A^{(\bar{g}_{1},\widetilde{g},\bar{g}_{2})}_{\widetilde{g}_{\bullet}}=|{\bar{g}_{1}}\rangle\langle{\bar{g}_{2}}|\delta_{\widetilde{g},\widetilde{g}_{\bullet}},$
(232)

where the virtual space has dimension $\dim\mathcal{H}_{virt}=|G^{\prime}|$
and where $\widetilde{g}_{\bullet}$ is an arbitrary fixed element of $C$.
$A^{(\bar{g}_{1},\widetilde{g},\bar{g}_{2})}_{\widetilde{g}_{\bullet}}$ is
simply given by the generalized AKLT state MPS tensor used in the MNC case
(198), plus a projector onto a trivial product state for the degrees of
freedom in $\mathcal{H}_{flav}$. Graphically,

$A^{g}_{\widetilde{g}_{\bullet}}=\vbox{\hbox{\includegraphics[width=130.08731pt]{figures/nonmna_mps}}},$
(233)

where the orange leg lives in $\mathcal{H}_{flav}$ and the circle denotes a
projection onto the state $\widetilde{g}_{\bullet}$.

$|\Psi_{\omega}\rangle$ has zero correlation length, is stabilized (modulo
$\widetilde{g}_{\bullet}$-dependent phases) by all of the global symmetry
operators $\mathcal{R}_{g}^{\otimes L}$, and has the correct pattern of
symmetry fractionalization; hence it defines a suitable reference state for
the phase $\mathsf{SPT}_{\omega}$. It is clear from this presentation that the
degrees of freedom in $\mathcal{H}_{flav}$ are not essential to defining the
topological properties of the SPT phase, and as such it is convenient to work
with a reference state which trivializes them away. Relatedly, we see that on
a finite chain, $|\Psi_{\omega}\rangle$ has $|G^{\prime}|$ symmetry-protected
modes localized to each edge; this shows that the number of protected edge
modes is determined only by the dimension of the MNC subgroup
$\mathcal{G}=G^{\prime}\times G^{\prime}$ (see also e.g. [20, 37]).

Physically, the purpose of string operators is that they allow one to move
between distinct degenerate edge states. Since there are only $|G^{\prime}|$
symmetry-protected modes, the space of operators which acts on the zero mode
subspace has dimension $|G^{\prime}|^{2}=|\mathcal{G}|$. Thus we will only
define $|\mathcal{G}|$ (and not $|G|$) different string operators, done in the
obvious way by focusing only on the action of the symmetry on the
$\mathcal{H}_{MNC}$ factor of $\mathcal{H}$:

######  Definition 12 (string operators for general $\omega$).

For $\underline{g}\in\mathcal{G}$, the string operators
$\mathcal{S}_{\underline{g};i\rightarrow j}$ are defined as

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

where the left and right shift operators are defined as

$S^{L}_{\underline{g}}\equiv
V_{\underline{g}}^{*}\otimes\mathbf{1}_{flav}\otimes\mathbf{1}_{r},\qquad
S^{R}_{\underline{g}}\equiv\mathbf{1}_{l}\otimes\mathbf{1}_{flav}\otimes
V_{\underline{g}}.$ (235)

Note that we have chosen the linear symmetry operators $\mathcal{R}_{g}$
appearing in the interior of the string operator’s support to be defined with
a particular section of $G$ picked out by $\pi^{-1}(\mathcal{G})$ — when
evaluated on states where the $\mathcal{H}_{flav}$ degrees of freedom are in a
product state (such as $|\Psi_{\omega}\rangle$), the exact choice of section
only modifies the action of $\mathcal{S}_{\underline{g};i\rightarrow j}$ by an
unimportant overall phase factor. It is easy to check that the choice of
$|\Psi_{\omega}\rangle$ in (232) gives a reference state stabilized (up to a
phase) by all $|\mathcal{G}|$ string operators:

$\mathcal{S}_{\underline{g};i\rightarrow
j}|\Psi_{\omega}\rangle=\chi_{\widetilde{g}_{\bullet}}(\pi^{-1}(\underline{g}))^{|j-i|}|\Psi_{\omega}\rangle\,\,\forall\,\,\underline{g}\in\mathcal{G},\,i<j.$
(236)

A parent Hamiltonian for the wavefunction $|\Psi_{\omega}\rangle$ (given a
fixed choice of $\widetilde{g}_{\bullet}$) is as in (200), but with an extra
term to fix all of the degrees of freedom in $\mathcal{H}_{flav}$ to equal
$|\widetilde{g}_{\bullet}\rangle$:

$H=\sum_{i}H_{i},\qquad
H_{i}=-\sum_{\underline{g}\in\mathcal{G}}S^{R}_{\underline{g},i}S^{L}_{\underline{g},i+1}-\mathbf{1}_{l}\otimes|\widetilde{g}_{\bullet}\rangle_{i}\langle\widetilde{g}_{\bullet}|_{i}\otimes\mathbf{1}_{r}.$
(237)

When restricted to the MNC subspace, $|\Psi_{\omega}\rangle$ looks exactly
like the references states constructed for MNC $\omega$. Using the technology
developed previously, we can therefore construct a quantum circuit
$\bar{\mathcal{Q}}_{\omega}$ which acts only on $\mathcal{H}_{MNC}$, and which
corrects any symmetric errors whose actions are restricted to
$\mathcal{H}_{MNC}$. The circuit $\bar{\mathcal{Q}}_{\omega}$ nevertheless
does not by itself provide a way to implement phase recognition, since — as we
will see shortly — more complicated types of errors are possible.

####  K.2.4 edge mode counting and accidental symmetries

Since the number of edge modes is determined only by $|\mathcal{G}|$, it is
natural to ask if in fact a $G$-SPT with MNC subgroup $\mathcal{G}$ is always
secretly equivalent to a fine-tuned version of a $\mathcal{G}$-SPT with MNC
factor set and an ‘accidental’ enlarged symmetry group $G$. It turns out that
this is sometimes — but not generically — the case.

If a $G$-SPT is to be equivalent to a fine-tuned version of a
$\mathcal{G}$-SPT, one should be able to break the symmetry down as
$G\leadsto\mathcal{G}$, without reducing the number of protected edge modes.
The only natural embedding of $\mathcal{G}$ into $G$ that exists is the one
given by the map $\pi_{*}$; thus this pattern of symmetry breaking is acheived
by preserving the subgroup $\pi_{*}(\mathcal{G})\subset G$, and breaking the
rest of $G$. In order to determine the number of edge modes that remain after
symmetry breaking, we need simply to compute the projective center of
$\pi_{*}(\mathcal{G})$, defined as

$C^{\pi_{*}(\mathcal{G})}_{\omega}=\\{\underline{g}\in\pi_{*}(\mathcal{G})\,:\,\lambda_{\omega}(g,h)=1\,\,\forall\,\,\underline{h}\in\pi_{*}(\mathcal{G})\\}.$
(238)

The number of protected edge modes (on a given edge) is then determined by

${\rm\\#\,edge\,\,modes}=\sqrt{\frac{|\mathcal{G}|}{|C^{\pi_{*}(\mathcal{G})}_{\omega}|}}.$
(239)

Depending on the scenario in question, the number of protected edge modes
could be either unchanged (in which case $G$ should indeed be viewed as
an‘accidental’ symmetry) or eliminated entirely. We will see how both
possibilities can be realized in the following example.

####  K.2.5 Example: $G=\mathbb{Z}_{pq}^{2}$

We return to our example of $G=\mathbb{Z}_{pq}^{2}$, with $p,q$ prime and the
non-MNC cohomology class $\omega=q$. As a reminder, in this case we have
$C=p\mathbb{Z}_{pq}^{2}\cong\mathbb{Z}_{q}^{2},\mathcal{G}\cong\mathbb{Z}_{p}^{2}$.

As in our discussion of the MNC case for $G=\mathbb{Z}_{N}^{2}$, we will
choose the projective representation $V_{\underline{g}}$ of $\mathcal{G}$ as
$V_{\underline{g}}=X^{\underline{g}_{1}}Z^{\underline{g}_{2}}$, where $X,Z$
are the $\mathbb{Z}_{p}$ clock and shift matrices. Thus the explicit form of
$\mathcal{R}_{g}$ is

$\mathcal{R}_{g}=V_{\underline{g}}^{*}\otimes\widetilde{R}_{g}\otimes
V_{\underline{g}}=X^{\underline{g}_{1}}Z^{\underline{g}_{2}}\otimes\left(\sum_{\widetilde{h}\in\mathbb{Z}_{q}^{2}}Z^{\widetilde{h}_{1}(\underline{g}_{1}+q\underaccent{\sim}{g}_{1})/q}\otimes
Z^{\widetilde{h}_{2}(\underline{g}_{2}+q\underaccent{\sim}{g}_{2})/q}\right)\otimes
X^{\underline{g}_{1}}Z^{-\underline{g}_{2}},$ (240)

where our choice of lift $\theta:C\rightarrow G$ is manifested in the factors
of $1/q$ appearing in the exponents of the operators constituting
$\widetilde{R}_{g}$.

On a given edge, our $G$-SPT has only $\sqrt{|\mathcal{G}|}=p$ protected zero
modes. Is this SPT then secretely a $\mathbb{Z}_{p}^{2}$ SPT with an
accidentally enhanced symmetry? To answer this question, we consider breaking
the symmetry down as $G\leadsto\pi_{*}(\mathcal{G})=q\mathbb{Z}_{pq}^{2}$
($i.e.$ the generators of $G$ are broken, but their $q$-fold powers are not).
The projective center of $\pi_{*}(\mathcal{G})$ is

$C_{q}^{q\mathbb{Z}_{pq}^{2}}=\frac{p}{\gcd(p,q)}\mathbb{Z}^{2}_{p}=\mathbb{Z}^{2}_{\gcd(p,q)}=\begin{dcases}\mathbb{Z}_{1}&q\neq
p\\\ \mathbb{Z}_{p}^{2}&q=p\end{dcases}$ (241)

where in the last equality we used that $p,q$ are prime. Thus the number of
edge modes is unchanged upon breaking
$\mathbb{Z}_{pq}^{2}\leadsto\mathbb{Z}_{p}^{2}$ if $p\neq q$ (and hence in
this case the full $G$ symmetry should be viewed as being accidental), while
the edge modes are completely eliminated if $q=p$ (so that in this case $G$
cannot be broken to any subgroup without completely trivializing the theory).
The latter fact is especially clear when one realizes that when $q=p$,
$\pi_{*}(\mathcal{G})=p\mathbb{Z}_{p^{2}}^{2}=C$.

###  K.3 Picture of general SPT ground states

We now need the counterpart to theorem 3, which established that for MNC
$\omega$, any $|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$ can be written
as a collection of linear symmetry actions (‘errors’) acting on the reference
state $|\Psi_{\omega}\rangle$. In what follows we will set
$\widetilde{g}_{\bullet}=e$ to be the identity for simplicity.

We begin by characterizing a basis for operators which is particularly well-
suited for the task at hand. Our previous operator decomposition formula can
be generalized as follows:

######  Proposition 13.

Any single-site operator $\mathcal{O}$ can be decomposed as

$\mathcal{O}=\sum_{g,h\in
G}C_{g,h}\mathcal{R}_{g}S^{R}_{\bar{h}}\mathcal{W}_{\widetilde{h}},$ (242)

where $C_{g,h}$ are complex coefficients, and the operators
$\mathcal{W}_{\widetilde{h}}$ are defined as

$\mathcal{W}_{\widetilde{h}}\equiv\sum_{\widetilde{l}\in
C}\mathbf{1}_{l}\otimes|{\widetilde{l}+\widetilde{h}}\rangle\langle{\widetilde{l}}|\otimes
V_{\Gamma^{-1}_{\omega}(\bar{\delta}(\widetilde{l},\widetilde{h}))}.$ (243)

###### Proof.

Consider working in the original basis, in which $R_{g}$ is diagonal and acts
in the regular representation (193). This representation is naturally
associated with the basis $\\{|g\rangle\,:\,g\in G\\}$ for the local Hilbert
space. Define the shift operators

$X_{g}=\sum_{h\in G}|{h+g}\rangle\langle{h}|.$ (244)

It is then straightforward to check that the set $\\{X_{g}R_{h}\,:\,g,h\in
G\\}$ generates all on-site operators. Indeed, this set clearly contains
$|G|^{2}=\dim(\mathcal{H})^{2}$ operators which are all linearly independent,
as

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

The $X_{g}$ and $R_{h}$ satisfy the commutation relation

$R_{g}X_{h}=\chi_{g}(h)X_{h}R_{g}.$ (246)

To find an operator basis better suited for the entangled pairs
representation, one possibility is to simply transform the $X_{h}$ into the
entangled pairs basis. We will do something that is nearly equivalent to this,
by looking for operators that pick up the same phase $\chi_{g}(h)$ upon
commuting past $\mathcal{R}_{g}$. Define the operator

$\mathcal{X}_{h}\equiv\sum_{\widetilde{l}\in
C}\mathbf{1}_{l}\otimes|{\widetilde{l}+\widetilde{h}}\rangle\langle{\widetilde{l}}|\otimes
V_{\Gamma_{\omega}^{-1}(\bar{h})}V_{\Gamma^{-1}_{\omega}(\bar{\delta}(\widetilde{l},\widetilde{h}))}.$
(247)

Commuting this past $\mathcal{R}_{g}$, we find

$\displaystyle\mathcal{R}_{g}\mathcal{X}_{h}$
$\displaystyle=\sum_{\widetilde{l}\in
C}V_{\underline{g}}^{*}\otimes\chi_{\theta(\widetilde{l}+\widetilde{h})}(g)|{\widetilde{l}+\widetilde{h}}\rangle\langle{\widetilde{l}}|\otimes
V_{\underline{g}}V_{\Gamma_{\omega}^{-1}(\bar{h})}V_{\Gamma^{-1}_{\omega}(\bar{\delta}(\widetilde{l},\widetilde{h}))}$
(248) $\displaystyle=\sum_{\widetilde{l}\in
C}V_{\underline{g}}^{*}\otimes\chi_{\theta(\widetilde{l})+\theta(\widetilde{h})-\delta\theta(\widetilde{l},\widetilde{h})}(g)|{\widetilde{l}+\widetilde{h}}\rangle\langle{\widetilde{l}}|\otimes
V_{\Gamma_{\omega}^{-1}(\bar{h})}V_{\Gamma^{-1}_{\omega}(\bar{\delta}(\widetilde{l},\widetilde{h}))}V_{\underline{g}}\chi^{\mathcal{G}}_{\bar{g}}(\underline{h}+\bar{\delta}(\widetilde{l},\widetilde{h}))$
$\displaystyle=\chi_{\bar{g}}^{\mathcal{G}}(\underline{h})\chi_{\theta(\widetilde{g})}(h)\mathcal{X}_{h}\mathcal{R}_{g}$
$\displaystyle=\chi_{g}(h)\mathcal{X}_{h}\mathcal{R}_{g}.$

where the last line follows from our character decomposition formula (215),
and where in the third equality we used121212For the example of
$G=\mathbb{Z}_{pq}^{2},\omega=q$ used earlier, this string of equalities reads
$\zeta_{pq}^{\delta\theta(\widetilde{l},\widetilde{h})\cdot
g}=\zeta_{pq}^{\delta\theta(\widetilde{l},\widetilde{h})\cdot[g]_{p}}=\zeta_{p}^{(\delta\theta(\widetilde{l},\widetilde{h})/q)[g]_{p}},$
(249) with $\underline{g}=[g]_{p}$ and
$\delta\theta(\widetilde{l},\widetilde{h})\in q\mathbb{Z}_{pq}^{2}$.

$\displaystyle\chi_{\delta\theta(\widetilde{l},\widetilde{h})}(g)$
$\displaystyle=\chi_{\delta\theta(\widetilde{l},\widetilde{h})}(\pi^{-1}\pi(g))=\chi^{\mathcal{G}}_{\pi_{*}^{-1}(\delta\theta(\widetilde{l},\widetilde{h}))}(\underline{g})=\chi^{\mathcal{G}}_{\bar{\delta}(\widetilde{l},\widetilde{h})}(\underline{g}).$
(250)

This suggests that $\\{\mathcal{R}_{g}\mathcal{X}_{h}\,:\,g,h\in G\\}$ forms a
complete basis of operators. We check this by calculating the trace
$\text{Tr}[\mathcal{R}_{g}\mathcal{X}_{h}\mathcal{X}_{h^{\prime}}^{\dagger}\mathcal{R}_{g^{\prime}}^{\dagger}]$.
To do so we first write

$\displaystyle\mathcal{X}_{h}\mathcal{X}_{h^{\prime}}^{\dagger}$
$\displaystyle=\sum_{\widetilde{l}\in
C}\mathbf{1}\otimes|{\widetilde{l}+\widetilde{h}}\rangle\langle{\widetilde{l}+\widetilde{h}^{\prime}}|\otimes
V_{\Gamma_{\omega}^{-1}(\bar{h})}V_{\Gamma^{-1}_{\omega}(\bar{\delta}(\widetilde{l},\widetilde{h}))}V_{\Gamma^{-1}_{\omega}(\bar{\delta}(\widetilde{l},\widetilde{h}^{\prime}))}^{\dagger}V_{\Gamma_{\omega}^{-1}(\bar{h}^{\prime})}^{\dagger}$
(251) $\displaystyle=\sum_{\widetilde{l}\in
C}\lambda_{h,h^{\prime},\widetilde{l}}\mathbf{1}\otimes|{\widetilde{l}+\widetilde{h}}\rangle\langle{\widetilde{l}+\widetilde{h}^{\prime}}|\otimes
V_{\Gamma^{-1}_{\omega}(\bar{h}-\bar{h}^{\prime}+\bar{\delta}(\widetilde{l},\widetilde{h})-\delta(\widetilde{l},\widetilde{h}^{\prime}))},$

where we have defined the rather ugly-looking function

$\lambda_{h,h^{\prime},\widetilde{l}}\equiv\varsigma_{\Gamma^{-1}_{\omega}(\bar{h}^{\prime}+\bar{\delta}(\widetilde{l},\widetilde{h}^{\prime}))}\omega(\Gamma^{-1}_{\omega}(\bar{h}+\bar{\delta}(\widetilde{l},\widetilde{h})),-\Gamma_{\omega}^{-1}(\bar{h}^{\prime}+\bar{\delta}(\widetilde{l},\widetilde{h}^{\prime})))\omega(\Gamma_{\omega}^{-1}(\bar{h}),\Gamma_{\omega}^{-1}(\bar{\delta}(\widetilde{l},\widetilde{h}))\omega^{*}(\Gamma_{\omega}^{-1}(\bar{h}^{\prime}),\Gamma_{\omega}^{-1}(\bar{\delta}(\widetilde{l},\widetilde{h}^{\prime}))),$
(252)

which satisfies $\lambda_{h,h,\widetilde{l}}=1$. Thus

$\displaystyle\text{Tr}[\mathcal{R}_{g}\mathcal{X}_{h}\mathcal{X}_{h^{\prime}}^{\dagger}\mathcal{R}_{g^{\prime}}^{\dagger}]$
$\displaystyle=\delta_{\widetilde{h},\widetilde{h}^{\prime}}\sum_{\widetilde{l}\in
C}\lambda_{h,h^{\prime},\widetilde{l}}\chi_{\theta(\widetilde{l})}(g-g^{\prime})\text{Tr}[V^{*}_{\underline{g}}V^{T}_{\underline{g}^{\prime}}\otimes
V_{\underline{g}}V^{\dagger}_{\underline{g}^{\prime}}V_{\Gamma^{-1}_{\omega}(\bar{h}-\bar{h}^{\prime})}]$
(253)
$\displaystyle=\delta_{\widetilde{h},\widetilde{h}^{\prime}}\delta_{\underline{g},\underline{g}^{\prime}}\sqrt{|\mathcal{G}|}\sum_{\widetilde{l}\in
C}\lambda_{h,h^{\prime},\widetilde{l}}\chi_{\theta(\widetilde{l})}(\iota(\underaccent{\sim}{g})-\iota(\underaccent{\sim}{g}^{\prime}))\text{Tr}[V_{\Gamma^{-1}_{\omega}(\bar{h}-\bar{h}^{\prime})}]$
$\displaystyle=\delta_{\widetilde{h},\widetilde{h}^{\prime}}\delta_{\bar{h},\bar{h}^{\prime}}\delta_{\underline{g},\underline{g}^{\prime}}|\mathcal{G}|\sum_{\widetilde{l}\in
C}\chi^{C}_{\widetilde{l}}(\underaccent{\sim}{g}-\underaccent{\sim}{g}^{\prime})$
$\displaystyle=\delta_{h,h^{\prime}}\delta_{g,g^{\prime}}|G|,$

as desired.

We now simply realize that $\mathcal{X}_{h}$ can be broken up as

$\mathcal{X}_{h}=S^{R}_{\Gamma_{\omega}^{-1}(\mkern
1.5mu\overline{\mkern-1.5muh\mkern-1.5mu}\mkern
1.5mu)}\mathcal{W}_{\widetilde{h}},$ (254)

The algebra $L^{2}(\mathcal{H})$ of onsite linear operators is then generated
as

$L^{2}(\mathcal{H})=\langle\mathcal{R}_{g}S^{R}_{\bar{h}}\mathcal{W}_{\widetilde{h}}\,\,:\,\,g,h\in
G\rangle,$ (255)

as claimed. ∎

For our analysis of SPT ground states, we further need to know how symmetric
operators can be decomposed. The following proposition follows easily from the
commutation relation (248) and character orthogonality:

######  Proposition 14.

Any multi-site symmetric operator $\mathcal{O}_{sym}$ can be decmposed as

$\mathcal{O}_{sym}=\sum_{\mathbf{g},\mathbf{h}\in
G^{L}}C_{\mathbf{g},\mathbf{h}}\delta\left(\sum_{i}h_{i}\right)\bigotimes_{i=1}^{L}\mathcal{R}_{g_{i}}\mathcal{X}_{h_{i}},$
(256)

where the $C_{\mathbf{g},\mathbf{h}}$ are complex coefficients.

###### Proof.

The proof is straightforward, and simply involves making use of the
commutation relation (248): for a general operator $\mathcal{O}$, we have

$\mathcal{O}\mathcal{R}_{g}^{\otimes L}=\mathcal{R}_{g}^{\otimes
L}\sum_{\mathbf{g},\mathbf{h}\in
G^{L}}\chi_{g}(\sum_{i}h_{i})C_{\mathbf{g},\mathbf{h}}\bigotimes_{i=1}^{L}\mathcal{R}_{g_{i}}\mathcal{X}_{h_{i}}.$
(257)

Since all of the terms in this linear combination are linearly independent,
character orthgoonality means that $\mathcal{O}$ is symmetric iff
$\sum_{i}h_{i}=e$. ∎

We can now state the analogue of theorem 3 for the case of general $\omega$:

######  Theorem 6 (relation between SPT states in the same phase, general
$\omega$).

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

$|\psi_{\omega}\rangle=\sum_{\mathbf{g},\mathbf{h}\in
G^{L}}C_{\mathbf{g},\mathbf{h}}\mathcal{R}_{\mathbf{g}}S^{R}_{\bar{\mathbf{h}}}\mathcal{W}_{\widetilde{\mathbf{h}}}|\Psi_{\omega}\rangle,$
(258)

where the $C_{\mathbf{g},\mathbf{h}}$ are complex coefficients satisfying

$\sum_{\mathbf{g},\mathbf{h}}|C_{\mathbf{g},\mathbf{h}}|^{2}=1,$ (259)

and the $\mathbf{h}$ are restricted so that

$\sum_{i}\widetilde{h}_{i}=e,\qquad\sum_{i}\bar{h}_{i}=-\sum_{i}\mathsf{rem}(\widetilde{\mathbf{h}})_{i},$
(260)

with the first equality holding in $C$ and the second holding in
$\mathcal{G}$, and where we have defined

$\mathsf{rem}(\widetilde{\mathbf{h}})_{i}\equiv\bar{\delta}\left(\sum_{j<i}\widetilde{h}_{j},\widetilde{h}_{i}\right)$
(261)

to be the remainder in $\mathcal{G}$ accumulated when adding the components of
$\widetilde{\mathbf{h}}$ up to the position $i$.

###### Proof.

The proof is a straightforward consequence of the decomposition (256), with
the conditions in (260) just coming from the fact that the sum over
$\mathbf{h}$ in (256) is restricted to those vectors such that
$\sum_{i}h_{i}=e$, together with the addition rule (218).

∎

Note that because we have chosen $\widetilde{g}_{\bullet}=e$, the
$\mathcal{W}_{\widetilde{\mathbf{h}}}$ operators in (258) only act as shift
matrices on $\mathcal{H}_{flav}$ (that is, they act trivially on
$\mathcal{H}_{MNC}$), since their action on $\mathcal{H}_{re}$ is controlled
by $\bar{\delta}(\widetilde{g}_{\bullet},\widetilde{h}_{i})$, which vanishes
for all $\widetilde{h}_{i}$ if $\widetilde{g}_{\bullet}=e$.

As written in (258), $|\psi_{\omega}\rangle$ is still not in a form that is
amenable to be analyzed with the EC machinery developed in previous sections.
This is because unlike in the case where $\omega$ is MNC, here the errors
acting on $|\Psi_{\omega}\rangle$ in (231) do not consist solely of onsite
symmetry operators. The problem here is ultimately the fault of the
$\mathcal{W}_{\widetilde{\mathbf{h}}}$ operators, which entangle the flavor
degrees of freedom on $\mathcal{H}_{flav}$ with those on $\mathcal{H}_{MNC}$.
They arise becuase of the addition rule (218), which says that shifting the
flavor degrees of freedom by amounts $\widetilde{h}_{i}$ with
$\sum_{i}\widetilde{h}_{i}$ trivial in $C$ is actually not in general a
symmetry — rather, one has a symmetry only if the sum
$\sum_{i}\theta(\widetilde{h}_{i})\in\pi_{*}(\mathcal{G})$ is trivial in $G$.
When $\sum_{i}\theta(\widetilde{h}_{i})\neq e$, symmetry is restored only when
one performs a compensating action on $\mathcal{H}_{MNC}$, which is reflected
in the constraint on $\bar{\mathbf{h}}$ in (260).

This means that when we look only at $\mathcal{H}_{MNC}$, the errors in (231)
do not appear to be symmetric, since $\sum\bar{h}_{i}$ is not in general equal
to the identity. Thus directly acting on $\mathcal{H}_{MNC}$ with the RG
circuit $\bar{\mathcal{Q}}_{\omega}$ — whose performance is predicated on the
assumption that only symmetric errors are present — will yield garbage. In
order to use $\bar{\mathcal{Q}}_{\omega}$ to perform phase recognition, we
need to convert the errors appearing in (258) into errors that are symmetric
when restricted to $\mathcal{H}_{MNC}$. Doing this is the task addressed in
the following subsection.

###  K.4 Removing the mixed errors

Our goal in this subsection is to construct a procedure by which the errors in
(258) can be converted into a set of errors which are symmetric when
restricted to $\mathcal{H}_{MNC}$.

Suppose we are given the value of $\widetilde{\mathbf{h}}$ for a particular
term in the linear combination of (258). We can then proceed as follows.
Starting from site $i=1$, we move along the chain and compute a running sum
$\sum_{j=1}^{i}\theta(\widetilde{h}_{j})$. Each time this sum ‘overflows’ in
$C$ and generates a remainder of an amount
$\mathsf{rem}(\widetilde{\mathbf{h}})_{i}\in\mathcal{G}$, one acts on the
wavefunction with the operator
$S^{R}_{-\Gamma^{-1}_{\omega}(\mathsf{rem}(\widetilde{\mathbf{h}})_{i}),i}$.
Sweeping across the entire chain in this matter thus ensures that one is left
with a state in which $\mathcal{H}_{MNC}$ is acted on by
$S^{R}_{\bar{\mathbf{h}}^{\prime}},$ where $\sum_{i}\bar{h}_{i}^{\prime}=e$.
Adding up the values of $\widetilde{h}_{i}$ in a local way ensures that the
$S^{R}_{-\Gamma^{-1}_{\omega}(\mathsf{rem}(\widetilde{\mathbf{h}})_{i}),i}$
operators are inserted in such a way that the combined product of shift
operators acting on $|\Psi_{\omega}\rangle$ always combine into charge-neutral
blocks over distances of a correlation length $\xi$ (with $\xi$ set by the
coefficients $C_{\mathbf{g},\mathbf{h}}$ as usual).

The process just described is results in the following protocol to eliminate
the mixed errors and perform phase recognition:

  1. 1.

Measure the flavor degrees of freedom in the computational basis of
$\mathcal{H}_{flav}$. Let the outcome of this measurement be
$\widetilde{\mathbf{h}}$ (after measuring, the subsystem $\mathcal{H}_{flav}$
can be discarded, as it will be decoupled from $\mathcal{H}_{MNC}$ for the
remainder of the protocol).

  2. 2.

Use an $O(L)$ amount of classical data processing to compute
$\mathsf{rem}(\widetilde{\mathbf{h}})$.

  3. 3.

Apply $\mathcal{U}_{\mathsf{rem}}(\widetilde{\mathbf{h}})$ to the measured
state, where

$\mathcal{U}_{\mathsf{rem}}(\widetilde{\mathbf{h}})\equiv\bigotimes_{i=1}^{L}S^{R}_{-\Gamma^{-1}_{\omega}(\mathsf{rem}(\widetilde{\mathbf{h}})_{i}),i}$
(262)

is a product of single-site unitaries that converts the mixed errors into
errors acting only on $\mathcal{H}_{MNC}$.

  4. 4.

Proceed by applying the error correction circuit $\bar{\mathcal{Q}}_{\omega}$
to $\mathcal{H}_{MNC}$.

While $\mathcal{U}_{\mathsf{rem}}(\widetilde{\mathbf{h}})$ is simply a tensor
product of single-qudit rotations, the data processing involved in computing
$\mathsf{rem}(\widetilde{\mathbf{h}})_{i}$ is non-local, since
$\mathsf{rem}(\widetilde{\mathbf{h}})_{i}$ depends on
$\widetilde{\mathbf{h}}_{j}$ for all $j\leq i$. Also note that we do not need
to post-select on the measurement outcomes $\widetilde{\mathbf{h}}$: any
outcome is as good as any other for the purposes of performing phase
recognition, as each set of terms with a fixed $\widetilde{\mathbf{h}}$ in the
linear combination (258) contain all of the information about the universal
aspects of the SPT phase.

That step 4 of the above protocol sufficies to perform phase recognition is
established by the following proposition:

######  Proposition 15.

For any $|\psi_{\omega}\rangle\in\mathsf{SPT}_{\omega}$, the state
$|\psi_{\omega}^{\widetilde{\mathbf{h}}}\rangle$ obtained after measuring the
flavor degrees of freedom to obtain the outcome $\widetilde{\mathbf{h}}$ and
applying the corrective circuit
$\mathcal{U}_{\mathsf{rem}}(\widetilde{\mathbf{h}})$ can be written as

$|\psi_{\omega}^{\widetilde{\mathbf{h}}}\rangle=\sum_{\underline{\mathbf{g}}\in
G^{L}}C_{\underline{\mathbf{g}}}(\widetilde{\mathbf{h}})\mathcal{R}^{\mathcal{G}}_{\underline{\mathbf{g}}}|\Psi_{\omega}\rangle,$
(263)

where $\mathcal{R}_{\underline{g}}^{\mathcal{G}}$ is the action of the
symmetry restricted to $\mathcal{H}_{MNC}$:

$\mathcal{R}^{\mathcal{G}}_{\underline{g}}=V_{\underline{g}}^{*}\otimes\mathbf{1}_{flav}\otimes
V_{\underline{g}}.$ (264)

###### Proof.

By construction, we have

$|\psi^{\widetilde{\mathbf{h}}}_{\omega}\rangle=\sum_{\mathbf{g}\in
G^{L},\bar{\mathbf{h}}\in\mathcal{G}^{L}}C_{\mathbf{g},\bar{\mathbf{h}}}(\widetilde{\mathbf{h}})\mathcal{R}_{\mathbf{g}}S^{R}_{\bar{\mathbf{h}}}|\Psi_{\omega}^{\widetilde{\mathbf{h}}}\rangle,$
(265)

where the $C_{\mathbf{g},\bar{\mathbf{h}}}(\widetilde{\mathbf{h}})$ are again
some set of complex coefficients, and

$|\Psi_{\omega}^{\widetilde{\mathbf{h}}}\rangle=\sum_{\mathbf{g}\in
G^{L}}\text{Tr}[A^{g_{1}}_{\widetilde{h}_{1}}\cdots
A^{g_{L}}_{\widetilde{h}_{L}}]$ (266)

is the canonical reference state with the flavor degrees of freedom fixed to
be $\widetilde{\mathbf{h}}$. Since the action of the corrective circuit
$\mathcal{U}_{\mathsf{rem}}(\widetilde{\mathbf{h}})$ yields a state in which
the errors are symmetric when restricted to $\mathcal{H}_{MNC}$, the
coefficients $C_{\mathbf{g},\bar{\mathbf{h}}}(\widetilde{\mathbf{h}})$
appearing in (265) are now constrained to satisfy $\sum_{i}\bar{h}_{i}=e$
(c.f. (260)). Thus when acting on
$|\Psi^{\widetilde{\mathbf{h}}}_{\omega}\rangle$, $S^{R}_{\bar{\mathbf{h}}}$
can be replaced by a product of $\mathcal{R}^{\mathcal{G}}_{\bar{\mathbf{h}}}$
operators for the same reasons as discussed in the proof of theorem 3. When
acting on $|\Psi^{\widetilde{\mathbf{h}}}_{\omega}\rangle$ the distinction
between between $\mathcal{R}_{\mathbf{g}}$ and
$\mathcal{R}^{\mathcal{G}}_{\underline{\mathbf{g}}}$ is not important, since
the action of the two differs only by an unimportant overall phase. Thus there
is no important dependence on $\widetilde{\mathbf{g}}$ in the sum, and so
after changing notation for the complex coefficients appearing in the linear
combination, we indeed arrive at (263).

∎

That this allows us to perform phase recognition then follows from the fact
that $|\psi_{\omega}^{\widetilde{\mathbf{h}}}\rangle$ has the same structure
as the groud state wavefunction of a MNC SPT phase. This means that our
previously developed RG circuit $\bar{\mathcal{Q}}_{\omega}$ can simply be
applied directly to $|\psi_{\omega}^{\widetilde{\mathbf{h}}}\rangle$, with the
remainder of the phase recognition procedure proceeding as in the MNC case.


Post-processing: peak picking, median filtering
3 |  | Anderson_TCD
---
(Anderson and Harte, 2021)
| CNN,
---
Prototypical Network
Acoustic features: PCEN, MelSpectrogram
Augmentation: SpecAugment
Post-processing: Probability averaging,
median filtering, minimum event length
4 | Baseline_TempMatch | Template Matching
5 |  | Cheng_BIT
---
(Cheng et al., 2021)
| CNN,
---
Prototypical Network
Acoustic features: PCEN, i-vector
Augmentation: SpecAugment.
Post-processing: threshold.
6 | Baseline_PROTO |  | CNN,
---
Prototypical Network
7 |  | Zhang_uestc
---
(Zhang et al., 2021)
| ResNet,
---
Prototypical Network
Acoustic features: PCEN
Augmentation: SpecAugment
Post-processing: threshold.
8 |  | Johannsmeier_OVGU
---
(Johannsmeier and Stober, 2021)
| CNN,
---
Prototypical Network
Acoustic features: PCEN, MelSpectrogram
Augmentation: Time stretching, Pitch and
Time shifting
Post-processing: threshold, gaussian smoothing
9 |  | Bielecki_SMSNG
---
(Bielecki, 2021)
| CNN,
---
Prototypical Network
Knowledge Distillation and Attention transfer loss.
Additional external data used.
Acoustic features: MelSpectrogram
Augmentation: melspectrogram time and
frequency masking.
Post-processing: min time length threshold,
predicted frames elongation.
Table 7: General characteristics of the 2021 submitted systems. Ordered by
rank of F-score on the evaluation set.