# Measuring the speed of Grover's Algorithm

I'm interested in analyzing how long Grover's algorithm takes as the number of qubits increases. I've been simulating it in IBMs quantum computer but when I asked the same question I got this response: https://quantumexperience.ng.bluemix.net/qstage/#/community/question?questionId=71b344418d724f8ec1088bafc75eb334

So that doesn't seem too useful. Is there anyway I could simulate this and gather my own data in other simulators?

Thank you!

• It would help if you expanded on the context of your question. Is it about worst-case complexity? What do you consider a number of minimal steps? Is your question about the particular implementation on the IBM processor? If this does not help, can you give us a description of what kind of plot you would like to make? – Juan Bermejo Vega Nov 9 '16 at 22:52

This happens approximately when the number of gates is $\sim \sqrt{N}$ where $N$ is the size of the domain of search for the algorithm. It is why it is said that asymptotic runtime complexity of Grover's algorithm is $O(\sqrt{N})$, which offers a quadratic quantum speed-up when compared to the classical algorithm with runtime complexity $O(N)$.
So answering your question - if you want to play around with the algorithm, you should try different numbers of Grover diffusion gates $k$ somewhere from $k = 1$ up to $k = N$. The runtime cost of the algorithm is proportional to $k$, whereas the IBM simulator (or any other) will calculate the probability of obtaining the correct answer for you. This way you can see which $k$ is best. As mentioned earlier, this is expected to grow as $k_{\text{best}} \sim \sqrt{N}$.