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:2008.13365 · Quantum Science and Technology

Quantum random access memory via quantum walk

Ryo Asaka, Kazumitsu Sakai, Ryoko Yahagi

Published Apr 1, 2021• 25 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/2058-9565/abf484

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

Technical analysis of the Resource-efficient Quantum Walkers Quantum Random Access Memory

Giuseppe De Riso, Giuseppe Catalano, Seth Lloyd +2 more

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 $\mathcal{O}(2^n)$ 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 $\mathcal{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.

quant-pharXiv:2609.40020•Oct 1, 2026•0 citations

Two-level quantum walkers on directed graphs. II. Application to quantum random access memory

Ryo Asaka, Kazumitsu Sakai, Ryoko Yahagi

This is the second paper in a series of two. Using a multiparticle continuous-time quantum walk with two internal states, which was formulated in the first paper [R. Asaka et al., preceding paper, Phys. Rev. A 107, 022415 (2023)], we physically implement a quantum random access memory (QRAM). Data with address information are dual-rail encoded into quantum walkers. The walkers pass through perfect binary trees to access the designated memory cells and copy the data stored in the cells. A roundabout gate allocated at each node serves as a router to move the walker from the parent node to one of two child nodes, depending on the internal state of the walker. In this process, the address information is sequentially encoded into the internal states so that the walkers are adequately delivered to the target cells. The present QRAM, which processes ${2}^{n}\phantom{\rule{4pt}{0ex}}m$-qubit data, is implemented in a quantum circuit of depth $O(nlog(n+m))$ and requires $O(n+m)$ qubit resources. This is more efficient than the conventional bucket-brigade QRAM that requires $O({n}^{2}+nm)$ steps and $O({2}^{n}+m)$ qubit resources for processing. Moreover, since the walkers are not entangled with any device on the binary trees, the cost of maintaining coherence can be reduced. Notably, by simply passing quantum walkers through binary trees, data can be automatically extracted in a quantum superposition state. In other words, any time-dependent control is not required.

arXiv:2204.08709•Physical Review A•Feb 13, 2023•10 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

Enhancing the yield of bucket brigade quantum random access memory using redundancy repair

Dongmin Kim, Sengthai Heng, Sanghyeon Lee +1 more

Quantum random access memory (qRAM) is an essential computing element for running oracle-based quantum algorithms. qRAM exploits quantum superposition to access all data stored in the memory cells simultaneously and guarantees the superior performance of quantum algorithms. A qRAM memory cell comprises logical qubits encoded through quantum error correction technology for successful operation against various quantum noises. In addition to quantum noise, the low-technology nodes based on silicon technology can increase the qubit density and may introduce defective qubits. As qRAM comprises many qubits, its yield will be reduced by defective qubits; these qubits must be handled using QEC scheme. However, the QEC scheme requires numerous physical qubits, which burdens resource overhead. In this paper, to resolve this overhead problem, we propose a novel quantum memory architecture that compensates for defective qubits by introducing redundant qubits. We also analyze the yield improvement offered by our proposed quantum memory architecture by varying the ideal fabrication error rate from 0.5 to 1% for different numbers of logical qubits in the qRAM. We demonstrate that for the qRAM comprising 1024 logical qubits, eight redundant logical qubits improved the yield by 95.92% from that of qRAM not employing the redundant repair scheme.

arXiv:2312.17483•Scientific Reports•Dec 27, 2025•5 citations

Quantum Random Access Memory

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

A random access memory (RAM) uses n bits to randomly address N=2(n) distinct memory cells. A quantum random access memory (QRAM) uses n qubits to address any quantum superposition of N memory cells. We present an architecture that exponentially reduces the requirements for a memory call: O(logN) switches need be thrown instead of the N used in conventional (classical or quantum) RAM designs. This yields a more robust QRAM algorithm, as it in general requires entanglement among exponentially less gates, and leads to an exponential decrease in the power needed for addressing. A quantum optical implementation is presented.

arXiv:0708.1879•Physical Review Letters•Apr 21, 2008•1,029 citations
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.
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.
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)\mathcal{O}(2^n)O(2n) required by the "Bucket Brigade" architecture by employing a number of quantum walkers that scales linearly with the address and message sizes, nnn and mmm, 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)\mathcal{O}(n+m)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.
This is the second paper in a series of two. Using a multiparticle continuous-time quantum walk with two internal states, which was formulated in the first paper [R. Asaka et al., preceding paper, Phys. Rev. A 107, 022415 (2023)], we physically implement a quantum random access memory (QRAM). Data with address information are dual-rail encoded into quantum walkers. The walkers pass through perfect binary trees to access the designated memory cells and copy the data stored in the cells. A roundabout gate allocated at each node serves as a router to move the walker from the parent node to one of two child nodes, depending on the internal state of the walker. In this process, the address information is sequentially encoded into the internal states so that the walkers are adequately delivered to the target cells. The present QRAM, which processes 2nm{2}^{n}\phantom{\rule{4pt}{0ex}}m2nm-qubit data, is implemented in a quantum circuit of depth O(nlog(n+m))O(nlog(n+m))O(nlog(n+m)) and requires O(n+m)O(n+m)O(n+m) qubit resources. This is more efficient than the conventional bucket-brigade QRAM that requires O(n2+nm)O({n}^{2}+nm)O(n2+nm) steps and O(2n+m)O({2}^{n}+m)O(2n+m) qubit resources for processing. Moreover, since the walkers are not entangled with any device on the binary trees, the cost of maintaining coherence can be reduced. Notably, by simply passing quantum walkers through binary trees, data can be automatically extracted in a quantum superposition state. In other words, any time-dependent control is not required.
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.
Quantum random access memory (qRAM) is an essential computing element for running oracle-based quantum algorithms. qRAM exploits quantum superposition to access all data stored in the memory cells simultaneously and guarantees the superior performance of quantum algorithms. A qRAM memory cell comprises logical qubits encoded through quantum error correction technology for successful operation against various quantum noises. In addition to quantum noise, the low-technology nodes based on silicon technology can increase the qubit density and may introduce defective qubits. As qRAM comprises many qubits, its yield will be reduced by defective qubits; these qubits must be handled using QEC scheme. However, the QEC scheme requires numerous physical qubits, which burdens resource overhead. In this paper, to resolve this overhead problem, we propose a novel quantum memory architecture that compensates for defective qubits by introducing redundant qubits. We also analyze the yield improvement offered by our proposed quantum memory architecture by varying the ideal fabrication error rate from 0.5 to 1% for different numbers of logical qubits in the qRAM. We demonstrate that for the qRAM comprising 1024 logical qubits, eight redundant logical qubits improved the yield by 95.92% from that of qRAM not employing the redundant repair scheme.
A random access memory (RAM) uses n bits to randomly address N=2(n) distinct memory cells. A quantum random access memory (QRAM) uses n qubits to address any quantum superposition of N memory cells. We present an architecture that exponentially reduces the requirements for a memory call: O(logN) switches need be thrown instead of the N used in conventional (classical or quantum) RAM designs. This yields a more robust QRAM algorithm, as it in general requires entanglement among exponentially less gates, and leads to an exponential decrease in the power needed for addressing. A quantum optical implementation is presented.