# Why does entanglement complicate quantum simulation?

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?

• @glS you're right. edited, thank you! May 22 at 11:53

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.

• Thanks for the detailed answer, it illustrates the point perfectly. Edited the question to state 2^n instead of n^2. May 22 at 12:01
• You are welcome. I edited my answer to match your question after editing, May 22 at 12:09