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:2204.08709 · Physical Review A

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

Ryo Asaka, Kazumitsu Sakai, Ryoko Yahagi

Published Feb 13, 2023• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.107.022416

Related papers

Two-level quantum walkers on directed graphs. I. Universal quantum computing

Ryo Asaka, Kazumitsu Sakai, Ryoko Yahagi

In the present paper, the first in a series of two, we propose a model of universal quantum computation using a fermionic or bosonic multiparticle continuous-time quantum walk with two internal states (e.g., the spin-up and -down states of an electron). A dual-rail encoding is adopted to convert information: A single qubit is represented by the presence of a single quantum walker in either of the two parallel paths. We develop a roundabout gate that moves a walker from one path to the next, either clockwise or counterclockwise, depending on its internal state. It can be realized by a single-particle scattering on a directed weighted graph with the edge weights 1 and $\ifmmode\pm\else\textpm\fi{}i$. The roundabout gate also allows the spatial information of the quantum walker to be temporarily encoded in its internal states. The universal gates are constructed by appropriately combining several roundabout gates, some unitary gates that act on the internal states, and two-particle scatterings on straight paths. No ancilla qubits are required in our model. The computation is done by just passing quantum walkers through properly designed paths. Namely, there is no need for any time-dependent control. A physical implementation of quantum random access memory compatible with the present model will be considered in the second paper [R. Asaka et al., following paper, Phys. Rev. A 107, 022416 (2023)].

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

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

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

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

Circuit implementation of bucket brigade qRAM for quantum state preparation

Pablo A. M. Casares

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

arXiv:2006.11761•Jun 21, 2020•11 citations
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.
In the present paper, the first in a series of two, we propose a model of universal quantum computation using a fermionic or bosonic multiparticle continuous-time quantum walk with two internal states (e.g., the spin-up and -down states of an electron). A dual-rail encoding is adopted to convert information: A single qubit is represented by the presence of a single quantum walker in either of the two parallel paths. We develop a roundabout gate that moves a walker from one path to the next, either clockwise or counterclockwise, depending on its internal state. It can be realized by a single-particle scattering on a directed weighted graph with the edge weights 1 and $\ifmmode\pm\else\textpm\fi{}i$. The roundabout gate also allows the spatial information of the quantum walker to be temporarily encoded in its internal states. The universal gates are constructed by appropriately combining several roundabout gates, some unitary gates that act on the internal states, and two-particle scatterings on straight paths. No ancilla qubits are required in our model. The computation is done by just passing quantum walkers through properly designed paths. Namely, there is no need for any time-dependent control. A physical implementation of quantum random access memory compatible with the present model will be considered in the second paper [R. Asaka et al., following paper, Phys. Rev. A 107, 022416 (2023)].
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.
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.
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.