How to Fault-Tolerantly Realize Any Quantum Circuit with Local Operations

We show how to realize a general quantum circuit involving gates between arbitrary pairs of qubits by means of geometrically local quantum operations and efficient classical computation. We prove that circuit-level local stochastic noise modeling an imperfect implementation of our derived schemes is equivalent to local stochastic noise in the original circuit. Our constructions incur a constant-factor increase in the quantum circuit depth and a polynomial overhead in the number of qubits. To execute an arbitrary quantum circuit on <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><a:mi>n</a:mi></a:math> qubits, we give a three-dimensional quantum fault-tolerance architecture involving <d:math xmlns:d="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><d:mi>O</d:mi><d:mo stretchy="false">(</d:mo><d:msup><d:mi>n</d:mi><d:mrow><d:mn>3</d:mn><d:mo>/</d:mo><d:mn>2</d:mn></d:mrow></d:msup><d:msup><d:mi>log</d:mi><d:mn>3</d:mn></d:msup><d:mo></d:mo><d:mi>n</d:mi><d:mo stretchy="false">)</d:mo></d:math> qubits and a quasi-two-dimensional architecture using <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><i:mi>O</i:mi><i:mo stretchy="false">(</i:mo><i:msup><i:mi>n</i:mi><i:mn>2</i:mn></i:msup><i:msup><i:mi>log</i:mi><i:mn>3</i:mn></i:msup><i:mo></i:mo><i:mi>n</i:mi><i:mo stretchy="false">)</i:mo></i:math> qubits. Applied to recent fault-tolerance constructions, this gives a fault-tolerance-threshold theorem for universal quantum computations with local operations, a polynomial qubit overhead, and a quasipolylogarithmic depth overhead. More generally, our transformation dispenses with the need for considering the locality of operations when designing schemes for fault-tolerant quantum information processing.