3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Related quantumcomputing.stackexchange.com/questions/25676/… $\endgroup$ Commented Apr 1, 2022 at 5:20
  • $\begingroup$ 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. $\endgroup$
    – xzkxyz
    Commented Apr 1, 2022 at 6:53

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.