Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2006.11761

Circuit implementation of bucket brigade qRAM for quantum state preparation

Pablo A. M. Casares

Published Jun 21, 2020• 11 citations
arXivHTMLPDF

Abstract

In this short review I aim to explain how we can construct a circuit implementation of the bucketbrigade qRAM first proposed in [1]. Used with classical data, this qRAM model can be used incombination with the quantum accessible data structure [2] to prepare arbitrary quantum statesquickly and repeatedly, once the data to be prepared is in memory

DOI
10.48550/arxiv.2006.11761

Related papers

Efficient Quantum State Preparation with Bucket Brigade QRAM

Alessandro Berti, Francesco Ghisoni

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 \in \mathbb{R}^{M \times N}$ in a quantum register of $Θ(\log_2(MN))$ qubits in $\mathcal{O}(\log_2^2(MN))$ time, {requiring a constant number of working qubits (under fixed precision) and $\mathcal{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.

arXiv:2510.16149•Oct 17, 2025•4 citations

Circuit-Level Construction of Bucket-Brigade QRAM Basis Encoding from Arbitrary Classical Data

Mohammed Al-Haidary, Ahmed Bouridane, Raouf Dridi

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.

International Conference on Signal Processing and Information Security (ICSPIS)•Nov 18, 2025•0 citations

Efficient Complex-Valued State Preparation on Bucket Brigade QRAM

Alessandro Berti, Francesco Ghisoni

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 $U_{2\mathrm{CR}}$ 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 \in \mathbb{C}^{M \times 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 $\mathcal{O}(\log_2^2(MN))$ BBQRAM query complexity, the QPU procedure reduces to BBQRAM retrievals and controlled-rotation cascades, with $\mathcal{O}(MN)$ memory cells per matrix and no reversible arithmetic on the QPU.

quant-pharXiv:2604.25644•Apr 29, 2026•0 citations

Quantum random access memory via quantum walk

Ryo Asaka, Kazumitsu Sakai, Ryoko Yahagi

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.

arXiv:2008.13365•Quantum Science and Technology•Apr 1, 2021•25 citations

Architectures for a quantum random access memory

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

A random access memory, or RAM, is a device that, when interrogated, returns the content of a memory location in a memory array. A quantum RAM, or qRAM, allows one to access superpositions of memory sites, which may contain either quantum or classical information. RAMs and qRAMs with $n$-bit addresses can access ${2}^{n}$ memory sites. Any design for a RAM or qRAM then requires $O({2}^{n})$ two-bit logic gates. At first sight this requirement might seem to make large scale quantum versions of such devices impractical, due to the difficulty of constructing and operating coherent devices with large numbers of quantum logic gates. Here we analyze two different RAM architectures (the conventional fanout and the ``bucket brigade'') and propose some proof-of-principle implementations, which show that, in principle, only $O(n)$ two-qubit physical interactions need take place during each qRAM call. That is, although a qRAM needs $O({2}^{n})$ quantum logic gates, only $O(n)$ need to be activated during a memory call. The resulting decrease in resources could give rise to the construction of large qRAMs that could operate without the need for extensive quantum error correction.

arXiv:0807.4994•Physical Review A•Nov 5, 2008•326 citations

From Bits to Qubits: The Theory and Practice of Quantum Data Encoding

Xiao-Ming Zhang, Arthur G. Rattew, Bujiao Wu +4 more

Encoding classical data into quantum systems is a foundational step in the execution of nearly all quantum algorithms, and a critical bottleneck in realizing practical quantum advantage. This review provides a comprehensive account of the concepts, algorithms, and practical considerations associated with quantum data encoding. We trace the development from its early conceptual foundations to recent advances, considering commonly used access models, such as quantum state preparation, unitary synthesis, QRAM and block encoding. We survey the circuit size, depth, space-time tradeoffs, as well as non-Clifford resources required for fault-tolerant implementation. We also discuss the roles of different access models in quantum algorithms. Special attention is given to structured data, such as sparse data, Boolean functions and data represented by tensor networks. This review bridges theory and applications, serving both as a pedagogical guide for newcomers and as a reference for active researchers. We also highlight the pivotal role of quantum data encoding in quantum computing and provide insights into future directions that will enable quantum advantage.

quant-pharXiv:2609.08058•Sep 9, 2026•4 citations
In this short review I aim to explain how we can construct a circuit implementation of the bucketbrigade qRAM first proposed in [1]. Used with classical data, this qRAM model can be used incombination with the quantum accessible data structure [2] to prepare arbitrary quantum statesquickly and repeatedly, once the data to be prepared is in memory
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×NA \in \mathbb{R}^{M \times N}A∈RM×N in a quantum register of Θ(log⁡2(MN))Θ(\log_2(MN))Θ(log2​(MN)) qubits in O(log⁡22(MN))\mathcal{O}(\log_2^2(MN))O(log22​(MN)) time, {requiring a constant number of working qubits (under fixed precision) and O(MN)\mathcal{O}(MN)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)),O\left({{2^{\tilde k}}(\tilde k + d)}\right),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 U2CRU_{2\mathrm{CR}}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×NA \in \mathbb{C}^{M \times N}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(log⁡22(MN))\mathcal{O}(\log_2^2(MN))O(log22​(MN)) BBQRAM query complexity, the QPU procedure reduces to BBQRAM retrievals and controlled-rotation cascades, with O(MN)\mathcal{O}(MN)O(MN) memory cells per matrix and no reversible arithmetic on the QPU.
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.
A random access memory, or RAM, is a device that, when interrogated, returns the content of a memory location in a memory array. A quantum RAM, or qRAM, allows one to access superpositions of memory sites, which may contain either quantum or classical information. RAMs and qRAMs with nnn-bit addresses can access 2n{2}^{n}2n memory sites. Any design for a RAM or qRAM then requires O(2n)O({2}^{n})O(2n) two-bit logic gates. At first sight this requirement might seem to make large scale quantum versions of such devices impractical, due to the difficulty of constructing and operating coherent devices with large numbers of quantum logic gates. Here we analyze two different RAM architectures (the conventional fanout and the ``bucket brigade'') and propose some proof-of-principle implementations, which show that, in principle, only O(n)O(n)O(n) two-qubit physical interactions need take place during each qRAM call. That is, although a qRAM needs O(2n)O({2}^{n})O(2n) quantum logic gates, only O(n)O(n)O(n) need to be activated during a memory call. The resulting decrease in resources could give rise to the construction of large qRAMs that could operate without the need for extensive quantum error correction.
Encoding classical data into quantum systems is a foundational step in the execution of nearly all quantum algorithms, and a critical bottleneck in realizing practical quantum advantage. This review provides a comprehensive account of the concepts, algorithms, and practical considerations associated with quantum data encoding. We trace the development from its early conceptual foundations to recent advances, considering commonly used access models, such as quantum state preparation, unitary synthesis, QRAM and block encoding. We survey the circuit size, depth, space-time tradeoffs, as well as non-Clifford resources required for fault-tolerant implementation. We also discuss the roles of different access models in quantum algorithms. Special attention is given to structured data, such as sparse data, Boolean functions and data represented by tensor networks. This review bridges theory and applications, serving both as a pedagogical guide for newcomers and as a reference for active researchers. We also highlight the pivotal role of quantum data encoding in quantum computing and provide insights into future directions that will enable quantum advantage.