  According to the Gottesman-Knill theorem, any quantum algorithm utilising
operations chosen exclusively from a particular restricted set are efficiently
simulable by a classical computer. Since some of these algorithms involve
entangled states, it is commonly concluded that entanglement is insufficient to
enable quantum speedup. As I explain, however, the operations belonging to this
set are precisely those which will never yield a violation of the Bell
inequalities. Thus it should be no surprise that entangled quantum states which
only undergo operations in this set are efficiently simulable classically. What
the Gottesman-Knill theorem shows us is that it is possible to use an entangled
state to less than its full potential. Nevertheless, there is a meaningful
sense in which entanglement is sufficient for quantum speedup: an entangled
quantum state provides sufficient physical resources to enable quantum speedup,
whether or not one elects to use these resources fully.
