Cuffaro, Michael E. (2014) On the Significance of the Gottesman-Knill Theorem. [Preprint]

PDF sufficiency_of_entanglement.pdf - Submitted Version Download (387kB)

Abstract

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.

---

Export/Citation:

EndNote | BibTeX | Dublin Core | ASCII/Text Citation (Chicago) | HTML Citation | OpenURL

Social Networking:

Share |

---

Item Type:	Preprint
Creators:	Creators Email ORCID Cuffaro, Michael E. mike@michaelcuffaro.com
Additional Information:	Published in the British Journal for the Philosophy of Science 68 (2017): 91-121.
Keywords:	Gottesman-Knill theorem Bell inequalities quantum speedup quantum computation entanglement hidden variables
Subjects:	Specific Sciences > Computation/Information > Quantum Specific Sciences > Physics > Quantum Mechanics
Depositing User:	Dr. Michael Cuffaro
Date Deposited:	03 Mar 2017 17:57
Last Modified:	03 Mar 2017 17:57
Item ID:	12869
DOI or Unique Handle:	10.1093/bjps/axv016
Subjects:	Specific Sciences > Computation/Information > Quantum Specific Sciences > Physics > Quantum Mechanics
Date:	5 April 2014
URI:	https://philsci-archive.pitt.edu/id/eprint/12869

Available Versions of this Item

• Is Entanglement Sufficient to Enable Quantum Speedup? (deposited 15 Sep 2012 14:40)
  • On the Significance of the Gottesman-Knill Theorem. (deposited 13 Aug 2013 12:38)
    • On the Significance of the Gottesman-Knill Theorem. (deposited 07 Apr 2014 13:58)
      • On the Significance of the Gottesman-Knill Theorem. (deposited 01 Nov 2014 14:09)
        • On the Significance of the Gottesman-Knill Theorem. (deposited 04 Jul 2015 13:33)
          • On the Significance of the Gottesman-Knill Theorem. (deposited 03 Mar 2017 17:57) [Currently Displayed]

Monthly Views for the past 3 years

Monthly Downloads for the past 3 years

Plum Analytics

Altmetric.com

Actions (login required)

View Item