The “tries everything at once” myth
Lesson 10 of 23 in the course “Quantum”. Free, with animations and a quiz.
A myth even the media repeat
Almost every article says: “A quantum computer tries all options at once, so it’s billions of times faster.” It sounds logical after the superposition lesson, but it’s not true. If it were that simple, a quantum computer would instantly solve any problem. In reality it can cleverly cancel wrong answers, and only for problems with a special mathematical structure.
Why “all at once” is a trap
Physicist Scott Aaronson has explained it this way for years. Yes, you can create a superposition of all options. But measure it right away and you get one random option. And you could check a random option on a regular laptop. So you need a trick: arrange interference so the right answer gets amplified and the rest cancel. In 2016 Aaronson and cartoonist Zach Weinersmith made the SMBC comic “The Talk” about it, and physicists still send it to each other.
Grover: an honest speedup
In 1996 Lov Grover came up with quantum search. Picture an unsorted database of a million records, and you need one. A classical computer checks all million in the worst case, half a million on average. Grover’s algorithm needs about 800 steps. That’s a “square root of N” speedup: a database 100 times bigger needs only 10 times more steps. Strong, but not instant, and nothing like “everything at once.” We’ll dig into it in the algorithms level.
Where the gain is huge and where it’s zero
An exponential gain, where a years-long problem becomes an hours-long one, is known only for a narrow set of problems. The main ones: factoring large numbers, which part of internet encryption relies on, and simulating molecules and materials. A moderate gain exists for search and some optimisation problems. For games, video, social media and spreadsheets there’s no benefit: an ordinary chip does it faster and cheaper. And there’s no proof that a quantum computer can quickly solve every hard problem.
Not a replacement but an accelerator
A quantum computer won’t replace your laptop or show up in your phone. It’s better to think of it like a graphics card: the CPU does all the ordinary work, the GPU takes graphics and neural networks. Likewise a quantum processor, called a QPU, gets only a narrow subtask from the ordinary computer, say computing a molecule’s energy, and sends back the answer. Big players are already placing QPUs next to supercomputers and building hybrid setups.
How not to fall for headlines
In 2019 Google announced that its Sycamore chip solved in 200 seconds a task a supercomputer would need 10,000 years for. IBM soon replied that about 2.5 days would do, and in 2022 Chinese researchers solved the same task in about 15 hours on 512 GPUs. And the task was purpose-built with no practical use. Before getting excited about news, run through the five checklist questions. Five “yes” answers are rare, and that’s normal: science moves in steps.
Check yourself
- What’s wrong with the headline “a quantum computer checks all passwords at once”?
Correct answer: Measurement gives one answer; for brute force there’s only a “square root of N” speedup. “All at once” is a myth. For guessing a password, Grover applies, and it gives a “square root of N” speedup, not an instant crack. - A startup promises a “quantum accelerator for Excel.” How do you rate it?
Correct answer: Skeptically: there’s no quantum gain for spreadsheets. A laptop handles ordinary spreadsheet maths faster and cheaper. Quantum gains exist only for narrow problems. - Which checklist question would first expose Sycamore’s 2019 record?
Correct answer: Does anyone need that task?. The task was designed for the demo and had no practical use. Plus, classical methods quickly closed the gap.
← Interference: the main trick Grover’s algorithm: quantum search →