Complexity Phase Transitions Generated by Entanglement

Entanglement is one of the physical properties of quantum systems responsible for the computational hardness of simulating quantum systems. But while the runtime of specific algorithms, notably tensor network algorithms, explicitly depends on the amount of entanglement in the system, it is unknown whether this connection runs deeper and entanglement can also cause inherent, algorithm-independent complexity. In this Letter, we quantitatively connect the entanglement present in certain quantum systems to the computational complexity of simulating those systems. Moreover, we completely characterize the entanglement and complexity as a function of a system parameter. Specifically, we consider the task of simulating single-qubit measurements of $k$-regular graph states on $n$ qubits. We show that, as the regularity parameter is increased from 1 to $n-1$, there is a sharp transition from an easy regime with low entanglement to a hard regime with high entanglement at $k=3$, and a transition back to easy and low entanglement at $k=n-3$. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.

Figure 1

(a) The family of quantum states we consider are graph states on a $k$-regular graph $G$ on $n$ qubits with arbitrary single qubit rotations $U_1,U_2,\dots ,U_n$. The measurements are done in the standard basis. (b) Phase transitions of the entanglement (as measured by entanglement width) and computational complexity—whether classical simulation is easy or hard—as a function of the regularity parameter $k$. For both the entanglement width and the computational complexity, we take the worst case over all $k$-regular graphs $G$ as well as $U_1,U_2,\dots ,U_n$.

Figure 2

(a) A grid graph with closed boundary conditions is a torus, which is a 4–regular graph. This is a resource state for MBQC: “cutting open” the torus along the pink lines gives back a grid graph. (b) Two tori connected together to construct a 5–regular graph. The pink vertices are ones we delete to recover a grid graph, which proves that this is a valid resource state for MBQC.

Figure 3

To perform local complementation $LC(G,a)$ of a graph $G$ with respect to vertex $a$ (pink), we take the complement of the subgraph comprising the neighbors of the pink vertex (green).

Figure 4

A visual proof that the complement of a grid graph is a resource state for MBQC. (a) A $3\times 3$ grid graph $G$. Consider (b) $\overline{G}$—the complement of $G$. (c) Apply a local complementation to vertex $a$. (d) Delete vertices $b$ and $c$. (e) Delete some of the gray vertices to finally reach a $2\times 2$ grid graph.