August 31, 2007

Possible quantum computer limits

A discussion of possible limitations on the power of quantum and classical computers

It is a useful discussion of NP hard problems. My reaction to it is that even if his conjecture that we cannot globally solve NP hard problems is correct there is still commercial viability in improving and expanding the cases where we can solve some NP hard problems.

I think the question of commercial viability is how often does a system not get stuck in local minima. Are there usable probabilities when the optimal solution is found over sufficiently complex problems.

if the best alternative systems only come up with an optimal solution for N=4, and special cases of N=5. But the new system can fairly freqently get optimal solutions up to N=100 or less frequently N=10000 then that could be a commercial advance.

Nature's protein folding may not be perfect for solving the NP hard protein folding problem but it is sufficiently successful to allow life to form. A commercially useful solution capability.

Intriguingly, Farhi and his collaborators proved that, on some problem instances where classical simulated annealing would take exponential time, the quantum adiabatic algorithm takes only polynomial time.

we also know of problem instances where the adiabatic algorithm takes exponential time just as simulated annealing does. So while this is still an active research area, right now the adiabatic algorithm does not look like a magic bullet for solving NP-complete problems.

If quantum computers can’t solve NP-complete problems in polynomial time, it raises an extremely interesting question: is there any physical means to solve NP-complete problems in polynomial time?

Are those problem instances sufficiently useful and widespread for commercial usefulness ? Google is not perfect for internet search, but it is commercially successful for the range of instances where it does provide solutions.