Quantum Speed-up of Computations
Bibliographic Data
| ID | 10706249 |
|---|---|
| Authors | Itamar Pitowsky (Hebrew University of Jerusalem, corresponding author) |
| Year | 2002 |
| Volume | 69 |
| Issue | S3 |
| Pages | S168-S177 |
| Publication date | 2002-09-01 |
| Peer Reviewed | Yes |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Philosophy of Science (JOURNAL) |
| Journal identifiers | ISSN: 0031-8248 • E-ISSN: 1539-767X |
| Publisher | Cambridge University Press (CUP) (PUBLISHER) |
| DOI | 10.1086/341843 |
| OpenAlex | W1991170403 |
| Language | EN |
| Citations received | 6 |
| References cited | 3 |
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...Nophysically 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. An even more extreme formulation of (more or less) the same thesis is due to Aharonov (1998): A probabilistic Turing machine can simulate any reasonable physical device in polynomial cost. She calls this The Modern Church Thesis. Aharonov refers here to probabilistic Turing machines that use random numbers in addition to the usual deterministic table of steps. It seems that such machines are capable to perform certain tasks faster than fully deterministic machines. The most famous randomized algorithm of that kind concerns the decision whether a given natural number is prime. A probabilistic algorithm that decides primality in a number of
Algorithm · Computation · Physics · Quantum · Quantum mechanics · Theoretical physics · Computer Science · Quantum Computing Algorithms and Architecture · Quantum Information and Cryptography · Quantum Mechanics and Applications
Quantum Hypercomputation—Hype or Computation
Information causality, the Tsirelson bound, and the ‘being-thus’ of things
The Physical Church–Turing Thesis
Hypercomputation and the Physical Church‐Turing Thesis
Reconsidering No-Go Theorems from a Practical Perspective
On the Significance of the Gottesman–Knill Theorem
| Unique citing works | 6 |
|---|---|
| Citations per year | 0,26 |
| Citation span | 2003 - 2020 (18) |
| Citation velocity | historical |
| Highly cited | No |
| Citation types | Neutral: 6 |