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.
5 comments
[ 16.0 ms ] story [ 39.7 ms ] threadWhat will it get us in the short and long term?
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).