Cowlix Wearing my mind on my sleeve

Saturday, March 09, 2002
Quantum computability

Computing the Noncomputable: Tien Kieu looks at the implications of quantum computation with regards to computability theory, in particular the halting problem. Are problems which are non-computable under traditional models solvable with quantum algorithms?

We explore in the framework of Quantum Computation the notion of computability, which holds a central position in Mathematics and Theoretical Computer Science. A quantum algorithm that exploits the quantum adiabatic processes is considered for the Hilbert's tenth problem, which is equivalent to the Turing halting problem and known to be mathematically noncomputable. Generalised quantum algorithms are also considered for some other mathematical noncomputables in the same and of different noncomputability classes. The key element of all these algorithms is the measurability of both the values of physical observables and of the quantum-mechanical probability distribution for these values. It is argued that computability, and thus the limits of Mathematics, ought to be determined not solely by Mathematics itself but also by physical principles.

Comments
Post a comment
Name:


Email Address:
 

URL:


Notes:
  • Name and email are required
  • Email will not be disclosed
  • HTML will be stripped
  • URLs will be linked
Comments:


Remember info?



March 2002
Sun Mon Tue Wed Thu Fri Sat
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
Line

Copyright © 2001-2002 by Wes Cowley
wcowley@cowlix.com