Part I, Foundations · Lesson 3
What a quantum computer is (and isn't)
The short version
A normal computer bit is a light switch: on or off. A qubit is more like a dial that holds a blend of both until you look, and when you look, it snaps to plain on or off. Quantum computers don't just try every answer at once. They choreograph these blends so wrong answers cancel out and right answers get louder. That only helps for a few special problems, but one of them is breaking today's public-key cryptography.
You'll learn to
- Explain the difference between a bit and a qubit, including superposition and measurement.
- Debunk the myth that quantum computers "try every answer at once" and explain interference instead.
- Describe entanglement as correlation, and say what it can't do.
- Explain why building a cryptographically relevant quantum computer is so hard.
Quantum computing attracts more hype per square inch than almost any other technology. You'll read that quantum computers "try every possible answer simultaneously," that they'll "make all encryption obsolete," or that they're "millions of times faster." None of those is quite right.
This lesson gives you an accurate mental model with no equations. It won't make you a physicist, but it will let you read a quantum headline and know which parts to believe.
Not a faster laptop
A quantum computer isn't a souped-up version of the computer you're reading this on. It's a different kind of machine that follows different rules, the rules of quantum mechanics, which govern atoms, electrons and light.
For most tasks, such as browsing, spreadsheets, video or AI chatbots, a quantum computer would offer no advantage at all. It shines on a small set of problems with special structure. Unfortunately for cryptographers, factoring and discrete logarithms are among them.
Bits and qubits
An ordinary bit is either 0 or 1, like a light switch. Everything your computer does is built from billions of these switches.
A qubit (quantum bit) can be in a superposition of 0 and 1. That doesn't mean it's secretly one or the other and we just don't know. It means its state is described by two numbers called amplitudes, one for 0 and one for 1.
The amplitudes tell you the odds of what you'll see when you look. Square an amplitude and you get a probability. A qubit with amplitudes 0.866 and 0.5 gives 0 with probability 0.866² = 75% and 1 with probability 0.5² = 25%.
Measurement: you only ever get one answer
Here's the catch that most hype skips. When you measure a qubit, you don't see the amplitudes. You get a single, ordinary 0 or 1. And the superposition is gone: the qubit is now just whatever you saw. Physicists call this collapse.
So one measurement tells you very little. To learn the probabilities, you have to prepare the same state again and again, measure each time, and count. Try it:
Press "Measure once" a few times and notice that each result is just a 0 or a 1. Then repeat 1,000 times and watch the counts settle near the predicted probabilities. Also notice what you can't do: you can't peek at a qubit's amplitudes directly. That limitation shapes every quantum algorithm.
The myth: "it tries every answer at once"
With many qubits, a superposition can include an enormous number of possibilities. Ten qubits can hold amplitudes over 1,024 combinations, and every extra qubit doubles the count. It's tempting to say the machine "computes all answers in parallel."
But remember measurement. If you put every possible answer in superposition and simply measure, you get one answer at random. That's no better than guessing.
The real power is interference. Amplitudes can be positive or negative (in general, they're complex numbers), so they can add up or cancel out, like waves in water. A good quantum algorithm is a carefully designed sequence of operations that makes the amplitudes of wrong answers cancel and the amplitudes of right answers reinforce. When you finally measure, the right answer is likely.
Lov Grover described his 1996 search algorithm in these terms: by properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. Designing that choreography is hard, and it only works for problems with the right structure. That's why there are only a handful of famous quantum algorithms, not thousands.
Entanglement: correlation without a phone line
Qubits can also be entangled. Two entangled qubits share a joint state that can't be described by treating each qubit separately. The bottom half of the widget shows the simplest example: each qubit on its own looks like a fair coin, yet the two always agree.
Entanglement is essential to quantum algorithms, because it lets amplitudes spread across combinations of many qubits. But it isn't magic telepathy. Neither side can choose what result they get, so entanglement can't be used to send a message, faster than light or otherwise.
Why they're so hard to build
Superpositions are fragile. Any stray interaction with the outside world, such as heat, vibration or a passing electromagnetic field, acts like a tiny unplanned measurement and scrambles the state. This is called decoherence, and it's why many quantum processors are cooled to near absolute zero and shielded heavily.
Even then, every operation has a small chance of error. Today's qubits are called noisy. A long calculation like Shor's algorithm would be ruined by errors long before it finished.
The fix is quantum error correction: spreading one reliable logical qubit across many noisy physical qubits and constantly checking for and correcting errors. It works in principle, but it's expensive. Most of the qubits in a future code-breaking machine would be doing error correction, not arithmetic.
How big is "big enough"?
A cryptographically relevant quantum computer (CRQC) is one large and reliable enough to break real-world public-key cryptography such as RSA-2048. Published resource estimates have fallen over time:
- In 2019, Craig Gidney and Martin Ekerå estimated RSA-2048 could be factored in about 8 hours with about 20 million noisy qubits.
- In May 2025, Gidney estimated it could be done in under a week with fewer than one million noisy qubits.
The Global Risk Institute's 2024 expert survey summed up the state of play: today's quantum processors are still far from being CRQCs, but the technology is advancing. Nobody can tell you the date a CRQC will exist. We'll look at the estimates, and why "nobody knows" is itself a reason to act, in the harvest-now-decrypt-later lesson.
What quantum computers are good at, and not
| Task | Quantum advantage? |
|---|---|
| Factoring and discrete logarithms (breaking RSA and elliptic curves) | Huge: Shor's algorithm, the subject of the next lesson |
| Unstructured search (including brute-forcing a key) | Modest: Grover's algorithm gives a square-root speedup, and it's hard to use in practice |
| Everyday computing: email, video, spreadsheets | None |
| Breaking the new post-quantum algorithms (lattices, hashes) | No known efficient attack, which is why they were chosen |
Note the careful wording in that last row. "No known attack" isn't "proven impossible." Nothing is quantum-proof. Some things are quantum-resistant, which is less catchy and more true.
What to remember
A quantum computer manipulates amplitudes, not answers. Measurement gives a single result and destroys the superposition, so algorithms must use interference to make the right answer likely. That trick works spectacularly for a few structured problems, and the two problems underneath today's public-key cryptography are among them. Next: exactly how Shor's algorithm does it.
Go deeper: what the widget's angle means
The widget writes the qubit's state as cos(θ/2)·|0⟩ + sin(θ/2)·|1⟩. The symbols |0⟩ and |1⟩ (read "ket zero" and "ket one") are just labels for the two possible measurement results. The two numbers in front are the amplitudes.
Because cos² + sin² = 1 for any angle, the two probabilities always add up to 100%, whatever θ you pick. At θ = 0° the qubit is certainly 0; at 180° it is certainly 1; at 90° it's a 50/50 split.
The circle in the widget is a slice of what physicists call the Bloch sphere. The full picture also has a second angle, the phase, which doesn't change single-qubit measurement odds but matters enormously for interference. Phase is exactly what Grover's oracle flips, as you'll see in the Grover lesson.
Summary
- A qubit holds amplitudes for 0 and 1; squaring an amplitude gives the probability of seeing that result.
- Measurement gives one ordinary bit and destroys the superposition, so you can't read amplitudes directly.
- Quantum speedups come from interference, making wrong answers cancel, not from "trying every answer at once."
- Entanglement creates correlations, but it can't send messages.
- Noise and decoherence make large machines hard to build; error correction needs many physical qubits per logical qubit.
- Published estimates for breaking RSA-2048 fell from about 20 million noisy qubits in about 8 hours (2019) to under one million in under a week (2025).
Questions
Get five of six right to mark the lesson complete. They also feed the final exam.
Sources
- Grover (1996), A fast quantum mechanical algorithm for database search
- Gidney & Ekerå (2019), How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Gidney (2025), How to factor 2048 bit RSA integers with less than a million noisy qubits
- Global Risk Institute, Quantum Threat Timeline Report 2024 (executive summary)
