Quantum Random Access Memory Qram

Short answer: A quantum random access memory (QRAM) uses n qubits to address any quantum superposition of N = 2^n memory cells. Two 2008 papers propose a "bucket-brigade" design in which only about log N switches, or n two-qubit interactions, are activated per memory call instead of order N, which they argue could make large QRAMs more robust. These are architecture proposals from 2008, not built devices, and the whole memory still needs order N gates.

What a QRAM is

A 2008 Physical Review Letters paper defines a random access memory (RAM) as using n bits to address N = 2^n distinct memory cells, and a QRAM as using n qubits to address any quantum superposition of those cells. A 2008 Physical Review A paper adds that a QRAM allows access to superpositions of memory sites, which may hold quantum or classical information. Many quantum algorithms assume such loading of data, which is why the cost matters.

Why it looks expensive

The Physical Review A paper says that any design for a RAM or QRAM with n-bit addresses requires order 2^n two-bit logic gates. It says this might at first make large quantum versions impractical because of the difficulty of operating coherent devices with large numbers of quantum logic gates. The arXiv version of the first paper says conventional architectures with memory laid out in a d-dimensional lattice involve throwing order N^(1/d) switches to reach one of N slots, which it says translates into slow speed and high energy use for classical RAM and a high decoherence rate for QRAM. For that reason, it says, little attention had been paid to developing a QRAM.

The bucket-brigade idea

The first paper presents an architecture it calls bucket-brigade, which it says reduces the number of switches that must be thrown during a memory call from order N^(1/d) to order log N. It says this exponentially reduces the memory call requirements compared with conventional designs, gives a more robust QRAM algorithm because it needs entanglement among exponentially fewer gates, and leads to an exponential decrease in the power needed for addressing. It presents a quantum optical implementation, with a figure showing atomic level structures for a possible bucket-brigade realization. The authors add the qualification that, if the travel time of signals along the wires is neglected, the reduction is in running time at the information-theoretic level.

The follow-up analysis

The Physical Review A paper analyzes two architectures, the conventional fanout design and the bucket brigade, and proposes proof-of-principle implementations. It shows that in principle only order n two-qubit physical interactions need take place during each QRAM call. It stresses the distinction: although a QRAM needs order 2^n quantum logic gates, only order n need be activated during a call. The authors say the resulting decrease in resources could allow large QRAMs to operate without extensive quantum error correction. The word "could" matters, as this is a design argument and was not demonstrated.

What this does not tell you

These papers do not describe an operating QRAM, and they do not analyze the effect of noise on the full memory in detail in the text we reviewed. The total number of components still grows with the memory size. Whether QRAM can be built at scale remains an open engineering question that these sources do not settle.

FAQ

What is a QRAM?

A memory addressed by n qubits that can access a superposition of N = 2^n cells.

What is the bucket-brigade design?

An architecture in which only order log N switches are activated per call, instead of order N.

Does it reduce the total number of gates?

No. The 2008 Physical Review A paper says the memory still needs order 2^n gates, but only order n are activated in a call.

Has a QRAM been built?

These papers describe proposals and proof-of-principle implementations, not a working large-scale device.

Why does QRAM matter?

Quantum algorithms that need to load classical data assume fast access to superpositions of memory cells, so the access cost affects their usefulness.