factual

Quantum computers won't efficiently solve NP-hard problems

There are fairly convincing arguments that quantum computers will not be able to efficiently find exact solutions to NP-hard problems like the traveling salesman problem; they can speed up exhaustive search only quadratically (square-root of the classical time), which is far less spectacular than the super-polynomial, nearly exponential speed-up they provide for factoring.

factualpending

Speaker

John Preskill

Evidence Quote

“we have pretty convincing arguments that quantum computers will not be able to efficiently solve exactly the NP hard problems”

Source

153 | John Preskill on Quantum Computers and What They're Good For— Sean Carroll's Mindscape
Created: 6/13/2026, 12:07:35 AM

Your notes

Loading notes...