Q-means, QRAM and how it helps algorithmic speedup

I am trying to understand how QRAM will help improve algorithm performance. I am reading a paper on Q-means classification, but I have noticed that some other algorithms (Grovers) seem to have a dependence on QRAM as well

For some algorithms, does then the speed-up only come from using QRAM - that it has some property where it allows lookup of data very fast? Is this the case?

• changed the question now Feb 18 '21 at 11:38

Partial answer (why qRAM is useful)

Currently, quantum computers do not have an operational memory. Quantum processor is composed of qubits which can be considered to be an elementary memory. However, they are rather used for performing calculations. There is no way how to save intermediate results.

Of course, you can measure an output of the quantum processor and based on this measurement to re-program the processor and run an algorithm with this new input. However, to get complete information, you need to perform so-called quantum tomography. This method is exponentially complex, hence it erase any speed up gained by the quantum algorithm. Moreover, you need many copies of measured qubits, i.e. to run the algorithm with original setting many times. But in case of qRAM, you can simply save a qubit in the memory (it is not as simple as it sounds, you need to establish entanglement between saved qubit and the memory, move the qubit to the memory and uncompute qubit in the processor - sorry, this is rather crude description).

To conclude, not to have a quantum RAM and use classical register and measurement instead, could completely destroy advantage brought by some quantum algorithms.

• thank you! Is this the case for Grovers algorithm then, that it is possible to implement it without qRAM, but since you do not have it you are losing a lot of what makes it powerful? Feb 17 '21 at 19:17
• @Andrew: Fortunately in case of Grover you do not have to do quantum tomography as the result is always basis state. So, you can get the result in one measurement, then process it classically and reprogram the quantum processor. Hence, there is slight decrease in speed. My answer was general, as you can see there are specific situation when you do not need qRAM very much but still, it can improve Grover. Look also at this article: The Effective Solving of the Tasks from NP by a Quantum Computer by S. Sysoev. It shows how you can change quadratic speed up of Grover to exponential with qRAM Feb 18 '21 at 10:53
• I don't quite understand what you are saying here. I'd say quantum algorithms that are proven/believed to be efficient do not require tomography of the output to read the result; that would make them pointless, as you yourself observe. The trivial example being Shor's: you don't need to do tomography of the output to obtain the result. Still, I don't see how this aspect is related to the qRAM issue
– glS
Feb 18 '21 at 12:10
• @glS: I meant that there are algorithms working with loops, i.e. they uses output from one calculation as an input to next one. In this case you would need, in general, to know state of output qubits. Of course, in case of Grover, you do not need to do tomography because output is basis state and to do more iterations simply put several circuits in row. However, this can be simplified with qRAM. To conclude, I meant that there is a problem with storing intermediate results and if you need them and they are not basis states, you need qRAM to avoid tomography and using classical registers. Feb 18 '21 at 15:13
• @MartinVesely can you give some examples of the type of algorithms you are thinking about?
– glS
Feb 18 '21 at 15:15

I think the point is that many quantum algorithms prove/are believed to be efficient to process data when said data is encoded in a quantum state.

An easy example of this being Grover, which produces (with high probability yada yada yada) the state $$|x\rangle$$ corresponding to the $$x$$ such that $$f(x)=1$$ for some given "oracle function" $$f$$. But the catch is that, if you want to think of this as "finding which element of $$\{x_1,...,x_n\}\subset\mathbb R^n$$ satisfies $$f(x_i)=1$$", you need to include the process of preparing a quantum state of the form $$\sum_i |x_i\rangle$$ into your complexity calculations. This is essentially what qRAM proposals strive to do.

In other words, many of these "quantum machine learning algorithms" show/argue that you can efficiently obtain the wanted result by processing quantum states that encode a given set of classical data vectors. But this is quite different than saying that these algorithms allow you to process efficiently the classical datasets in the first place. You can make the two things (sort of) equivalent if you can show that using a "qRAM" you can always load classical data efficiently into a quantum memory, but, as far as I know, whether this is indeed possible/practical remains a murky point that is still actively investigated.