5
$\begingroup$

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?

$\endgroup$
2
  • 5
    $\begingroup$ I don't know what your question is. (1) Is QRAM a self-consistent and interesting model of computation? (2) Is somebody likely to build a QRAM machine in the next 30 years? Please clarify. $\endgroup$ Commented Jun 22, 2023 at 18:23
  • $\begingroup$ @PeterShor The former. I updated the question. Sorry for the confusion. $\endgroup$
    – terett
    Commented Jun 23, 2023 at 18:22

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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