The preparation of data in quantum states is a critical component in the design of quantum algorithms. The cost of this step can significantly limit the realization of quantum advantage in domains such as machine learning, finance, and chemistry. One of the main approaches to achieve efficient state preparation is through the use of Quantum Random Access Memory (QRAM), a theoretical device for coherent data access with several proposed hardware implementations. In this work, we present a framework that integrates the hardware model of the Bucket Brigade QRAM (BBQRAM) with the classical data structure of the Segment Tree to achieve efficient state preparation. We introduce a memory layout that embeds a segment tree within BBQRAM memory cells by preserving the segment tree's hierarchy and supporting data retrieval in logarithmic time via specialized access primitives. We demonstrate that our method encodes a matrix
A∈RM×N in a quantum register of
Θ(log2(MN)) qubits in
O(log22(MN)) time, {requiring a constant number of working qubits (under fixed precision) and
O(MN) memory cells within the BBQRAM architecture.} We further illustrate the method through a numerical example. This framework provides theoretical support for quantum algorithms that assume negligible data loading overhead and establishes a foundation for designing classical-to-quantum encoding algorithms that are aware of the underlying hardware QRAM architecture.
The bucket-brigade architecture [1], [2]—a tree-based quantum memory encoding scheme—is a QRAM encoding design with one of the lowest known computational complexities. It theoretically offers a polylogarithmic complexity [3]–[5], although in practical gate-based implementations, the gate count scales exponentially with the number of qubits. Despite theoretical advancements, no algorithm yet exists that can generate QRAM basis encoding circuits for arbitrary input datasets, which is a significant barrier to practical encoding scalability. This paper proposes an algorithm capable of generating such circuits more efficiently than the standard bucket-brigade construction, thus reducing the number of address accesses and overall gate complexity. The asymptotic upper bound of the encoding circuit generated by our algorithm is derived to be
O(2k~(k~+d)), which achieves asymptotically exponential savings over general unitary synthesis as shown later in the paper. The resulting circuits provide a quantum data encoding layer that can be composed with downstream query or transform routines when needed. An example vector will be used throughout this paper to demonstrate a 60% gate count reduction. This is the first automated implementation of its kind-a foundational step towards developing a scalable QRAM encoding for quantum computing systems.
Efficient quantum state preparation is a critical component in quantum algorithms that process large classical data, and it is fundamental to realizing quantum advantage in domains such as machine learning, quantum linear algebra, and quantum finance. Building on the framework of~\cite{berti2025efficient}, which integrates Bucket Brigade QRAM (BBQRAM) with a segment tree to achieve amplitude encoding in polylogarithmic query time, we present two improvements within the same architecture-aware framework. First, we remove the
U2CR subroutine by classically precomputing the rotation angles determined by the segment tree and storing these angles directly in the BBQRAM cells. The tradeoff is that the classically loaded QRAM stores precomputed fixed-point angles rather than raw subtree weights. Second, we extend the construction to complex-valued matrices
A∈CM×N by storing a leaf phase alongside each precomputed rotation angle and using a two-step magnitude-then-phase procedure; the real signed case is naturally subsumed as a one-bit phase specialization. At unchanged
O(log22(MN)) BBQRAM query complexity, the QPU procedure reduces to BBQRAM retrievals and controlled-rotation cascades, with
O(MN) memory cells per matrix and no reversible arithmetic on the QPU.
Quantum random access memory (QRAM) enables efficient classical data access for quantum computers -- a prerequisite for many quantum algorithms to achieve quantum speedup. Despite various proposals, the experimental realization of QRAM remains largely unexplored. Here, we experimentally investigate the circuit-based bucket-brigade QRAM with a superconducting quantum processor. To facilitate the experimental implementation, we introduce a hardware-efficient gate decomposition scheme for quantum routers, which effectively reduces the depth of the QRAM circuit by more than 30% compared to the conventional controlled-SWAP-based implementation. We further propose an error mitigation method to boost the QRAM query fidelity. With these techniques, we are able to experimentally implement the QRAM architectures with two and three layers, achieving query fidelities up to 0.800
± 0.026 and 0.604$\pm$0.005, respectively. Additionally, we study the error propagation mechanism and the scalability of our QRAM implementation, providing experimental evidence for the noise resilience nature of the bucket-brigade QRAM architecture. Our results highlight the potential of superconducting quantum processors for realizing a scalable QRAM architecture.
Abstract A novel concept of quantum random access memory (qRAM) employing a quantum walk is provided. Our qRAM relies on a bucket brigade scheme to access the memory cells. Introducing a bucket with chirality left and right as a quantum walker, and considering its quantum motion on a full binary tree, we can efficiently deliver the bucket to the designated memory cells, and fill the bucket with the desired information in the form of quantum superposition states. Our procedure has several advantages. First, we do not need to place any quantum devices at the nodes of the binary tree, and hence in our qRAM architecture, the cost to maintain the coherence can be significantly reduced. Second, our scheme is fully parallelized. Consequently, only O(n) steps are required to access and retrieve O(2 n ) data in the form of quantum superposition states. Finally, the simplicity of our procedure may allow the design of qRAM with simpler structures.
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.