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.

arXiv comment23 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 (30)

• Quantum Machine Learning
• Quantum support vector machine for big data classification
• Quantum machine learning in feature Hilbert spaces
• Quantum Amplitude Amplification and Estimation
• An introduction to quantum machine learning
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum computers can search rapidly by using almost any transformation
• Toward the first quantum simulation with quantum speedup
• Quantum machine learning: a classical perspective
• Universal computation by multi-particle quantum walk
• Architectures for a quantum random access memory
• Implementing a distance-based classifier with a quantum interference circuit
• Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
• A scheme for direct detection of qubit-environment entanglement generated during qubit pure dephasing
• On the robustness of bucket brigade quantum RAM
• Fault tolerant resource estimation of quantum random-access memories
• Scalable quantum memory in the ultrastrong coupling regime
• Resilience of quantum random access memory to generic noise
• A Robust Quantum Random Access Memory
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Scalable and High-Fidelity Quantum Random Access Memory in Spin-Photon Networks
• Quantum circuit for the fast Fourier transform
• Quantum random access memory via quantum walk
• Optimal Usage of Quantum Random Access Memory in Quantum Machine Learning
• 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