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!

  • 1
    $\begingroup$ 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? $\endgroup$ – Juan Bermejo Vega Nov 9 '16 at 22:52

The runtime complexity is of course proportional to the number of Grover's diffusion operators in the quantum circuit.

As you probably know, quantum algorithms are probabilistic. You are free choose the number of Grover's operators, and thus the runtime of the algorithm. The more gates you put - the longer it takes to run, but the probability of obtaining the correct answer increases.

However, it only makes sense to add new gates until some point when the probability of obtaining correct answer increases so slightly that this benefit fails to cover the cost of adding +1 gate to the runtime.

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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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