Quantum Hypercomputation - Hype or Computation?

Publication Year:
Usage 900
Downloads 900
Repository URL:
Hagar, Amit; Korolev, Alex
preprint description
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.