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

Abstract

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 𝒪(2ⁿ) 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 𝒪(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.

Resource-efficient quantum-walker quantum random access memory
Giuseppe De Riso, Giuseppe Catalano, Seth Lloyd +2
Physical Review Research2 Oct 2026Peer-reviewedCC BY 4.0Atomic, molecular & optical physicsCrossref
Efficient Fidelity Estimation of General Quantum Resource States via Clifford Circuits
Shunta Takahashi, Keisuke Fujii
arXiv4 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Resource-efficient formulations of the Knapsack problem for quantum computing
Pim van den Heuvel, Vrinda Mehta, Dennis Willsch +2
arXiv4 Nov 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Resource efficient Sample Based Quantum Simulation through Fragmentation and Virtual Partitioning of QPU
R. Pradeep, Anurag Chaudhary, Ashish Kumar Patra +4
arXiv30 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Resource-Efficient Synthesis of Sparse Quantum States
Renaud Vilmart, Sunheang Ty, Chetra Mang
HAL19 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationHAL

Cite

BibTeX RIS

BibTeX

@misc{riso2026technical,
  title = {{Technical analysis of the Resource-efficient Quantum Walkers Quantum Random Access Memory}},
  author = {Giuseppe De Riso and Giuseppe Catalano and Seth Lloyd and Vittorio Giovannetti and Dario De Santis},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40020},
  eprint = {2609.40020},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40020},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Technical analysis of the Resource-efficient Quantum Walkers Quantum Random Access Memory
AU  - Giuseppe De Riso
AU  - Giuseppe Catalano
AU  - Seth Lloyd
AU  - Vittorio Giovannetti
AU  - Dario De Santis
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40020
UR  - https://arxiv.org/abs/2609.40020
AB  - 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 𝒪(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 𝒪(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.
ER  -

Abstract

Related

Cite