A Distillation-teleportation Protocol For Fault-tolerant QRAM

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 $\Omega (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