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

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?

• Apr 1, 2022 at 5:20
• It would be good to think carefully about what you mean by "time consumption". If you mean literally the clock time it takes to run two algorithms on the same input, they may not have the same time consumption even if they are two classical algorithms. Apr 1, 2022 at 6:53

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