Philosophy of Science 74 (3):347-363 (2007)

Authors
Amit Hagar
Indiana University, Bloomington
Abstract
A recent attempt to compute a (recursion‐theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion‐theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1086/521969
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 51,591
Through your library

References found in this work BETA

Hypercomputation.B. Jack Copeland - 2002 - Minds and Machines 12 (4):461-502.
Quantum Speed-Up of Computations.Itamar Pitowsky - 2002 - Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
Super Turing-Machines.Jack Copeland - 1998 - Complexity 4 (1):30-32.

View all 9 references / Add more references

Citations of this work BETA

Computation in Physical Systems.Gualtiero Piccinini - 2010 - Stanford Encyclopedia of Philosophy.
The Physical Church-Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
On the Significance of the Gottesman–Knill Theorem.Michael E. Cuffaro - 2017 - British Journal for the Philosophy of Science 68 (1):91-121.

View all 9 citations / Add more citations

Similar books and articles

Many Worlds, the Cluster-State Quantum Computer, and the Problem of the Preferred Basis.Michael E. Cuffaro - 2012 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 43 (1):35-42.
Quantum Hypercomputability?Amit Hagar & Alexandre Korolev - 2006 - Minds and Machines 16 (1):87-93.
Quantum Hypercomputation.Tien D. Kieu - 2002 - Minds and Machines 12 (4):541-561.
Quantum Mechanics and Computation.Bart D’Hooghe & Jaroslaw Pykacz - 2004 - Foundations of Science 9 (4):387-404.
A Quantum Computer Only Needs One Universe.A. M. Steane - 2003 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 34 (3):469-478.
Quantum Computation in Brain Microtubules.Stuart R. Hameroff - 2002 - Physical Review E 65 (6):1869--1896.
Quantum Computing.Amit Hagar & Michael Cuffaro - 2019 - Stanford Encyclopedia of Philosophy.
Quantum Algorithms: Philosophical Lessons.Amit Hagar - 2007 - Minds and Machines 17 (2):233-247.
Computation and Hypercomputation.Mike Stannett - 2003 - Minds and Machines 13 (1):115-153.

Analytics

Added to PP index
2009-01-28

Total views
98 ( #93,694 of 2,331,168 )

Recent downloads (6 months)
2 ( #397,056 of 2,331,168 )

How can I increase my downloads?

Downloads

My notes