Latent Computational Complexity of Symmetry-Protected Topological Order with Fractional Symmetry

An emerging insight is that ground states of symmetry-protected topological orders (SPTOs) possess latent computational complexity in terms of their many-body entanglement. By introducing a fractional symmetry of SPTO, which requires the invariance under 3-colorable symmetries of a lattice, we prove that every renormalization fixed-point state of 2D $({\mathbb{Z}}_2{)}^m$ SPTO with fractional symmetry can be utilized for universal quantum computation using only Pauli measurements, as long as it belongs to a nontrivial 2D SPTO phase. Our infinite family of fixed-point states may serve as a base model to demonstrate the idea of a “quantum computational phase” of matter, whose states share universal computational complexity ubiquitously.

Figure 1

The 1D cluster state $|{\psi }_{1C}⟩$ (a), and 2D Union Jack state $|{\psi }_{\mathrm{UJ}}⟩$ (b), canonical examples of the entangled many-body states we investigate. (a) The 1D cluster state is formed from qubit $|+⟩$ states [with $|+⟩≔(1/\sqrt{2})(|0⟩+|1⟩)$] on a 1D spin chain, which are entangled with nearest-neighbor $CZ$ gates acting as $CZ|\alpha ,\beta ⟩=(-1{)}^{\alpha ·\beta }|\alpha ,\beta ⟩$. (b) The Union Jack state is obtained from $|+⟩$ states on a 2D Union Jack lattice, which are entangling with nearest-neighbor triple $CCZ$ gates acting as $CCZ|\alpha ,\beta ,\gamma ⟩=(-1{)}^{\alpha ·\beta ·\gamma }|\alpha ,\beta ,\gamma ⟩$. Both $|{\psi }_{1C}⟩$ and $|{\psi }_{\mathrm{UJ}}⟩$ possess distinctive “fractional symmetries”, leaving them invariant under $X$ applied to all qubits on sites of a single color ($A$, $B$, or $C$). Replacing the ($d-1$)-controlled $Z$ gates by unitaries $U({\omega }_d)$ parametrized by $d$-cocycles of a group $G$, we obtain the cocycle states of Ref. [23]. Cocycle states with fractional symmetry can be graphically represented by expanding every vertex into a collection of virtual qubits, and expanding every entangling gate into a product of $CZ$’s or $CCZ$’s (see Fig. 2).

Figure 2

(a) Fixing a $G=({\mathbb{Z}}_2{)}^m$ generating set at sites $A$ and $B$ lets us represent the entangling gates $U({\tau }_2)$ forming our $\frac{1}{2}$-symmetric 2-cocycle state using an $m\times m$ binary component matrix, ${\widehat{\tau }}_2$. Nonzero entries of ${\widehat{\tau }}_2$ give $CZ$ gates between adjacent virtual qubits. Color-dependent changes of generating set (corresponding to color-dependent changes of basis on the single-spin Hilbert spaces) enact Gaussian elimination, reducing ${\widehat{\tau }}_2$ to a diagonal normal form in which our state is simply $r=\mathrm{rank}({\widehat{\tau }}_2)$ disjoint 1D cluster states. Here, $m=3$ and $r=2$. (b) In 2D, we again use color-dependent changes of generating set to simplify our state, but now represent 3-body entangling gates $U({\tau }_3)$ as 3-index binary component tensors, ${\widehat{\tau }}_3$ (not shown). Nonzero entries of ${\widehat{\tau }}_3$ give $CCZ$ gates between triples of virtual qubits. Our normal form reduces this state to $r$ disjoint irreducible 3-cocycle states, where again $m=3$ and $r=2$. (c) Representatives of the ${\zeta }_3(2)=4$ irreducible 3-cocycle states that exist in $G=({\mathbb{Z}}_2{)}^2$. Theorem 1 proves that any $1/3$-symmetric 3-cocycle state with $G=({\mathbb{Z}}_2{)}^m$ is either trivial, isomorphic to one of these states (up to permutation of lattice colors), or isomorphic to two disjoint copies of the Union Jack state (the only irreducible state in ${\mathbb{Z}}_2$). An exhaustive numerical search shows that of the $2^{m^3}=2^{27}$ possible $1/3$-symmetric cocycle states in $G=({\mathbb{Z}}_2{)}^3$, there exist only ${\zeta }_3(3)=50$ distinct irreducible states up to local changes of basis. However, a precise classification of irreducible cocycle states is unnecessary for our purposes, since every irreducible state is a Pauli universal resource state (Corollary 1).