Do quantum algorithms and classical algorithms of the same complexity have the same time consumption?

Question

The classical computer field likes to use the complexity O(x) to represent the complexity of an algorithm. Is this concept applicable to quantum computers, if quantum algorithm A with the same complexity O is as fast as classical algorithm B? Or is there an additional discussion of the hardware elements?

Answer 1

Yes, complexity notation has the same meaning in quantum computation as it does in classical computation.

In particular, comparing a classical and a quantum algorithm for the same problem that are both $O(n)$, for example, has exactly the same interpretation as comparing two classical algorithms for the same problem that both have running times $O(n)$. In that case, the actual running time on a particular instance of the problem can be very different for several reasons:

• Just because two algorithms scales as $O(n)$, they can have very different running times, say $n$ or $10^{10}n$
• Complexity theory only talks about asymptotic behaviour. For a specific instance, you may not be in the asymptotic regime and so you know very little about the specific run time of that case.
• Complexity theory only talks about the worst-case scaling of a particular instance size. A specific instance may not be the worst case, and what is the worst case for one algorithm may not be the worst case for another.
• If the two algorithms run on different hardware, then the hardware may have different "clock rates" (or some equivalent measure of speed) that makes the absolute run time different. This is pretty much the same effect as my first point about different scaling coefficients.
• Note that there are also different computational methods for different hardware. These are usually deemed to be "equivalent" if there's a polynomial overhead in converting between them. That polynomial can also make a big difference to the running time.

All of that said, the only meaningful statement of being able to say two algorithms as "as fast" as each other is to look at the $O()$ scaling and see that they're the same. This is equally true for quantum versus classical comparisons.