arXiv:2609.40020
Technical analysis of the Resource-efficient Quantum Walkers Quantum Random Access Memory
Giuseppe De Riso, Giuseppe Catalano, Seth Lloyd, Vittorio Giovannetti, Dario De Santis
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 $\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.
AI Summary
This technical follow-up develops a quantum-walker qRAM architecture for coherently retrieving an $m$-bit classical message from one of $N=2^n$ memory cells. It addresses how to reduce stationary quantum routing resources and the number of parallel routing trees while retaining efficient queries. Routing information is carried by an ordered train of address and data walkers rather than stored in node qutrits. Controlled address-transmission gates distribute each address bit to subsequent walkers; passive scattering gates route them by internal state. Address walkers separate from the data train after use and are recollected through a mirrored output tree. The paper specifies routing, memory-copy and retrieval operations, with resource counts derived from gate decompositions and explicit propagation schedules. The basic long-range scheme uses $O(n+m)$ carriers and one binary tree, with depth $O(n^2+nm)$. A backup-assisted variant replaces multi-target interactions with two- and three-carrier, range-2 gates; pipelining gives depth $O(n+m)$, reported as $10n+4m$ steps apart from additional query overhead. Particle-conserving alternatives use dual-rail encoding or four-level qudits. The short-range qudit construction requires $n+m$ carriers, one tree and nearest-neighbor operations, with reported depth $5n+2m$. All variants retain $O(2^n)$ routing hardware, and dense address superpositions engage $O(2^n)$ elements. Concrete hardware mappings, quantitative noise analysis and fault-tolerant implementation remain open. Photonic controlled operations require nonlinear interactions unavailable in linear optics; synchronous propagation assumes a global classical clock.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 34 pages, 14 figures. Companion paper to arXiv:2508.02855