Why is entanglement so important if it introduces dependent information?

Question

I still don't understand, why is entanglement such a crucial property of a quantum algorithm. If I understand it, it means that the information between different qubits is somehow correlated, which means redundant, at least in statistics.

Answer 1

Entanglement is more than just classical correlation, since it involves a level of correlation that does not exist at all in "classical" statistics.

If you consider a classical random process, like the flipping of a coin (in which "heads" is labeled by $|0\rangle$ and "tails" is labeled by $|1\rangle$), then spinning that coin can in many ways simulate a quantum superposition like $\left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right)$ since there's a 50%, or $|\frac{1}{\sqrt{2}}|^2$, probability of getting "heads" or "tails" (a quantum superposition can be more general than that, and even have imaginary numbers for the coefficients, but even then it's possible to model their current state using classical statistics).

Entanglement is more complicated than that, in a fundamental way. It means that if we have two systems which can each exist in states $|0\rangle$ or $|1\rangle$, then you cannot write the state as $|0\rangle|b\rangle$ or $|1\rangle|b\rangle$ for any state $|b\rangle$ even if $|b\rangle$ is in a superposition. This can be modelled by a classical computer, but in general, the cost would be exponential in the number of members in the entangled state.

Early in this website's life, I answered some similar questions:

• What's the difference between a set of qubits and a capacitor with a subdivided plate?
• If quantum speed-up is due to the wave-like nature of quantum mechanics, why not just use regular waves?