Today, please fasten your seat belts. We'll look at a paper from an Australian mathematician, Tien Kieu. Here is what he discovered.
Problems that used to be considered "unsolvable" or "incomputable" may be solved using the almost mystical properties of quantum mechanics.
Are you scratching your head? Wait, it's only the beginning.
Computability has long been defined by the so-called "Turing-Church Thesis," named for the 20th century's two giants of computer science and mathematical logic, Alonzo Church and Alan Turing, who essentially invented the modern-day computer.
"Problem solvability" has been equated ever since with "Turing computability." If a computer (Turing Machine) cannot solve a problem, the problem cannot be solved, and vice-versa -- if you have an insoluble problem, a computer will not be able to solve it!
"We dispute the Turing-Church thesis by showing that there exist computable functions -- computable by executing well-defined quantum mechanical procedures in a finite manner -- that are not Turing-computable," Kieu claims in a recent paper on the topic. In other words, Kieu claims to have discovered incomputable problems that are actually computable with the help of quantum mechanics.
Still with me?
Kieu's work may kill two mathematical birds with one stone by solving the tenth of David Hilbert's famous 23 mathematical problems, which happens to be equivalent to solving Turing's famous "halting problem."
In the year 1900, Hilbert asked for a way to decide whether any algebraic equation involving only whole numbers could be solved using an algorithm or program -- a set of well-defined rules executed in a finite number of steps. This was Hilbert's famous "tenth problem" (of 23).
Kieu believes he has solved both problems. With quantum mechanics, he says he can use a "quantum algorithm" to search through an infinite number of potential solutions to Hilbert's proposed equation and perform the search in a finite period of time.
If there is a solution, he will see it -- and since he has seen every possible solution, he will know whether the equation can be solved using his algorithm (Hilbert's problem), and he will know whether his "quantum computer" will halt, since it is done computing (Turing's problem).
You don't have enough? Tien Kieu's paper, "Quantum algorithm for the Hilbert's tenth problem," is just a click away.
Here is the abstract.
We propose a quantum algorithm for the classically non-computable Hilbert's tenth problem, which ultimately links to the Turing halting problem. Quantum continuous variables and quantum adiabatic evolution are employed for an implementation. Also discussed are a method for the time estimation for the adiabatic evolution, and a comparison with more the well-known quantum computation employing a finite number of qubits. Provided certain hamiltonian and its ground state can be physically constructed according to the algorithm, the notion of effective computability is extended beyond the Church-Turing thesis of classical computability.
Source: Mike Martin, NewsFactor Network, October 7, 2002
6:16:16 PM Permalink
|
|
