factual

Popular Writers Wrongly Conflate NP with BQP

The biggest mistake popular writers have made about quantum computers for 25 years is conflating NP with BQP — writing as if a quantum computer is a magical machine for solving all NP problems by trying each answer in a parallel universe — when in fact NP and BQP are believed to be incomparable, factoring was a lucky special case, and typical exponentially hard problems remain exponentially hard on a quantum computer.

factualpending

Speaker

Scott Aaronson

Evidence Quote

“the biggest mistake that popular writers make when they write about quantum computers, and this has been true for 25 years by now... is that they conflate NP with BQP”

Source

99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity— Sean Carroll's Mindscape
Created: 6/13/2026, 12:26:25 AM

Your notes

Loading notes...