\section{Definition of $k$-local circuits}
\label{sec: def}
{\color{black}
In this section, we lay out the definitions of the notions of locality that we will be concerned with throughout the paper. The first and most common notion of locality is geometric locality. Any lattice system has a natural notion of distance between pairs of sites, which allows us define a geometrically local unitary gate as one which acts only on sites that can be contained within a ball of some finite radius. Here and throughout, the word finite means independent of system size, \textit{i.e.} finite even in the thermodynamic limit. Naturally, such a gate acts only on a finite number of sites in the lattice. One can construct a circuit of geometrically local gates
\begin{equation}
    U=\prod_{\ell=1}^D\left( \prod_{i} u_{\ell,i} \right)
\end{equation}
where each gate $u_{\ell,i}$ is geometrically local and the gates within a given layer $\ell$ have non-overlapping support, such that they can be applied in parallel. We call such a unitary $U$ a quantum circuit (QC). When the number of layers $D$ is finite, $U$ is called a finite-depth quantum circuit (FDQC). It is also interesting to define symmetric QCs, which are circuits in which each gate individually commutes with some symmetry operator.

We can extend the notion of the geometric locality to $k$-locality. A gate is called $k$-local if it has support on at most $k$ sites. Thus a $k$-local gate shares the few-body property of a geometrically local gate while ignoring the relative position and distance between spins. We define a $k$-local quantum circuit, $\mathrm{QC}_k$\xspace, to be composed of $k$-local gates $u_{\ell,i}$ where $k$ is finite, such that the gates are applied in layers and in each layer they have non-overlapping support. When the number of layers is finite, we call the circuit a finite-depth $\mathrm{QC}_k$\xspace ($\mathrm{FDQC}_k$\xspace).

Clearly, every QC is also a $\mathrm{QC}_k$\xspace, but in general, a $\mathrm{QC}_k$\xspace is more powerful in the sense that writing a many-body unitary operator as a $\mathrm{QC}_k$\xspace can sometimes be accomplished with lower depth than is required to write it as a QC. As a simple example, consider the unitary operator which generates the $N$-qubit GHZ state from a product state. This can only be implemented with a linear-depth QC due to the presence of long-range correlations in the GHZ state \cite{Aharonov2018}. However, it can be done with a $\mathrm{QC}_k$\xspace having depth that is logarathmic in $N$, see Refs.~\cite{Cruz2019,Liao2021} for example. Similarly, the unitary which generates the two-dimensional toric code ground state, an example of topological order, requires a linear-depth QC \cite{Bravyi2006} but can be done in a log-depth $\mathrm{QC}_k$\xspace \cite{konig2009exact,Liao2021}. Notably, neither of these unitaries can be written as an $\mathrm{FDQC}_k$\xspace \cite{Aharonov2018}, so we say that the GHZ and toric code states remain non-trivial in the $k$-local setting. In contrast, the unitaries discussed in this paper will primarily be circuits that require linear depth using a (symmetric) QC, but can be performed in finite-depth using a (symmetric) $\mathrm{QC}_k$\xspace, so we say they become trivial in the $k$-local setting.
}

\section{$k$-local instability of SPT\lowercase{s}} \label{sec:spt}

In this section, we ask whether SPT states can be prepared by symmetric FDQC$_k$. In Secs.~\ref{sec:1D} and \ref{sec:2D} we consider global on-site symmetries. While it is known that a linear-depth symmetric QC is needed to create an SPT ground state \cite{HuangChen} from a symmetric product state, we will show that a symmetric $\mathrm{FDQC}_k$\xspace is sufficient. We first give an intuitive physical argument as to why this is the case by studying the boundaries of SPT phases, and we then construct an explicit finite-depth $k$-local symmetric circuit that disentangles fixed-point SPT states. In Sec.~\ref{sec:SSPT}, we show that SPT phases protected by subsystem symmetries (SSPT phases) can also become trivial in the $k$-local scenario. Conversely, we argue in Sec.~\ref{sec:higherformSPT} that SPT phases protected by higher-form symmetries remain non-trivial even in the $k$-local scenario. In Appendix \ref{app:finitetime}, we give alternative finite-time $k$-local constructions of SPT states which have the advantage that all interactions are local except for one special qubit which can interact with all others.


\subsection{1D SPT phases with global symmetries} \label{sec:1D}

Let us first consider 1D SPT phases. The characteristic feature of 1D SPT order is the existence of zero-energy edge modes that are protected by the bulk symmetry. On periodic boundaries, the ground state is unique. But when an edge is introduced, there is a ground state degeneracy that is exponentially localized near the two edges of the system. These edge modes are robust in the sense that no local, symmetric perturbation can split the degeneracy. However, these edge modes are not robust to $k$-local interactions, as a symmetric interaction can be used to couple the two edges in such a way as to split the degeneracy. This suggests that 1D SPT orders are not robust to $k$-local symmetric interactions. However, there may still be some non-trivial bulk properties that cannot be removed by $k$-local interactions. We show that this is not the case by explicitly constructing a symmetric $\mathrm{FDQC}_k$\xspace which maps generic SPT fixed-point states to product states. 

We can understand why such a circuit should exist using a simple folding argument. Namely, consider a 1D SPT ordered state $|\psi\rangle$ on a ring. Suppose that we ``fold'' the ring, bringing the two opposite sides close to each other. In the bulk of the folded system, it looks like we have stacked the state with its spatially reversed self, see Fig.~\ref{fig:1d_disentangler}. However, it is well known that SPT phases are invertible, meaning that there exists a second state $|\psi^{-1}\rangle$ such that the joint system $|\psi\rangle\otimes |\psi^{-1}\rangle$ is in a trivial SPT phase. For this statement to make sense, it is important to specify how the symmetry acts on the joint system. If $|\psi\rangle$ has symmetry $G$ with an on-site representation $U(g)$, then the symmetry acts on the joint system ``diagonally'', \textit{i.e.} with representation $U(g)\otimes U(g)$ of $G$. If we instead considered the symmetry group $G\times G$ represented by $U(g)\otimes U(h)$ with $g$ not necessarily equal to $h$, then the stacked system is still in a nontrivial phase with respect to this larger symmetry. In the folded system, the global symmetry indeed acts in the same way across the whole ring, so the total symmetry group is still only $G$.

It turns out that the spatial inverse of the SPT fixed-point states is in fact the inverse state in the above sense \cite{Chen2013}, so the bulk of the folded system looks like a trivial SPT phase. Then, there must be a symmetric finite-depth circuit that disentangles the bulk to a product state. Looking at this picture without folding, the disentangling circuit couples the two distant edges of the ring, therefore requiring long-range $k$-local gates.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{1d_disentangler.png}
    \caption{Disentangling 1D SPT phases with $k$-local symmetric gates. After folding a 1D chain with periodic boundary conditions in half, the resulting system looks like a stack of the chain and its spatial inverse in the bulk. This stack can be disentangled with symmetric gates acting on the highlighted qubits, which correspond to $k$-local gates in the original system. For fixed-point SPT states, these gates are the $W_i$ defined in Eq.~\ref{eq:wi_cluster}, one such gate is highlighted in red where each line is a $CZ$ gate. Note that the adjacent vertical gates cancel each other pairwise in the bulk.}
    \label{fig:1d_disentangler}
\end{figure}

Let us explicitly construct such a circuit. We give only a single example here, as the general case is covered by the construction in Sec.~\ref{sec:qca}.
The example we consider is the 1D cluster state \cite{Briegel2001}, which can be created from a product state using a finite circuit in the following way,
\begin{equation} \label{eq:1d_clus}
    |\psi_C\rangle = \left(\prod_{i=1}^N CZ_{i,i+1}\right) |+\rangle^{\otimes N}
\end{equation}
where $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ and $CZ = I - 2|11\rangle\langle 11|$ is the controlled-$Z$ gate. Assuming $N$ is even, $|\psi_C\rangle$ has a $\mathbb{Z}_2\times\mathbb{Z}_2$ symmetry generated by $X_{\mathrm{odd}} = \prod_{i=1}^{N/2} X_{2i+1}$ and $X_{\mathrm{even}} = \prod_{i=1}^{N/2} X_{2i}$. 

Importantly, while the circuit of controlled-$Z$ gates commutes with this symmetry as a whole, the individual gates do not. Since the 1D cluster state has non-trivial SPT order \cite{Son2012}, there does not exist a symmetric FDQC which maps it to a product state \cite{Chen2011,HuangChen}. However, it is possible using a symmetric $\mathrm{FDQC}_k$\xspace. Consider the gates,
\begin{equation} \label{eq:wi_cluster}
    W_i = CZ_{i,i+1} CZ_{i+1,N-i} CZ_{N-i+1,N-i} CZ_{N-i+1,i},
\end{equation}
which are depicted in Fig.~\ref{fig:1d_disentangler}. It is straightforward to check that $W_i$ commutes with the $\mathbb{Z}_2\times\mathbb{Z}_2$ symmetry. Furthermore, we have,
\begin{equation} \label{eq:1dspt_disent}
    \left( \prod_{i=1}^{N/2-1} W_i \right)|\psi_C\rangle = |+\rangle^{\otimes N},
\end{equation}
as shown in Fig.~\ref{fig:1d_disentangler}. Since the $W_i$ all commute with each other, and since the support of each $W_i$ overlaps with the support of finitely many others, they can be applied in a finite number of layers such that this is a symmetric $\mathrm{FDQC}_k$\xspace which trivializes the cluster state.

It is instructive to note that $W_i$ is the operator that creates a small 4-site cluster state on a ring, which explains why it is symmetric. The $k$-local disentangling circuit can therefore be interpreted as a ``bubbling'' procedure in which one decomposes the $N$-site cluster state into a number of small 4-site cluster states and then disentangles each 4-site cluster state with a symmetric $k$-local gate. 

\subsection{2D and higher-dimensional SPT phases} \label{sec:2D}

\begin{figure}
    \centering
    \includegraphics[width=0.8\linewidth]{2d_disentangler.png}
    \caption{Disentangling 2D SPT phases with $k$-local symmetric gates. We show a folded system with spherical boundary conditions, which leads to a thin rectangular prism. A torus is obtained by identifying the left and right faces. A subset of the lattice coloring is shown. The rectangular prism geometry can be decomposed into smaller rectangular prisms. The symmetric gate $W_p$ is defined by acting with $CCZ$ on all 12 of the triangular faces of this prism. When applying $W_p$ to every prism, all bulk gates that act on faces parallel to the $z$-axis cancel between neighboring prisms, leaving only gates on the surface of the large rectangular prism.}
    \label{fig:2d_disentangler}
\end{figure}


The folding argument from the previous section carries over equally well to SPT phases with global symmetries in 2D and higher. We give only the 2D argument explicitly, as the generalization to higher dimensions is straightforward. We again give a single example as the general case (in all dimensions) is covered by Sec.~\ref{sec:qca}.

As in 1D, we can predict that 2D SPT phases are trivial with $k$-local interactions by considering the boundary. Consider the example of a topological insulator, which has a gapless helical edge on the boundary of a disk. With local symmetric interactions, the edge cannot be gapped out without breaking the symmetry (although see \cite{ChouTI, KimchiTI}). However two opposite points on the boundary have helical currents moving in opposite directions, which could backscatter off each other if coupled by a $k$-local perturbation. Therefore, it is possible to introduce a $k$-local symmetric term that couples opposite points and gaps out the edge without breaking symmetry. 

As before, we will confirm this intuition by constructing explicit symmetric $\mathrm{FDQC}_k$\xspace disentanglers. As our example, we choose the 2D hypergraph state, first defined in Ref.~\cite{Yoshida2016}. The state is defined on a triangular lattice with one qubit per site. We choose boundary conditions of a sphere for our demonstration, but a torus would work equally well. The state is defined as follows,
\begin{equation} \label{eq:hypergraph}
    |\psi_H\rangle = \left(\prod_{\triangle} CCZ_\triangle\right) |+\rangle^{\otimes N}
\end{equation}
where $CCZ$ acts on the three qubits around a triangle as $CCZ = I-2|111\rangle\langle 111|$. This state has SPT order protected by a $\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2$ symmetry \cite{Yoshida2016}. This symmetry relies on the fact that the lattice is 3-colorable, meaning that each site can be assigned a color (red, blue, or green) such that neighboring sites have different colors, see Fig.~\ref{fig:2d_disentangler}. The symmetry is then generated by the operators $X_R$, $X_B$, and $X_G$, which are tensor products of $X$ on every red, blue, and green site, respectively. We remark that this state is closely related to the Levin-Gu state \cite{Levin2012} which is an example of 2D SPT order with $\mathbb{Z}_2$ symmetry \footnote{The Levin-Gu state can be obtained by acting on $|\psi_H\rangle$ with $CZ$ on every neighboring pair of spins and $Z$ on every spin \cite{Wei2018a}.}. As before, the circuit of $CCZ$'s is symmetric as a whole on closed boundary conditions, but the individual gates are not symmetric.

By folding the 2D system, we get a state defined on the surface of a thin rectangular prism. This rectangular prism can be decomposed into a number of small rectangular prisms with triangular faces, see Fig.~\ref{fig:2d_disentangler}. We label these prisms by $p\in P$. For each such prism $p$, we define a gate,
\begin{equation}
    W_p = \prod_{\triangle\in p} CCZ_\triangle,
\end{equation}
which is depicted in Fig.~\ref{fig:2d_disentangler}. As in the 1D case, this operator can be interpreted as creating a small instance of $|\psi_H\rangle$ on a triangulation of a sphere, and it, therefore, respects the $\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2$ symmetry. Applying this operator to every prism, we have,
\begin{equation}
    \left(\prod_{p\in P} W_p\right) |\psi_H\rangle = |+\rangle^{\otimes N},
\end{equation}
so this is a symmetric $\mathrm{FDQC}_k$\xspace disentangler.

\subsection{SPT phases with subsystem symmetries}
\label{sec:SSPT}

\begin{figure}
    \centering
    \includegraphics[width=0.8\linewidth]{sspt_disentangler.png}
    \caption{ Disentangling 2D SSPT phases with $k$-local symmetric gates. The dashed lines are shown as a guide for the eye. A torus is obtained by identifying the left and right opposite faces. The gate $W_c$ consists of $CZ$s on every solid edge, with qubits on located at the small dots (not drawn on the upper figure). The thick solid loop and dots indicate the support of one line-like subsystem symmetry generator.
    }
    \label{fig:sspt_disentangler}
\end{figure}

We now turn to SPT phases protected by subsystem symmetries. These are symmetries that act on rigid, lower-dimensional submanifolds of the entire system, such as straight lines across a 2D lattice \cite{Raussendorf2019,You2018,Devakul2019,Devakul2018class,You2020}. These are similar to 1D SPTs, in that they are characterized by an extensive degeneracy on the edge \cite{You2018,Devakul2019}. Indeed, if a 2D SSPT phase on a cylinder is treated like a quasi-1D system along the cylinder's length, then it behaves like a 1D SPT phase with a sub-extensive number of symmetry generators \cite{Stephen2019}.

The prototypical SSPT phase is represented by the 2D cluster state \cite{Briegel2001}. This state consists of qubits on a 2D square lattice and is defined as follows,
\begin{equation}
    |\psi_{2DC}\rangle = \left(\prod_{\langle ij\rangle} CZ_{i,j}\right)|+\rangle^{\otimes N},
\end{equation}
where the product is over all nearest neighbors in the square lattice. The symmetries of this model form rigid diagonal lines spanning the square lattice, defined as,
\begin{equation}
    U_{c,\pm} = \prod_x X_{(x,c\pm x)}
\end{equation}
where $i=(x,y)$ is a coordinate on the 2D square lattice. Similar to the cases of global symmetry, one can use the folding trick to create $|\psi_{2DC}\rangle$ on a closed 2D manifold using a symmetric $\mathrm{FDQC}_k$\xspace consisting of the symmetric $k$-local gates $W_c$ defined in Fig.~\ref{fig:sspt_disentangler}. 

We remark that, in order for a diagonal line of symmetry to act the same on the top and bottom layers of the fold as in Fig.~\ref{fig:sspt_disentangler}---which is necessary for the folding argument to work---we needed to put $|\psi_{2DC}\rangle$ on a $45^\circ$-rotated square lattice. We note that this results in some triangular faces appearing on spherical boundaries (which are absent on the torus). For general subsystem symmetries, which can have more complex geometries such as fractal geometries \cite{Devakul2018class}, we expect that a symmetric $\mathrm{FDQC}_k$\xspace will only be able to create SSPT states on spatial manifolds with nice enough geometry such that there are distant regions in space where the symmetry mirrors itself.

\subsection{SPT phases with higher-form symmetries}
\label{sec:higherformSPT}


In this section, we argue that, in contrast to global and subsystem symmetries, phases protected by higher-form symmetries are robust to $k$-local symmetric interactions. In general, a $q$-form symmetry is one that acts on closed codimension-$q$ submanifolds of space. In contrast to subsystem symmetries, these submanifolds are not rigid and can be deformed freely. These symmetries are local in the sense that they may have support on only a finite number of sites. For example, a 1-form symmetry in 3D is generated by objects acting on any closed 2D surface embedded in the 3D space.

We first observe that the folding argument used for global symmetries does not carry over to the case of higher-form symmetries. This is because folding in this case does not correspond to stacking in the usual sense. Recall that stacking requires the symmetry to act in the same way on the two layers. When we fold a system with global symmetry, acting with the symmetry on the whole system automatically has identical action on the two layers of the fold. However, this is not the case when we fold a system with higher-form symmetry, since the symmetry generators can act independently on either layer. Because of this, the bulk of the folded system resembles two stacked SPT states, each with its own independent symmetry, and such a system has non-trivial SPT order. More concretely, any $k$-local gate which acts on $k$ distant qubits also commutes \textit{locally} with the symmetry. This is in contrast to the $\mathrm{FDQC}_k$\xspace{}'s used to disentangle the SPTs above which only commute with the symmetry globally. In Sec.~\ref{sec:randomcirc}, we give numerical evidence for the 1D cluster state that $k$-local gates which commute with the symmetry locally are not sufficient to destroy the SPT order, suggesting the same may be true for higher-form SPTs.

Examining the boundary of a higher-form SPT also suggests that it may be $k$-local non-trivial. Higher-form SPTs in 3D, for example, 
can support topologically ordered boundary theories such as a 2D toric code \cite{Walker2012,Yoshida2016}. However, unlike in the case of global symmetry discussed above, $k$-local interactions cannot trivialize this boundary theory because the 2D toric code, and any number of stacks of it, is $k$-local non-trivial \cite{Aharonov2018}.  


\section{Unified construction of symmetric $k$-local circuits for QCA} \label{sec:qca}

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{shift_qca.png}
    \caption{(a) A pair of counter-propagating 1D QCA implementing the shift operation, where information flows in the directions of the arrows, can be realized by a depth-2 $k$-local circuit of SWAP gates, indicated by double-headed arrows, where all solid arrows first act in parallel, then all dotted arrows act in parallel. (b) Truncating this circuit stitches the top and bottom lines of qubits into a single ring acted on by the shift QCA.}
    \label{fig:shift_qca}
\end{figure}

In this section, we show that locality-preserving unitary operators, also known as quantum cellular automata (QCA) \cite{Farrelly2020}, can be implemented as $\mathrm{FDQC}_k$\xspace{}'s. We give a generic construction of these $\mathrm{FDQC}_k$\xspace{}'s that works in any spatial dimension $d$. We only deal with translationally-invariant QCA, but this condition can likely be relaxed to a certain extent. We also assume the QCA acts on a lattice with mirror symmetry in all $d$ directions. here are QCA that cannot be expressed as an FDQC, such as the 1D shift QCA $Q_{S}$ which acts on an operator $O_i$ supported on-site $i$ by shifting it by one site, $Q_S O_iQ_S^{-1} = O_{i+1}$. In 1D and 2D, it has been shown that all QCA are shifts up to an FDQC \cite{Gross2012,Freedman2020}. In 3D, however, there are believed to be QCA which are neither shifts nor circuits \cite{Haah2022,Haah2021,Shirley2022}. Our result implies that all of these QCA become trivial in the $k$-local scenario, i.e., they can be written as an $\mathrm{FDQC}_k$\xspace. Additionally, if the QCA commutes with some global symmetry, it may not be possible to write it as a \textit{symmetric} FDQC, even if it is an FDQC. Nonetheless, the $\mathrm{FDQC}_k$\xspace we construct consists of symmetric gates, so this result gives an alternative demonstration of the triviality of SPT order by applying it to the QCA which generate the SPT states, such as those in Eq.~\ref{eq:1d_clus} and Eq.~\ref{eq:hypergraph}.

The main ideas which lead to this result are the following. Given a QCA $Q$ acting in $d$ spatial dimensions, we start with the known fact that $Q\otimes Q^{-1}$ can be realized by an FDQC \cite{Arrighi2011,Farrelly2020}. By truncating this FDQC to a finite region of space, we obtain a $k$-local circuit acting on a single conjoined system. On one half of this system, the circuit acts like $Q$, while on the other half, it acts like $Q^{-1}$. We then show that $Q^{-1}$ is equivalent to the spatial inversion of $Q$ in one direction, which we denote as $\bar{Q}$, up to a finite-depth circuit consisting of $(d-1)$-dimensional QCA. The action of $Q$ on one half and $\bar{Q}$ on the other is nothing more than $Q$ applied to a periodic system. An inductive argument then concludes that $Q$ can be implemented as a $\mathrm{FDQC}_k$\xspace. This idea is demonstrated in Fig.~\ref{fig:shift_qca} for the simple example of the shift QCA. In this case, the second part of the argument is not needed as $\bar{Q}$ is already equal to $Q^{-1}$. 

\subsection{Construction from 1D Margolus representation}

Consider a QCA $Q$ which acts on a Hilbert space $\mathcal{H}=(\mathbb{C}^d)^{\otimes N}$. Now construct a doubled Hilbert space $\mathcal{H}_A\otimes \mathcal{H}_B$ made of two copies of $\mathcal{H}$. For every degree of freedom $i$ in $\mathcal{H}$, we have two degrees of freedom $[i]_A$ and $[i]_B$ in $\mathcal{H}_A\otimes \mathcal{H}_B$. Let $Q_{A}$ ($Q_B$) denote $Q$ acting on $\mathcal{H}_{A}$ ($\mathcal{H}_{B}$) and write $V=Q_B^{-1}Q_A$. Now write $\mathcal{S}_{AB}=\prod_i S_i$ where $S_i$ is the SWAP operation that exchanges sites $[i]_A$ and $[i]_B$. For now, we imagine that $A$ and $B$ are geometrically close such that $S_i$ is a local operator. Then we have,
\begin{align}
    V &= Q_B^{-1}Q_A \nonumber \\
    &=  \mathcal{S}_{AB} Q^{-1}_A \mathcal{S}_{AB} Q_A \nonumber \\
    &= \left(\prod_i S_i\right) \left(\prod_i Q^{-1}_A S_i Q_A\right).
\end{align}
Since $S_i$ is a local operator and $V$ is locality-preserving, $V_i \equiv Q_A S_i Q_A^{-1}$ is a local operator. Since the $V_i$ all commute with each other, the above formula can be parallelized into a finite-depth circuit realizing $V$. 

Now we imagine truncating the above circuit as follows,
\begin{equation} \label{eq:vr}
    V_R =\left(\prod_{i\in R} S_i\right) \left(\prod_{i\in R} Q^{-1}_A S_i Q_A\right)
\end{equation}
where $R$ is some finite connected subset of sites. Far outside of the region $R$, $V_R$ will act as the identity. Deep inside the region $R$, $V_R$ will act as $Q_AQ^{-1}_B$. To understand what happens near the boundaries of $R$, we will employ the so-called Margolus representation of a QCA. We will first describe this for 1D systems and then show how to extend to higher dimensional systems at the end.

Take the physical space to be a 1D chain with sites indexed by a single integer $i$. By blocking a finite number of sites, \textit{i.e.} enlarging the unit cell, it is always possible to make $Q$ have unit range, meaning that if $O_i$ is an operator supported on a site $i$, then $QO_iQ^{-1}$ is supported at most on sites $i-1,i,i+1$. Then, according to the results of Ref.~\cite{Schumacher2004}, the QCA can be written in the following Margolus representation,
\begin{equation} \label{eq:standard}
    Q = \left( \prod_{i} v_{2i-1,2i} \right)\left( \prod_{i} u_{2i,2i+1} \right)
\end{equation}
where $u$ is a unitary operator
mapping from the $d^2$-dimensional Hilbert space $\mathbb{C}^d\otimes \mathbb{C}^d$ to the $\ell r$-dimensional Hilbert space $\mathbb{C}^\ell\otimes\mathbb{C}^r$ where $d$ is the dimension of a unit cell and $\ell r=d^2$. Similarly, $v$ is a unitary operator mapping from $\mathbb{C}^r\otimes \mathbb{C}^\ell$ to $\mathbb{C}^d\otimes \mathbb{C}^d$.
Graphically, we can represent the right-hand side of this equation as,
\begin{equation} \label{eq:standard_form}
    \includegraphics[scale=0.5]{standard_form.png}
\end{equation}
where the solid, dashed, and dotted lines have dimensions $d$, $\ell$, and $r$, respectively. The arrows indicate the orientation of the unitaries $u$ and $v$  and are expressed formally by the spatial ordering of the Hilbert space labels on the left and the right. This will become important when we invert this orientation, as we define shortly. The standard form encompasses all 1D QCA, even the shift QCA which is not an FDQC but can nonetheless be realized with $d=2$, $\ell=1$, and $r=4$ using the following operators,
\begin{equation} \label{eq:shift_standard_form}
    \includegraphics[scale=0.25]{shift_standard_form.png}
\end{equation}
where indices connected by solid red lines take the same value. We note that the $\ell$ and $r$-dimensional Hilbert spaces are not physical, and are rather a technical tool used to write the Margolus representation. $Q$ is nonetheless a well-defined unitary operator acting on the 1D chain which can be implemented as a sequence of $k$-local gates, as we will show.

\begin{figure*}
    \centering
    \includegraphics[width=\linewidth]{1d_qca_klocal.png}
    \caption{The truncated circuit $V_R$ where the 1D QCA $Q$ is expressed in standard form. The downwards- (upwards-) shifted vertical lines correspond to degrees of freedom in the $A$ ($B$) subsystem. The lighter-colored rectangles represent the inverses $u^{-1}$ and $v^{-1}$ as indicated in the first expression. An arrow between two lines indicates the SWAP operation $S_i$ between degrees of freedom in the two subsystems. In the second expression, most gates have canceled pairwise, leaving only those shown. For visual clarity, the vertical lines have been shortened. The third expression is equivalent to the second expression up to the symmetric finite-depth quantum circuits (FDQCs) $W_1$ and $W_2$; see Eq.~\ref{eq:W1W2}. Note that the strict equivalence up to symmetric FDQCs is in one spatial dimension, $d=1$. In higher dimensions ($d>1$), we use the compactified picture such that the equivalence is up to a circuit that is finite-depth along the non-compactified direction and in general, a $(d-1)$-dimensional QCA along the $d-1$ compactified directions; see main text.}
    \label{fig:vr}
\end{figure*}


We now insert the standard form of $Q$ into the definition of $V_R$ where we take $R$ to be a segment of the 1D line $R=[c,d]$. Without loss of generality, suppose that $c$ is odd and $d$ is even such that the length of $R$ is even. We then have, 
\begin{align}
    V_R =& \left(\prod_{i=c}^d S_i\right) \left(\prod_{i=c}^d Q^{-1}_A S_i Q_A\right) \nonumber \\
    =&\left(u^{-1}_{[c-1]_A,[c]_B}u^{-1}_{[d]_B,[d+1]_A}\right)
    \nonumber \\
    & \left(\prod_{i=\frac{c+1}{2}}^{d/2-1} u^{-1}_{[2i]_B,[2i+1]_B}\right) \left(\prod_{i=\frac{c+1}{2}}^{d/2} v_{[2i-1]_A,[2i]_A}\right)
    \nonumber \\
    &\left(\prod_{i=\frac{c+1}{2}}^{d/2} v^{-1}_{[2i-1]_B,[2i]_B}\right)
    \left(\prod_{i=\frac{c-1}{2}}^{d/2} u_{[2i]_A,[2i+1]_A}\right)
\end{align}
This is depicted in the first two diagrams in Fig.~\ref{fig:vr}. As is clear from the figure, these unitaries can be parallelized into two layers of disjoint operators. Furthermore, we see that the degrees of freedom within $R$ have been stitched into a single periodic 1D system, a ring of length $L=2(d-c+1)+2$ with spins in the $A$ ($B$) subsystem forming the ``front'' (``back'') of the ring that we denote as $\mathcal{R}$. Whenever we use the notation $\mathcal{R}$, we imagine it as representing a finite periodic array of sites that can be ordered counter-clockwise as $[c]_A,\dots,[d+1]_A,[d]_B,[d-1]_B,\dots,[c]_B,[c-1]_A$. 

The operator $V_R$ is not exactly $Q$ acting on the finite periodic system defined by $\mathcal{R}$, which is depicted in the third expression in Fig.~\ref{fig:vr}. Instead, there are ``defects'' near the boundary of $R$ where the Margolus representation is inverted and has its orientation reversed. However, we  show that $V_R$ is equivalent to $Q$ up to composition with an FDQC. Given any QCA $Q$, we show that its inverse $Q^{-1}$ is related to its orientation-reversed self $\bar{Q}$ by an FDQC. This is intuitively clear for 1D QCA such as the shift QCA: reversing the direction of the shift is the same as inverting it. Generally, $\bar{Q}$ will not equal $Q^{-1}$, but they will differ only by an FDQC in 1D. Indeed, if we let $ind(Q)$ be the rational-valued index of $Q$ as defined in Ref.~\cite{Gross2012}, then it is straightforward to show that $ind(Q^{-1})=ind(Q)^{-1}=ind(\bar{Q})$, which implies that $Q^{-1}$ and $\bar{Q}$ differ by an FDQC in 1D \cite{Gross2012}. 

To explicitly construct the circuit which maps $\bar{Q}$ to $Q^{-1}$, we introduce the unitary $w = \bar{v}u$ where $\bar{v}$ is the spatial reversal (opposite orientation) of $v$ obtained by exchanging the left and right input and output Hilbert spaces. Graphically,
\begin{equation}
    \includegraphics[scale=0.5]{w_gate.png}
\end{equation}
Note that $w$, unlike $u$ and $v$, is a proper unitary gate that maps $\mathbb{C}^d\otimes \mathbb{C}^d$ to itself. Observe that we have $wu^{-1}=\bar{v}$ and $v^{-1}\bar{w}=\bar{u}$ where $\bar{w}$ is again the spatial reversal of $w$. Then we have,
\begin{equation}
   \left( \prod_{i} w_{2i,2i+1} \right) Q^{-1}\left( \prod_{i} \bar{w}_{2i-1,2i} \right)=\bar{Q}.
\end{equation}
Using this, we define the circuits acting on the ``back'' of $\mathcal{R}$,
\begin{align}
\label{eq:W1W2}
    W_1&=\left(w_{[c-1]_A,[c]_B}w_{[d]_B,[d+1]_A}\right) \left(\prod_{i=\frac{c+1}{2}}^{d/2-1} w_{[2i]_B,[2i+1]_B}\right) \nonumber \\
    W_2&=\left(\prod_{i=\frac{c+1}{2}}^{d/2} \bar{w}_{[2i-1]_B,[2i]_B}\right),
\end{align}
such that,
\begin{align}
    W_1V_R W_2  =&\left(\bar{v}_{[c-1]_A,[c]_B}\bar{v}_{[d]_B,[d+1]_A}\right)
    \nonumber \\
    & \left(\prod_{i=\frac{c+1}{2}}^{d/2-1} \bar{v}_{[2i]_B,[2i+1]_B}\right) \left(\prod_{i=\frac{c+1}{2}}^{d/2} v_{[2i-1]_A,[2i]_A}\right)
    \nonumber \\
    &\left(\prod_{i=\frac{c+1}{2}}^{d/2} \bar{u}_{[2i-1]_B,[2i]_B}\right)
    \left(\prod_{i=\frac{c-1}{2}}^{d/2} u_{[2i]_A,[2i+1]_A}\right)
\end{align}
The operator $W_1V_RW_2$ is 
shown in the third expression in
Fig.~\ref{fig:vr}, from which it is clear that $W_1V_RW_2$ is nothing but $Q$ applied to $\mathcal{R}$. According to the 1D topology of $\mathcal{R}$, $V_R$ is not geometrically local since it contains gates coupling qubits on opposite sides of $\mathcal{R}$. However, it is still $k$-local. Therefore, $W_1V_RW_2$ is a $\mathrm{FDQC}_k$\xspace that realizes $Q$ on a finite ring, where $Q$ is an arbitrary 1D QCA. We remark that for certain QCA, the gate $w$ is the identity. This includes the circuit that creates the 1D cluster state and the shift QCA. In these cases, $V_R$ already realizes $Q$ on a ring.


\subsection{Application to compactified higher-dimensional systems}

Having shown that all 1D QCA can be realized as a $\mathrm{FDQC}_k$\xspace, we now move on to higher dimensional QCA acting on $d$-dimensional lattices. For simplicity, we assume we have a simple hypercubic structure although the construction should generalize to any translationally invariant QCA on a lattice with mirror symmetries. We also assume without loss of generality that the QCA has a unit range in all $d$ directions. It is known that a local Margolus form is not possible for two-dimensional QCA and higher \cite{Arrighi2008}. However, we can still obtain the desired results by applying the 1D Margolus representation, which was also used to understand the index theory of higher dimensional QCA \cite{Freedman2020}. To do this, we simply compactify the $d$-dimensional QCA $Q$ along all spatial dimensions except for one to obtain a quasi-1D chain of supersites $i$ each containing a number of sites that is extensive in the $d-1$ compactified dimensions. Since $Q$ has a unit range, it will spread operators contained in supersite $i$ only to supersites $i-1,i,i+1$ such that $Q$ can be viewed as a 1D QCA of unit range acting on the compactified system. Therefore, it may be written in the Maroglus representation of Eq.~\ref{eq:standard_form} where each solid vertical line now represents one supersite.

Applying the construction described above then automatically gives a $\mathrm{FDQC}_k$\xspace on the supersites realizing $Q$. However, we must be careful to confirm that the depth of the $k$-local circuit and the value of $k$ are both independent of system size in the compactified dimensions. This is clearly true of $V_R$, whose definition in Eq.~\ref{eq:vr} is unaffected by the compactification and hence it is still $k$-local and finite-depth. Note that while the definition of $V_R$ depends on which dimensions we choose to compactify, $V_R$ is unaffected by whether we actually compactify those dimensions or not. What remains then is to check that the unitary $w$ used to define $W_1$ and $W_2$ can be realized as an $\mathrm{FDQC}_k$\xspace. In particular, we first show that $W_1$ and $W_2$ are $d$-dimensional circuits that are finite-depth along the non-compactified direction and act as locality-preserving unitaries ($(d-1)$-dimensional QCAs) along the $d-1$ compactified directions; also check Fig.~\ref{fig:vr}. Following that, we use induction to show that $W_1$ and $W_2$ can be realized as an $\mathrm{FDQC}_k$\xspace. 

We now show that $w$ is locality-preserving as well as transitionally invariant in the compactified dimensions, \textit{i.e.} it is a $(d-1)$-dimensional QCA. Let $O$ be a local operator. Recall that $w=\bar{v}u$. Let $uOu^{-1} = \sum_k A^k \otimes B^k$ where $A^k$ and $B^k$ are operators supported only on the $\ell$- and $r$-dimensional Hilbert spaces that come out of $u$, respectively. Using Schmidt decomposition we can always choose $A^k$ ($B^k$) to come from a linearly independent set of operators acting on $\mathbb{C}^\ell$ ($\mathbb{C}^r$). Let $C^k=\bar{v}A^k\bar{v}^{-1}$ and $D^k=\bar{v}B^k\bar{v}^{-1}$. Note that since $v$ is a unitary map and since $A^k$ and $B^k$ were linearly independent, $C^k$ and $D^k$ are linearly independent as well. Then from linearity, we have,
\begin{align}\label{eq:wow}
    wOw^{-1} = \sum_k C^kD^k.
\end{align}
As we show below, the locality-preserving property of the original QCA $Q$ ensures that each $C^k$ and $D^k$ in this sum is localized around $O$ (meaning that they all are contained in a ball of finite radius centered around $O$), and thus $w$ is locality-preserving. 

Consider the action of $Q$ on $O$. In the following calculation, we will be more explicit with site indices; we write $O_{2i,2i+1}$ to represent the two (super)site operators $O$ acting on (super)sites $2i$ and $2i+1$. Then,
\begin{align}
    &QO_{2i,2i+1}Q^{-1} \nonumber \\
    &= \left( \prod_{j} v_{2j-1,2j} \right)\sum_k A^k_{2i}\otimes B_{2i+1}^k \left( \prod_{j} v^{-1}_{2j-1,2j} \right) \nonumber \\
    &= \sum_k \left(v_{2i-1,2i}A^k_{2i}v^{-1}_{2i-1,2i}\right) \otimes \left(v_{2i+1,2i+2}B^k_{2i+1}v^{-1}_{2i+1,2i+2}\right)  \nonumber \\
    &=\sum_k \bar{C}^k_{2i-1,2i} \otimes \bar{D}^k_{2i+1,2i+2}
    \label{eq:nonlocalop}
\end{align}
where the bars appearing on $C^k$ and $D^k$ again indicate spatial reversal since $A^k$ and $B^k$ have been conjugated by $v$ rather than $\bar{v}$. As is shown in Appendix \ref{app:w}, since $Q O_{2i,2i+1} Q^{-1}$ is contained around $O$, linear independence ensures that each $\bar{C}^k$ and $\bar{D}^k$ should be contained around $O$. This in turn shows that $w O w^{-1}$ in Eq.~\ref{eq:wow} is also contained around $O$, and hence $w$ is also locality-preserving in the $d-1$ compactified dimensions. A similar argument shows that $w$ is translationally invariant in the compactified directions if $Q$ is (see Appendix \ref{app:w} for details). In other words, $w$ is a $(d-1)$-dimensional QCA. 

We finish the proof using an inductive argument. We have already explicitly shown how to realize any 1-dimensional QCA as a $\mathrm{FDQC}_k$\xspace. Now suppose we can realize any $d$-dimensional QCA as a $\mathrm{FDQC}_k$\xspace. Then, given a $(d+1)$-dimensional QCA $Q$, we have shown how to prepare it using the $\mathrm{FDQC}_k$\xspace $V_R$ and the unitary $w$. Since $w$ is a $d$-dimensional QCA, we can by assumption realize it, and hence $Q$ itself, as an $\mathrm{FDQC}_k$\xspace. We note that $w$ is not an FDQC in general, so this inductive step is necessary. For example, if we consider the 2D QCA that shifts operators diagonally, then $w$ will be a 1D shift QCA.

We now discuss our result in light of the conjecture stated in Ref.~\cite{Shirley2022} which states that QCA realizing Witt-equivalent topological orders should be related by a finite-depth circuit i.e., according to this conjecture, one would expect the existence of a finite-depth circuit relating $\bar{Q}$ and $Q^{-1}$. A QCA $Q$ is naturally associated with the chiral topological order $\mathcal{M}_Q$ appearing on, say, the top boundary of the 3D Walker-Wang model achieved by truncating the model prepared by QCA $Q$ on a torus. The bottom boundary will support a topological order of the opposite chirality such that the slab as a whole gives a Witt-trivial topological order, \textit{i.e.} one that admits a gapped boundary to vacuum. Then, if we take $\bar{Q}$, which exchanges the top and bottom boundaries relative to $\mathcal{M}_Q$, we have $\mathcal{M}_{\bar{Q}}\sim (\mathcal{M}_Q)^{-1}$ where $\sim$ indicates the equivalence in terms of boundary topological order. Similarly, if we consider $Q^{-1}$, we have $\mathcal{M}_{Q^{-1}}\sim(\mathcal{M}_Q)^{-1}$, which gives $\mathcal{M}_{\bar{Q}}\sim \mathcal{M}_{Q^{-1}}$. Our $k$-local unitary $w$, that relates $\bar{Q}$ and $Q^{-1}$ is a  circuit whose depth is a constant function of the dimension orthogonal to the truncated boundaries of the Walker-Wang model. Since the choice of the truncation direction is arbitrary, this implies we can write down a different choice of $w$ for each direction such that its depth is constant along that direction. This is the only requirement for $\bar{Q}$ and $Q^{-1}$ to lead to Witt-equivalent boundary topological orders at the top and bottom boundaries of the associated slabs respectively.
Hence, this leads to a refinement of the above-mentioned conjecture of Ref.~\cite{Shirley2022} to possibly include shifts along all but one direction in the relation of $\bar{Q}$ and $Q^{-1}$ such that they result in Witt-equivalent boundary topological order after truncation. 


\subsection{Symmetric QCA and SPT phases}

We now turn to the symmetry properties of the $\mathrm{FDQC}_k$\xspace constructed in the previous section. Suppose $Q$ is a symmetric QCA, meaning that it commutes with a global symmetry $U(g) = u(g)^{\otimes N}$ for $g\in G$. Note that here we do not assume that $Q$ is composed of symmetric gates, as we do not even assume that $Q$ is composed of gates in the first place. 
Let $U_{A}(g)$ ($U_{B}(g)$) denote $U(g)$ acting on the $A$ ($B$) subsystem. $U_A(g) U_B(g)$ clearly commutes with the swap operators $S_i$, since it is a tensor product of the same operator $u(g)$ on every site. Given that $Q_A$ is assumed to be symmetric, $V_i=Q_AS_iQ_A^{-1}$ commutes with $U_A(g) U_B(g)$ as well, and thus all gates in the circuit $V_R$ defined in Eq.~\ref{eq:vr} commute with $U_A(g) U_B(g)$ for all $g\in G$.
When we view the sites acted on by $V_R$ as the ring $\mathcal{R}$, $U_A(g) U_B(g)$ is just $U(g)$ acting on all sites in the ring, so it is just the global symmetry of the ring which we denote as $U_\mathcal{R}(g)$. For $c \le i \le d$, $V_i$ and $S_i$ have trivial support outside $\mathcal{R}$, and hence the fact that they commute with $U_A(g)U_B(g)$ readily shows that they also commute with $U_\mathcal{R}(g)$. Next, it follows from the results of \cite{Cirac2017} that $w$ commutes with $U(g)$ for all $g\in G$, see Appendix \ref{app:w} for detail. Therefore, $W_1 V_R W_2$ is a symmetric $\mathrm{FDQC}_k$\xspace whose gates commute with $U_\mathcal{R}(g)$ for all $g\in G$.

This result has implications for SPT phases. Observe that the $\mathrm{FDQC}_k$\xspace{}'s used to disentangle the SPT fixed-point states in Sec.~\ref{sec:spt} generate the same unitary operators as the non-symmetric FDQCs used to define the states in the first place, which we call SPT entanglers. That is, our constructions didn't just trivialize the fixed-point states, they achieved the stronger task of trivializing the SPT entanglers themselves. This perspective allows us to apply our results on representing QCA as symmetric $\mathrm{FDQC}_k$\xspace{}'s to SPT phases. For example, fixed-point states for a large class of bosonic SPT phases (the ``in-cohomology'' phases) with global symmetry are given by the cocycle states defined in Ref.~\cite{Chen2013}. These states are in turn defined by FDQCs which commute with the global symmetry, but they are not symmetric circuits since the individual gates are not symmetric. Now, our construction allows these circuits to be written as $\mathrm{FDQC}_k$\xspace{}'s with symmetric gates. This shows that all in-cohomology SPT phases are trivial in the $k$-local scenario. Our construction can be applied to beyond-cohomology SPT phases as well, although these are less well-understood at the Hamiltonian level. One example of a beyond-cohomology SPT phase in 4D with $\mathbb{Z}_2$ symmetry was given in Ref.~\cite{Fidkowski2020}, which also constructed a $\mathbb{Z}_2$-symmetric SPT entangler. This entangler is a FDQC, so our construction can be applied to get a symmetric $\mathrm{FDQC}_k$\xspace. 

Finally, we note that our approach immediately fails for higher-form symmetries. This is because the gates in $V_R$ commute only with $U_A(g)U_B(g)$ and not $U_{A}(g)$ or $U_{B}(g)$  individually. That is, the only symmetry operators which commute with $V_R$ are those which act in the same way on the front and back half of $\mathcal{R}$. But the full higher-form symmetry group includes operators that act different on the two halves, as discussed in Sec.~\ref{sec:higherformSPT}. So $V_R$ does not commute with the full higher-form symmetry group. 

\section{Instability of SPT states in monitored random circuits}\label{sec:randomcirc}

Recently, there has been a surge of interest in the entanglement dynamics of monitored random quantum circuits (for a review, see \cite{fisheretalreview}). In particular, certain symmetric monitored random circuits have been studied which can sustain SPT states within a certain range of the circuit parameters \cite{LavasanietalSPT, friedmanetaladaptive}.  In this section, we study the implication of our results for the stability of such states and use this to gain intuition on what kinds of $k$-local circuits can and cannot trivialize SPT phases.

Consider arranging $N$ qubits, initialized in $|+\rangle ^ {\otimes N}$ state, on a 1D ring and applying the following quantum process: at each step, with probability $p$ a random two-qubit unitary $U$ is applied to the system or, with probability $1-p$ a qubit $i$ is chosen uniformly at random and $g_i\equiv Z_{i-1}X_iZ_{i+1}$ is measured. The latter tends to drive the state towards the 1D cluster state which satisfies $g_i|\psi_C\rangle=|\psi_C\rangle$. In the following, we consider four different ensembles of two-qubit unitaries: a) all two-qubit geometrically local Clifford unitaries, b) two-qubit geometrically local Clifford unitaries that respect the $\mathbb{Z}_2\times \mathbb{Z}_2$ symmetry $X_{\mathrm{odd}}$ and $X_{\mathrm{even}}$,
c) $2$-local Clifford unitaries that respect the same $\mathbb{Z}_2\times \mathbb{Z}_2$ symmetry and finally, d) $2$-local Clifford unitaries that respect the $\mathbb{Z}_2^{N}$ symmetry generated by $X_i$ for $i=1,\cdots,N$, i.e., are diagonal in the local $X$-basis. In the case of geometrically local unitaries, a site $i$ is chosen  at random, and a two-qubit unitary, chosen randomly from the appropriate ensemble, is applied to qubits $i$ and $i+1$. As for $2$-local unitaries, two different sites $i$ and $j$ are chosen randomly and then a random unitary from the appropriate ensemble is applied to them.   We are interested in the late-time states of this family of random circuits. 

At $p=0$, the circuit consists of only $g_i$ stabilizer measurements. Therefore, the late-time state of any realization of the random circuit would be an SPT state. The SPT nature of this state can be probed by the non-local analog of Edwards–Anderson glass-order parameter\cite{bahri2015localization,sang2021measurement, LavasanietalSPT},
\begin{align}
    s=\frac{2}{N(N-1)}\sum_{i<j}s_{i,j}^2,
\end{align}
with $s_{i,j}$ being the SPT string order parameter,
\begin{align}
    s_{i,j}=\langle \psi | \prod_{k=i}^j g_k |\psi \rangle.
\end{align}
$s$ is equal to $1$ for $|\psi_C\rangle$. In general, SPT states are characterized by $s>0$, while for trivial states or random states, $s=0$ in the thermodynamic limit. We are interested in $\bar s$, which is $s$ averaged over random circuit realizations. We note that $s$ is not an {\it experimentally} accessible quantity, but it is certainly accessible in simulations, which is sufficient for our present purposes. 

\begin{figure}
    \centering
    \subfigure[]{{\label{fig:local_u}\includegraphics[width=0.49\linewidth]{figures/local_u.pdf}}}
    \subfigure[]{{\label{fig:local_sym_u}\includegraphics[width=0.49\linewidth]{figures/local_sym_u.pdf}}}
    \subfigure[]{{\label{fig:2local_sym_u}\includegraphics[width=0.49\linewidth]{figures/2local_sym_u.pdf}}}
    \subfigure[]{{\label{fig:2local_locally_sym_u}\includegraphics[width=0.49\linewidth]{figures/2local_locally_sym_u.pdf}}}
    \caption{Averaged string order parameter $\bar{s}$ versus $p$ for monitored random circuits where the unitary gates are chosen randomly from a) local two-qubit Clifford unitaries, b) local two-qubit $\mathbb{Z}_2 \times \mathbb{Z}_2$ symmetric Clifford unitaries, c) 2-local $\mathbb{Z}_2 \times \mathbb{Z}_2$ symmetric Clifford unitaries, and d) 2-local $\mathbb{Z}^N$ symmetric Clifford unitaries.}
    \label{fig:sbar_plots}
\end{figure}
Fig.~\ref{fig:sbar_plots} shows $\bar{s}$ as a function of $p$ for each of the unitary ensembles described above. Fig.~\ref{fig:local_u} corresponds to the random circuit where the unitary gates are chosen from the ensemble of local two-qubit Clifford gates without imposing any symmetry restriction. As expected, the SPT structure in the late time state vanishes for any $p>0$. And on the other hand, if we restrict the local unitary gates to respect the $\mathbb{Z}_2 \times \mathbb{Z}_2$ symmetry, the SPT structure survives up to finite $p_c>0$, as is shown in Fig.~\ref{fig:local_sym_u}. Interestingly, when the unitary gates are chosen from the set of $2$-local Clifford unitaries that respect the $\mathbb{Z}_2\times \mathbb{Z}_2$ symmetry, the SPT structure vanishes again for any $p>0$, as illustrated in Fig.~\ref{fig:2local_sym_u}. This is consistent with our findings that SPT states can be trivialized by $k$-local symmetric unitary gates. Lastly, Fig.~\ref{fig:2local_locally_sym_u} corresponds to the circuit where the unitary gates are chosen from the highly constrained ensemble of 2-local Clifford unitaries that map $X_i$ to itself for all $i$. This symmetry restriction is reminiscent of the symmetry restriction for higher-form SPTs as discussed in Sec.~\ref{sec:higherformSPT}. While this set includes long-range entangling gates, we see that the SPT structure  survives up to a finite $p>0$, which is consistent with our intuition that $k$-local gates with local symmetry constraints are not much more powerful in terms of disentangling the SPT structure than just local symmetric gates. 


\section{Discussion}
\label{sec:discussion}

We have constructed explicit finite-depth circuits consisting of (symmetric) $k$-local gates to disentangle SPT phases and to realize all QCA. The circuits imply that the classification of SPT phases and the classification of QCA collapse to a single trivial phase in the presence of $k$-local interactions. They also imply that any SPT state and any QCA can be prepared using a finite-depth circuit of $k$-local gates. We note that our arguments only address {\it worst case stability} - whether there exists an FDQC of $k$-local gates that can trivialize a given state. We have {\it not} addressed `typical case stability' i.e., whether we should expect a state to be trivialized by a circuit of {\it randomly} chosen $k$-local gates. Addressing the typical case stability is an interesting and important problem for future work, and the results of Sec.~\ref{sec:randomcirc} give the first step in this direction. Also, a key ingredient in our arguments was to `fold' the system in such a way that it resembled a stack of the system with its inverted self. This naturally assumes some sort of mirror symmetry is present in the lattice. Therefore, it is natural to ask whether our results can be applied to systems on more general lattices and to what extent translational invariance can be relaxed.

We remark that SPT phases can be used as resources for measurement-based quantum computation (see \cite{Wei2018a} for a review). That is, given a ground state in a suitable SPT phase, one can perform measurements on that ground state in order to simulate a quantum computation. While the computational capability of a state as a resource for MBQC is stable to local symmetric perturbations, our results seem to imply that it may be unstable to $k$-local symmetric perturbations in the case of global or subsystem symmetries. Indeed, in Ref.~\cite{Raussendorf2019}, the authors explicitly identified a symmetric $k$-local interaction whose presence would invalidate the strategy that was used to prove MBQC universality. In contrast, fault-tolerant MBQC can be achieved using SPT phases with higher-form symmetries \cite{Raussendorf2006}, which appear to be stable even under symmetric $k$-local interactions.

While we have focused on bosonic systems, we believe that many of our arguments should apply to fermionic systems as well. Indeed, our physical arguments for the triviality of SPT phases based on their boundary physics and invertibility should carry over {\it mutatis mutandis}. Specifically, the free fermion SPT phases (i.e.,topological insulators and superconductors) are characterized by non-trivial boundary states, which are manifestly rendered trivial if one can couple distinct boundaries together via $k$-local interactions. Meanwhile, \cite{WangSenthil} showed that the set of fermionic SPT phases in three dimensions, protected by some combination of antiunitary symmetries and charge conservation, is exhausted by combinations of the free fermion SPTs and bosonic SPTs - and bosonic SPTs we have constructively shown to be trivializable. This suggests that these fermion SPTs should also be trivializable by $k$-local interactions. Similarly, we expect that many, if not all, fermionic QCA should become trivial in the $k$-local setting \cite{Fidkowski2019,Piroli2021a}. However, establishing rigorous results on fermionic SPTs and QCA is left to future work. 

In contrast to SPT states and QCA, intrinsic topological order is known to be stable under finite-depth $k$-local circuits \cite{Aharonov2018}, meaning that a non-trivial topological phase will not become trivial. However, this doesn't mean that the classification of intrinsic topological phases will remain unchanged. Indeed, in the $k$-local scenario, it is possible that the braiding of topological excitations becomes ill-defined, so some topological phases which differ only by braiding statistics may become the same phase. 
Also, in symmetry-enriched topological (SET) phases, the topological order is stable but the nontrivial symmetry fractionalization pattern of the SET may not be stable under $k$-local circuits. For instance, certain symmetry fractionalization patterns can be canceled by stacking with SPT states \cite{Barkeshli2019}. Since we know that SPT states can be prepared with finite-depth $k$-local circuits, such symmetry fractionalization patterns are not stable to finite-depth $k$-local circuits. A thorough investigation of the stability of intrinsic topological order and symmetry fractionalization is left for future work. 

\begin{figure}
    \centering   
    \subfigure[]{{\label{fig:toric_code_stack_ERG}}\includegraphics[width=0.85\linewidth]{figures/toric_code_stack_ERG.pdf}} \\ \vspace{5mm}
    \subfigure[]{{\label{fig:Xcube_ERG}}\includegraphics[width=0.9\linewidth]{figures/Xcube_ERG.pdf}}
    \caption{(a) Action of a $k$-local circuit on a stack of toric codes, in general, leads to a model that is no longer a finite-depth local quantum circuit (FDQC) equivalent to a stack. (b) Top: X-cube model is foliated i.e., there exists a finite-depth local quantum circuit under which an $L\times L\times L$ X-cube model maps to an X-cube model of dimensions $L\times L\times (L-1)$ and a layer of toric code. Bottom: Action of a $k$-local circuit on the X-cube model, in general, leads to a model that is no longer finite-depth local quantum circuit (FDQC) equivalent to a foliated model.}
    \label{fig:stackERG}
\end{figure}

Another class of phases for which the action of $k$-local circuits is interesting are fracton phases (for reviews, see \cite{fractonarcmp, pretkoreview, radzihovskyreview}). The defining property of fracton phases is the restricted mobility of the excitations, which comes about because the non-trivial excitations are not locally creatable, but instead, arise at the `corners' of extended operators. For instance, in the X-cube model \cite{VijayHaahFu} the fractons arise at the corners of membrane operators. Since these excitations cannot be created (or destroyed) by any few-body operator, they cannot be moved by $k$-local perturbations (without creating additional excitations), and thus the restricted mobility survives. Nonetheless, not all properties of fracton phases are unchanged. For instance, the geometric nature of entanglement can be modified under $k$-local gates. To illustrate this,  we specialize to {\it gapped} fracton phases, which are characterized by nonlocal entanglement with geometric rigidity \cite{decipher, maetal, schmitzetal, bernevigentanglement}. We expect that this nonlocal entanglement survives under $k$-local gates, much like the corresponding entanglement structure in phases with intrinsic topological order, but (we will argue) the geometric structure does not survive. For instance, consider a stack of 2D toric codes. Each copy of 2D toric code has a topological order that is stable under $k$-local gates that couple degrees of freedom in that copy alone. However, under a $k$-local circuit that couples different copies of toric codes, the foliation structure of the stack can be lost and no longer recoverable using a geometrically local FDQC; see Fig.~\ref{fig:toric_code_stack_ERG}. This argument extends to foliated fracton codes (see e.g. \cite{shirleyfoliated}). Under a finite-depth geometrically local quantum circuit (FDQC), a stack of two-dimensional topological codes, which is said to form the foliations of the fracton order, can be extracted out. For extracting one layer of a two-dimensional model alone, the `exfoliating' circuit applies local disentangling operations on the boundary of the fracton order. However, a $k$-local circuit can entangle the extracted foliations back into the fracton order in a way that it can no longer be disentanglable via an FDQC. In this sense, the structure of the entanglement has changed i.e., there is no ex-foliation via a geometrically-local FDQC. We illustrate this for the example of the X-cube model in Fig.~\ref{fig:Xcube_ERG}. A detailed exploration of fracton phases under $k$-local circuits is a promising topic for future work. 

Recently, Floquet codes have also been discussed in the literature~\cite{Hastings_2021}. Such codes are defined by a series of instantaneous codes, each of which is an instance of intrinsic topological order. Hence, it is natural to expect that such codes are stable to $k$-local noise. Floquet codes can exhibit nontrivial automorphisms of topological excitations. Such automorphisms are also exhibited in radical Floquet phases \cite{Poetal} defined using the same underlying model as the Floquet code. The radical Floquet phases, though are associated with a bulk unitary that implements a nontrivial shift QCA at the boundary in the form of a fractional chiral edge mode. Despite our results on the QCA having equivalent $k$-local circuit constructions, it is possible that such edge properties of radical Floquet phases may survive $k$-local perturbations because of the possible survival of the bulk automorphism of topological charges, $e$ and $m$, and the bulk-boundary correspondence. We leave this for a future investigation. It could also be interesting to discuss symmetry-enriched Floquet codes, bearing in mind the subtleties associated with defining symmetries for Floquet unitaries \cite{RegnaultFloquet}.

Lastly, it is natural to extend our work by modifying the definition of a locality-preserving unitary. One can weaken the constraint of locality-preserving by allowing exponential tails in the definition of a local operator. We conjecture that there exist $k$-local circuits also for such \textit{approximate locality-preserving unitaries}~\cite{Ranard_2022}, as would be realized by Hamiltonian time evolution. As a concrete application, we expect that invertible chiral states (like integer quantum Hall states) can be trivialized by $k$-local Hamiltonians, using constructions similar to the ones presented in our paper, although since we expect that chiral phases cannot be captured by zero-correlation length models, there may not be a nicely behaved truncation to $k$-local circuits. We can also consider a $k$-locality-preserving unitary ($\mathrm{QCA}_k$) which maps local operators to $k$-local operators acting on at most $k$ qubits. While we have shown that every QCA a $\mathrm{FDQC}_k$\xspace, this may not be true for $\mathrm{QCA}_k$. 


\begin{acknowledgments}
We thank Daniel Bulmash, Tyler Ellison, Mike Hermele, and Dominic Williamson for discussions, and we thank Jeongwan Haah and Drew Potter for feedback on the manuscript. 
Work by RN was supported by the U.S. Department of Energy (DOE), Office of Science, Basic Energy Sciences (BES) under Award \# DE-SC0021346. This work was begun during a visit to the Aspen Center for Physics (DTS, AD, and RN). The Aspen Center for Physics is supported by the National Science Foundation grant PHY-1607611. AD and DTS are supported by the Simons Foundation through the collaboration on Ultra-Quantum Matter (651440, DTS; 651438, AD). AD is supported by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (PHY-1733907). AD, AL, and RN acknowledge the KITP program on Quantum Many-Body Dynamics and Noisy Intermediate-Scale Quantum Systems, where part of the work was completed. The KITP is supported by the National Science Foundation under Grant No. NSF PHY-1748958. The authors acknowledge the University of Maryland supercomputing resources (http://hpcc.umd.edu) made available for conducting the research reported in this paper.

\end{acknowledgments}


