Fault-Tolerant Quantum Computation with Long-Range Correlated Noise

We prove a new version of the quantum accuracy threshold theorem that applies to non-Markovian noise with algebraically decaying spatial correlations. We consider noise in a quantum computer arising from a perturbation that acts collectively on pairs of qubits and on the environment, and we show that an arbitrarily long quantum computation can be executed with high reliability in $D$ spatial dimensions, if the perturbation is sufficiently weak and decays with the distance $r$ between the qubits faster than $1/r^D$.