Quantum computing Grover's Algorithm

Question

Question:-

How much does exploiting quantum computing actually speed up computing? (We know that it hassome effect, because of Grover’s algorithm, but how much? Does BQP=P?)

What I know

I understand Grover's Algorithm but solving this question seems to be a tough.

Source of Grover's Algorithm:-

https://en.m.wikipedia.org/wiki/Grover%27s_algorithm

Is there any way to solve this?

Answer 1

Well, using a classical naive search algorithm where you look at one entry after the other in a register, it would take on average N/2 calls before you find the result you are looking for. Grover's algorithm would, assuming you have a register of all entries in a superposition state already prepared, only take square root of N calls on average. For large registers, this is a huge gain.

What the story doesn't tell is that the preparation of the register is costly. Everytime you call Grover's algorithm, you "consume" the entire register. Therefore, Grover's algorithm's real cost would be square root of N * (cost of preparation of the register). Sadly, the preparation of the quantum register (superposition of state of all entries in the register) scales with N. Therefore, Grover's algorithm might not provide an actual gain to the classical search algorithm!

It remains to be seen if there are efficient ways to prepare the quantum register. If one could find a O(sqrt(N)) way to prepare it, it would, at the very least, be as efficient as the classical search algorithm.

Answer 2

The observations by @Exeko on the computational cost of Grover's algorithm based Search Operations is quite valid and important concern when it is implemented out of the box. However, the cost of preparation and cost of information retrieval from the quantum register can be minimised by introducing a quantum bloom filter with verifiable random functions. Quantum Bloom Filter will help us to eliminate false positives in the register. Hence we don't need to consume the entire register every time. We have implemented Grover's algorithm in IBM Q last year with an additional Quantum Bloom Filter with a full adder circuit. This could help us to achieve quadratic speed-up in the end to end search performance.