Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM

Abstract

This is the second paper in a series of two. Using a multi-particle continuous-time quantum walk with two internal states, which has been formulated in the first paper (arXiv:2112.08119), 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$ $m$-qubit data, is implemented in a quantum circuit of depth $O(n\log (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.

23 pages; ver. 2: fixed typos. This is the second paper in a series of two. The first paper is arXiv:2112.08119

References in corpus (7)

• An introduction to quantum machine learning
• Quantum random access memory
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Universal computation by multi-particle quantum walk
• Architectures for a quantum random access memory
• Scalable quantum memory in the ultrastrong coupling regime
• Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing

Cited by in corpus (5)

• QRAM: A Survey and Critique
• Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Refined Criteria for QRAM Error Suppression via Efficient Large-Scale QRAM Simulator
• Optimizing topology for quantum probing with discrete-time quantum walks