Architectures for a quantum random access memory

By Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone. 2008

303 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/9a37680ee0add761b4c9e2e2e8ad6b9fd2e19da9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Quantum machine learning: a classical perspective (2017, background): “The proponents of the QRAM [45,46] claim that only O(log(Nd)) components need to be active, while the others can be considered as ‘non-active’ and error-free.”
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, methodology): “A notable difference between this paper and most previous work on QRAM [63,66 – 68] is that we describe the cost of QROM in terms of a fault-tolerant cost model: the number of T gates performed and the number of ancilla qubits required.”
Challenges and opportunities in quantum optimization (2023, unknown): “Although concrete proposals to build QRAM exist 106,107 , a scalable fault-tolerant implementation is yet to be found 108–110 , making this at best a long-term prospect.”