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 :

\begin{equation} \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 \end{equation}

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 :

\begin{equation}\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} \end{equation}

If qubits are entangled : \begin{equation}\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} \end{equation} 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 : \begin{equation} \bigoplus_{i=1}^n SU(2) \end{equation}

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 ?

  • 1
    $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Commented Jul 24, 2023 at 11:42
  • 1
    $\begingroup$ 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$. $\endgroup$
    – glS
    Commented Jul 24, 2023 at 15:58
  • $\begingroup$ 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 ? $\endgroup$
    – deb2014
    Commented Jul 26, 2023 at 9:00

1 Answer 1


If you stick to pure states, the existence of entanglement at some point in the dynamics is an obvious necessary requirement to do anything useful. This is however not as useful as statement as it might seem. For pure states, the only way to not have entanglement is if the qubits are completely uncorrelated, in which case it's quite obvious nothing interesting can happen.

At the same time, presence of entanglement also doesn't guarantee anything. You can have highly entangled states and still the system being efficiently simulatable classically (eg stabiliser circuits).

You can make more quantitative statements, but which ones are interesting depends strongly on the context. For example, formalisms such as tensor networks can be used to argue that small degrees of entanglement are also relatively easy to simulate, in a more quantitative way. But the fact remains that not being able to simulate things efficiently via tensor networks is far from being evidence of there not being another way to efficiently simulate the system.

  • $\begingroup$ I like your focus on pure states. I might ask it as a separate question, but would tensor networks work to simulate mixed-state DQC1 circuits, or can DQC1 simulation even fit into the tensor-network formalism? $\endgroup$ Commented Jul 25, 2023 at 14:35
  • $\begingroup$ I'm not sure tbh. I don't know much about DQC1 models $\endgroup$
    – glS
    Commented Jul 25, 2023 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.