> Is [lower asymptotic time complexity] why “quantum computing is faster” is a common belief? Yes. Quantum computers are not faster classical computers, they a

> Is [lower asymptotic time complexity] why “quantum computing is faster” is a common belief? Yes. Quantum computers are not faster classical computers, they are a type of computer with access to a wider class of operations. The asymptotic advantage is needed in order to overcome the fact that quantum computers are actually slower (due to the overhead of error correction). The slowdown is not small, either. When I estimate the cost of error-correcting an AND gate under superposition I get numbers like 1 CPU millisecond. Bad enough that mere quadratic advantages may not be enough to overcome the constants in practice.