I am interested in reading data from a real database and I find qRAM has the effect of loading data: $\sum\phi\left|i\right>\left|0\right>\rightarrow\sum\phi\left|i\right>\left|d_i\right>$, where $\left|i\right>$ is the index of address and $\left|d_i\right>$ is the corresponding data at address i. I am wondering what the complexity of loading n input using qRAM is. I find some materials say the qRAM locates one memory cell in $\log n$ time, which means it takes $O(n\log n)$ time to access n memory cells. Also, some other materials say loading n data can be done in $O(\log n)$ time. I am confused about it. Besides, all materials I find only discuss the loading problem. Storing problem is not mentioned, so I am also wondering if we can modify a data in qRAM.
1 Answer
For reading classical data addressed by a quantum register, you want a "QROM circuit". QROM circuits work by building the data into the circuit being performed. A QROM circuit with $n$ address qubits and $m$ output bits costs at least $\Omega(\text{min}(\sqrt{m2^n}, 2^n))$ T gates to perform. See section III.C of https://arxiv.org/abs/1805.03662 or most of https://arxiv.org/abs/1812.00954 or Appendices A-C of https://arxiv.org/abs/1902.02134 .
If you want to be able to write data in addition to reading data, I believe the cost of reading and writing increases to $\Omega(m 2^n)$ T gates, and you will need to keep $m$ qubits around to store the written data. Basically the circuit would look like $O(m2^n)$ CSWAPs using the address bits to move each bit of the targeted data register to be at the memory register with index 0, working with the data at index 0, then using $O(m2^n)$ CSWAPs to move the data back.
