Source-linked AI summary
Architectures for a quantum random access memory
Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone
TL;DR
Large-scale qRAM appears costly because addressing 2^n sites requires O(2^n) gates. The paper analyzes fanout and bucket-brigade architectures, showing that only O(n) two-qubit physical interactions need be activated during each qRAM call.
Problem
qRAM designs require O(2^n) two-bit logic gates for n-bit addresses, raising concerns about constructing and operating large coherent devices.
Method
The paper analyzes conventional fanout and bucket-brigade RAM architectures and proposes quantum optical and solid-state proof-of-principle implementations.
Results
Only O(n) two-qubit physical interactions need be activated during each qRAM call, despite the device requiring O(2^n) quantum logic gates.
Takeaways & Limitations
The reduced number of active interactions could support large qRAMs operating without extensive quantum error correction.
Takeaways & Limitations
Fanout qRAMs face noise and decoherence problems as n grows, while bucket-brigade retrieval requires O(n^2) steps and remains subject to switching and environmental errors.
Abstract
from arXiv · showhide
A random access memory, or RAM, is a device that, when interrogated, returns the content of a memory location in a memory array. A quantum RAM, or qRAM, allows one to access superpositions of memory sites, which may contain either quantum or classical information. RAMs and qRAMs with n-bit addresses can access 2^n memory sites. Any design for a RAM or qRAM then requires O(2^n) two-bit logic gates. At first sight this requirement might seem to make large scale quantum versions of such devices impractical, due to the difficulty of constructing and operating coherent devices with large numbers of quantum logic gates. Here we analyze two different RAM architectures (the conventional fanout and the "bucket brigade") and propose some proof-of-principle implementations which show that in principle only O(n) two-qubit physical interactions need take place during each qRAM call. That is, although a qRAM needs O(2^n) quantum logic gates, only O(n) need to be activated during a memory call. The resulting decrease in resources could give rise to the construction of large qRAMs that could operate without the need for extensive quantum error correction.
I. DESCRIPTION OF THE PROTOCOL
The paper contrasts fanout addressing, which simultaneously controls exponentially many switches, with bucket-brigade routing, which stores address bits in three-state elements and activates only the addressed route.
- Fanout architecture: The fanout scheme interprets each address bit as a direction at one binary-tree level, defining one of 2^n possible paths.The k’th address bit controls 2^k switches, so all tree nodes must be controlled even though only n lie on the selected path.
- Fanout architecture: The fanout architecture requires simultaneous control over 2^n −1 tree nodes, although only n switches directly participate in addressing one memory cell.This creates the central scaling drawback of conventional fanout routing.
- Reduced-activation design: The modified fanout circuit achieves memory addressing with activation of only O(n) transistors.This modification targets the excessive activation inherent in the conventional electronic implementation.
- Bucket-brigade architecture: The bucket-brigade replaces tree switches with trits that store 0, 1, or • and progressively carve the selected route as address bits arrive.A passive • trit adopts the incoming bit and subsequently routes signals along the corresponding branch.
A. Quantum RAM
The quantum protocols preserve coherence while comparing fanout and bucket-brigade architectures. The bucket-brigade reduces active control and can tolerate switching errors that scale inversely with address length, whereas fanout becomes vulnerable to decoherence as n grows.
- Quantum conversion: Quantum RAM implementations require reversible routing and preservation of quantum coherence, using a quantum bus that traverses the binary tree and couples to memory cells.The two architectures can both be converted into quantum RAM algorithms through reversible processes.
- Fanout qRAM: Fanout qRAM requires each index qubit to control 2^k bifurcations, creating a fragile macroscopic superposition prone to noise and decoherence as n increases.The paper identifies high-fanout control as a principal quantum implementation challenge.
- Hybrid architecture: A hybrid architecture trades the amount of coherent control against the number of quantum memory elements required.This provides an intermediate design between fanout and bucket-brigade implementations.
1. Fanout quantum RAM
The fanout qRAM uses a coherently routed quantum bus to translate binary addresses into bus positions and access memory cells in superposition. Reversing that translation removes address–bus entanglement before returning the result.
- Quantum routing: The fanout qRAM routes a quantum bus coherently through all 2^n binary-tree paths using unitary transformations controlled by the index qubits.The k’th index qubit controls 2^k bifurcations, paralleling the classical fanout architecture.
- Address translation: The n controlled transformations perform a binary-to-unary translation from the binary address in Q to the bus position.The bus position represents the path selected by the address register.
- Memory access: The bus locally interacts with each memory cell reached by the superposed paths and coherently copies its content into the bus’s internal degree of freedom.For one-bit memory cells, this copy is implemented by a single C-NOT gate.
- Uncomputation: Running the binary-to-unary translation backwards removes the correlation between the index register and bus position, leaving the bus qubit with the accessed memory value.Uncomputing restores the index register and disentangles it from the routing tree.
2. Bucket-brigade quantum RAM
The bucket-brigade qRAM uses qutrits as quantum switches that sequentially store address qubits, route a bus qubit to memory, and then reverses the process to restore the routing tree.
- Qutrits in states |0⟩ and |1⟩ route incoming qubits up or down, while |•⟩ stores an incoming qubit through a unitary swap operation.The qutrits’ first two levels store the incoming qubit state when the qutrit is in the wait state.
- The bus qubit reaches the addressed memory cell, whose state is coherently transferred into the bus, including superpositions of memory locations.
- Reflecting the bus through the tree uncomputes its position, after which U_s† recovers the address qubits and restores every qutrit to |•⟩.
- Although the tree contains O(2^n) qutrits, only n qutrits are active during any protocol run.
B. Generalizations
The qRAM architecture supports quantum memory contents, while geometric memory layouts can reduce the number of circuit elements without reducing addressable capacity.
- The qRAM schemes work when addressed memory cells contain purely quantum information, but no-cloning prevents copying that data into the output register.Instead, the protocol delocalizes the information originally contained in the memory cell.
- A bidimensional memory array divides the index register into row and column parts, reducing circuit elements while preserving the number of addressable memory cells.
- Equal-sized rows and columns reduce the number of necessary circuit elements to the square root of its original value.
- Three-dimensional arrays could reduce circuit elements further, but require more complex wiring and are not typically used.
II. PHYSICAL IMPLEMENTATIONS
The paper develops detailed physical qRAM designs that allow hybrid implementations, in which the quantum bus and memory cells may use different physical systems.
- The physical-implementation section constructs detailed qRAM designs while accounting for hybrid encodings of the bus and memory cells.Examples include photons for the bus and trapped atoms for memory elements.
A. Quantum optical implementation of the fanout qRAM
The optical fanout qRAM encodes address qubits in trapped atoms and maps them onto a photon’s spatial modes, which then interact with the corresponding memory cells.
- The index register is encoded in n trapped two-level atoms, while a single photon carries polarization information and is routed into 2^n spatial modes.
- The photon’s spatial mode is coherently correlated with successive address bits through repeated atom–photon C-NOT operations and polarization-to-path conversion.
- The optical design uses atomic levels in which |0⟩Qk does not interact with the photon, whereas |1⟩Qk interacts with the photon’s |±⟩ polarization states.
- After all n address bits are transferred, each spatial mode of the bus photon interacts with the first bit of its corresponding memory location.
- A kth address bit controls 2^k controlled-controlled-NOT gates but interacts with the bus qubit only once, making information-carrying interactions exponentially fewer than logical gates.
B. Phase gate implementation of the fanout qRAM
The fanout qRAM implementation uses controlled phase shifts across 2^n cavities so that only the address-selected cavity resonates, after which memory contents are extracted by superconducting qubits. The design has solid-state variants, but charge-noise coherence is a concern.
- Phase-gate routing: 2^n cavities encode the binary-tree implementation, with Q-register qubits inducing phase shifts so only the indexed cavity resonates.The resonance window must be on the order of π/2^n to distinguish cavities with similar phase shifts.
- Memory readout: Memory contents are extracted by coupling each cell to a cavity containing two superconducting qubits that store and emit the cell information.The two-qubit arrangement removes a feedback effect in the extraction process.
- Illustrative operation: In the illustrated case Q = |011⟩ addresses the fourth memory location, whose one makes only the corresponding path resonant.The figure marks that path with a thick dashed line.
- Solid-state realization: Single-electron transistors and Coulomb blockade provide one possible solid-state realization of the fanout circuit model.Index qubits can coherently tunnel charge onto control qubits that impose Coulomb blockade on switching-tree lines.
- Coherence constraint: Charge noise may rapidly decohere a charge fanout qRAM, whereas cavity coherence times can be microseconds rather than nanoseconds for charge qubits.The comparison concerns the cavity-based solid-state implementation described in detail.
C. Bucket-brigade implementation
The bucket-brigade qRAM stores address bits in qutrits distributed through a cavity-and-atom binary tree, routing later photons according to earlier stored bits. It returns the memory content on a bus qubit while re-emitting the address qubits, but requires O(n^2) sequential steps and low passive-state excitation errors.
- Address loading: Photons carrying Q-register qubits sequentially configure atomic qutrits in coupled cavities, storing each bit as |zero⟩ or |one⟩.The implementation uses polarization or time-bin photon encoding and Raman transitions for storage.
- Data retrieval: The memory cell’s content is transferred to the bus qubit while all Q-register qubits are re-emitted and available again.This is the stated end result of the coherent retrieval protocol.
- Address routing: Qutrit routing states couple later photons to up or down tree paths according to the previously stored address bits.The figure associates up levels with dashed arms and down levels with dotted arms.
- Protocol cost: O(n^2) sequential coupling steps are required to retrieve one of 2^n memories coherently.The implementation can use atoms coupled through photons or alternative solid-state artificial atoms with tunable coupling schemes.
- Error condition: Successful coherent calls require passive |•⟩ states to be excited rarely enough that the error rate stays significantly below 1/O(n^2).Otherwise signals may be routed along incorrect paths.
- Noise resilience: Only n qutrits are active in each component of a superposed address call, making such superpositions typically robust to noise and loss.This contrasts with the use of the full circuit across a superposition of many memory sites.
III. CONCLUSIONS
The paper proposes the bucket-brigade paradigm for reducing fanout in classical and quantum RAMs and discusses optical and solid-state implementations.
- Conclusion: The bucket-brigade paradigm reduces the degree of fanout required during a memory call in classical and quantum RAMs.The conclusion presents this as a new construction paradigm for both types of RAM.
- Conclusion: The proposed qRAM implementations use quantum optical and solid-state quantum information-processing techniques.These implementations are presented as possible ways to realize the bucket-brigade approach.