Quantum Hypercomputation - Hype or Computation?
Hagar, Amit and Korolev, Alex (2007) Quantum Hypercomputation - Hype or Computation?.
Full text available as: |
Abstract
A recent attempt to compute a (recursion--theoretic) non--computable 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: | Quantum computing; Hypercomputation; Church-Turing Thesis; Computational complexity; Undecidability |
|---|---|
| Subjects: | Specific Sciences: Computation/Information: Quantum Specific Sciences: Computation/Information: Classical Specific Sciences: Computer Science Specific Sciences: Physics: Quantum Mechanics |
| ID Code: | 3180 |
| Deposited By: | Hagar, Amit |
| Deposited On: | 21 Febuary 2007 |
| Additional Information: | Forthcoming in Philosophy of Science |