A defining feature in the field of quantum computing is the potential of a quantum device to outperform its classical counterpart for a specific computational task.By now, several proposals exist showing that certain sampling problems can be done efficiently quantumly, but are not possible efficiently classically, assuming strongly held conjectures in complexity theory, a feature dubbed quantum speedup.However, the effect of noise on these proposals is not well understood in general, and in certain cases it is known that simple noise can destroy the quantum speedup.Here we develop a fault-tolerant version of one family of these sampling problems, based on nonadaptive measurements on regular graph states composed of m qubits.We show that these sampling problems can be implemented fault tolerantly using quantum circuits of constant depth.We present two constructions, each taking poly(m) physical qubits, some of which are prepared in noisy magic states.The first of our constructions is a constant depth quantum circuit composed of single-and two-qubit nearest-neighbor Clifford gates in four dimensions.This circuit has one layer of interaction with a classical computer before final measurements.Our second construction is a constant depth quantum circuit with single-and two-qubit nearest-neighbor Clifford gates in three dimensions, but with two layers of interaction with a classical computer before the final measurements.For each of these constructions, we show that there is no classical algorithm which can sample according to its output distribution in poly(m) time, assuming two standard complexity theoretic conjectures hold.The noise model we assume is the so-called local stochastic quantum noise.Along the way, we introduce various concepts such as constant depth magic state distillation and constant depth output routing, which arise naturally in measurement based quantum computation, but have no constant-depth analog in the circuit model.
A defining feature in the field of quantum computing is the potential of a quantum device to outperform its classical counterpart for a specific computational task.By now, several proposals exist showing that certain sampling problems can be done efficiently quantumly, but are not possible efficiently classically, assuming strongly held conjectures in complexity theory, a feature dubbed quantum speedup.However, the effect of noise on these proposals is not well understood in general, and in certain cases it is known that simple noise can destroy the quantum speedup.Here we develop a fault-tolerant version of one family of these sampling problems, based on nonadaptive measurements on regular graph states composed of m qubits.We show that these sampling problems can be implemented fault tolerantly using quantum circuits of constant depth.We present two constructions, each taking poly(m) physical qubits, some of which are prepared in noisy magic states.The first of our constructions is a constant depth quantum circuit composed of single-and two-qubit nearest-neighbor Clifford gates in four dimensions.This circuit has one layer of interaction with a classical computer before final measurements.Our second construction is a constant depth quantum circuit with single-and two-qubit nearest-neighbor Clifford gates in three dimensions, but with two layers of interaction with a classical computer before the final measurements.For each of these constructions, we show that there is no classical algorithm which can sample according to its output distribution in poly(m) time, assuming two standard complexity theoretic conjectures hold.The noise model we assume is the so-called local stochastic quantum noise.Along the way, we introduce various concepts such as constant depth magic state distillation and constant depth output routing, which arise naturally in measurement based quantum computation, but have no constant-depth analog in the circuit model.
We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on Nˉ logical qudits of depth Tˉ, we construct a fault-tolerant circuit on N=poly(Nˉ) physical qudits of depth Tˉ⋅Nˉo(1), which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number N1−o(1) of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits.
Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance.
Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.
We construct a polynomial-time classical algorithm that samples from the output distribution of noisy geometrically local Clifford circuits with any product-state input and single-qubit measurements in any basis. Our results apply to circuits with nearest-neighbor gates on an O(1)-D architecture with depolarizing noise after each gate. Importantly, we assume that the circuit does not contain qubit resets or mid-circuit measurements. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are important candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results can be extended to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant to current experiments. Importantly, these results do not require randomness assumptions over the circuit families considered (such as anticoncentration properties) and instead hold for every circuit in each class as long as the depth is above a constant threshold. This allows us to rule out the possibility of fault-tolerance in these circuit models. As a key technical step, we prove that interspersed noise causes a decay of long-range entanglement at depths beyond a critical threshold. To prove our results, we merge techniques from percolation theory and Pauli path analysis.
We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δ, with parallel runtime 2O(d)loglog(n/δ) and n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(logn). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(logn/loglogn). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
Fault tolerant quantum computers repetitively apply a four-step procedure: First, perform a few one and two-qubit quantum gates. Second, perform a syndrome measurement on a subset of the qubits. Third, perform fast classical computations to establish if and where errors occurred. And, fourth, correct the errors with a correction step. The next iteration applies the same procedure with new one and two-qubit gates. Even though current error-rates prohibit this procedure to work and fault tolerant quantum computing remains a distant goal, the same procedure can already prove useful today. In this work we make use of this four-step scheme not to carry out fault-tolerant computations, but to enhance short, constant -depth, quantum circuits that perform 1 qubit gates and nearest−neighbor 2 qubit gates.We introduce a new computational model called Local Alternating Quantum Classical Computations (LAQCC) . In this model, qubits are placed in a grid and they can only interact with their direct neighbors; the quantum circuits are of constant depth with intermediate measurements; a classical controller can perform log-depth computations on these intermediate measurement outcomes and control future quantum operations based on the outcome. This model fits naturally between quantum algorithms in the NISQ era and full-fledged fault-tolerant quantum computation. We first prove that any Clifford circuit has an equivalent LAQCC circuit, and that any LAQCC circuit can be simulated by a QNC1 circuit. Next, we conjecture the non-simulatability of LAQCC by showing that LAQCC contains the class of Instantaneous Quantum Polynomial-time circuits. We also show that any LAQCC circuit with polynomial-sized quantum circuits and unbounded classical computations is contained in the class of quantum circuits equipped with post-selection gates with respect to the task of state preparation. We continue by presenting LAQCC implementations of different subroutines, including OR-gates, quantum Fourier transforms and Threshold gates. These subroutines prove vital in constructing three state preparation routines in the main part of this work. Preparing a uniform superposition uses constant-depth arithmetic gates, combined with an exact Grover implementation by Long. For the W -state, we employ a compress-uncompress method to switch between a binary and one-hot encoding. This method extends to the more generalized Dicke-states, the superposition of n -bit strings of Hamming weight k , for k=O(n) , but fails for higher k due to the birthday paradox. We extend this protocol to a protocol that prepares many-body scar states, highly excited states with low entanglement and longer coherence times than states with the same energy density. We present a circuit for preparing Dicke-states for larger k requiring log-depth circuits that maps between the factoradic number system and the combinatorial number system.
A quantum computation can be described by the evolution of a collection of quantum bits, or qubits, according to the laws of quantum mechanics, from an initial state encoding the input of a problem, to its solution represented by the final state. A machine capable of performing this task, a quantum computer, must be robust against errors caused by the inherent imperfections in the fabrication and control of such complex systems. This thesis examines the theory of fault‑tolerant quantum computation, tailored to the physical constraints of today’s leading platforms, most notably superconducting circuits and neutral‑atom arrays.A fault-tolerant quantum computation requires to correct errors in real time, at the cost of a dedicated architectural layer whose integration may introduce additional noise. A possible simplification uses a quantum memory model where information is encoded in a pair of configurations of a multi-qubit system, stabilized by the uniform application of a simple local rule fitting within the theory of cellular automata. We propose a short-term solution, the shearing-rule which protects a one-dimensional repetition code against errors with good performance but lacks a threshold. This shortcoming is addressed by adding small local classical memories, used to define the signal-rules decoders, where error correction relies on exchanging binary signals. Combined with biased-noise qubits, such as cat qubits, these local decoders define a fully local one-dimensional quantum memory.The final part of the manuscript addresses the advantage of quantum machines over their classical counterparts. We emphasize that any such demonstration must account for the presence of noise to be meaningful — for example, while exact sampling from the output distribution of circuits drawn from certain families is believed to be hard for classical computers, the task may become tractable if one allows for an approximate solution that reflects the presence of noise. In this context, we propose a constant-depth quantum circuit that solves a sampling problem in a fault-tolerant manner. Because our approach is particularly well-suited to the atom rearrangement capabilities of neutral-atom array platforms, we hope it will contribute to a future experimental demonstration of a fault-tolerant quantum advantage.
We construct the first known fault-tolerant scheme for injecting states into quantum error-correcting codes with constant space and time overhead. That is, we construct a family of constant-rate quantum error-correcting codes for which a set of bare physical qubits can be injected, i.e. fault-tolerantly encoded, into a code block. Similarly, a code state can be ejected, i.e. fault-tolerantly decoded, back into bare physical qubits. We show that these injection and ejection procedures succeed under circuit-level locally stochastic noise, while incurring just a small constant probability of corrupting each qubit, which is unavoidable for bare physical qubits. We also show how to perform fault-tolerant error correction and code-state preparation under locally stochastic noise. All of our gadgets can be implemented with constant quantum circuit depth (i.e. are single-shot), and with a number of physical qubits growing linearly with the number of logical qubits, assuming the ability to run polynomial-sized noiseless classical circuits on the side.
We construct our quantum codes by taking a high-dimensional hypergraph product of classical LDPC codes, which in turn are a simplified version of Spielman's linear-time encodable codes (STOC'95). As our resulting product codes are only resilient to physical errors occurring with non-uniform probabilities across qubits, we then show how to concatenate with inner codes of various sizes to obtain fault-tolerance against uniform noise.