Realizing computationally complex quantum circuits in the presence of noise and imperfections is a challenging task. While fault-tolerant quantum computing provides a route to reducing noise, it requires a large overhead for generic algorithms. Here, we develop and analyze a hardware-efficient, fault-tolerant approach to realizing complex sampling circuits. We co-design the circuits with the appropriate quantum error-correcting codes for efficient implementation in a reconfigurable neutral atom-array architecture, constituting what we call a of the sampling algorithm. Specifically, we consider a family of ⟦ 2 D , D , 2 ⟧ quantum error-detecting codes whose transversal and permutation gate set can realize arbitrary degree- D instantaneous quantum polynomial (IQP) circuits. Using native operations of the code and the atom-array hardware, we compile a fault-tolerant and fast-scrambling family of such IQP circuits in a hypercube geometry, realized recently in the experiments by Bluvstein [Nature 626, 7997 (2024)]. We develop a theory of second-moment properties of degree- D IQP circuits for analyzing hardness and verification of random sampling by mapping to a statistical mechanics model. We provide strong evidence that sampling from these hypercube IQP circuits is classically hard to simulate even at relatively low depths. We analyze the linear cross-entropy benchmark (XEB) in comparison to the average fidelity and, depending on the local noise rate, find two different asymptotic regimes. To realize a fully scalable approach, we first show that Bell sampling from degree-4 IQP circuits is classically intractable and can be efficiently validated. We further devise new families of ⟦ O ( d D ) , D , d ⟧ color codes of increasing distance d , permitting exponential error suppression for transversal IQP sampling. Our results highlight fault-tolerant compiling as a powerful tool in co-designing algorithms with specific error-correcting codes and realistic hardware.
Realizing computationally complex quantum circuits in the presence of noise and imperfections is a challenging task. While fault-tolerant quantum computing provides a route to reducing noise, it requires a large overhead for generic algorithms. Here, we develop and analyze a hardware-efficient, fault-tolerant approach to realizing complex sampling circuits. We co-design the circuits with the appropriate quantum error-correcting codes for efficient implementation in a reconfigurable neutral atom-array architecture, constituting what we call a of the sampling algorithm. Specifically, we consider a family of ⟦ 2 D , D , 2 ⟧ quantum error-detecting codes whose transversal and permutation gate set can realize arbitrary degree- D instantaneous quantum polynomial (IQP) circuits. Using native operations of the code and the atom-array hardware, we compile a fault-tolerant and fast-scrambling family of such IQP circuits in a hypercube geometry, realized recently in the experiments by Bluvstein [Nature 626, 7997 (2024)]. We develop a theory of second-moment properties of degree- D IQP circuits for analyzing hardness and verification of random sampling by mapping to a statistical mechanics model. We provide strong evidence that sampling from these hypercube IQP circuits is classically hard to simulate even at relatively low depths. We analyze the linear cross-entropy benchmark (XEB) in comparison to the average fidelity and, depending on the local noise rate, find two different asymptotic regimes. To realize a fully scalable approach, we first show that Bell sampling from degree-4 IQP circuits is classically intractable and can be efficiently validated. We further devise new families of ⟦ O ( d D ) , D , d ⟧ color codes of increasing distance d , permitting exponential error suppression for transversal IQP sampling. Our results highlight fault-tolerant compiling as a powerful tool in co-designing algorithms with specific error-correcting codes and realistic hardware.
Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.
Between NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation, we propose a scheme to achieve a provable superpolynomial quantum advantage (under some widely accepted complexity conjectures) that is robust to noise with minimal error correction requirements. We choose a class of sampling problems with commuting gates known as sparse IQP (Instantaneous Quantum Polynomial-time) circuits and we ensure its fault-tolerant implementation by introducing the tetrahelix code. This new code is obtained by merging several tetrahedral codes (3D color codes) and has the following properties: each sparse IQP gate admits a transversal implementation, and the depth of the logical circuit can be traded for its width. Combining those, we obtain a depth-1 implementation of any sparse IQP circuit up to the preparation of encoded states. This comes at the cost of a space overhead which is only polylogarithmic in the width of the original circuit. We furthermore show that the state preparation can also be performed in constant depth with a single step of feed-forward from classical computation. Our construction thus exhibits a robust superpolynomial quantum advantage for a sampling problem implemented on a constant depth circuit with a single round of measurement and feed-forward.
Quantum error correction (QEC) [1,2] is essential for the realization of large-scale quantum computers [3,4]. However, due to the complexity of operating on the encoded ‘logical’ qubits [5,6], understanding the physical principles for building fault-tolerant quantum devices and combining them into efficient architectures is an outstanding scientific challenge. Here we utilize reconfigurable arrays of up to 448 neutral atoms to implement the key elements of a universal, fault-tolerant quantum processing architecture and experimentally explore their underlying working mechanisms. We first employ surface codes to study how repeated QEC suppresses errors [6,7], demonstrating 2.14(13)x below-threshold performance in a four-round characterization circuit by leveraging atom loss detection and machine learning decoding [8,9]. We then investigate logical entanglement using transversal gates and lattice surgery [10–12], and extend it to universal logic through transversal teleportation with 3D [[15,1,3]] codes [13,14], enabling arbitrary-angle synthesis with polylogarithmic overhead [5,15]. Finally, we develop mid-circuit qubit re-use [16], increasing experimental cycle rates by two orders of magnitude and enabling deep-circuit protocols with dozens of logical qubits and hundreds of logical teleportations [17–20] with [[7,1,3]] and high-rate [[16,6,4]] codes while maintaining constant internal entropy. Our experiments reveal key principles for efficient architecture design, involving the interplay between quantum logic & entropy removal, judiciously using physical entanglement in logic gates & magic state generation, and leveraging teleportations for universality & physical qubit reset. These results establish foundations for scalable, universal error-corrected processing and its practical implementation with neutral atom systems.
Abstract Suppressing errors is the central challenge for useful quantum computing 1 , requiring quantum error correction (QEC) 2–6 for large-scale processing. However, the overhead in the realization of error-corrected ‘logical’ qubits, in which information is encoded across many physical qubits for redundancy 2–4 , poses substantial challenges to large-scale logical quantum computing. Here we report the realization of a programmable quantum processor based on encoded logical qubits operating with up to 280 physical qubits. Using logical-level control and a zoned architecture in reconfigurable neutral-atom arrays 7 , our system combines high two-qubit gate fidelities 8 , arbitrary connectivity 7,9 , as well as fully programmable single-qubit rotations and mid-circuit readout 10–15 . Operating this logical processor with various types of encoding, we demonstrate improvement of a two-qubit logic gate by scaling surface-code 6 distance from d = 3 to d = 7, preparation of colour-code qubits with break-even fidelities 5 , fault-tolerant creation of logical Greenberger–Horne–Zeilinger (GHZ) states and feedforward entanglement teleportation, as well as operation of 40 colour-code qubits. Finally, using 3D [[8,3,2]] code blocks 16,17 , we realize computationally complex sampling circuits 18 with up to 48 logical qubits entangled with hypercube connectivity 19 with 228 logical two-qubit gates and 48 logical CCZ gates 20 . We find that this logical encoding substantially improves algorithmic performance with error detection, outperforming physical-qubit fidelities at both cross-entropy benchmarking and quantum simulations of fast scrambling 21,22 . These results herald the advent of early error-corrected quantum computation and chart a path towards large-scale logical processors.
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.
Quantum computers have the potential to solve certain problems exponentially faster than classical computers. However, realizing this potential in practice is a major challenge, as it requires precise control over large-scale quantum systems operating at extremely low error rates. Quantum error correction (QEC) provides a path to achieving such error rates, but its substantial resource overhead poses a significant practical barrier. In addition, identifying which computational problems offer a provable quantum advantage—and which remain fundamentally intractable—remains an open question. This thesis presents progress towards addressing both of these challenges. The first part of this thesis describes advances that substantially reduce the resource overhead of QEC. We begin by presenting realizations of logical circuits in dynamically reconfigurable arrays of neutral atoms. By jointly decoding the logical qubits, we reduce the cost of implementing such transversal Clifford circuits by a factor proportional to the code distance. We then develop new theories of fault tolerance to extend these savings to universal quantum computation with magic state inputs. Finally, we introduce techniques for fast correlated decoding, enabling practical implementations of these improvements in experimental hardware. Collectively, these advances accelerate progress toward large-scale computation and reduce the cost of QEC by over an order of magnitude. The second part of the thesis explores the relative power of quantum and classical computation in combinatorial optimization, a class of problems that is ubiquitous in science and engineering and foundational to the theory of computational complexity. We experimentally implement the optimized quantum adiabatic algorithm (QAA) in neutral atom arrays and observe evidence of a superlinear speedup over classical simulated annealing on certain hard problem instances. To interpret these results, we develop a theoretical framework to compare the performance of QAA with a broad class of classical Markov chain Monte Carlo algorithms. We identify conditions under which a quantum quadratic speedup is achievable and propose modifications to the QAA to reliably realize this advantage. Together, these contributions advance both the practical implementation and theoretical understanding of quantum algorithms.