In

Fabric-of-Reality@yahoogroups.com, Bruno Marchal <marchal@...>

wrote:

> Indeed in this case quantum computer seems to be able to compute

> more quicky some class of function (but caution, this does not

> include the NP complete!

However, at least in theory it may be possible (if a quantum

computer has access to closed timelike curve qubits) to compute NP

complete problems in practice. Dave Bacon has written a paper that

says:

"Quantum computation with quantum data that can traverse closed

timelike curves represents a new physical model of computation. We

argue that a model of quantum computation in the presence of closed

timelike curves can be formulated which represents a valid

quantification of resources given the ability to construct compact

regions of closed timelike curves. The notion of self-consistent

evolution for quantum computers whose components follow closed

timelike curves, as pointed out by Deutsch [Phys. Rev. D 44, 3197

(1991)], implies that the evolution of the chronology respecting

components which interact with the closed timelike curve components

is nonlinear. We demonstrate that this nonlinearity can be used to

efficiently solve computational problems which are generally thought

to be intractable. In particular we demonstrate that a quantum

computer which has access to closed timelike curve qubits can solve

NP-complete problems with only a polynomial number of quantum gates."

Do closed timelike curves exist? Can they be harnessed? I don't

know. But if they do and if they can, then given some time, we may

figure out a way to do it.

You can find his paper here:

http://arxiv.org/PS_cache/quant-
ph/pdf/0309/0309189v3.pdf

Best regards,

Michael Bacon (no relation to Dave)