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