You are correct. That is a horrible explanation. And incomplete.
* The state of a qubit has two basis states. Arbitrary states are linear combinations (=superposition) of these basis states. Importantly, the coefficients in the linear combination can be positive or negative.
* The state of N qubits has 2^N basis states. poly(N) gate can put the state of the N qubits in which each of the 2^N basis states has a non-zero coefficient.
* In quantum algorithms, we play with the coefficients. Basically, certain problems (like factoring) have structure such that you can change the coefficients so that the ones corresponding to the correct answer have magnitude approximately 1, while other coefficients have magnitude 0. This is enabled by the fact that coefficients are positive and negative, and so by mixing them, you can cancel some out.
* When you measure the qubits, the random answer you get is proportional to the coefficients squared. Hence, with high probability you get the right answer.
Where does the speed up come from? When you put the state of N qubits in the linear combination of 2^N basis states, and run it through the problem, that is akin to computing all answers in parallel. Like for factoring, checking all possible divisors to see which ones work. But to extract the answer out in the way described above, you have to do additional processing. This only works for some problems, with the right structure.
> In quantum algorithms, we play with the coefficients.
Is it accurate to say, more simply (simplicity being a high priority here), that 'we play with the probabilities' of collapse to one basis state or to the other - thus skipping the need to explain linear combinations or coefficients?
Well, all the playing happens with the positive/negative coefficients. Without explaining that you can cancel them out with each other, it will not be clear how all-positive probabilities collapse to some basis states.
In fact, classical stochastic computational models have exactly this deficiency. You can't pump up probabilities of some unknown states. They can only tend towards a uniform mixture.
* The state of a qubit has two basis states. Arbitrary states are linear combinations (=superposition) of these basis states. Importantly, the coefficients in the linear combination can be positive or negative.
* The state of N qubits has 2^N basis states. poly(N) gate can put the state of the N qubits in which each of the 2^N basis states has a non-zero coefficient.
* In quantum algorithms, we play with the coefficients. Basically, certain problems (like factoring) have structure such that you can change the coefficients so that the ones corresponding to the correct answer have magnitude approximately 1, while other coefficients have magnitude 0. This is enabled by the fact that coefficients are positive and negative, and so by mixing them, you can cancel some out.
* When you measure the qubits, the random answer you get is proportional to the coefficients squared. Hence, with high probability you get the right answer.
Where does the speed up come from? When you put the state of N qubits in the linear combination of 2^N basis states, and run it through the problem, that is akin to computing all answers in parallel. Like for factoring, checking all possible divisors to see which ones work. But to extract the answer out in the way described above, you have to do additional processing. This only works for some problems, with the right structure.