Quantum Computers Arent Turing Equivalent

They're not even NonDeterministicTuringMachine-equivalent. They're SupraTuring?. TienKieu? showed in 2002 that quantum computers can solve Turing-incomputable problems including the Halting Problem. See http://arxiv.org/abs/quant-ph/0110136 for details.

It should be noted that the conclusions of that paper have been challenged; go to the link for the paper above to read more.

Yes, and the challenge has been refuted. Looks like we're really through the looking glass on this one.

The abstract says

'[...] where quantum continuous variables and quantum adiabatic evolution are employed.'

This means, that it employs InfiniteNonDeterminism, which really is beyond TuringEquivalent, but I doubt, that 'quantum continuous variables' are physically possible.

-- GunnarZarncke


EditText of this page (last edited November 20, 2014) or FindPage with title or text search