Is entanglement necessary for quantum computation?

Question

Entanglement is often discussed as being one of the essential components that makes quantum different from classical. But is entanglement really necessary to achieve a speed-up in quantum computation?

Answer 1

Short answer: yes

One has to be a little bit more careful setting up the question. Thinking about a circuit as being composed of state preparation, unitaries, and measurements, it is always in principle possible to "hide" anything we want, such as entangling operations, inside the measurement. So, let us be precise. We want to start from a separable state of many qubits, and the final measurements should consist of single-qubit measurements. Does the computation have to transition through an entangled state at some point in the computation?

Pure states

Let's make the one further assumption that the initial state is a pure (product) state. In that case, the system must go through an entangled state. If it didn't, it is easy to simulate the computation on a classical computer because all you have to do is hold $n$ single-qubit pure states in memory, and update them one at a time as the computation proceeds.

One can even ask how much entanglement is necessary. Again, there are many different ways that entanglement can be moved around at different times. A good model that provides a reasonably fair measure of the entanglement present is measurement-based quantum computation. Here, we prepare some initial resource state, and it is single-qubit measurements that define the computation that happens. This lets us ask about the entanglement of the resource state. There has to be entanglement and, in some sense, it has to be at least "two-dimensional", it cannot just be the entanglement generated between nearest neighbours of a system on a line [ref]. Moreover, one can show that most states of $n$ qubits are too entangled to permit computation in this way.

Mixed states

The caveat in all that I've said so far is that we're talking about pure states. For example, we can easily simulate a non-entangling computation on pure product states. But what about mixed states? A mixed state is separable if it can be written in the form $$ \rho=\sum_{i=1}^Np_i\rho^{(1)}_i\otimes\rho^{(2)}_i\otimes\ldots\otimes\rho^{(n)}_i. $$ Importantly, there is no limit on the value $N$, the number of terms in the sum. If the number of terms in the sum is small, then by the previous argument, we can simulate the effects of a non-entangling circuit. But if the number of terms is large, then (to my knowledge) it remains an open question as to whether it can be classically simulated, or whether it can give enhanced computation.