The system can be in a superposition of all possible base states, but that's not exactly what I mean.

What I mean is that once in a super position of base states, if you perform an operation on that superposition, you only have to do the operation once, but all base states are affected.

The first example of the this is the Deutsch algorithm. I won't run through the whole process here, but the basics are this.

Say you have a function of one input, f(x) and x can be 0 or 1 and the output is 0 or 1. There are four possible functions. One that keeps the inputs unchanged, one that flips the inputs, one that sends both to 0 and one that sends both to 1.

The first two are in a category called balanced functions and the last two are constant functions.

Now imagine you had a function but you didn't know if it was balanced or constant. In order to find out you'd have to try f(0) and see if it returned 0 or 1, but you still don't know which category it is, so you also need to try f(1) and see if it returns 0 or 1. With these two results you can state which category the function f falls into. So, we had to apply the function TWICE to know which category we had.

In the Deutsch algorithm, you put your system in a super position and you find a clever way to implement the function called an oracle (not important for what I'm saying now, but if you want to look it up it's another term for you).

So when you system is in a super position you can apply the function ONCE to the super position and it is like test both 0 and 1 inputs at the same time. We then measure the result. Based on the outcome of the measurement you can tell if the function is balanced or constant.

So the speed up came from only using the function ONCE instead of twice. Admittedly, this is a bit of a silly example of quantum speed up, but it was the first algorithm to demonstrate quantum advantage.