Peter Shor / The quantum algorithm
Can a quantum computer really be faster?
That time, that place
Even after the 1980s claim that imitating nature would need a machine running on quantum rules, the quantum computer remained an imaginary machine. Nice to have — but **for what?** Nobody had shown it could do anything an ordinary computer could not.
Why this question
Shor, a mathematician at Bell Labs, asked the question backwards: if qubits are good at something, what is it?
Qubits are good at two things. Bind several together and the possibilities grow 2, 4, 8 times over. And possibilities can meet and **cancel each other out.**
He found a problem that fit both exactly: splitting a big number into two primes multiplied together. 15 is 3 times 5 — easy. But a 300-digit number takes an ordinary computer longer than the age of the universe. To split it you must find a hidden 'repeating beat' inside the number, and beat-finding is just the sort of job where wrong candidates can be made to cancel.
What was found
In 1994 Shor proved it on paper: a large enough quantum computer could split even a 300-digit number **in hours.**
That problem happened to be the internet's lock. Nearly every code guarding banks, email and shopping rested on one fact — big numbers are hard to split. They were safe not because no key existed, but because making the key took the age of the universe.
Overnight, a story about an imaginary machine became a problem about locks.
Until then the quantum computer stopped at 'possible in principle'. With no evidence it could do what ordinary computers could not, neither money nor people gathered.
The proof was mathematics, but experiment soon followed. In 2001 a seven-qubit device factored 15 into 3 × 5 by Shor's method — a humble number, but the first confirmation that the paper method runs on real atoms.
Quantum computing moved from the margins to the centre. And meanwhile, with the machine not yet built, the world is already switching to new locks that even a quantum computer cannot open — changing the locks before the thief arrives.