Stephen Paul King references:
> http://www.cs.auckland.ac.nz/~cristian/coinsQIP.pdf
whose abstract begins,
"Is there any hope for quantum computer to challenge the Turing barrier,
i.e., to solve an undecidable problem, to compute an uncomputable
function? According to Feynman's '82 argument, the answer is negative.
This paper re-opens the case: we will discuss solutions to a few simple
problems which suggest that quantum computing is theoretically capable
of computing uncomputable functions."
We discussed this article briefly in July. Calude relies on infinite
dimensional Hilbert space with the inputs prepared in an infinite
superposition. Without claiming to understand all the details, this
looks to me like it would require an infinite amount of work to prepare.
It is well known that under idealized classical Newtonian physics,
computations are possible that break the Turing barrier if you have
infinite precision in your inputs. Of course, we don't live in a
Newtonian universe. This new result has something of the same flavor,
applied to a quantum mechanical universe. It still relies on infinities.
When a finite quantum computer can break the Turing barrier, that will
prove something. But when your first step is to prepare an infinite
superposition, that has no applicability to the physical universe.
Hal Finney
Received on Mon Dec 30 2002 - 12:40:29 PST