On the Significance of the Gottesman–Knill Theorem


Authors
Michael Cuffaro
Ludwig Maximilians Universität, München
Abstract
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 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.
Keywords Gottesman-Knill theorem  Bell inequalities  quantum speedup  quantum computation  entanglement  computational complexity
Categories (categorize this paper)
Reprint years 2013, 2014, 2017
DOI 10.1093/bjps/axv016
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 49,017
Through your library

References found in this work BETA

La Nouvelle Cuisine.J. S. Bell - 2004 - In Speakable and Unspeakable in Quantum Mechanics. Cambridge University Press. pp. 232--248.

View all 30 references / Add more references

Citations of this work BETA

What is Quantum Information?Olimpia Lombardi, Federico Holik & Leonardo Vanni - 2016 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 56:17-26.
Information Causality, the Tsirelson Bound, and the 'Being-Thus' of Things.Michael E. Cuffaro - forthcoming - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics.
Reconsidering No-Go Theorems From a Practical Perspective.Michael E. Cuffaro - 2018 - British Journal for the Philosophy of Science 69 (3):633-655.

Add more citations

Similar books and articles

On the Physical Explanation for Quantum Computational Speedup.Michael E. Cuffaro - 2013 - Dissertation, The University of Western Ontario
Reconsidering No-Go Theorems From a Practical Perspective.Michael E. Cuffaro - 2018 - British Journal for the Philosophy of Science 69 (3):633-655.
Quantum Communication Complexity.Gilles Brassard - 2003 - Foundations of Physics 33 (11):1593-1616.
Do We Really Understand Quantum Mechanics?Franck Laloë - 2012 - Cambridge University Press.
Modal Quantum Theory.Benjamin Schumacher & Michael D. Westmoreland - 2012 - Foundations of Physics 42 (7):918-925.
Quantum Teleportation.H. J. Kimble - 1999 - Vienna Circle Institute Yearbook 7:141-146.
Rotational Invariance and the Spin-Statistics Theorem.Paul O'Hara - 2003 - Foundations of Physics 33 (9):1349-1368.
Philosophical Implications of Bell's Theorem.Niall Shanks - 1987 - Dissertation, University of Alberta (Canada)

Analytics

Added to PP index
2014-01-16

Total views
150 ( #56,878 of 2,310,673 )

Recent downloads (6 months)
3 ( #351,016 of 2,310,673 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature