Aleksander Kubica

We present a protocol for fault-tolerantly implementing the logical quantum random access memory (QRAM) operation, given access to a specialized, noisy QRAM device. For coherently accessing classical memories of size 2^n, our protocol consumes only poly(n) fault-tolerant quantum resources (logical gates, logical qubits, quantum error correction cycles, etc.), avoiding the need to perform active error correction on all Ω(2^n) components of the QRAM device. This is the first rigorous conceptual demonstration that a specialized, noisy QRAM device could be useful for implementing a fault-tolerant quantum algorithm. In fact, the fidelity of the device can be as low as 1/poly(n). The protocol queries the noisy QRAM device poly(n) times to prepare a sequence of n-qubit QRAM resource states, which are moved to a general-purpose poly(n)-size processor to be encoded into a QEC code, distilled, and fault-tolerantly teleported into the computation. To aid this protocol, we develop a new gate-efficient streaming version of quantum purity amplification that matches the optimal sample complexity in a wide range of parameters and is therefore of independent interest. The exponential reduction in fault-tolerant quantum resources comes at the expense of an exponential quantity of purely classical complexity---each of the n iterations of the protocol requires adaptively updating the 2^n-size classical dataset and providing the noisy QRAM device with access to the updated dataset at the next iteration. We show that this classical operation can be parallelized to poly(n) classical circuit depth, but only in a model where classical sparse matrix-vector multiplication for 2^n-dimensional vectors can be as well. While our protocol demonstrates that QRAM is more compatible with fault-tolerant quantum computation than previously thought, the need for significant classical computational complexity exposes potentially fundamental limitations to realizing a truly poly(n)-cost fault-tolerant QRAM.

We investigate layer codes, a family of three-dimensional stabilizer codes that can achieve optimal scaling of code parameters and a polynomial energy barrier, as candidates for self-correcting quantum memories. First, we introduce two decoding algorithms for layer codes with provable guarantees for local stochastic and adversarial noise, respectively. We then prove that layer codes are partially self-correcting quantum memories. With memory times scaling exponentially in the linear size of the system, layer codes outperform the previously demonstrated subexponential scaling of the welded solid code. Notably, we argue that partial self-correction without the requirement of efficient decoding is more common than expected, as it arises from a diverging energy barrier. This draws a sharp distinction between partially self-correcting systems, and partially self-correcting memories. Another novel aspect of our work is an analysis of layer codes constructed from random Calderbank–Shor–Steane codes. We show that these random layer codes have optimal scaling (up to logarithmic corrections) of code parameters and a polynomial energy barrier. Finally, we present numerical studies of their memory times and report behavior consistent with partial self-correction.

We present a low-overhead architecture that supports the layout and resource estimation of large-scale fault-tolerant quantum algorithms. Utilizing recent advances in fault tolerance with transversal gate operations, this architecture achieves a run time speed-up on the order of the code distance d, which we find directly translates to run time improvements of large-scale quantum algorithms. Our architecture consists of functional building blocks of key algorithmic subroutines, including magic state factories, quantum arithmetic units, and quantum look-up tables. These building blocks are implemented using efficient transversal operations, and we design space-time-efficient versions of them that minimize interaction distance, thereby reducing atom move times and minimizing the volume for correlated decoding. We further propose models to estimate their logical error performance. We perform resource estimation for a large-scale implementation of Shor's factoring algorithm, one of the prototypical benchmarks for large-scale quantum algorithms, on dynamically reconfigurable neutral atom arrays, finding that 2048-bit RSA factoring can be executed with 19 million qubits in 5.6 days, for 1 ms QEC cycle times. This represents close to 50x speed-up of the run-time compared to existing estimates with similar assumptions, with no increase in space footprint, achieving a genuine reduction of the space-time volume required for error-corrected quantum computation, and bringing the runtime of large-scale algorithms on emerging platforms into a practical regime.

Quantum Tanner codes constitute a family of quantum low-density parity-check (LDPC) codes with good parameters, i.e., constant encoding rate and relative distance. In this article, we prove that quantum Tanner codes also facilitate single-shot quantum error correction (QEC) of adversarial noise, where one measurement round (consisting of constant-weight parity checks) suffices to perform reliable QEC even in the presence of measurement errors. We establish this result for both the sequential and parallel decoding algorithms introduced by Leverrier and Zemor. Furthermore, we show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round. Combined with good code parameters, the resulting constant-time overhead of QEC and robustness to (possibly time-correlated) adversarial noise make quantum Tanner codes alluring from the perspective of quantum fault-tolerant protocols.

We address a question of leveraging the noise bias to simplify quantum error correction (QEC) protocols and improve their performance. We focus on the previously unexplored bias between the amplitude damping and dephasing errors that is fundamental to many quantum technologies. We propose a simple scheme to convert amplitude damping errors into erasure errors. Despite its simplicity, our scheme significantly improves the performance of QEC protocols and can be extended to handle leakage errors. Importantly, we provide two concrete realizations with superconducting circuits, analyzing their performance both from the analytical and numerical perspective. Our results provide a breakthrough shift in the current architecture paradigm. Namely, they suggest that engineering efforts should focus on improving the dephasing and the quality of quantum coherent control, as they effectively limit the performance of fault-tolerant protocols.

Abstract We present a simple proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code (QECC) with its ability to achieve a universal set of transversal logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols to characterize the QECC performance measured in terms of the worst-case entanglement fidelity. The theorem is applicable to a large class of decoherence models, including erasure and depolarizing noise. Our approach is unorthodox, as instead of following the established path of utilizing QECCs to mitigate noise in quantum metrological protocols, we apply methods of quantum metrology to explore the limitations of QECCs.

Abstract Estimating the reducing overhead of existing fault tolerance schemes is a crucial step toward realizing scalable quantum computers. Many of the most promising schemes are based upon two-dimensional (2D) topological codes such as the surface and color codes. In these schemes, universal computation is typically achieved using readily implementable Clifford operations along with a less convenient and more costly implementation of the $T$ gate. In our work, we compare the cost of fault-tolerantly implementing the $T$-gate in 2D color codes using two leading approaches: state distillation and code switching to a 3D color code. We report that state distillation is more resource-efficient than code switching, in terms of both qubit overhead and space-time overhead. In particular, we find a $T$ gate threshold via code switching of $0.07(1)\%$ under circuit noise, almost an order of magnitude below that for distillation with 2D color codes. To arrive at this result, we provide and implement a simplified end-to-end recipe for code switching, detailing each step and providing important optimization considerations. We not only find numerical overhead estimates of this code switching protocol, but also lower bound various conceivable improvements. We also optimize the 2D color code for circuit noise yielding it's largest threshold to date $0.37(1)\%$, and adapt and optimize the restriction decoder and find a threshold of $0.80(5)\%$ for the 3D color code with perfect measurements under $Z$ noise. We foresee that this analysis will influence the choice of which FT schemes and which salable hardware designs should be pursued in future.

Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead. Recent advances have shown that by jointly decoding logical qubits in algorithms composed of transversal gates, the number of syndrome extraction rounds can be reduced by a factor of the code distance d, at the cost of increased classical decoding complexity. Here, we reformulate the problem of decoding transversal circuits by directly decoding relevant logical operator products as they propagate through the circuit. This procedure transforms the decoding task into one closely resembling that of a single-qubit memory propagating through time. The resulting approach leads to fast decoding and reduced problem size while maintaining high performance. Focusing on the surface code, we prove that this method enables fault-tolerant decoding with minimum-weight perfect matching, and benchmark its performance on example circuits including magic state distillation. We find that the threshold is comparable to that of a single-qubit memory, and that the total decoding run time can be, in fact, less than that of conventional lattice surgery. Our approach enables fast correlated decoding, providing a pathway to directly extend single-qubit QEC techniques to transversal algorithms.

Fault-tolerant quantum computation (FTQC) requires compiling logical quantum circuits encoded using a quantum error-correcting code into physical operations tailored to specific hardware architectures. Lattice surgery has emerged as a leading method to perform logical computation, initially motivated by superconducting qubit architectures with geometrically local connectivity. However, current lattice surgery techniques are limited due to certain paradigmatic assumptions that are widely regarded as standard. In our works we identify and address two of these limiting paradigms. First, prior work has predominantly focused on the surface code, even though other topological codes offer certain advantages. Second, compilation schemes usually follow a place-and-route paradigm where logical qubits remain fixed in space throughout the computation. We initiate a more flexible line of work that goes beyond both aforementioned paradigms. To address the first, we introduce the concept of a code substrate - a blueprint for realizing quantum error correction with topological quantum codes using lattice surgery. We formulate the problem using two layers of abstraction. The microscopic level specifies how lattice surgery operations are realized using distance-preserving ancilla regions, while the macroscopic level abstracts compilation as a “mapping” and “routing” problem on a coarse-grained routing graph. We exemplify this framework with detailed constructions for the color code and folded surface code. To challenge the second paradigm, we exploit movable logical qubits through teleportation during logical CNOT execution. Building on the color code substrate, we adapt the measurement-based CNOT scheme to incorporate logical qubit teleportations without additional time overhead. This enables data qubits to dynamically change positions during compilation – “mapping” and “routing” are thus not viewed as independent and subsequent steps, as previous methods have in an overly simplified manner. This flexibility has the potential to substantially reduce routed circuit depth. Thus, movable logical qubits can be exploited even when physical qubits remain static, making movement-based compilation applicable not only to trapped ion and neutral atom platforms - where physical qubits are dynamic by design - but also to superconducting architectures. In addition to the conceptual work, we provide a set of open-source tools for the compilation of logical circuits for the color code on GitHub https://github.com/munich-quantum-toolkit/qecc.

Quantum low-density parity-check (qLDPC) codes can be implemented by measuring only low-weight checks, making them compatible with noisy quantum hardware and central to the quest to build noise-resilient quantum computers. A fundamental open question is how constraints on check weight limit the achievable parameters of qLDPC codes. Here, we study stabilizer and subsystem codes with constrained check weight, combining analytical arguments with numerical optimization to establish strong upper bounds on their parameters. We show that stabilizer codes with checks of weight at most three cannot have nontrivial distance. We also prove tight tradeoffs between rate and distance for broad families of CSS stabilizer and subsystem codes with checks of weight at most four and two, respectively. Notably, our bounds are applicable to general qLDPC codes, as they rely only on check-weight constraints without assuming geometric locality or special graph connectivity. In the finite-size regime, we derive numerical upper bounds using linear programming techniques and identify explicit code constructions that approach these limits, delineating the landscape of practically relevant qLDPC codes with tens or hundreds of physical qubits.