A Distillation-Teleportation Protocol for Fault-Tolerant QRAM

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\left(2^{n}\right)$ 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 / \operatorname{poly}(n)$. The protocol queries the noisy QRAM device $\operatorname{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 faulttolerantly 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 faulttolerant QRAM.