Quantum speed-up of computations

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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1086/341843
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 30,133
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
21 Undecidability and Intractability in Theoretical Physics.Stephen Wolfram - 2013 - Emergence: Contemporary Readings in Philosophy and Science.
Laplace's Demon Consults an Oracle: The Computational Complexity of Prediction.I. Pitowsky - 1996 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 27 (2):161-180.

View all 7 references / Add more references

Citations of this work BETA
On the Significance of the Gottesman–Knill Theorem.MIchael E. Cuffaro - 2017 - British Journal for the Philosophy of Science 68 (1):91-121.
Quantum Algorithms: Philosophical Lessons.Amit Hagar - 2007 - Minds and Machines 17 (2):233-247.
The Physical Church-Turing Thesis: Modest or Bold?G. Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
Reconsidering No-Go Theorems From a Practical Perspective.Michael E. Cuffaro - forthcoming - British Journal for the Philosophy of Science:axw038.
Quantum Hypercomputation—Hype or Computation?Amit Hagar & Alex Korolev - 2007 - Philosophy of Science 74 (3):347-363.

Add more citations

Similar books and articles
Added to PP index
2009-01-28

Total downloads
70 ( #77,144 of 2,191,803 )

Recent downloads (6 months)
1 ( #290,783 of 2,191,803 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature