Is there an example that would demonstrate the importance of both entanglement and superposition?
The usual "quantum parallelization" example, (e.g., from Nielsen and Chuang chapter 1) is probably a good one.
I will summarize below, with some embelishments.
One assumes a unitary $U_f$ exists that can implement a function $f$ that takes $n$ bits to one bit. The action on a state $|x\rangle_n|y\rangle$ is:
$$
U_f|x\rangle|y\rangle = |x\rangle_n |y \oplus f(x)\rangle\;.
$$
(Yawn, boring so far, right?)
OK, so now apply the same unitary $U_f$ to a superposition that is generated by hitting a single initial state $|0\rangle_n$ with a tensor product of n Hadamard gates (and leave the output state alone for now):
$$
U_f H^{\otimes n}|0\rangle_n|0\rangle = \frac{1}{\sqrt{2}^n}U_f\sum_{x=0}^{2^n-1}|x\rangle_n|0\rangle
$$
$$
=\frac{1}{\sqrt{2}^n}\sum_{x=0}^{2^n-1}|x\rangle_n|f(x)\rangle \;,
$$
where, (Wow!), I now have "magically" "evaluated" that function for every single one of it's inputs. That resulting state is generally entangled.
I just don't want to say "just trust me entanglement can be used to speed up computations"...
Yeah, please don't say that. It's not even wrong.
For example, our "magical" "evaluation" of all of the $2^n$ function inputs "in parallel" is mostly illusory. There is no way to extract that data as a single computation. We can only measure the state and the result of the measurement will be one of the many (x, f(x)), which only tells us anything about a single function evaluation.
