2
$\begingroup$

Consider Grover's Algorithm, which identifies a specific $N$-bit string from the set of all $N$-bit strings. The string test function only has to be called $2^{\frac{N}{2}}$ times instead of $2^{N-1}$ times classically.

But in the QC case, there is overhead: a pre-processing step of applying a Hadamard gate $N$ times, and then for each function call, another Hadamard gate is needed in addition to an "Inversion about the mean" step.

The books I'm using never talk about these "overhead" steps. If they are considered, will it make the QC algorithm slower than the classical one?

$\endgroup$

1 Answer 1

2
$\begingroup$

The books never talk about the overhead introduced by the Hadamard gates because the speedup of Grover's search algorithm is defined specifically in terms of the number of calls to the oracle (the string test function in terms of the question). The cost of one oracle call is a lot more than the cost of applying the Hadamard gates before and after, so that cost is neglected.

If you want to get a more practical estimate of the complexity of Grover's algorithm, you have to take into account the detailed costs of implementing the oracle, which is also a lot more than the cost of the Hadamard gates.

I like the paper Is quantum search practical? by Viamontes, Markov, and Hayes for a good explanation of the things that need to be considered when comparing Grover's search to classical search algorithms.

$\endgroup$
2
  • $\begingroup$ Thank you for your reply. I think my question then becomes why is "calls to the oracle" the standard? Shouldn't all the other steps, like Hadamard gates, be accounted for too? If they are, is the algorithm still faster or more efficient than in a classical computer? $\endgroup$
    – itere79
    Commented Jan 13 at 19:13
  • $\begingroup$ Oracles are a standard for query complexity model, to describe algorithms that are not aware of the problem structure and access the problem only via an oracle. Implementing the oracle has vastly different complexity depending on the exact problem - finding an 1111 state is very different from solving a SAT problem or a realistic problem. In practice Grover is not considered efficient, once we take into account the cost of oracle implementation for a practical problem, the fact that quantum operations are slower than classical, and compare it to a better-than-black-box-serach classical algo $\endgroup$ Commented Jan 13 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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