On the plausability of quantum RAM

Question

I'm fairly new to quantum computation and quantum complexity theory, but I came across some articles that suggest that quantum RAM (QRAM) is not very realistic assumption. For example some works show that even if we are willing to assume QRAM, the structure needed to implement it could also be exploited classically, preventing speedup, e.g., [1].

The reason why I was interested in QRAM is that I was wondering how fast one can compute the rank of an exponential size matrix (also if someone has any idea whether one can get any quantum speedup here I would be happy to hear!). However, the typical assumption for HHL-type algorithms seems to be that one can access the input implicitly, such as through a black-box that finds the nonzero entries in a given row of the matrix. Or sometimes it is assumed that the input is provided using QRAM.

Given this, is QRAM a self-consistent and interesting model of computation? Does it makes sense to even consider HHL-type algorithms with QRAM access?

Answer 1

To answer your question, a QRAM is a self-consistent and interesting model of quantum computation. It appears to be more powerful (up to a polynomial factor) than the usual circuit model of quantum computation, and studying it theoretically is not an unreasonable thing to do.

On the other hand, if you're looking at computing the rank of an exponential size matrix, you really can't assume the matrix is stored in the memory of a QRAM, because then, unless the matrix is sparse, you would need exponential-size quantum memory. But if you assume that the data is given through oracle access, then to make a fair comparison with classical machines, you have to give the classical machine a comparable oracle. This is what the paper you link to explores.

Finally, actually building a QRAM seems much harder experimentally than building a standard circuit-model quantum computer, because it seems very hard to physically implement indirect addressing.