Quantum speed-up of computations
Proceedings of the Philosophy of Science Association 2002 (3):S168-S177 (2002)
Abstract
1. The Physical Church-Turing Thesis. Physicists often interpret the Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system . . . No physically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time.DOI
10.1086/341843
My notes
Similar books and articles
Physical hypercomputation and the church–turing thesis.Oron Shagrir & Itamar Pitowsky - 2003 - Minds and Machines 13 (1):87-101.
SAD computers and two versions of the Church–Turing thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Turing-, human- and physical computability: An unasked question. [REVIEW]Eli Dresner - 2008 - Minds and Machines 18 (3):349-355.
Analytics
Added to PP
2009-01-28
Downloads
100 (#125,635)
6 months
1 (#451,971)
2009-01-28
Downloads
100 (#125,635)
6 months
1 (#451,971)
Historical graph of downloads
Citations of this work
Quantum Information Theory and the Foundations of Quantum Mechanics.Christopher Gordon Timpson - 2013 - Oxford University Press.
Quantum Information Theory & the Foundations of Quantum Mechanics.Christopher Gordon Timpson - 2004 - Oxford University Press.
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.
Hypercomputation and the Physical Church‐Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
References found in this work
On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Computers and Intractability. A Guide to the Theory of NP-Completeness.Michael R. Garey & David S. Johnson - 1983 - Journal of Symbolic Logic 48 (2):498-500.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes.John Earman & John D. Norton - 1993 - Philosophy of Science 60 (1):22-42.
Non-Turing Computers and Non-Turing Computability.Mark Hogarth - 1994 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:126-138.