How to Evaluate a Quantum Use Case

Quantum computing genuinely offers speedups for some problems. The trouble is that almost every popular claim quotes the speedup for one isolated step and silently ignores everything around it: getting data in, getting answers out, and surviving hardware errors. This chapter builds a five-question filter you can apply to any claim. Every later chapter in this course applies it to one application area.

The five questions:

1. Is the speedup verified? Is it a mathematically proved advantage, or a heuristic hope?
2. What does data loading cost? A quantum computer cannot act on your data until the data is inside a quantum state.
3. What does each oracle call cost? Many algorithms are quoted in abstract 'queries' whose real cost is hidden.
4. Does the error budget survive? Every gate on real hardware fails with some probability, and failures compound.
5. Is the classical baseline moving? Classical algorithms and hardware improve while the quantum roadmap unfolds.

A use case that passes all five is rare. That is not pessimism; it is why the few survivors (covered in quantum simulation and post-quantum cryptography) matter so much. For context on what has actually been demonstrated, see our quantum advantage reality page.

A few definitions, since you may be landing here directly. A qubit is the quantum version of a bit; its state is described by amplitudes, complex numbers whose squared magnitudes give measurement probabilities (see probability amplitudes). An algorithmic speedup means the quantum algorithm needs fundamentally fewer steps as the problem grows, not that any one step is faster.

Speedups come in tiers, and the tier decides everything:

• Proved, superpolynomial. Superpolynomial means the gap over classical grows faster than any fixed power of the problem size; exponential growth is the familiar example. Shor's factoring algorithm and simulating quantum physics itself. These change what is computable in practice, assuming large error-corrected machines. This is proved theory; the machines are not yet built.
• Proved, quadratic. Grover's search: a task needing N steps classically needs about √N quantum queries. Proved in the abstract query model, a way of counting cost that tallies only the calls to an answer-checking subroutine and ignores what each call itself costs, but fragile in practice, as the next section shows.
• Heuristic. QAOA for optimization and most quantum machine learning. No proof of advantage exists; evidence is empirical and, so far, does not show end-to-end wins on problems anyone needs solved.

Rule of thumb: a quadratic speedup on paper is a red flag to check the overheads, not a green light.

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

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

Quantum query count. Grover needs about (π/4)·√N oracle calls. √(1,000,000,000) ≈ 31,623. Multiply: 0.7854 × 31,623 ≈ 24,836 oracle calls. That is roughly a 20,000× reduction in queries: 500,000,000 / 24,836 ≈ 20,132. Impressive so far.

The data loading cost. An 'oracle call' assumes the database is already queryable in superposition: the quantum ability to hold a weighted combination of all indices at once. For unstructured classical data sitting on a disk, building that queryable structure requires touching every record at least once: at least 1,000,000,000 operations before the first Grover step runs.

End-to-end totals. Quantum: 1,000,000,000 (loading) + 24,836 (queries) ≈ 1,000,024,836 operations. Classical: 500,000,000. The quantum approach does about 2× more work, before counting error correction or the fact that each quantum operation is currently far slower than a classical memory read. The quadratic speedup did not vanish because the theory is wrong; it vanished because the theory counts queries and your problem is dominated by data movement. Grover remains genuinely interesting where the 'database' is computed on the fly from a small description (for example, searching for inputs satisfying a formula), because then there is nothing to load.

Every gate on real hardware fails with some probability. The error rate of a gate is that failure probability; 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 vendor's number: suppose each two-qubit gate fails with probability 0.001 (0.1%). Your algorithm needs 5,000 such gates. The probability that every gate succeeds is (1 − 0.001)⁵⁰⁰⁰. Compute it by hand via logarithms: ln(0.999) ≈ −0.0010005, and 5000 × (−0.0010005) = −5.0025, so the success probability is e^−5.0025 ≈ 0.0067, or 0.67%. Roughly 7 shots in 1000 are error-free, and worse, you usually cannot tell which 7.

Invert the question: how many gates can you afford if you demand at least 50% success? Success is e raised to −(G × 0.0010005), and that stays at or above 0.5 exactly when the exponent's size G × 0.0010005 ≤ ln 2 ≈ 0.693 (because e raised to −0.693 is 0.5), so G ≤ 692: about 700 two-qubit gates at this archetype error rate. Grover on a billion items needs vastly more. This is why error correction (course: quantum error correction) is not optional for the famous algorithms, and why circuit depth is a first-class metric (circuit depth).

Oracle cost. Algorithm papers count abstract queries to an 'oracle', a subroutine that recognizes or scores answers. On a real machine that subroutine must be built from gates, reversibly, which often multiplies the gate count by large factors. When someone quotes query counts, always ask what one query compiles to; our gate decomposition chapter shows how quickly this grows.

The moving baseline. You are not competing against today's classical computing but against classical computing on the day your quantum solution ships. Two honest observations from the record: classical algorithms for simulating 'quantum advantage' sampling experiments improved by orders of magnitude within two years of the 2019 claim (details in chapter 5), and classical heuristics for optimization keep improving on exactly the problems quantum methods target (optimization reality page). A use case that beats today's classical baseline by 20% has no margin; one that changes the complexity class, like factoring, has margin measured in orders of magnitude.

Applying the filter to current devices: today's machines have tens to a few thousand physical qubits with two-qubit error rates that make circuits beyond a few hundred to a few thousand entangling gates unreliable, uncorrected. No commercially deployed machine runs error-corrected algorithms at useful scale; error correction is demonstrated at small scale in research settings. You can check the real, sourced numbers yourself: browse current QPUs, compare them side by side, and read how to read hardware specs so that vendor-claimed and independently measured figures do not blur together. Every figure on those pages carries a source and a date; treat any claim without one the way you would treat an unbenchmarked performance claim in a pull request.

Before believing any quantum use case, write down:

1. Speedup status: proved superpolynomial, proved quadratic, or heuristic? Only the first survives overheads comfortably.
2. Data in: operations needed to load the input. If it scales with the dataset size, a quadratic query speedup is likely dead on arrival.
3. Oracle out: what one query costs in real gates after compilation.
4. Error budget: total gates × per-gate error; is the success probability acceptable, or does it require error correction that does not yet exist at scale?
5. Baseline: the best classical method today, and its trajectory.

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 arithmetic.