According to the Gottesman–Knill theorem, quantum algorithms that utilize 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 article 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.
2The Gottesman–Knill Theorem
3The Significance of the Gottesman–Knill Theorem
4Classical Communication and Locally Causal Description
5Constraining Locally Causal Descriptions in the Practical Context of Inquiry
6The Sufficiency of Entanglement Thesis
Appendix ARecovering Statistics for Bipartite Entangled States Generated from Gottesman–Knill Operations
Appendix BRecovering Statistics of Pauli Measurements on the GHZ State