  Entanglement has been shown to be necessary for pure state quantum
computation to have an advantage over classical computation. However, it
remains open whether entanglement is necessary for quantum computers that use
mixed states to also have an advantage. The one clean qubit model is a form of
quantum computer in which the input is the maximally mixed state plus one pure
qubit. Previous work has shown that there is a limited amount of entanglement
present in these computations, despite the fact that they can efficiently solve
some problems that are seemingly hard to solve classically. This casts doubt on
the notion that entanglement is necessary for quantum speedups. In this work we
show that entanglement is indeed crucial for efficient computation in this
model, because without it the one clean qubit model is efficiently classically
simulable.

Quantum Physics