Not space complexity this time.
Just want to know the limitations of its performance
1
-
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 BotJan 13, 2022 at 6:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
