Measuring the gap

Grover's algorithm has a clean theoretical story: unstructured search in O(√N) queries instead of the classical O(N). For a database of 32 entries that's 4 optimal iterations instead of up to 32. The math is sound, the circuit is well-understood, and the ideal-simulator result confirms it — at N=32 the marked answer comes out with P=1.00 on a noiseless simulation. Then you run the same circuit on real quantum hardware, and the number is [hardware capture pending].

That gap is the whole post. Not as a failure story — the hardware is doing what physics allows — but as a precise measurement of what "NISQ" means in practice: the circuit depth required to express the speedup exceeds what current hardware can execute without noise destroying the interference pattern you need.

The experiment

The benchmark is Grover's algorithm against classical linear search, run for search-space sizes N ∈ {8, 16, 32} (n ∈ {3, 4, 5} qubits). Each N was run with four distinct marked states and five outer repetitions; the device numbers are means across those runs with run-to-run spread recorded.

The contrast algorithm is Bernstein–Vazirani (BV): recover a hidden n-bit string in a single oracle query. BV is also a quantum algorithm, but it uses a shallow circuit — one layer of controlled-X gates into a phase-kickback ancilla. Where Grover's circuit depth grows with N, BV stays flat. If the failure is genuinely "quantum computers can't do this," BV should collapse too. If the failure is circuit depth × gate error, BV should survive. The data resolves this unambiguously.

For a full walkthrough of what the circuits are actually doing — How Grover's search actually works →

The headline result — collapse across N

Three series: the ideal simulator (flat near 1.0), classical search (always correct by construction), and the device. On the ideal simulator Grover at N=8 returns the marked answer with P≈0.94, N=16 with P≈0.96, N=32 with P≈1.00. On the device: N=8 gives [hardware capture pending], and by N=32 the result is [hardware capture pending] — at or near the random floor of 1/32 ≈ 0.03.

Ideal-simulator data from Aer (reproducible). Device data: hardware capture pending.

Why not just run more iterations?

Grover is not a monotone algorithm. Each oracle + diffuser iteration rotates the amplitude state toward the marked answer by a fixed angle. Run the right number of iterations (≈ π/4 · √N) and you land near the top. Keep going and you rotate past the peak and the probability drops. At N=16 the optimal count is 3 iterations, giving P≈0.96 — then it falls to 0.59 at the next step.

Ideal simulator only (Aer). Shows the amplitude-amplification oscillation — a controlled rotation you can overshoot. No QPU time required.

The mechanism: gate error × depth

The collapse isn't random hardware failure — it follows directly from how Grover's circuit scales. Each iteration adds another oracle + diffuser layer, both of which decompose into multi-controlled gates that the transpiler expands into sequences of two-qubit CX or ECR gates. The transpiled circuit depth at N=32 is roughly 18 layers. BV at N=32 transpiles to a single layer.

Each physical gate has an error rate. IBM Heron-class devices run at ~0.1–0.3% per two-qubit gate under current calibration. A Grover circuit at N=32 decomposes into 288 two-qubit gates when transpiled to a CX basis — the committed two_qubit_gates_decomposed figure — before device routing adds more. Compound that error and the fidelity of the final state is degraded to near-random before you measure. BV's shallow circuit escapes this compound loss.

Aer-transpiled depths. On real hardware the depth will be higher due to routing overhead and native gate decomposition — the ratio is the signal, not the absolute numbers.

The contrast: BV survives where Grover collapses

Bernstein–Vazirani solves a different problem (hidden string recovery) but uses the same quantum resource class. Its circuit is shallow by construction — one superposition layer, one oracle layer, one measurement. On the ideal simulator both BV and Grover sit near 1.0 across all N. On the device, BV at N=32 gives P≈[hardware capture pending] while Grover at N=32 gives P≈[hardware capture pending]. The gap is not "quantum doesn't work." It is "circuits this deep don't work on current hardware."

Solid lines: device. Dashed lines: ideal simulator reference. Device lines pending hardware capture.

The asymptotic picture — theory, not measurement

The theoretical speedup is real. O(√N) grows slower than O(N) — for large enough N, a fault-tolerant quantum computer running Grover would win. The problem is that "large enough N" and "fault-tolerant" require error-correction overheads that are not available on current NISQ hardware. The crossover point is not in the range of anything we can usefully run today.

Theory chart — not a measurement. The O(√N) advantage requires fault-tolerant quantum error correction; the crossover is far beyond NISQ device capabilities.

Does error mitigation help?

Dynamical decoupling (DD) and measurement twirling are the standard mitigation toolkit on IBM hardware. The panel below compares Grover device success with mitigation off vs on across N. Significance is assessed per N from run-to-run spread: where the off and on intervals overlap, no effect is claimed; where they are disjoint, the signed difference (off−on) is shown. Device data is pending; the panel will update once the capture run is committed.

Error bars show run-to-run spread (4096 shots per run). Hardware capture pending.

Where quantum advantage is actually landing in 2026

The result above is specific: Grover's algorithm for unstructured search, on NISQ hardware, today. It doesn't generalise to all quantum computing. The problems where serious advantage claims are being made are structurally different:

• –Quantum simulation of physical systems (chemistry, materials). This is the originally-intended use case for quantum hardware — simulating quantum systems is naturally suited to quantum computers. Google's 2025 claims around superconductor simulation and IBM's molecular-energy calculations are in this class. These are recent results awaiting independent replication, but they are the credible frontier.
• –Variational quantum eigensolvers (VQE) and quantum approximate optimisation (QAOA) for small problem instances. Current results are roughly par-with-classical on matched hardware, not a win — but the trajectory is meaningful.
• –Quantum key distribution and quantum communication protocols. These are already deployed commercially and don't depend on the gate-depth problem at all.

None of these are the Grover unstructured-search story. The mechanism is different (the speedup is exponential for simulation, not quadratic), the circuit structure is different (often variational, not fixed-iteration), and the error budget is different (shorter circuits that survive current noise levels better).

The finance angle — a sidebar

Finance has been one of the most heavily marketed quantum sectors. The realistic 2026 picture: on small-instance portfolio optimisation and option-pricing problems, quantum hardware has reached par-with-classical on matched problem sizes. That is an important engineering milestone — it means the hardware is doing something coherent on a finance-relevant workload. It is not a production win, and no credible result shows quantum beating a well-tuned classical solver on any finance problem at useful scale. The honest characterisation is: promissory, advancing, not yet competitive.

Reproducibility caveats

Takeaway

Quantum computing is real and advancing. The theoretical speedups are mathematically sound. What current hardware cannot do is execute the deep circuits needed to realise those speedups at any practically interesting problem size, because gate error accumulates faster than the algorithm can produce a useful signal. The gap is not hype — it's physics, and it's measurable. When you run Grover at N=32 and read back the random floor, you've measured exactly where the fault-tolerance wall is.

Classical silicon wins for these workloads today. That isn't a permanent statement — it's a calibration point. The relevant question is how far the hardware needs to advance before the gap closes, and for which problem classes it closes first. The simulation class is the honest answer to the second question; the fault-tolerance overhead is the honest answer to the first.

Methodology note — why this isn't a numbered demo