What surprises me, is that every algorithm listed here is faster (has a smaller time complexity) than its classical counterpart. Is this why “quantum computing is faster” is a common belief?
The point is: the only reason people care about quantum algorithms is because they are faster. That's what makes quantum computers interesting.
Of course you can build quantum algorithms that are slower. Maybe there are some obscure cases where this gives deeper insights into understanding quantum computing. But overall they're just not interesting, so they won't end up in such a list.
> 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.
They are faster because the type of operations that they can perform puts them in other complexity classes.
In particular, it is possible for a quantum computer to use entanglement for storing the "same variable" at multiple locations at once. Measurement can also be used for driving computation, by limiting the possible state-space of variables that are entangled to the one that you observe. That way you gain access to methods of computation that are not available for classical machines.
See "EPR-pairs" and "measurement" for more details. (Use wikipedia, for example.)
