I think Xcelerate meant polynomial - which is an exponential improvement. It is not known but strongly believed that quantum computers cannot solve NP-complete

I think Xcelerate meant polynomial - which is an exponential improvement. It is not known but strongly believed that quantum computers cannot solve NP-complete problems. Be wary of anything that has "quantum computer" and "exponentially more powerful" in the same sentence. It is not yet know whether Quantum computers can simulate all physical systems - though probably better than even odds for - perhaps some exotic physics might underlie some systems (on the other hand it is not known if quantum computing is even needed at all for physical systems, though only a handful have this doubt). But QCs should be able to simulate many kinds of systems, and even before full quantum computers we might get useful systems that simulate particular classes of Hamiltonians. I don't know enough physics to grasp all the details but simulating a system involves preparing a state, evolving the Hamiltonian and reading out the result. Preparing the Hamiltonian can be done in time polynomial of the size of the system (I don't know anything more exact) and depending on the details of the system (local, sparse) and method in use, evolution can be as fast as linear in the size of the system (and though no general method allow sublinear calculation, particular hamiltonians could well admit such a speedup). And although, in general, non-sparse systems can't be simulated in polynomial time there should be methods that allow reductions/decomposition into simpler problems. There also other caveats: reading out the result requires a lot of sampling and error correction is a thorn. All these are why quantum computers are not some magical device - they're much too finickity, and to be preferred mainly as a last resort. They'll be pivotal for chemistry and to biochemists, pharmacology, material science and solid state physics (so better classical computers) but it seems hard to find any utility in general computer science. -- Even if the difficulty of general QC algorithms is from the failings of human intuition, that still suggests to me that methods like inductive or genetic or automatic programming will easily outperform humans.