What protocols have been proposed to implement quantum RAMs?

Question

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?

Answer 1

A good summary on the current state of QRAM (as of 2017) can be found in this paper, and a comparison of it with classical methods can be found in this talk. The Giovannetti type "bucket brigade" QRAM still seems to be the best that is known, although modifications exist. There are serious caveats to the use of any such QRAM, and no alternative that avoids these has yet been proposed (other than using massively parallelized classical computers).

The "bucket brigade" QRAM encodes in superposition $N$ $d$-dimensional vectors into $\log(Nd)$ qubits using $\mathcal{O}(\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.

The issue depends on how many components need to be active at once. Ideally, the number of active components needs only be linear with the number of qubits in the memory. However, actual implementations are usually far from ideal.

This paper, for example, looks at the effects of noise, and concludes that the need for error correction could remove any advantages of the small number of active components. The severity of this potential problem depends on what algorithm is being used by the quantum computer, and so how many times the QRAM must be queried. For a polynomial number of queries, full fault-tolerance could be avoided. But for superpolynomial queries, such as for Grover's search, full-tolerance seems to be needed.

As far as comparing to other possibilities goes, it has been argued that the exponential number of resources for the QRAM should be compared to a classical parallel architecture with an exponential number of processors. The quantum algorithm does not look so great with this comparison. As explained here, some algorithms for which we expect a quantum speedup are actually slower when this parallelism is taken into account.

Though not as general in scope, another proposal for putting classical data into superpositions was also proposed here and so deserves a mention.