Re: What's the application?
Your understanding is incorrect.
Relatively few problems have known efficient solutions with a quantum computer, but that isn’t the same at all.
The key point is that a QC can execute at least one NP-hard problem in polynomial time. There is a theorem similar to the Turing computability theorem for Turing machines that shows that *any* NP problem is solvable in polynomial time if you can solve any other one. Almost all “interesting” hard problems are known to be NP complete.
However.....
A) The proof is not constructive, it just says it can be done
B) Those that have been found often still have nasty complexities. O(N43) is still brutal even if it is polynomial
In the example of ECC you gave, you are exchanging the current situation where (almost) all mathematicians are very sure there is no way to do it because it is proved NP hard (but haven’t managed to prove NP NE P). For a situation where they all know it is possible (but haven’t yet had an incentive to work on it because the first assumption isn’t met).
Biting the hand that feeds IT
