PhilSci Archive

Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup

Cuffaro, Michael (2011) Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup. [Preprint]

WarningThere is a more recent version of this item available.
PDF (Draft: comments welcome.) - Draft Version
Download (341Kb) | Preview


    Of the many and varied applications of quantum information theory, perhaps the most fascinating is the sub-field of quantum computation. In this sub-field, computational algorithms are designed which utilise the resources available in quantum systems in order to compute solutions to computational problems with, in some cases, exponentially fewer resources than any known classical algorithm. While the fact of quantum computational speedup is almost beyond doubt, the source of quantum speedup is still a matter of debate. In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Cleve et al.'s solution to Deutsch's problem, Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill & Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.

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

    Item Type: Preprint
    Keywords: quantum computation; quantum speedup; quantum information; entanglement; DQC1; mixed state; explanation
    Subjects: Specific Sciences > Computation/Information > Quantum
    Specific Sciences > Physics > Quantum Mechanics
    Depositing User: Dr. Michael Cuffaro
    Date Deposited: 04 Feb 2012 08:27
    Last Modified: 04 Feb 2012 08:27
    Item ID: 9008

    Available Versions of this Item

    Actions (login required)

    View Item

    Document Downloads