How Quantum Computers Will Correct Their Errors

quantamagazine.org

Anyone got the current elevator pitch for quantum computing?

What will it get us in the short and long term?

One thing we know almost for sure is that Quantum Computers would be exponentially faster than classical computers can be at simulating quantum mechanics.

Basically, with all known algorithms, a classical computer needs exponential time to simulate a quantum computer.

This is not yet a proven fact (P != BQP), and given the history of P!=NP, is not likely to be proven too soon.

There are also a few algorithms of more general interest, such as faster than O(n) search, surprisingly (Grover's algorithm, which has a high probability of finding the input that produces a given output of a given function after O(sqrt n) steps).

Just a minor extension to this answer: efficiently simulating quantum mechanics is of practical interest, given that much of chemistry, physics, and material science depends on working with numerical models of nature.

That's right. I hope this ushers in a new manufacturing high point for the US.

Reply on news.ycombinator.com