What is the purpose of a quantum RAM in quantum algorithms?

Question

I see many papers (e.g. Quantum principal component analysis) in which the existence of qRAM is necessary. What's the actual purpose of qRAM in quantum algorithms?

Answer 1

This is discussed in chapter 5 of Ciliberto et al..

The purpose of most quantum(-enhanced) machine learning algorithms is to speed-up the processing of classical data over what is possible with classical machine learning algorithms. In other words, the context is that you have a set of classical vectors $\{\boldsymbol x_k\}_k$, and you want to compute some function $\boldsymbol f(\boldsymbol x_k)$ of this data (which may then be used as an estimator of some property, or as a function characterising a classifier to be used for new data points, or something else). Most quantum machine learning algorithms tell you that, provided you are able to efficiently perform the mapping $$\{\boldsymbol x_k\}_k\mapsto\lvert \{\boldsymbol x_k\}\rangle= N\sum_{kj} x_{kj}\lvert k,j\rangle,$$ then it is sometimes possible to compute $\boldsymbol f(\{\boldsymbol x_k\})$ more efficiently. It is, however, highly nontrivial how to perform such mapping efficiently.

To maintain the potential exponential speed-ups of the quantum algorithms, this conversion needs to be efficient. If this is not the case, then one ends up in a situation in which the quantum algorithm can solve the problem very efficiently, but only after a lengthy preprocessing of the data has been performed, therefore killing the whole point of using the quantum algorithm.

This is where QRAMs come into play. A QRAM is a device that can (theoretically) encode $N$ $d$-dimensional classical vectors into (the amplitudes of) a quantum state of $\log(Nd)$ qubits, in time $\mathcal O(\log(Nd))$. As discussed in Ciliberto et al., as well as in this related answer, the actual feasibility of QRAMs is still not entirely clear, and many caveats remain.