Entanglement also allows multiple states to be acted on simultaneously, unlike classical bits that can only have one value at a time. Entanglement is a necessary ingredient of any quantum computation that cannot be done efficiently on a classical computer.
–"Qubit", Wikipedia
I thought this was the definition of superposition. Why is quantum entanglement so important in quantum computing, to the point where advances are also measured in number of qubits entangled?
Both of these terms depend on what basis you're in, which can make them a little arbitrary. For example, I think of a single particle in the state $\left|\uparrow\right> + \left|\downarrow\right>$ as in a superposition, though someone else who prefers the $\hat x$ basis may disagree and call it their eigenstate (we're both right). Similarly, entanglement is something we only understand if we work in the single-particle basis. There, we define an entangled state as a state that cannot be written as a product of single-particle states. By a single-particle state, I mean something that can be written as $\left|\psi\right>_1 \otimes \left|\psi \right>_2$ for two particles.
For example, $\left|\uparrow\right>_1 \left|\uparrow\right>_2$ is not entangled, since it's just the product of $\left|\uparrow\right>_1$ and $\left|\uparrow\right>_2$. This is a very correlated state, but it's not entangled. Here, I'm using the subscript to denote which particle. An example of a state that isn't entangled is:
$$ \left|\uparrow\right>_1 \left|\uparrow\right>_2 + \left|\uparrow\right>_1 \left|\downarrow\right>_2 + \left|\downarrow\right>_1 \left|\uparrow\right>_2 + \left|\downarrow\right>_1 \left|\downarrow\right>_2$$
this is because I can write it as:
$$(\left|\uparrow\right>_1 + \left|\downarrow\right>_1) \otimes (\left|\uparrow\right>_2 + \left|\downarrow\right>_2)$$
On the other hand, the following states are entangled:
$$ \left|\uparrow\right>_1 \left|\uparrow\right>_2 + \left|\uparrow\right>_1 \left|\downarrow\right>_2 + \left|\downarrow\right>_1 \left|\uparrow\right>_2 - \left|\downarrow\right>_1 \left|\downarrow\right>_2$$ $$ \left|\uparrow\right>_1 \left|\uparrow\right>_2 + \left|\downarrow\right>_1 \left|\downarrow\right>_2$$
The latter is known as a Bell state. You cannot write either of these states as a generic $\left|\psi\right>_1 \otimes \left|\psi \right>_2$: go ahead and try!
A more practical metric I use is: does the result of measuring the state of one particle change my expectation of the state of another? If yes, the particles must be entangled. (Warning: if the answer is no, it doesn't rule out entanglement! You might need a more clever experiment). For example, if I start with $\left|\uparrow\right>_1 \left|\downarrow\right>_2$, and I know I will measure that the second particle is $\downarrow$, regardless of what basis I measure the first particle in. However, if I start with the state $\left|\uparrow\right>_1 \left|\uparrow\right>_2 + \left|\downarrow\right>_1 \left|\downarrow\right>_2$, I have $50-50$ odds measuring that the second particle is $\uparrow$ or $\downarrow$. If I measure that the first particle is $\uparrow$, suddenly I know that I'll measure the second particle is $\uparrow$. I've learned something about the second particle only by measuring the first. A measurement on the first particle has changed the odds on the outcome of measuring the second, the hallmark of entanglement.
Side note: If a friend places two marbles in a bag, and promises that both are red or both are blue, you'd get a similar result as my second experiment. But this is not entanglement, that's just a classical lack of knowledge! My proposed experiment to measure entanglement of $\left|\uparrow\right>_1 \left|\uparrow\right>_2 + \left|\downarrow\right>_1 \left|\downarrow\right>_2$, by measuring each particle in the $\hat z$ basis is convincing only if you know that you started in a pure, quantum mechanical state. In reality you need a more clever experiment to show that you have an entangled state. Examples include Bell's inequality and the CHSH inequality.
An entangled state is essentially a superposition of states of different qubits, in such a way that they cannot be factored into a tensor product of individual states, such as the Bell state $$|\psi\rangle=\frac{1}{\sqrt{2}}\left(|00\rangle+|11\rangle\right).$$ In such a state both qubits are correlated in the specific sense that they exhibit non-classical correlations that can be used to break Bell inequalities inaccessible to states with correlations achievable under local operations and classical communication.
It is important to use entanglement - rather than superposition - as a resource in quantum computing, because if you only allow single-qubit superposition states then the computation can be efficiently simulated by a classical computer. More specifically, since you can write all single-qubit states as $$|\psi\rangle=\cos(\theta)|0\rangle+e^{i\phi}\sin(\theta)|1\rangle,$$ with two real parameters, you can change each qubit for $2n$ classical bits, to simulate the quantum computation to $n$-bit accuracy. This is a polynomial overhead and thus turns efficient computations into efficient computations.
It's important to note that entanglement need not be all there is to quantum computing as some non-entangled states can exhibit non-classical behaviour. This is one reason why quantum discord is being championed as a better figure of merit for the "nonclassicalness" of a state by some.
Generally superposition refers to a single particle having a combination ('superposition') of two states. For example, a photon having a combination of vertical and horizontal polarization.
Entanglement generally refers to different particles having correlated quantum states. For example, the spin of two (physically separated) electrons being antiparallel.
A qubit can exhibit both superposition and entanglement, which classical 'bits' do not.
Entanglement can be used as a tool in quantum computing, for example in 'superdense' coding---which is able to transport two bits of classical information via a single entangled qubit.
The best thing about qubits are that they can exist in superposition of multiple states. They can also do multiple things at the same time. But, to do complex calculations, they need to work together. Quantum Entanglement can be key to that. Research on "How" is still under progress. Just take a look at its feature: If you seperate two entangled qubits and destroy state superposition of one of qubits by Quantum Decoherence, the other fully isolated qubit will be alerted about this instantly (faster than light). The state superposition of other qubit will also be lost and end up with exactly opposite state of 1st qubit.
