  According to the Gottesman-Knill theorem, quantum algorithms which utilise
only the operations belonging to a certain restricted set are efficiently
simulable classically. Since some of the operations in this set generate
entangled states, it is commonly concluded that entanglement is insufficient to
enable quantum computers to outperform classical computers. I argue in this
paper that this conclusion is misleading. First, the statement of the theorem
(that the particular set of quantum operations in question can be simulated
using a classical computer) is, on reflection, already evident when we consider
Bell's and related inequalities in the context of a discussion of computational
machines. This, in turn, helps us to understand that the appropriate conclusion
to draw from the Gottesman-Knill theorem is not that entanglement is
insufficient to enable a quantum performance advantage, but rather that if we
limit ourselves to the operations referred to in the Gottesman-Knill theorem,
we will not have used the resources provided by an entangled quantum system to
their full potential.
