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 \mathrm{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/\mathrm{poly}(n). The protocol queries the noisy QRAM device \mathrm{poly}(n) times to prepare a sequence of n-qubit QRAM resource states, which are moved to a general-purpose \mathrm{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. 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 \mathrm{poly}(n)-cost fault-tolerant QRAM.

Personal information

Alex is a senior scientist at the AWS Center for Quantum Computing (CQC), where he leads the quantum algorithms team. His current research interests include quantum algorithms for linear algebra problems, quantum/classical simulation of many-body physics, and opportunities for co-design between quantum algorithms and fault-tolerant architectures. Before joining AWS, Alex did a PhD at Caltech, where he worked on the complexity theory underlying random circuit sampling experiments. 

Reference

https://arxiv.org/abs/2505.20265