Cuffaro, Michael (2013) On the Necessity of Entanglement for the Explanation of Quantum Speedup. [Preprint]

Preview

PDF necessity_of_entanglement.pdf - Draft Version Download (369kB)

Abstract

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 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:

Share |

---

Item Type:	Preprint
Creators:	Creators Email ORCID Cuffaro, Michael mcuffaro@uwo.ca
Keywords:	quantum computation; quantum speedup; quantum information; entanglement; DQC1; mixed state; explanation
Subjects:	Specific Sciences > Computation/Information Specific Sciences > Physics > Quantum Mechanics
Depositing User:	Dr. Michael Cuffaro
Date Deposited:	29 Mar 2013 13:44
Last Modified:	02 Apr 2013 13:03
Item ID:	9654
Subjects:	Specific Sciences > Computation/Information Specific Sciences > Physics > Quantum Mechanics
Date:	6 March 2013
URI:	https://philsci-archive.pitt.edu/id/eprint/9654

Available Versions of this Item

• Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup. (deposited 07 Dec 2011 16:19)
  • Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup. (deposited 04 Feb 2012 13:27)
    • Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup. (deposited 07 Jun 2012 12:50)
      • Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup. (deposited 01 Oct 2012 02:42)
        • On the Necessity of Entanglement for the Explanation of Quantum Speedup. (deposited 29 Mar 2013 13:44) [Currently Displayed]

Monthly Views for the past 3 years

Monthly Downloads for the past 3 years

Plum Analytics

Actions (login required)

View Item