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.

Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.

Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.

A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.