How to Evaluate a Quantum Use Case

Quantum computing really does offer speedups for some problems. The trouble is how most popular claims are told. They quote the speedup for one step on its own. They quietly skip everything around it: getting data in, getting answers out, and surviving hardware errors.

Think of an ad that says a sports car goes 0 to 60 in three seconds. That is true. But if your trip is across town at rush hour, the traffic decides how long it takes, not the engine. Quantum claims often quote the engine and skip the traffic. Where the picture breaks: a car is still at least as fast as walking. A quantum computer can end up slower than a normal one once you count everything.

This chapter builds a five-question filter you can use on any claim. Every later chapter in this course applies it to one area. The five questions:

1. Is the speedup verified? Is it a proven advantage in math, or just a hopeful guess?
2. What does data loading cost? A quantum computer can't work on your data until the data is inside a quantum state.
3. What does each oracle call cost? Many algorithms are measured in abstract "queries." The real cost of each one is hidden.
4. Does the error budget survive? Every gate on real hardware fails some of the time, and failures pile up.
5. Is the classical baseline moving? Normal (classical) algorithms and hardware keep improving while the quantum roadmap plays out.

A use case that passes all five is rare. That is not gloom. It is why the few survivors matter so much. They are covered in quantum simulation and post-quantum cryptography. For what has actually been demonstrated, see our quantum advantage reality page.

A few definitions, in case you landed here first:

• A qubit is the quantum version of a bit.
• Its state is described by amplitudes. These are numbers (possibly complex) whose squares give the chances of each measurement result. See probability amplitudes.
• An algorithmic speedup means the quantum algorithm needs far fewer steps as the problem grows. It does not mean any one step is faster.

Speedups come in tiers, and the tier decides everything:

• Proven, superpolynomial. Superpolynomial means the gap over classical grows faster than any fixed power of the problem size. Exponential growth is the familiar example. Examples: Shor's factoring algorithm, and simulating quantum physics itself. These change what is practical to compute, if large error-corrected machines exist. This is proven theory. The machines are not yet built.
• Proven, quadratic. Example: Grover's search. A task that needs N steps classically needs about √N quantum queries. So a task of 1,000,000 steps needs about 1,000 queries. This is proven in the abstract "query model." That is a way of counting cost that only counts calls to an answer-checking routine and ignores what each call costs. It is fragile in practice, as the next section shows.
• Heuristic. A heuristic is a method that often works but has no proof. Examples: QAOA for optimization, and most quantum machine learning. No proof of advantage exists. The evidence comes from experiments. So far, it doesn't show full wins on problems anyone needs solved.

Rule of thumb: a quadratic speedup on paper is a red flag to check the extra costs. It is not a green light.

Claim: "Grover search finds a record in an unsorted database of a billion entries quadratically faster." Let's count everything, step by step.

Classical cost. N = 1,000,000,000 records. On average you check half of them before you find the target: 1,000,000,000 / 2 = 500,000,000 lookups.

Quantum query count. Grover needs about (π/4)·√N oracle calls. An oracle is the routine that checks "is this the one?" Let's do the arithmetic:

1. √(1,000,000,000) ≈ 31,623.
2. π/4 ≈ 0.7854. Multiply: 0.7854 × 31,623 ≈ 24,836 oracle calls.
3. That is roughly a 20,000× cut in queries: 500,000,000 / 24,836 ≈ 20,132.

Impressive so far.

The data loading cost. An "oracle call" assumes the database can already be queried in superposition. That is the quantum ability to hold a weighted mix of all the record numbers at once. But say your data is a normal, unsorted file on a disk. To build that quantum-ready structure, you must touch every record at least once. That is at least 1,000,000,000 steps before the first Grover step runs.

An everyday example: a super-fast librarian who can find any book in seconds — but only after every book has been moved into her special library. If you have to carry in a billion books first, her speed doesn't help much.

Full totals.

• Quantum: 1,000,000,000 (loading) + 24,836 (queries) ≈ 1,000,024,836 steps.
• Classical: 500,000,000.

The quantum approach does about 2× more work. And that is before counting error correction, or the fact that each quantum step is now far slower than a normal memory read. The quadratic speedup didn't vanish because the theory is wrong. It vanished because the theory counts queries, and your problem is ruled by moving data. Grover is still truly interesting when the "database" is computed on the fly from a short description. One example is searching for inputs that satisfy a formula. Then there is nothing to load.

Every gate on real hardware fails some of the time. A gate's error rate is that chance of failure. Its fidelity is roughly one minus the error rate. See two-qubit fidelity and fidelity, error, and calibration.

Worked example, using an archetype figure, not any company's number. Say each two-qubit gate fails with chance 0.001 (0.1%). Your algorithm needs 5,000 such gates. The chance that every gate succeeds is (1 − 0.001)⁵⁰⁰⁰. Let's compute it by hand with logarithms:

1. ln(0.999) ≈ −0.0010005.
2. 5000 × (−0.0010005) = −5.0025.
3. So the chance of success is e^−5.0025 ≈ 0.0067, or 0.67%.

That means roughly 7 shots in 1000 are error-free. Worse, you usually can't tell which 7.

Now flip the question. How many gates can you afford if you want at least a 50% chance of success? The chance of success is e raised to −(G × 0.0010005), where G is the number of gates. That stays at 0.5 or above only when G × 0.0010005 ≤ ln 2 ≈ 0.693. (That is because e raised to −0.693 is 0.5.) So G ≤ 692. That is about 700 two-qubit gates at this archetype error rate.

Think of a chain. It is only as strong as its weakest link, and a longer chain has more chances to break. Where the picture breaks: a snapped chain is easy to see. A failed quantum gate usually leaves no visible sign.

Grover on a billion items needs far more than 700 gates. This is why error correction is not optional for the famous algorithms (course: quantum error correction). It is also why circuit depth is a key metric (circuit depth).

Oracle cost. Algorithm papers count abstract queries to an "oracle," a routine that spots or scores answers. On a real machine, that routine must be built from gates. It must also be reversible, meaning it can be run backwards. That often multiplies the gate count many times over. When someone quotes query counts, always ask what one query turns into. Our gate decomposition chapter shows how fast this grows.

The moving baseline. You are not competing against today's classical computers. You are competing against classical computers on the day your quantum solution ships. Think of a race where the finish line keeps moving. Two honest points from the record:

• Classical methods for simulating "quantum advantage" sampling experiments improved by orders of magnitude (many factors of ten) within two years of the 2019 claim. Details are in chapter 5.
• Classical shortcuts for optimization keep improving on exactly the problems quantum methods target. See the optimization reality page.

A use case that beats today's classical baseline by 20% has no safety margin. One that changes the complexity class, like factoring, has a margin measured in orders of magnitude.

Here is the filter applied to today's devices. Current machines have tens to a few thousand physical qubits. Their two-qubit error rates make circuits unreliable beyond a few hundred to a few thousand entangling gates, without correction. No commercially deployed machine runs error-corrected algorithms at useful scale. Error correction is demonstrated at small scale in research labs.

You can check the real, sourced numbers yourself. Browse current QPUs, compare them side by side, and read how to read hardware specs. That way, company claims and independently measured figures won't blur together. Every figure on those pages has a source and a date. Treat any claim without one like an untested speed claim in a code review.

Before you believe any quantum use case, write down:

1. Speedup status: proven superpolynomial, proven quadratic, or heuristic? Only the first survives the extra costs comfortably.
2. Data in: how many steps to load the input? If it grows with the dataset size, a quadratic query speedup is likely dead on arrival.
3. Oracle out: what does one query cost in real gates after compiling?
4. Error budget: total gates × error per gate. Is the chance of success good enough? Or does it need error correction that doesn't yet exist at scale?
5. Baseline: what is the best classical method today, and where is it heading?

The rest of this course is this checklist applied honestly: chemistry, optimization, machine learning, and sampling. Where a case passes, we will say so plainly. Where it fails, we will show the math.