QRAM: A Survey and Critique

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. 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. Escaping the constraints of active QRAM 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. In summary, we conclude that cheap, asymptotically scalable passive QRAM is unlikely with existing proposals, due to fundamental obstacles that we highlight. These obstacles are deeply rooted in the requirements of QRAM, but are not provably inevitable; we hope that our results will help guide research into QRAM technologies that circumvent or mitigate these obstacles. 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.

References in corpus (38)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum Amplitude Amplification and Estimation
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum machine learning: a classical perspective
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Architectures for a quantum random access memory
• A quantum-inspired classical algorithm for recommendation systems
• Quantum memories at finite temperature
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Efficient Distributed Quantum Computing
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Circuit-Based Quantum Random Access Memory for Classical Data
• Focus beyond quadratic speedups for error-corrected quantum advantage
• On the robustness of bucket brigade quantum RAM
• Mid-Infrared ultra-high-Q resonators based on fluoride crystalline materials
• Fault-tolerant logical gates in quantum error-correcting codes
• Fault tolerant resource estimation of quantum random-access memories
• Towards provably efficient quantum algorithms for large-scale machine-learning models
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Resilience of quantum random access memory to generic noise
• Experimental demonstration of a quantum router
• Experimental realization of 105-qubit random access quantum memory
• A Robust Quantum Random Access Memory
• Quantum Machine Learning for Finance
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Improved Quantum Information Set Decoding
• Quantum random access memory via quantum walk
• Sieving for closest lattice vectors (with preprocessing)
• An ultra-high gain single-photon transistor in the microwave regime
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine

Cited by in corpus (2)

• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Refined Criteria for QRAM Error Suppression via Efficient Large-Scale QRAM Simulator