[cgearhart]

Literally 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]

The 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]

Grover's algorithm provides a quadratic speedup, but sqrt(n!) is not quadratic time; it's super-exponential.