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?

  • 1
    $\begingroup$ Hello, we prefer it if one post contains only one question. Also problems we will face will probably lead to dicussion/opinions and is therefore not the best question for Quantum Computing StackExchange. $\endgroup$ – MEE Apr 6 '18 at 13:51
  • $\begingroup$ @MEE replaced two questions with one. $\endgroup$ – Anton Karazeev Apr 6 '18 at 14:04
  • $\begingroup$ related to quantumcomputing.stackexchange.com/q/115/55 $\endgroup$ – glS Apr 6 '18 at 17:07

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.