A New Kind of Science: The NKS Forum (http://forum.wolframscience.com/index.php)
- Pure NKS (http://forum.wolframscience.com/forumdisplay.php?forumid=3)
-- computational equivalence and quantum computing (http://forum.wolframscience.com/showthread.php?threadid=1083)

computational equivalence and quantum computing

Does quantum computing means an exception to the principle of computational equivalence ?

In the book I found this

http://www.wolframscience.com/nksonline/page-1058a-text

"Quantum computing (1980s): there is the potential for fundamental parallelism in computations."

Best wishes.

exponential to linear complexity

More precisely, a classical algorithm of exponential complexity should lead to a quantum algorithm of linear complexity.

Is this correct ?

Is this against the principe of computational equivalence ?

It just isn't correct. Leaving aside for a moment the fact that QC is almost purely theoretical at this point, QC does not do "more" computation per step or process unlimited amounts of information. There is no more information in a q-bit than in a classical bit - each answers exactly one yes or no question. There are just some sorts of questions that it is inefficient to ask classically, particularly about averages or ensembles, that in principle might be asked much more directly of q-bits.

You can in some cases directly access information about averages or correlations, that classically you'd have to sum over a large number of states to answer the same way. But you don't have the information a classical algorithm would use to get the answer. You get correlation information at the expense of level information, or average information at the expense of component information, etc. If that makes the particular bits you want more accessible great, it gives a speed up for those sorts of questions. It blurs out other bits, rendering them inaccessible. (You know an average without knowing the individual values of the things averaged, e.g.) But if those are things you don't care about, no problem.

A bubble sort algorithm doesn't use every possible pairwise comparison to order a list. It therefore gives a speed-up compared to inefficient comparison of all possible pairings, when you don't care about the value of every pairwise comparison. Limiting the questions asked to only the ones needed is the source of the speed up. Same thing happens with QC. The aspects of a system that can in principle be queried, include useful overall averages or other ensemble properties, correlations, and power spectra, which classically would require adding up lots of bits to deduce. QM allows bits of information about such questions to be found without the classically intervening details. (Indeed, it forces there to be a trade off between them, such that knowing one exactly implies not knowing the others).

That's the claim of careful QC advocates. Even that remains a theoretical and possible advantage at this point, not a realized one. There are a lot of uncareful QC claims in the world, though.