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.
PDF - Draft Version
Download (97Kb) | Preview


    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:

    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 10:40
    Last Modified: 13 Aug 2013 08:38
    Item ID: 9325

    Available Versions of this Item

    Actions (login required)

    View Item

    Document Downloads