PhilSci Archive

Is Entanglement Sufficient to Enable Quantum Speedup?

Cuffaro, Michael (2012) Is Entanglement Sufficient to Enable Quantum Speedup? [Preprint]

WarningThere is a more recent version of this item available.
sufficiency_of_entanglement.pdf - Draft Version

Download (99kB)


According to the Gottesman-Knill theorem, any quantum algorithm utilising operations chosen exclusively from a particular restricted set are efficiently simulable by a classical computer. Since some of these algorithms involve entangled states, it is commonly concluded that entanglement is insufficient to enable quantum speedup. As I explain, however, the operations belonging to this set are precisely those which will never yield a violation of the Bell inequalities. Thus it should be no surprise that entangled quantum states which only undergo operations in this set are efficiently simulable classically. What the Gottesman-Knill theorem shows us is that it is possible to use an entangled state to less than its full potential. Nevertheless, there is a meaningful sense in which entanglement is sufficient for quantum speedup: an entangled quantum state provides sufficient physical resources to enable quantum speedup, whether or not one elects to use these resources fully.

Export/Citation: EndNote | BibTeX | Dublin Core | ASCII/Text Citation (Chicago) | HTML Citation | OpenURL
Social Networking:
Share |

Item Type: Preprint
Keywords: quantum computation quantum speedup Gottesman-Knill theorem sufficiency of entanglement
Subjects: Specific Sciences > Computation/Information > Quantum
Specific Sciences > Physics > Quantum Mechanics
Depositing User: Dr. Michael Cuffaro
Date Deposited: 15 Sep 2012 14:40
Last Modified: 13 Aug 2013 12:38
Item ID: 9325

Available Versions of this Item

Monthly Views for the past 3 years

Monthly Downloads for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item