Not space complexity this time.

Just want to know the limitations of its performance

  • 2
    $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Commented Jan 13, 2022 at 6:43

1 Answer 1


Time complexity in itself does not care how you solve the problem. If you have a solution on a classical machine that takes $O(n)$ and a quantum one that also takes $O(n)$ then both are equally good complexity-wise (practically: probably the classical one being cheaper, more pragmatic etc.)

If you have a solution that is $O(n^4)$ on a quantum or classical machine, it is theoretically decent (polynomial), but practically not very useful For relatively small inputs of size ~100k we'd need $10^{20}$ operations, which regardless of their speed will take thousands of years to complete.

Sometimes we see researchers excited that best known classical algorithm is exponential, but there is a quantum equivalent that gives good results with solid probability and complexity $O(n^4)$ or so. These are interesting from a research standpoint, and for some applications can make a big difference, but as a rule of thumb - they are not practically useable.


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