Logo Logo
Switch Language to German
Cuffaro, Michael E. (2014): On the Significance of the Gottesman-Knill Theorem. In: The British Journal for the Philosophy of Science
Full text not available from 'Open Access LMU'.


According to the Gottesman-Knill theorem, quantum algorithms utilising operations chosen from a particular restricted set are efficiently simulable classically. Since some of these algorithms involve entangled states, it is commonly concluded that entanglement is insufficient to enable quantum computers to outperform classical computers. I argue, however, that what the Gottesman-Knill theorem shows us is only that if we limit ourselves to the Gottesman-Knill operations, we will not have used the entanglement provided to its full potential, for all of the Gottesman-Knill operations are such that their associated statistics (even when they involve entangled states) are reproducible in a local hidden variables theory that we would deem plausible in the context of a discussion of quantum computation.