Quantum random access memory (qRAM) remains a persistent bottleneck---not because the lookup specification is unclear, but because implementing a single coherent query can demand deep active control, long-range routing, or unrealistic unit-cost oracle assumptions. We address this tension through a universal, data-independent lookup unitary (U-QRAM) in which the database resides in memory qubits and functions as quantum control. Our first contribution is a hardware-explicit reformulation: U-QRAM equals time evolution under a single time-independent Hamiltonian that is a sum of mutually commuting projector terms---one per memory cell. Because these terms commute, the order of application is irrelevant: they may be executed sequentially or in parallel without changing the target unitary. Our second contribution identifies the most direct path to constant-locality interactions: when addresses are encoded in a unary (one-hot, mode-addressed) register, each Hamiltonian term reduces to 3-local form, replacing the usual (log N)-controlled fan-in barrier with spatial or modal selectivity. We maintain conservative claims: constant latency requires explicit hardware assumptions (global buses, all-to-all connectivity, or native multi-body interactions), and we provide compiled circuit baselines for when such assumptions do not hold.
Quantum random access memory (qRAM) remains a persistent bottleneck---not because the lookup specification is unclear, but because implementing a single coherent query can demand deep active control, long-range routing, or unrealistic unit-cost oracle assumptions. We address this tension through a universal, data-independent lookup unitary (U-QRAM) in which the database resides in memory qubits and functions as quantum control. Our first contribution is a hardware-explicit reformulation: U-QRAM equals time evolution under a single time-independent Hamiltonian that is a sum of mutually commuting projector terms---one per memory cell. Because these terms commute, the order of application is irrelevant: they may be executed sequentially or in parallel without changing the target unitary. Our second contribution identifies the most direct path to constant-locality interactions: when addresses are encoded in a unary (one-hot, mode-addressed) register, each Hamiltonian term reduces to 3-local form, replacing the usual (log N)-controlled fan-in barrier with spatial or modal selectivity. We maintain conservative claims: constant latency requires explicit hardware assumptions (global buses, all-to-all connectivity, or native multi-body interactions), and we provide compiled circuit baselines for when such assumptions do not hold.
Quantum random access memory (QRAM) is a central primitive for coherent data access in quantum algorithms, yet it remains controversial in practice because the wall-clock cost of "one lookup" can hide routing depth, control overhead, and geometric constraints. We present a universal QRAM construction (U-QRAM) in which the database is a physical memory register that participates in the lookup unitary as quantum control. This yields a single fixed, data-independent lookup unitary on A⊗D⊗M that is correct for all basis-encoded databases.
Our first contribution is an explicit, exact Hamiltonian realization: U-QRAM equals a single time-independent evolution UQRAM=exp(−iHtot) where Htot is a sum of mutually commuting projector terms, one per memory cell, and the construction avoids control-dependent phase ambiguities. Our second contribution is an architectural sharpening: under unary (one-hot, mode-addressed) encoding of the address, each cell term becomes uniform and 3-local, delineating the most direct path toward constant-latency interpretations. We keep claims conservative by separating latency from work and stating explicit hardware assumptions required for constant wall-clock queries.
Quantum random access memory (QRAM) is a central primitive for coherent data access in quantum algorithms, yet it remains controversial in practice because the wall-clock cost of "one lookup" can hide routing depth, control overhead, and geometric constraints. We present a universal QRAM construction (U-QRAM) in which the database is a physical memory register that participates in the lookup unitary as quantum control. This yields a single fixed, data-independent lookup unitary on A ⊗ D ⊗ M that is correct for all basis-encoded databases. Our first contribution is an explicit, exact Hamiltonian realization: U-QRAM equals a single time-independent evolution U_QRAM = exp(-iH_tot) where H_tot is a sum of mutually commuting projector terms, one per memory cell, and the construction avoids control-dependent phase ambiguities. Our second contribution is an architectural sharpening: under unary (one-hot, mode-addressed) encoding of the address, each cell term becomes uniform and 3-local, delineating the most direct path toward constant-latency interpretations. We keep claims conservative by separating latency from work and stating explicit hardware assumptions required for constant wall-clock queries.
Quantum Random Access Memory (qRAM) is a critical component for achieving quantum advantage in algorithms ranging from database search to quantum machine learning. In a recently introduced model [arXiv:2508.02855], we proposed a resource-efficient qRAM architecture based on discrete-time quantum walkers. This article serves as a comprehensive technical follow-up, providing the full mathematical derivations, detailed protocol specifications, and in-depth resource analysis. Moreover, we extend the original proposal with novel techniques for the purpose of making the qRAM implementation more realistic. Our model resolves the primary drawbacks of leading qRAM proposals: it avoids the exponential number of active nodes O(2n) required by the "Bucket Brigade" architecture by employing a number of quantum walkers that scales linearly with the address and message sizes, n and m, respectively. Simultaneously, it overcomes the spatial bottlenecks of previous quantum-walker schemes by eliminating the need for multiple parallel trees. We propose two algorithmic paradigms: the long- and the short-range approaches, which differ by the length of interaction of the main routing gates employed in the qRAM. We formalize the routing, message-copy, and walker retrieval phases for both variants and we show how, while the long-range scheme employs controlled gates having a multitude of target systems, the short-range approach decomposes these interactions into sequences of 2- and 3-body local gates, which improves the architecture's feasibility for near-term experimental implementation. Finally, our comprehensive resource analysis confirms that the short-range approach achieves the optimal O(n+m) circuit depth. Within these two paradigms, we explore the potential of different types of quantum walkers, namely bosons, dual-rail qubits and four-level qudits.
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.
Universal QRAM (U-QRAM) is a fixed, data-independent unitary interface that implements coherent random-access reads relative to a designated computational "truth-table" basis on the memory register. This work studies restricted-access inference: the memory register is persistent but inaccessible, while an experimenter may prepare and measure only accessible registers and may invoke the fixed read interaction.
Allowing the memory to be in an arbitrary quantum state (pure or mixed, possibly entangled with an inaccessible reference system, or a coherent superposition of truth tables), we establish a sharp, protocol-independent limitation of read-only access. For any finite-query protocol -- including arbitrary accessible ancillas, intermediate measurements, adaptivity, and general CPTP processing between queries -- the induced output state on the accessible registers depends on the memory state only through its diagonal in the truth-table basis. Equivalently, read-only access factors through dephasing (pinching) in that basis; coherences between distinct truth tables are operationally invisible.
Consequently, every memory-hypothesis testing task reduces to a standard state-discrimination problem on the accessible registers, and the minimum-error optimal measurement is characterized by Helstrom theory. We illustrate the framework with three explicit examples: (i) the phase-kickback reduction recovering the one-query Bernstein-Vazirani/Deutsch-Jozsa geometry, (ii) a minimal Helstrom instance with optimal success probability 3/4, and (iii) perfect indistinguishability of relative phases in entangled truth-table superpositions.
Abstract Giovannetti, Lloyd, and Maccone (2008) proposed a quantum random access memory (QRAM) architecture to retrieve arbitrary superpositions of N (quantum) memory cells via quantum switches and O(log(N)) O ( log ( N ) ) address qubits. Toward physical QRAM implementations, Chen et al. (2021) recently showed that QRAM maps natively onto optically connected quantum networks with O(log(N)) O ( log ( N ) ) overhead and built-in error detection. However, modeling QRAM on large networks has been stymied by exponentially rising classical compute requirements. Here, we address this bottleneck by: (1) introducing a resource-efficient method for simulating large-scale noisy entanglement, allowing us to evaluate hundreds and even thousands of qubits under various noise channels; and (2) analyzing Chen et al.’s network-based QRAM as an application at the scale of quantum data centers or near-term quantum internet; and (3) introducing a modified network-based QRAM architecture to improve quantum fidelity and access rate. We conclude that network-based QRAM could be built with existing or near-term technologies leveraging photonic integrated circuits and atomic or atom-like quantum memories.