4 ms·
> (But it solves them exponentially faster than a classical computer) do you mean literally exponentially? or do you mean "a lot" faster?
by statusquoantefa 7y ago
> (But it solves them exponentially faster than a classical computer)
do you mean literally exponentially? or do you mean "a lot" faster?
- smountjoy 7y agoThe difference in running time grows exponentially with the size of the input. I'd say that's "literally" exponential.
- cgearhart 7y agoLiterally exponentially. But keep in mind that QC does not mean you can solve _any_ problem exponentially faster than a binary computer. If something is NP-Complete (or any of the less familiar “hard problem” classes) then it’s still gonna be hard for the quantum computer. So you’ll get an exponential speed up for some specific problems like quantum circuit sampling, but it can’t help you solve the Traveling Salesman Problem any faster unless we find a new algorithm—and even then that would imply P=NP. There’s still lots that QC could bring to the table even if it only works for some problems, but it’s not expected to completely replace classical computers—more like augment them with some new super powers.
- primaryobjects 7y agoThe Traveling Salesman Problem is indeed a potential application of quantum computing. Grover’s Search could theoretically find a solution in quadratic time (sqrt(n!) versus n!). On a physical quantum computer, this would have profound impact to many different real-world applications.
- teraflop 7y agoGrover's algorithm provides a quadratic speedup, but sqrt(n!) is not quadratic time; it's super-exponential.