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\left({{2^{\tilde k}}(\tilde k + d)}\right),$ 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.
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.
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.
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.
Quantum algorithms claim significant speedup over their classical counterparts for solving many problems. An important aspect of many of these algorithms is the existence of a quantum oracle, which needs to be implemented efficiently in order to realize the claimed advantages in practice. A quantum random access memory (QRAM) is a promising architecture for realizing these oracles. In this paper we develop a new design for QRAM and implement it with Clifford+T circuit. We focus on optimizing the T-count and T-depth since non-Clifford gates are the most expensive to implement fault-tolerantly in most error correction schemes. Integral to our design is a polynomial encoding of bit strings and so we refer to this design as [Formula: see text]. Compared to the previous state-of-the-art bucket brigade architecture for QRAM, we achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit-count same. Specifically, if N is the number of memory locations to be queried, then [Formula: see text] has T-depth [Formula: see text], T-count [Formula: see text] and uses O(N) logical qubits, while the bucket brigade circuit has T-depth [Formula: see text], T-count O(N) and uses O(N) qubits. Combining two [Formula: see text] we design a quantum look-up-table, [Formula: see text], that has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. A quantum look-up table (qLUT) or quantum read-only memory (QROM) has restricted functionality than a QRAM. For example, it cannot write into a memory location and the circuit needs to be compiled each time the contents of the memory change. The previous state-of-the-art CSWAP architecture has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. Thus we achieve a double exponential improvement in T-depth while keeping the T-count and qubit-count asymptotically same. Additionally, with our polynomial encoding of bit strings, we develop a method to optimize the Toffoli-count of circuits, specially those consisting of multi-controlled-NOT gates.
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 routers (QRouters) are essential components of bucket-brigade quantum random access memory (QRAM), enabling quantum applications such as Grover’s search and quantum machine learning. Despite significant theoretical advances, achieving scalable and coherent QRouters experimentally remains challenging. Here, we demonstrate coherent quantum routers using a superconducting quantum processor, laying a practical foundation for scalable QRAM systems. The quantum router at the core of our implementation utilizes the transition composite gate scheme, wherein auxiliary energy levels temporarily mediate conditional interactions. By leveraging two-qubit primitives in its construction, the quantum router preserves straightforward initialization and calibration while significantly reducing circuit depth and duration relative to traditional gate-based decompositions. Moreover, by encoding routing addresses in the nonadjacent qutrit states | 0 ⟩ and | 2 ⟩ , our design inherently enables erasure-detection capability, providing efficient postselection to mitigate routing errors. Experimentally, we achieve an average fidelity of 94.8% across three individual QRouters, and we validate scalability through a two-layer quantum routing network achieving a fidelity of 82.4%. Our results represent a significant advancement in quantum routing technology, providing enhanced fidelity, built-in error resilience, and practical scalability crucial for the development of future QRAM and large-scale quantum computing architectures.
Quantum random access memory (qRAM) is valuable for applying quantum computers to a broad range of problems and for successfully implementing large-scale quantum computation systems. Despite its importance, its adoption may be restricted by the fact that the decomposition of the qRAM function contains non-transversal gates, which cannot be executed transversally on any quantum error correction (QEC) code. To overcome these limitations, existing works employ techniques like magic state distillation. However, distillation is time-and qubit-intensive. This paper presents a fault-tolerant, resource-efficient implementation of qRAM based on pieceable fault tolerance. By breaking the logical CSWAP and Toffoli gate into simpler, easier-to-execute but non-transversal components, we first show that bucket-brigade qRAM can be implemented in polynomial depth without the need for ancillary magic states, further gate decomposition, or other gates. Afterward, we demonstrate the resource efficiency of this method of attaining fault tolerance in quantum operations. Based on resource estimation results, fault-tolerant bucket brigades using the pieceable technique perform better than fault-tolerant bucket brigades using magic state distillation with respect to the number of physical qubits, time, and cost.