# Is entanglement necessary for quantum computation?

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?

• phys.org/news/2008-12-quantum-entanglement.html – Steven Sagona Jul 9 '18 at 6:50
• @StevenSagona That news article talks about the model DQC1. There is always entanglement in that model, it's just that a naive first analysis only looks for it in one particular place, where it turns out not to be. – DaftWullie Jul 9 '18 at 7:08
• Did you ask and answer this question because of my answer to: quantumcomputing.stackexchange.com/a/2601/2293 ? – user1271772 Jul 13 '18 at 11:55
• @user1271772 Nope! Although I did ask it because of something said to me as a comment that I needed a more complete response that I could reference. – DaftWullie Jul 13 '18 at 11:59
• @DaftWullie: I don't understand why my answer has 5 negative votes. Perhaps saying "entanglement is considered a requirement for QC" was not sufficient on it's own? – user1271772 Jul 13 '18 at 12:00

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.

• This work (arxiv.org/pdf/quant-ph/0301063.pdf) might be of interest here. Entanglement in a quantum system has to scale as a polynomial of system size to get an exponential quantum speed up. A quantum algorithm can be classically simulated with resources that scale as with the exponential of entanglement. – biryani Jul 9 '18 at 6:59
• although non-exponential speed-ups such as Grover can get away with tiny amounts of entanglement, my own work . – DaftWullie Jul 9 '18 at 7:10
• What do you think about this paper? I didn't have time to go through it carefully, but it states that Grover's can be done without entanglement (at slower speeds). – Steven Sagona Jan 28 at 23:50
• @StevenSagona It's a kind of cheat/sales pitch. Although we usually talk about $n$ qubits, with a Hilbert space of dimension $2^n$, you could get that Hilbert space by using a single particle with a Hilbert space of dimension $2^n$ (e.g. sending the particle down $2^n$ different paths), and there is certainly no entanglement present (actually, there's a philosophical question there re. path based superposition/entanglement). There are gate costs associated with this conversion, but by using an oracle model, as in Grover's, those costs get hidden and it appears to be achieving the same thing. – DaftWullie Jan 29 at 8:50
• Ah I see. Thanks for answering, this actually resolves some conceptual questions in my head (as it was not obvious to me why simply superpostion of a single particle is insufficient to provide the same mechanisms as these entangled systems). – Steven Sagona Jan 29 at 21:53