  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 work, 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.
