MilestoneTheory & algorithmsConfirmed

Researchers prove quantum computers cannot solve NP problems by brute force

Jan 1, 1997

Charles Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani prove that, for a search through a black box with no structure, no quantum algorithm can beat the square-root speedup of Grover's algorithm. Brute-force search over all possible answers stays exponentially slow.

Why it matters

It sets a limit on what quantum computers can do: they are not a shortcut through every hard problem, and large speedups need problems with structure to exploit.

Charles H. Bennett · Ethan Bernstein · Gilles Brassard · Umesh Vazirani · IBM · Université de Montréal · UC Berkeley

See it on the timeline

Related

• Lov Grover finds a quantum algorithm for faster unstructured search (May 1996)