PhilSci Archive

On the Significance of the Gottesman-Knill Theorem

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

WarningThere is a more recent version of this item available.
[img] 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:
CreatorsEmailORCID
Cuffaro, Michael E.mike@michaelcuffaro.com
Additional Information: Forthcoming in the British Journal for the Philosophy of Science.
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: 04 Jul 2015 13:33
Last Modified: 04 Jul 2015 13:33
Item ID: 11542
DOI or Unique Handle: 10.1093/bjps/axv016
Subjects: Specific Sciences > Computation/Information > Quantum
Specific Sciences > Physics > Quantum Mechanics
Date: 5 April 2014
URI: http://philsci-archive.pitt.edu/id/eprint/11542

Available Versions of this Item

Monthly Views for the past 3 years

Monthly Downloads for the past 3 years

Plum Analytics

Altmetric.com

Actions (login required)

View Item View Item