Error Correction 3

Abstract: Quantum devices can process data in a fundamentally different way than classical computers. To leverage this potential, many algorithms require the aid of a quantum Random Access Memory (QRAM), i.e. a module capable of efficiently loading datasets (both classical and quantum) onto the quantum processor. However, a realisation of this fundamental building block is still outstanding, since existing proposals require prohibitively many resources for reliable implementations, or are not compatible with current architectures. Moreover, present approaches cannot be scaled-up, as they do not allow for efficient quantum error-correction. Here we develop a QRAM design, that enables fast and robust QRAM calls, naturally allows for fault-tolerant and error-corrected operation, and can be integrated on present hardware. Our proposal employs a special quantum resource state that is consumed during the QRAM call: we discuss how it can be assembled and processed efficiently in a dedicated module. Concretely, we provide detailed blueprints and quantitative estimations for modern neutral-atom processors, demonstrating that high-fidelity QRAM queries can be implemented at rates compatible with the fault-tolerant computational clock-time. Our work places a long missing, fundamental component of quantum computers within reach of currently available technology; this opens the door to algorithms featuring practical quantum advantage, including search or oracular problems, quantum chemistry and machine learning.

Abstract: It has previously been shown that fault-tolerant syndrome can be enabled with flag gadgets. In essence, this relies upon the fact that syndrome extraction circuits are Clifford circuits. In this work we extend our previous framework to produce flag gadgets for syndrome extraction to a framework to flag any Clifford circuit. The construction we present allows a Clifford circuit including n two-qubit gates acting upon physical qubits in a code of distance d to be made fault tolerant to distance d using O(d^2 log(nd^2 log n)) ancilla qubits and O(nd^2 log(nd^2 log n)) extra CNOTs. This framework opens new pathways to universal fault-tolerance, for instance by allowing T gates to be implemented transversally while (a subset of) Clifford gates are fault-tolerantly implemented using flags, or by creating higher-reliability magic states using a flagged preparation circuit.

Abstract: 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.