<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-24T12:20:10.317Z
2023-06-24T12:26:22.633Z
2023-06-24T12:26:22.633Z
Peter Shor 
<p>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., <a href="https://arxiv.org/abs/1811.00414" rel="nofollow noreferrer">[1]</a>.</p>
<p>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.</p>
<p>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?</p>

CC BY-SA 4.0
2023-06-22T18:23:12.940Z
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.
Peter Shor 
CC BY-SA 4.0
2023-06-23T18:22:29.793Z
@PeterShor The former. I updated the question. Sorry for the confusion.
terett
<quantum-computing><linear-algebra>
On the plausability of quantum RAM
terett
# On the plausability of quantum RAM

(Asked by: username_0 on 2023-06-19)

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]](https://arxiv.org/abs/1811.00414).

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?

**Tags:** quantum-computing, linear-algebra

> **Comments:**
> **username_1**: 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.  
> **username_0**: @PeterShor The former. I updated the question. Sorry for the confusion.  

---

## 1 answers

### Answer by username_1 on 2023-06-24. Score: 5

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.


---

