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• 8 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•6 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•23 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•0 citations

Resource-efficient simulation of noisy quantum circuits and application to network-enabled QRAM optimization

Luís Bugalho, Emmanuel Zambrini Cruzeiro, Kevin C. Chen +3 more

Abstract Giovannetti, Lloyd, and Maccone (2008) proposed a quantum random access memory (QRAM) architecture to retrieve arbitrary superpositions of N (quantum) memory cells via quantum switches and $$O(\log (N))$$ O ( log ( N ) ) address qubits. Toward physical QRAM implementations, Chen et al. (2021) recently showed that QRAM maps natively onto optically connected quantum networks with $$O(\log (N))$$ O ( log ( N ) ) overhead and built-in error detection. However, modeling QRAM on large networks has been stymied by exponentially rising classical compute requirements. Here, we address this bottleneck by: (1) introducing a resource-efficient method for simulating large-scale noisy entanglement, allowing us to evaluate hundreds and even thousands of qubits under various noise channels; and (2) analyzing Chen et al.’s network-based QRAM as an application at the scale of quantum data centers or near-term quantum internet; and (3) introducing a modified network-based QRAM architecture to improve quantum fidelity and access rate. We conclude that network-based QRAM could be built with existing or near-term technologies leveraging photonic integrated circuits and atomic or atom-like quantum memories.

arXiv:2210.13494•npj Quantum Information•Oct 20, 2023•11 citations

Continuous-Time Quantum Walk in Glued Trees: Localized State-Mediated Almost Perfect Quantum-State Transfer

Vincent Pouthier, Lucie Pepe, Saad Yalouz

In this work, the dynamics of a quantum walker on glued trees is revisited to understand the influence of the architecture of the graph on the efficiency of the transfer between the two roots. Instead of considering regular binary trees, we focus our attention on leafier structures where each parent node could give rise to a larger number of children. Through extensive numerical simulations, we uncover a significant dependence of the transfer on the underlying graph architecture, particularly influenced by the branching rate (M) relative to the root degree (N). Our study reveals that the behavior of the walker is isomorphic to that of a particle moving on a finite-size chain. This chain exhibits defects that originate in the specific nature of both the roots and the leaves. Therefore, the energy spectrum of the chain showcases rich features, which lead to diverse regimes for the quantum-state transfer. Notably, the formation of quasi-degenerate localized states due to significant disparities between M and N triggers a localization process on the roots. Through analytical development, we demonstrate that these states play a crucial role in facilitating almost perfect quantum beats between the roots, thereby enhancing the transfer efficiency. Our findings offer valuable insights into the mechanisms governing quantum-state transfer on trees, with potential applications for the transfer of quantum information.

Entropy•Jun 2, 2024•1 citation
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.
Abstract Giovannetti, Lloyd, and Maccone (2008) proposed a quantum random access memory (QRAM) architecture to retrieve arbitrary superpositions of N (quantum) memory cells via quantum switches and O(log⁡(N))O(\log (N))O(log(N)) O ( log ( N ) ) address qubits. Toward physical QRAM implementations, Chen et al. (2021) recently showed that QRAM maps natively onto optically connected quantum networks with O(log⁡(N))O(\log (N))O(log(N)) O ( log ( N ) ) overhead and built-in error detection. However, modeling QRAM on large networks has been stymied by exponentially rising classical compute requirements. Here, we address this bottleneck by: (1) introducing a resource-efficient method for simulating large-scale noisy entanglement, allowing us to evaluate hundreds and even thousands of qubits under various noise channels; and (2) analyzing Chen et al.’s network-based QRAM as an application at the scale of quantum data centers or near-term quantum internet; and (3) introducing a modified network-based QRAM architecture to improve quantum fidelity and access rate. We conclude that network-based QRAM could be built with existing or near-term technologies leveraging photonic integrated circuits and atomic or atom-like quantum memories.
In this work, the dynamics of a quantum walker on glued trees is revisited to understand the influence of the architecture of the graph on the efficiency of the transfer between the two roots. Instead of considering regular binary trees, we focus our attention on leafier structures where each parent node could give rise to a larger number of children. Through extensive numerical simulations, we uncover a significant dependence of the transfer on the underlying graph architecture, particularly influenced by the branching rate (M) relative to the root degree (N). Our study reveals that the behavior of the walker is isomorphic to that of a particle moving on a finite-size chain. This chain exhibits defects that originate in the specific nature of both the roots and the leaves. Therefore, the energy spectrum of the chain showcases rich features, which lead to diverse regimes for the quantum-state transfer. Notably, the formation of quasi-degenerate localized states due to significant disparities between M and N triggers a localization process on the roots. Through analytical development, we demonstrate that these states play a crucial role in facilitating almost perfect quantum beats between the roots, thereby enhancing the transfer efficiency. Our findings offer valuable insights into the mechanisms governing quantum-state transfer on trees, with potential applications for the transfer of quantum information.