What feature of a quantum algorithm makes it better than its classical counterpart? Are quantum computers faster than classical ones in all respects?
1$\begingroup$ Are you asking about "quantum algorithms" or quantum computers in general? If it's the latter, then the short answer is that "speed" of physical quantum computers are heavily implementation dependent (there's also the issue of noise and fault-tolerance). As of yet, none of them are "faster" (in any legitimate sense) than your typical smartphone. However, some quantum algorithms are (in theory) known to be faster than their classical counterparts. The reason for that isn't straightforward (for instance, there's a lengthy debate about whether entanglement causes any speedup at all). $\endgroup$– Sanchayan DuttaMay 20, 2019 at 8:36
$\begingroup$ Related: Is entanglement necessary for quantum computation?, If quantum speed-up is due to the wave-like nature of quantum mechanics, why not just use regular waves? & Simplest algorithm for intuitively demonstrating quantum speed-up?. $\endgroup$– Sanchayan DuttaMay 20, 2019 at 8:42
$\begingroup$ @SanchayanDutta. Thanks for the answer. I was asking about quantum computers, in general. By the way, are you getting paid for answering or monitoring questions on SE? $\endgroup$– Tobias FritznMay 20, 2019 at 8:45
3$\begingroup$ To summarize Niel's answer, it can be said that speedup of quantum algorithms is specifically due to destructive interference. To quote Aaronson "The goal in quantum computing is to choreograph a computation so that the amplitudes leading to wrong answers cancel each other out, while the amplitudes leading to right answers reinforce.". I'll later try to write a detailed answer to your question, but this is a topic I too find very interesting. Thanks for asking the question. $\endgroup$– Sanchayan DuttaMay 20, 2019 at 9:06
"What feature of a quantum algorithm makes it better than its classical counterpart?"
First, a classical algorithm can be thought of as a quantum algorithm that makes no use of quantum superpositions. Therefore a quantum algorithm can be at least as good as its classical counterpart. No classical algorithm can be "better" than quantum algorithms can do, because one example of a quantum algorithm is the classical algorithm itself.
What is a feature of quantum algorithms that make them better than classical algorithms? The feature of quantum entanglement and superposition, which allows us to answer the Deutsch-Jozsa problem with 1 query instead of $2^n$.
"Are quantum computers faster than classical ones in all respects?"
I believe we do not know much about "speed". We know that we can factor the number $n$ with $log^3(n)$ operations instead of $n$ operations, but how fast are those operations going to be? We only know the answer to this question for quantum computers that have < 10000 qubits, and these have not been able to factor numbers larger than about 7 digits. You can see in WolframAlpha that factoring any number with ~10 digits finishes instantly, so even if the IBM quantum computer is faster, it is insignificantly faster. We need millions of physical qubits (100s of logical qubits) to make a real comparison, and what that million-qubit architecture will look like (if it's even possible to make) is something we don't yet know. Maybe to make a device with a million qubits will come at the sacrifice of gate fidelities or gate speeds.
The answer is "no" quantum algorithms are not better in "all respects" because they are harder to implement physically!
I think the key issue here is interference from the elements in the superposition. If you do not have interference, you do not get any speedup, just a probabilistic classical algorithm.
The answers above say that interference, entanglement, and superposition are the reasons for a quantum computer being faster. While this is not wrong, it is not the full story either.
Stabiliser computation, which starts with a $|0...0\rangle$ basis state and then applies Clifford operations to it, before measuring it in the computational basis, heavily involves interference, entanglement and superposition, yet is efficiently classically simulable (this result is known as the Gottesman-Knill theorem). So those features are obviously not "the" reason quantum computers are better at certain tasks. They might be necessary features, but not sufficient.
So to get a true answer we would need to characterise some kind of property of resource that can be present in a quantum computer that is necessary for the computation to be faster. I think a good candidate for this is the negativity in a probability distribution. Using, for instance, a Wigner function, we can represent any quantum state as a `quasi-probability distribution', that is a probability distribution where probabilities are allowed to be negative. Quantum operations then become quasi-stochastic operations. There are classical simulation algorithms that can simulate a quantum computation using this quasi-stochastic representation of a quantum computation. Crucially, the speed of this simulation depends on how much negativity is present in the computation.
So we could equally well say that quantum computers are better than classical computers because they can deal with negative probabilities.
$\begingroup$ No amplitudes are something else again. Quasi-probabilities also allow you to describe mixed states, and so go beyond the pure quantum framework where amplitudes make sense. See for instance this paper: iopscience.iop.org/article/10.1088/1367-2630/14/11/113011/meta $\endgroup$– JohnSep 11, 2021 at 20:46