factual

Shor's Algorithm Puts Factoring in BQP

Peter Shor's 1994 algorithm showed that factoring an n-digit number, the basis of most modern encryption, lies in BQP — solvable on a quantum computer in roughly N-squared operations — versus the best known classical algorithm (the number field sieve) which takes time growing exponentially in roughly the cube root of N; this exploits special structure from group theory, number theory and the Fourier transform, not mere parallel-universe trial of every divisor.

factualpending

Speaker

Scott Aaronson

Evidence Quote

“Shor showed that the factoring problem is in BQP... if you could build a quantum computer then you could factor an n-digit number using a number of elementary operations that only scales like N squared, roughly”

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...