World's most popular travel blog for travel bloggers.

# Proving that quantum circuits not involving entanglement are inefficient

, ,
Problem Detail:

I heard in a video that it can be proven that quantum circuits not involving entanglement can be efficiently simulated on a classical computer; i.e., that there is no point to building quantum circuits not involving entanglement. I have heard this referenced elsewhere in google searches, but nowhere can I find this proof mentioned. What is the proof of this?

A general state of $n$ qubits can be written as follows :

$|\psi\rangle = \sum\limits_{x=0}^{2^{n-1}}\alpha_x|x\rangle$

Which means you need $2^n$ complex numbers to describe an arbitrary state of $n$ qubits.

A non entangled state on $n$ qubits can be written in the following way:

$|\psi\rangle = \bigotimes\limits_{i=1}^{n}\left(\alpha_i|0\rangle + \beta_i|1\rangle\right)$

Which means we only need $2n$ complex numbers to describe it. If we assume that we only deal with circuits such that two different qubits are never entangled, this property holds throughout the entire computation.

This is enough to see how to simulate the circuit, always remember the $2n$ complexes describing your non entangled state, and apply the desired operators on specific qubits (remember that it is garunteed that applying cnot will not result in entanglement).

That said, don't take this as evidence to the fact that quantum computing without entanglement doesn't extend classical computation in any way. For example, see this paper (Quantum computation without entanglement, Eli Biham et al). They reproduce some known results in the blackbox model (which are impossible on a classical computer) without entanglement.