(Computational chemistry may be intractable, even with approximations, on classical hardware—but what about if one has a quantum computer with a few hundred qubits, enough that one can do quantum simulation?) The importance of constant factors is one of the major traps in practical use of complexity classes: a fancy algorithm with a superior complexity class may easily be defeated by a simpler algorithm with worse complexity but faster implementation.
This example contradicts the point he’s trying to make here. Quantum computers are thought to be asymptomatically faster at some tasks (including quantum simulation) but have much, much worse constant factors for individual operations.
This example contradicts the point he’s trying to make here. Quantum computers are thought to be asymptomatically faster at some tasks (including quantum simulation) but have much, much worse constant factors for individual operations.