On the Significance of the Gottesman-Knill Theorem

Cuffaro, Michael E. (2014): On the Significance of the Gottesman-Knill Theorem. In: The British Journal for the Philosophy of Science

Abstract

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.

• Item Type: Journal article
• Form of publication: Preprint
• Faculties: Philosophy, Philosophy of Science and Religious Science > Munich Center for Mathematical Philosophy (MCMP); Philosophy, Philosophy of Science and Religious Science > Munich Center for Mathematical Philosophy (MCMP) > Philosophy of Physics
• Subjects: 100 Philosophy and Psychology > 100 Philosophy
• ISSN: 1464-3537
• Language: English