Source-linked AI summary
Quantum random access memory
Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone
TL;DR
Conventional RAM architectures require many switches to access memory, making classical decoding costly and qRAM implementations inefficient and noise-prone. The paper introduces the bucket-brigade architecture, replacing active gates with three-level memory elements and reducing active addressing operations to O(log N), while noting that present RAM energy costs may not justify its added delays and memory elements.
Problem
Conventional RAM architectures require O(N 1/d) switches to access one of N=2^n memory slots, causing high energy use for classical RAM and high decoherence for qRAM.
Method
The bucket-brigade architecture sends address and signal through a bifurcation graph whose nodes are three-level memory elements, or qutrits in the quantum setting.
Results
The architecture reduces active gates and two-body interactions during a memory call from O(N) to O(log2 N), while requiring only O(r log N) entangled qutrits for a query involving a superposition of r memory cells.
Takeaways & Limitations
The bucket-brigade could simplify qRAM implementation, reduce decoherence, and save addressing energy by limiting coherent activity to logarithmically many elements.
Takeaways & Limitations
For current RAMs, leakage and refreshing dominate dissipation, so addressing-energy savings may not justify the bucket-brigade’s additional delays and memory elements.
Abstract
from arXiv · showhide
A random access memory (RAM) uses n bits to randomly address N=2^n distinct memory cells. A quantum random access memory (qRAM) uses n qubits to address any quantum superposition of N memory cells. We present an architecture that exponentially reduces the requirements for a memory call: O(log N) switches need be thrown instead of the N used in conventional (classical or quantum) RAM designs. This yields a more robust qRAM algorithm, as it in general requires entanglement among exponentially less gates, and leads to an exponential decrease in the power needed for addressing. A quantum optical implementation is presented.