# What protocols have been proposed to implement quantum RAMs?

The crucial role of random access memories (RAMs) in the context of classical computation makes it natural to wonder how one can generalise such a concept to the quantum domain.

Arguably the most notable (and first?) work proposing an efficient QRAM architecture is Giovannetti et al. 2007. In this work it was shown that their "bucket brigate" approach allows access to the content of the memory with $\mathcal O(\log N)$ operations, where $N$ is the number of memory slots. This is an exponential improvement with respect to alternative approaches, which require $\mathcal O(N^{\alpha})$ operations. Implementing this architecture is however highly nontrivial from an experimental point of view.

Is the above the only known way to implement a QRAM? Or have there been other theoretical works in this direction? If so, how do they compare (pros and cons) with the Giovannetti et al. proposal?

The "bucket brigade" QRAM encodes in superposition $N$ $d$-dimensional vectors into $log(Nd)$ qubits using $𝒪(log(Nd))$ time. An alternative scheme with polynomial time reduction was proposed in this paper. In either case, the number of physical resources used is is exponential with the number of qubits. This could cause problems that limit the implementation and/or usefulness of the scheme.