Why does entanglement complicate quantum simulation?

Question

To model a single qubit one would need enough memory for $2$ complex numbers. If we have an $N$ qubit system, we would have to store $2N$ complex numbers.

The general statement is that to store an $N$-qubit system, one would require memory for $2^N$ complex numbers. My understanding is that entanglement somehow transforms $2N$ into $2^N$ but I don't understand how.

So why do entangled systems require more memory than non-entangled ones?

Answer 1

Welcome to Quantum Computing StackExchange.

To see why it would require $2^n$ complex numbers instead of $2n$ to represent a general entangled $n$-qubit state, let's assume we have a 3-qubit system,

$(\alpha_1, \beta_1), (\alpha_2, \beta_2), (\alpha_3, \beta_3)$

Where $(\alpha_i, \beta_i)$ denotes the representation of the $i^{th}$ qubit in a classical computer memory.

If we apply $X$-gate on the first qubit the state will become,

$(\beta_1, \alpha_1), (\alpha_2, \beta_2), (\alpha_3, \beta_3)$

And if we apply $Z$-gate on the second qubit we will have,

$(\beta_1, \alpha_1), (\alpha_2, -\beta_2), (\alpha_3, \beta_3)$

As you can see, only $2n$ memory locations are sufficient.

Now, let's introduce entanglement. If we apply a $CNOT$-gate to the first two qubits, then we will not be able to write the state of each qubit separately. You can easily check that the state will become,

$(\beta_1\alpha_2, -\beta_1\beta_2, -\alpha_1\beta_2, \alpha_1\alpha_2), (\alpha_3, \beta_3)$

And if we then apply a $CNOT$-gate to the second two qubits the new state will be,

$(\beta_1\alpha_2\alpha_3, \beta_1\alpha_2\beta_3, -\beta_1\beta_2\beta_3, -\beta_1\beta_2\alpha_3, -\alpha_1\beta_2\alpha_3, -\alpha_1\beta_2\beta_3, \alpha_1\alpha_2\beta_3, \alpha_1\alpha_2\alpha_3)$

It is an $8$-dimensional vector which needs 8 (= $2^3$) complex numbers to represent it instead of 6 (= $2.3$) as it was before introducing any entanglement.