# Understanding quantum computing power of entanglement

I read here that the power of quantum computing lies in the fact that the Hilbert space size of a $$n$$ qubits register grows exponentially with $$n$$, but only when entangled.

I would like to understand more quantitatively this.

Assume qubits are not entangled, the register state can be factorized :

$$$$\lvert\varphi\rangle = \bigotimes_{i=1}^n(c_0^i\lvert 0\rangle + c_1^i\lvert 1\rangle) = a_0\lvert 0\dots 0\rangle + a_1\lvert 0\dots 01\rangle + \dots + a_{2^{n-1}}\lvert 1\dots 1\rangle$$$$

If qubits are all entangled, one cannot go from right side to left side of equality.

If qubits are not entangled, the register can be described by $$2n$$ complex coefficients, but if they are all entangled, we need $$2^n$$ coefficients. But, whether or not qubits be entangled the size of the Hilbert space for the register is still $$2^n$$ because this is the number of fundamental (pure) states. So what does entangling concretely changes ? from a computational advantage point of view ?

Indeed, I also read there that applying an elementary gate on one qubit of the register updates as a whole all $$2^n$$ coefficients of the register.

For example, assume I apply an elementary Hadamard gate operation on qubit $$k$$. If qubits are not entangled :

$$$$\tag{1} \begin{split} H_k\lvert\varphi\rangle &= \bigotimes_{i=1}^{k-1}(c_0^i\lvert 0\rangle + c_1^i\lvert 1\rangle)\otimes [c_0^k\lvert +\rangle + c_1^k\lvert -\rangle]\otimes \bigotimes_{i=k+1}^n(c_0^i\lvert 0\rangle + c_1^i\lvert 1\rangle)\\ &= \bigotimes_{i=1}^{k-1}(c_0^i\lvert 0\rangle + c_1^i\lvert 1\rangle)\otimes \biggl[\frac{c_0^k+ c_1^k}{\sqrt{2}}\lvert 0\rangle+\frac{c_0^k- c_1^k}{\sqrt{2}}\lvert 1\rangle\biggr]\otimes \bigotimes_{i=k+1}^n(c_0^i\lvert 0\rangle + c_1^i\lvert 1\rangle)\qquad (1) \end{split}$$$$

If qubits are entangled : $$$$\tag{2} \begin{split} H_k\lvert\varphi\rangle & = a_0 H_k\lvert 0\dots 0\rangle + a_1 H_k\lvert 0\dots 01\rangle + \dots + a_{2^{n-1}}H_k\lvert 1\dots 1\rangle\\ &= \frac{a_0}{\sqrt{2}}\biggl[\lvert 0\dots 0\rangle + \lvert 0\dots 010\dots 0\rangle\biggr] + \dots +\frac{a_p}{\sqrt{2}}\biggl[\lvert 0\dots 0\rangle - \lvert 0\dots 010\dots 0\rangle\biggr]+ \dots\qquad (2) \end{split}$$$$ where $$p$$ is the index of the pure state $$\lvert 0\dots 010\dots 0\rangle$$ where qubit $$k$$ is equal to $$\lvert 1\rangle$$

From Eq. 2, one can see that indeed, a single gate operation actually changes all $$2^n$$ coefficients while on Eq. 1, one can afford to update only the 2 complex coefficients of qubit $$k$$. But again, developing the factorization of Eq. 1 would lead to $$2^n$$ coefficients that would similarly be updated.

So, what does entanglement really changes ?

Additionally, the single qubit dynamic space is $$SU(2)$$. For $$n$$ not entangled qubits, it will be : $$$$\bigoplus_{i=1}^n SU(2)$$$$

When qubits are entangled, the corresponding dynamic space will be $$SU(2^n)$$.

Are these spaces, $$SU(2)^{\oplus^n}$$ and $$SU(2^n)$$, equivalent ?

• To say that quantum computing's power comes from the scaling of the size of the Hilbert space is perhaps part of the story, but certainly not the entire story. In particular, if you were interested in probabilistic classical computation, you'd need to use an exponentially large vector of probabilities to track everything. And there is an equivalent of entanglement: correlation. Commented Jul 24, 2023 at 11:42
• note that $\mathbf{SU}(2)^{\oplus n}$ and $\mathbf{SU}(2^n)$ are extremely different. The former has dimension $n(2^2-1)=3n$, the latter has dimension $(2^n)^2-1=2^{2n}-1$.
– glS
Commented Jul 24, 2023 at 15:58
• Does it mean that the possibilities of transforming a register of entangled qubits are much more numerous than that of not entangled ones ? and consequently, that the number of entangled states are much more numerous than that of not entangled ones, in the Hilbert space ? Commented Jul 26, 2023 at 9:00