1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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