QRAM A Survey and Critique

Title: QRAM: A Survey and Critique
Speaker: Samuel Jaques from University of Oxford/ University of Waterloo
Additional citations on the slide:
Slide 2: From Kupberberg, 2013. Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. arxiv.org/abs/1112.3333
Slide 9, 13: From Jaques and Schanck, 2019. Quantum cryptanalysis in the RAM model:
Claw-fi nding attacks on SIKE. eprint.iacr.org/2019/103
Slide 11: Figure from Fowler, Mariantoni,Martinis, Cleland, 2012. Surface codes: Towards practical large-scale quantum computation. arxiv.org/abs/1208.0928
Slide 19: Figure from Berry, Gidney, Motta, McClean, Babbush, 2019. Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization. arxiv.org/abs/1902.02134
Abstract:
Quantum random-access memory (QRAM) is a mechanism to access data (quantum or classical) based on addresses which are themselves a quantum state. QRAM has a long and controversial history, and here we survey and expand arguments and constructions for and against.
We use two primary categories of QRAM from the literature: (1) active, which requires external intervention and control for each QRAM query (e.g. the error-corrected circuit model), and (2) passive, which requires no external input or energy once the query is initiated. In the active model, there is a powerful opportunity cost argument: in many applications, one could repurpose the control hardware for the qubits in the QRAM (or the qubits themselves) to run an extremely parallel classical algorithm to achieve the same results just as fast. Escaping these constraints requires ballistic computation with passive memory, which creates an array of dubious physical assumptions, which we examine in detail. Considering these details, in everything we could find, all non-circuit QRAM proposals fall short in one aspect or another. We apply these arguments in detail to quantum linear algebra and prove that most asymptotic quantum advantage disappears with active QRAM systems, with some nuance related to the architectural assumptions.
In summary, we conclude that cheap, asymptotically scalable passive QRAM is unlikely with existing proposals, due to fundamental limitations that we highlight. We hope that our results will help guide research into QRAM technologies that attempt to circumvent or mitigate these limitations. Finally, circuit-based QRAM still helps in many applications, and so we additionally provide a survey of state-of-the-art techniques as a resource for algorithm designers using QRAM.
arXiv: arxiv.org/abs/2305.10310