Lesson C: What quantum computers are good for
Simulating nature, breaking codes, search, and what they won’t speed up
The interactive version checks every answer, gives hints and saves your progress in this browser. This page is the same lesson on one page, with the answers folded away.
1 / 7 · Learn
Before you start
Lesson A said that quantum computers are expected to be much faster for some problems, somewhat faster for others, and no help for most. This lesson sorts out which problems are which, from simulating molecules to the codes that protect the internet. It needs nothing beyond everyday arithmetic.
Check yourself
A warm-up: make a guess before reading on. The lesson comes back to it.
Which of these jobs is a quantum computer expected to help with most?
- ASearching your email
- BStreaming a film
- CRunning a big spreadsheet
- DSimulating a molecule, to help design a better battery
Show the answer
Answer: D. Simulating a molecule, to help design a better battery
A molecule’s electrons follow quantum rules, so describing them exactly overwhelms ordinary computers, while a quantum computer can mimic them directly. The other three jobs are already fast, and no quantum speedup is known for them.
Why not the others
- A. Search sounds like a natural quantum job, and there is a quantum search method. But its speedup is modest, and your email is already found almost at once through an index, like the one at the back of a book. The strongest expected use is simulating molecules, which are quantum themselves.
- B. Streaming is mostly about moving data across the network and unpacking it, which ordinary chips already do quickly, and no quantum speedup is known for it. The job quantum computers are most expected to help with is simulating molecules, which are quantum themselves.
- C. A spreadsheet does ordinary arithmetic, which ordinary chips do billions of times a second, and no quantum speedup is known for it. The strongest expected use is simulating molecules, which are quantum themselves.
2 / 7 · Learn
Simulating nature
Start with the job quantum computers were first imagined for. Recall Lesson B: describing a set of qubits exactly takes a list of numbers that doubles with every qubit added. 2 qubits need 4 numbers, 3 need 8, and 30 need about a billion, roughly what a laptop can hold.
The same doubling turns up in nature. How a molecule holds together, and how it reacts, is decided by its electrons, and electrons follow quantum rules. Roughly speaking, each place an electron could sit in a molecule is either filled or empty, like a 0 or a 1, and an exact description needs a number for every combination. Each place added roughly doubles the list.
That is why Richard Feynman, as Lesson B told, suggested using quantum things to simulate quantum things. A quantum computer doesn’t have to write the list down: its qubits can stand for the places directly, one qubit each, so the machine grows in step with the molecule instead of doubling.
It still can’t show you the whole list. As in Lesson A, a measurement gives one answer, so a simulation has to be designed to measure what a chemist wants to know, such as how much energy a reaction releases.
Check yourself
Why is simulating a molecule such a natural job for a quantum computer?
- AThe molecule’s electrons follow quantum rules, so an exact description doubles as the molecule grows, while qubits can stand for them directly
- BIt can try every possible molecule at once and pick out the best one
- CMolecules are tiny, and quantum computers are built for tiny things
- DIt can read out the whole list of numbers that describes the molecule
Hints
- Think back to Lesson B: what happens to the length of an exact description each time a piece is added?
- Which of these options is about the molecule being quantum itself?
Show the answer
Answer: A. The molecule’s electrons follow quantum rules, so an exact description doubles as the molecule grows, while qubits can stand for them directly
Electrons follow quantum rules, so their exact description doubles as a molecule grows, which overwhelms ordinary memory. A quantum computer’s qubits can stand for the places electrons sit, so it grows in step with the molecule.
Why not the others
- B. That is the “every answer at once” picture that Lesson A took apart: a measurement gives one outcome, not a verdict on every molecule. The fit is more direct than that: the qubits mimic the molecule’s own electrons.
- C. Size isn’t the reason: plenty of tiny things are simple to simulate. What matters is that electrons follow quantum rules, so an exact description on an ordinary computer doubles with each place an electron could sit, while qubits can stand for those places directly.
- D. A measurement gives one outcome, not the whole list, so a simulation is designed to measure one quantity, such as an energy. The advantage is that the qubits can hold the description at all, where an ordinary computer’s memory runs out.
One honest caveat. Chemists rarely need the full list: clever approximations on ordinary computers already handle most molecules well, and they keep improving. The hard cases are those in which many electrons are tightly linked to one another, such as the clusters of metal atoms at the heart of many catalysts (substances that speed up a chemical reaction without being used up) and some of the materials in batteries. Those are the targets. The hope is better catalysts and batteries, but for now these are hopes, not results.
Check yourself
A chemist’s molecule is already handled well by standard approximations on a laptop. How much would a large quantum computer be expected to help her with it?
- AProbably very little: the expected gains are for hard cases, where many electrons are tightly linked
- BNot at all, because quantum computers can’t simulate molecules
- CA great deal: every molecule is simulated far faster on a quantum computer
Show the answer
Answer: A. Probably very little: the expected gains are for hard cases, where many electrons are tightly linked
Approximations on ordinary computers already handle most molecules. The hoped-for gains are on the hard cases, where many electrons are tightly linked and the approximations fail.
Why not the others
- B. They can, and it is their most promising use. It is just that a molecule an ordinary computer already handles well leaves little to gain. The hoped-for gains are on hard cases, such as the metal clusters in catalysts.
- C. When an approximation already works, an ordinary computer gets the answer quickly and cheaply, so there is little left to gain. The hoped-for gains are on hard cases, where many electrons are tightly linked and the approximations break down.
How big is the gain for chemistry?
For simulating how many kinds of quantum system change over time, quantum computers have methods whose cost grows only modestly with the size of the system, while the best known ordinary methods in general run into Lesson B’s doubling. For the most common task in chemistry, finding a molecule’s lowest energy, the picture is less clear. A 2023 study by chemists and quantum-computing researchers found no evidence yet of an exponential gain (one that, like the doubling, keeps multiplying as molecules grow) across chemistry in general. The gain may still be large for particular hard molecules. That is why this lesson calls simulation the strongest expected use rather than a sure thing.
3 / 7 · Learn
Codes that protect the internet
When your phone connects to your bank, the two need a shared secret key to scramble their messages, yet they have never met, and anyone on the network can listen in. Public-key cryptography solves this. It lets two strangers agree on a secret over an open line, and lets a website prove who it is with a digital signature.
It works because some math problems are easy one way and very hard the other. Multiplying two large prime numbers (whole numbers, like 3, 5 and 7, that only 1 and themselves divide evenly) is quick. Going back, finding the two primes from their product (factoring), is thought to be hopelessly slow for ordinary computers once the numbers have hundreds of digits. A widely used method called RSA relies on this; elliptic-curve cryptography relies on a related problem.
How hard is factoring for an ordinary computer?
15 = 3 × 5 is easy to undo by trying small numbers. But trying gets out of hand fast. In 2020 a team factored a 250-digit number of this kind using about 2,700 core-years: the work one processor core would do in 2,700 years, shared across many machines. In 2026, with large clusters of graphics chips, the record moved up to 270 digits. The RSA keys in common use have about 600 digits, and no known method on ordinary computers could factor one in any reasonable time.
In 1994 Peter Shor found a quantum algorithm that factors quickly, and a version of it solves the elliptic-curve problem too. It works as Lesson A described: the problem hides a repeating pattern, and the algorithm’s steps make the amplitudes (the numbers that, unlike chances, can cancel) pile up on outcomes that reveal the pattern.
On a large error-corrected quantum computer, one that keeps catching and fixing its own mistakes as it runs (Lesson D shows how), Shor’s algorithm would break the public-key methods that protect much of the internet’s traffic today. No such machine exists yet, and nobody knows when one will. Even so, browsers and messaging apps are already changing.
Check yourself
No quantum computer can break today’s public-key methods yet. Why are browsers and messaging apps already switching to new ones?
- AQuantum computers can already break them, and this is being kept quiet
- BMessages recorded today could be decrypted years from now, once a large enough quantum computer exists
- COrdinary computers have become fast enough to factor the numbers in use
- DThe new methods are faster, so it is a routine upgrade
Hint
- Can an eavesdropper keep a copy of scrambled messages they can’t read yet?
Show the answer
Answer: B. Messages recorded today could be decrypted years from now, once a large enough quantum computer exists
This is called harvest now, decrypt later: an eavesdropper can store scrambled traffic today and decrypt it once a large quantum computer exists. Anything that must stay secret for years needs protecting now.
Why not the others
- A. There is no public evidence of that, and published estimates say breaking a real key would take a far larger and more reliable machine than any that exists. The reason is about the future: scrambled traffic recorded today could be decrypted later.
- C. They haven’t come close. As of late 2026, the largest number of this kind factored with ordinary computers has 270 digits, while keys in use have about 600, and every extra digit makes the job harder. The worry is a future quantum computer, together with traffic recorded today.
- D. Speed isn’t the reason: the new methods actually send more data than the old ones. The reason is that scrambled traffic recorded today could be decrypted later, once a large quantum computer exists.
The fix doesn’t need a quantum computer at all. Post-quantum cryptography means new public-key methods that run on ordinary computers and phones, built on different math problems for which no quantum shortcut is known. The first standards were published in 2024, and post-quantum key agreement is already switched on in major browsers, phones and messaging apps. Signatures are taking longer to switch over.
Not every kind of encryption is in danger. Once two sides share a key, the bulk of their data is scrambled with symmetric encryption, such as AES, where both sides use the same key. The best known quantum attack on it is a search for the key (the next part), which saves at most a square root, and longer keys make up for that.
Step 1 · agree on a key
Step 2 · scramble the data
A secure connection in two steps. Step 1 rests on a problem like factoring: 3 × 5 = 15 is quick, but going back from a 600-digit product is hopeless for ordinary computers. Shor’s algorithm would change that, so step 1 is being replaced first. Step 2 needs, at most, longer keys.
Check yourself
Which of these would a large quantum computer running Shor’s algorithm put at risk?
- AA secret key agreed with a post-quantum method
- BA secret key that two strangers agreed on with an elliptic-curve method
- CData scrambled with AES under a key the two sides already share safely
Show the answer
Answer: B. A secret key that two strangers agreed on with an elliptic-curve method
Shor’s algorithm breaks the problems behind the old public-key methods: factoring (RSA) and its elliptic-curve cousin. Symmetric encryption such as AES, and post-quantum methods, have no known quantum shortcut of that kind.
Why not the others
- A. Post-quantum methods are built on math problems for which no quantum shortcut is known, Shor’s included. Resisting it is the whole point of them.
- C. Shor’s algorithm attacks the math behind public-key methods: factoring and its elliptic-curve cousin. AES has no such structure; the best known quantum attack on it is a search for the key, which saves at most a square root, and longer keys make up for that.
More dates: the switch so far
NIST, the US standards agency, published the first three post-quantum standards in August 2024. Post-quantum key agreement was switched on by default in Chrome and Firefox in 2024 and in Apple’s systems in 2025, and messaging apps such as Signal (2023) and iMessage (2024) added it too. By late 2025, about half of the human web traffic passing through Cloudflare, a large internet company, used it. As of late 2026, post-quantum certificates, the signatures that prove a website’s identity, were still being trialled and not yet in general use. US and UK government plans aim to finish the switch by 2035.
4 / 7 · Worked example
Search: a smaller speedup
Lesson A ended on the honest version of “a quantum computer tries every answer at once”: a measurement gives one answer, so a quantum algorithm has to make the wrong answers cancel and the right one add up. How much that helps depends on the problem.
Take a search with no structure: one item among many passes a test, and nothing hints where it is. In 1996 Lov Grover found a quantum method that needs only about the square root of the number of items, in steps. (The square root of a number is the number that, multiplied by itself, gives it.) Each step nudges a little more amplitude toward the right answer. Here is what that buys.
Worked example
Searching a million items
A list of a million items holds one marked item, and the only way to find it is to test items.
An ordinary computer
It tests items one by one: up to a million tests, and about half a million on average.
Grover’s method
About a thousand steps, because 1,000 × 1,000 = 1,000,000. That is a thousand times fewer.
The catch
Each quantum step is much slower than one test on an ordinary chip. It has to run the test on the qubits themselves, and on a machine large enough to be useful, error correction (Lesson D) adds many more operations. Suppose, as a round illustration, that one quantum step takes as long as a million ordinary tests.
Compare
A thousand quantum steps then take as long as 1,000 × 1,000,000 = 1,000,000,000 ordinary tests: a thousand times longer than the ordinary computer’s million. For this list, the ordinary computer wins easily.
Your turn
Keep the same assumption: one quantum step takes as long as a million ordinary tests. Now the list has a trillion items, a million million. An ordinary computer needs up to a trillion tests; Grover’s method needs about a million steps, because 1,000,000 × 1,000,000 is a trillion. Which finishes first?
- AThe quantum computer, by about a million times
- BNeither: they take about the same time
- CThe ordinary computer, by about a thousand times
Hints
- How long do a million quantum steps take, counted in ordinary tests?
- Multiply: a million steps × a million tests each.
- Compare that with the ordinary computer’s trillion tests.
Show the answer
Answer: B. Neither: they take about the same time
A million quantum steps × a million tests each = a trillion tests, the same as the ordinary computer. The two draw level; only still bigger lists favor the quantum computer.
Why not the others
- A. That counts steps but forgets that each quantum step is slow. A million steps, each as long as a million tests, take as long as a million million tests: a trillion, the same as the ordinary computer.
- C. That was the answer for a million items. With a trillion items the square root saves more: a million steps, each as long as a million tests, add up to a trillion tests, so the two draw level.
Only on still bigger lists does the square root pull ahead. And ordinary computers have another advantage: a search can be split across thousands of processors, while Grover’s steps have to run one after another and gain much less from splitting. Against many processors, a quantum computer may have to run for months before it even draws level. So a square-root speedup is real, but it is expected to pay off only rarely.
Where the million comes from (a 2021 study)
In a study published in 2021, Google researchers estimated the costs on a future error-corrected machine built from superconducting circuits. The operations a quantum search step is mostly built from would take around 170 millionths of a second each, while one core of an ordinary processor does billions of simple operations a second. In their simplest example, one quantum step took as long as about half a million ordinary tests. The quantum computer then needed over two hours just to draw level with one ordinary processor core, and about a year to draw level with 3,000 of them. Their verdict: “the prospects are generally poor for a quadratic speedup”, the usual term for a square-root saving.
The million in the worked example is a round number of that size; the real figure depends on the problem and the machine.
What about optimization, such as planning the best routes for a fleet of delivery vans, or machine learning? Many hopeful claims are made, sometimes of an exponential speedup: one where, as with Lesson B’s doubling, the gap keeps multiplying as the problem grows.
No big quantum speedup has been proved for these problems in general, and most researchers doubt that quantum computers can solve the hardest of them quickly. Many proposed quantum methods can only be judged by trying them, and those trials are still under way. Some claims of big gains were later matched by improved ordinary methods: in 2018 a student found an ordinary algorithm that nearly matched a celebrated quantum one for making recommendations, like those for films.
Check yourself
A company says its quantum computer will plan routes for a delivery fleet “exponentially faster” than any ordinary computer. What is the most reasonable response?
- ABelieve it: a quantum computer tries every route at once
- BBelieve it: that is exactly what Grover’s search gives
- CAsk for evidence: no big quantum speedup is known for problems like this, and the gains that are known are modest
- DDismiss it outright: quantum computers can never help with any optimization problem
Show the answer
Answer: C. Ask for evidence: no big quantum speedup is known for problems like this, and the gains that are known are modest
No exponential quantum speedup is known for problems like route planning. The known gains are modest, such as Grover’s square root, and claims of more need evidence; some have later been matched by ordinary methods.
Why not the others
- A. A measurement gives one answer, not a verdict on every route (Lesson A). Trying routes “at once” is no help unless the wrong answers can be made to cancel, and for route planning no method is known that does that dramatically.
- B. Grover’s saving is a square root: a trillion tests become about a million steps, not a handful. That is far short of exponential, and slow error-corrected steps often eat even that.
- D. That goes too far. Grover-style methods give a square-root saving in principle, and other quantum methods are still being studied. What is missing is evidence of a big speedup, so ask for it.
5 / 7 · Explore
Sorting the tasks
What about the computing you do every day? Email, video, web pages, games and spreadsheets have no known quantum speedup. They are already fast, and most of their work is moving data around rather than solving hard problems. Some tasks are even proved to have no big speedup: sorting a list by comparing items takes a quantum computer about as many comparisons as an ordinary one.
Big gains need a problem with a special structure that interference can exploit (Lesson A), and most everyday problems have none. So a large quantum computer, if one is built, would be a specialized machine working alongside ordinary computers, which control it and do almost everything else. Nobody expects it to replace the chips in your phone or laptop.
Why not big data?
A quantum computer can’t take in a huge pile of data any faster than the data can be read in, item by item. If a task is mostly about working through a large data set, just loading it can cost as much as an ordinary computer’s whole job. Quantum algorithms do best when the input is small and the hard part is the calculation, as in factoring one large number or simulating one molecule.
Check yourself
Sort each task by what a large, error-corrected quantum computer is expected to offer over the best methods known for ordinary computers.
Match each of these…
- Factoring a 600-digit number to break an RSA key
- Simulating how the tightly linked electrons in a catalyst behave during a reaction
- Finding the one input that passes a test, when nothing hints where it is
- Finding an AES key by trying keys
- Sorting a long list of names
- Streaming a film
…with one of these
- Modest speedup at best
- No speedup expected
- Large speedup
Hints
- Which tasks have a special structure for interference to exploit, such as a quantum system or a hidden repeating pattern?
- A search with no structure gets Grover’s square root at most.
- Everyday tasks, and sorting, get no big speedup.
Show the answer
| Factoring a 600-digit number to break an RSA key | Large speedup |
| Simulating how the tightly linked electrons in a catalyst behave during a reaction | Large speedup |
| Finding the one input that passes a test, when nothing hints where it is | Modest speedup at best |
| Finding an AES key by trying keys | Modest speedup at best |
| Sorting a long list of names | No speedup expected |
| Streaming a film | No speedup expected |
Large: factoring (Shor’s algorithm) and simulating tightly linked electrons. Modest at best: a search with no structure and trying AES keys (Grover’s square root). None expected: sorting (proved) and streaming.
These ideas come back with their math later in the course. Lesson 10 maps the families of quantum algorithms and what has been proved about them. In Part 2, Lesson 15 works through Simon’s algorithm, the idea Shor’s algorithm grew from, and Lessons 16 and 17 build Grover’s search and show exactly where its square root comes from.
6 / 7 · Mastery check
Mastery check
Check yourself
Which of these is the strongest case for a quantum computer?
- AWorking out how the tightly linked electrons in a metal-containing catalyst behave
- BMaking a web search engine answer faster
- CTraining a large AI model on text from the internet
- DDrawing video-game graphics faster
Show the answer
Answer: A. Working out how the tightly linked electrons in a metal-containing catalyst behave
Electrons follow quantum rules, so their exact description doubles as a molecule grows, while qubits can stand for them directly. Hard cases such as the metal clusters in catalysts are where quantum computers are most expected to help.
Why not the others
- B. A search engine looks words up in a huge index built in advance, which ordinary computers do very fast; the data is the bottleneck, and no quantum speedup is known. The strongest case is simulating quantum systems, such as the electrons in a catalyst.
- C. No big quantum speedup is known for machine learning in general, and a quantum computer can’t take in huge amounts of data faster than they can be read in. The strongest case is simulating quantum systems, such as the electrons in a catalyst.
- D. Graphics is ordinary arithmetic done in parallel on chips built for it, and no quantum speedup is known. The strongest case is simulating quantum systems, such as the electrons in a catalyst.
Check yourself
Two people chat through an app that agrees on its secret key with an elliptic-curve method only, with no post-quantum method. An eavesdropper records everything they send, key agreement included. Years later, a large error-corrected quantum computer is built. What can the eavesdropper now do?
- ARead them only if a quantum search can also break the AES encryption
- BRead every message ever recorded, including those protected by post-quantum key agreement
- CRecover the key with Shor’s algorithm and read the old messages
- DNothing: the messages were sent before the machine existed
Show the answer
Answer: C. Recover the key with Shor’s algorithm and read the old messages
Shor’s algorithm breaks elliptic-curve key agreement, so a recording made today can be decrypted once the machine exists: harvest now, decrypt later. Post-quantum key agreement closes that gap, which is why it is being switched on now.
Why not the others
- A. The weak link is the key agreement, not AES. Shor’s algorithm recovers the shared key from the recorded exchange, and with the key, the AES-scrambled messages unlock normally.
- B. Post-quantum methods are built on problems with no known quantum shortcut, so messages protected by them stay safe. Only the old public-key methods fall to Shor’s algorithm.
- D. Recorded messages don’t expire. The key agreement can be broken later from the recording: that is the harvest-now, decrypt-later threat, and the reason apps are switching now.
Check yourself
To find one marked item among a million, Grover’s method needs about a thousand steps, where an ordinary computer may need a million tests. Why might the ordinary computer still finish first?
- AGrover’s method works only on lists that are already sorted
- BIt can’t: Grover’s speedup is exponential, so the quantum computer always wins
- CEach quantum step, with error correction, can take far longer than an ordinary test
- DGrover’s method is a guess that has to be repeated about a million times
Show the answer
Answer: C. Each quantum step, with error correction, can take far longer than an ordinary test
A thousand steps beat a million tests only if each step is about as fast as a test. Error-corrected quantum steps are expected to be far slower, so the square root pays off only on enormous problems.
Why not the others
- A. It works on lists with no order at all; that is its point. The catch is the time per step: one error-corrected quantum step can take as long as a great many ordinary tests.
- B. The saving is a square root: a thousand steps instead of a million, far short of exponential. If each quantum step takes as long as a million tests, the thousand steps take a thousand times longer than the ordinary search.
- D. Grover’s method doesn’t rely on repeated guessing: about a thousand steps make the right answer very likely. The catch is the time per step: one error-corrected quantum step can take as long as a great many ordinary tests.
Check yourself
Suppose large quantum computers are built. What is expected to happen to everyday computing, such as email, video and spreadsheets?
- AIt stays on ordinary computers: no quantum speedup is known for it
- BOnly sorting lists gets faster
- CPhones and laptops switch to quantum chips once they are small enough
- DIt all runs much faster, because qubits hold far more than bits
Show the answer
Answer: A. It stays on ordinary computers: no quantum speedup is known for it
Everyday tasks are already fast and have no special structure for interference to exploit. Quantum computers would be specialized machines working alongside ordinary computers.
Why not the others
- B. Sorting is one of the few tasks proved to get no big quantum speedup. Everyday computing in general has none known.
- C. Size isn’t what stands in the way: no quantum speedup is known for everyday tasks, so there would be nothing to gain. Quantum computers are expected to be specialized machines working alongside ordinary ones.
- D. Measuring qubits gives one answer, as Lesson A showed: ten qubits give ten bits, no more. Speedups come from interference on problems with a special structure, and everyday tasks have none to exploit.
7 / 7 · Recap
Recap
Key ideas
Quantum computers help only with problems that have a special structure for interference to exploit. For most tasks they offer nothing.
Simulating molecules and materials is the strongest expected use: electrons are quantum, so an exact description doubles as the system grows, while qubits can stand for them directly. The gains are for hard cases, and how big they are is still debated.
Shor’s algorithm would break today’s public-key cryptography on a large error-corrected machine. Post-quantum replacements are already rolling out, because of harvest now, decrypt later. Symmetric encryption such as AES is only mildly affected.
Grover’s search needs about the square root of the number of tests: about a thousand steps for a million items. Slow error-corrected steps often cancel that gain, and big speedups for optimization and machine learning are unproven.
Everyday computing has no known quantum speedup, and sorting provably has no big one.
Go further
Free resources for when you want more than this lesson covers.
- What is post-quantum cryptography?NIST · Article
A plain question-and-answer page on why encryption is being replaced now, including harvest now, decrypt later.
- State of the post-quantum Internet in 2025Bas Westerbaan, Cloudflare · Article
A detailed survey of how much web traffic already uses post-quantum key agreement, and why signatures are slower to switch.
- Key chemistry question answered, no quantum computer requiredKevin Hartnett, Quanta Magazine · Article
How ordinary computers answered a famous test question for quantum chemistry in 2026, and what may still be left for quantum machines.
- Major quantum computing advance made obsolete by teenagerKevin Hartnett, Quanta Magazine · Article
The 2018 story of a student whose ordinary algorithm nearly matched a celebrated quantum one for making recommendations.