WHAT CLASSICAL COMPUTERS CAN'T DO (AND WHERE QUANTUM HELPS)

You already know, from any algorithms course, that not all growth rates are created equal. An O(n) algorithm and an O(2^n) algorithm might both "work," but only one of them is still working by the time your input gets large. This lesson makes that distinction concrete with real numbers, and then draws an honest line around exactly where quantum computers help — and, just as importantly, where they don't.

A Concrete Look at Exponential Blowup

Let's ground this in numbers you can check yourself. Suppose an algorithm takes 2^n basic steps to solve a problem of size n, and your computer can perform one billion (10^9) steps per second — a reasonable estimate for a modern CPU core.

This table is the entire justification for this whole field. Real-world RSA encryption uses numbers with hundreds of digits (thousands of bits), and the best known classical factoring algorithms scale in a way that isn't quite this simple 2^n (it's technically sub-exponential, called the General Number Field Sieve), but the practical conclusion is the same: for large enough keys, classical factoring is hopeless within any human timescale. Shor's algorithm (Module 14) changes this picture entirely for a sufficiently large quantum computer — bringing that "beyond the age of the universe" number down to hours or days.

An Important Nuance: Not All Hard Problems Get Faster

Here's a myth this lesson exists specifically to correct: quantum computers do not magically solve all exponentially-hard problems in fast (polynomial) time.

Computer scientists classify problems into complexity classes — you've likely encountered P (solvable quickly, i.e., in polynomial time, by a classical computer) and NP (solutions can be checked quickly, but not necessarily found quickly), with NP-hard problems being (informally) at least as hard as the hardest problems in NP. Quantum computers are believed to not efficiently solve general NP-hard problems (like the Traveling Salesman Problem, in its exact form) — there's no known quantum algorithm that brings NP-hard problems down to polynomial time, and most researchers believe none exists.

What quantum computers do offer are speedups for specific, structured problems where the problem's mathematical shape happens to be exploitable by superposition and interference. The clearest examples:

Notice the last row carefully — it's there on purpose. A "quadratic speedup" like Grover's (turning O(N) into O(√N))) is real and useful, but it's a far cry from turning an exponential problem into a fast one. Only Shor's algorithm and quantum simulation offer the dramatic exponential-style speedups that make headlines.

An Analogy for the Search Speedup

Think of unstructured search the way you'd think about looking for one specific unlabeled file among a huge pile of unsorted, unindexed files — no filenames, no folder structure, nothing to sort by. Classically, your only honest strategy is to check files one at a time; on average, you'll need to check about half the pile, and in the worst case, all of it. This is exactly the kind of problem where a sorted structure (like a binary search tree, which you already know gives O(log N)) doesn't exist to help you — there's no shortcut, because the data has no exploitable structure.

Grover's algorithm (Module 14) gives a quadratic speedup for exactly this scenario: checking roughly √N "locations" using quantum superposition and interference, instead of N. For a pile of 1,000,000 unsorted files, that's the difference between checking around 1,000,000 items and checking around 1,000 — a real, meaningful improvement, though not the exponential jump Shor's algorithm provides for factoring.