Robert König

To quantify the accuracy of logical gates in approximate quantum error correction, we introduce the {\em composable logical gate error}. This quantity accounts for both deviation from the target gate and leakage out of the code space. It is subadditive under gate composition, enabling simple circuit analysis, and can be bounded using matrix elements of physical unitaries between (approximate) logical basis states. As a case study, we study the composable logical gate error of linear optics implementations of Paulis and Cliffords in approximate Gottesman-Kitaev-Preskill (GKP) codes. We find that the logical gate error for implementations of Pauli gates depends linearly on the squeezing parameter. This means that their accuracy increases monotonically with the amount of squeezing. In contrast, implementations of some Clifford gates retain a constant logical gate error even in the limit of infinite squeezing. This highlights that results derived for ideal GKP codes do not always translate to physically realistic approximate codes. We propose a way of sidestepping this no-go result in hybrid qubit-oscillator systems with Gaussian, multi-qubit, and qubit-controlled Gaussian unitaries. We propose implementations of logical gates using two oscillators and three qubits, whose logical gate error is bounded by a linear function of the squeezing parameter and scales polynomially with the number of encoded qubits.

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 n qubits, we give a 3D quantum fault-tolerance architecture involving O(n^3/2 log^3 n) qubits, and a quasi-2D architecture using O(n^2 log^3 n) 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 quasi-polylogarithmic 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.

We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or without locality constraints. We overcome these limitations, proposing a quantum advantage demonstration amenable to experimental realizations. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.