Case Study: Auditing a Quantum Advantage Claim

"The first principle is that you must not fool yourself — and you are the easiest person to fool." — Richard Feynman

Executive Summary

A press release lands in your inbox. A quantum hardware startup announces that its 84-qubit processor has "solved in 12 minutes a problem that would take a classical supercomputer 47 years." Your CTO forwards it with one line: "Should we be worried that our competitors are buying these?"

Your job is not to be impressed and not to be dismissive. It is to decompose the claim into its checkable parts. In this case study you will take a realistic advantage claim apart using only Chapter 1 material — complexity classes, the difference between structured and unstructured speedups, and the distinction between a sampling milestone and a useful computation — and produce a one-page assessment your CTO can act on.

Skills applied

  • Distinguishing a sampling task from a decision or optimization task (§1.3, §1.4).
  • Identifying which complexity class a claimed speedup would actually live in (§1.3).
  • Recognizing the "best known classical algorithm" moving target (§1.6).
  • Separating physical qubits from logical qubits (§1.6).
  • Translating a technical assessment into a business recommendation (§1.8).

Background

The claim, verbatim

"QubitDyne's Meridian-84 processor has demonstrated quantum advantage on a commercially relevant optimization workload. In benchmark trials, Meridian-84 sampled the solution space of a 60-variable portfolio-allocation problem in 12 minutes. A classical supercomputer performing the same calculation by brute force would require an estimated 47 years. Meridian-84 is available now through our cloud platform."

Four sentences. At least five things in them require scrutiny.

What we know from the chapter

Three facts from Chapter 1 do most of the work here:

  1. Quantum speedups are problem-specific. There is no general "quantum computers are faster." Exponential speedups are known for factoring, discrete log, and simulating quantum systems — problems with exploitable algebraic or physical structure. Unstructured search gets a quadratic speedup and no more, by the BBBV lower bound.
  2. Optimization is not on the exponential-speedup list. Combinatorial optimization is the single most over-claimed application area in the field. QAOA (Chapter 20) is a heuristic with no proven advantage over the best classical heuristics.
  3. Physical qubits are not logical qubits. An 84-qubit uncorrected device has an error rate that limits usable circuit depth to hundreds of gates at best.

Phase 1: What kind of problem is this, really?

The claim says "sampled the solution space." That word is doing enormous work.

Sampling means: produce bitstrings distributed according to some probability distribution. This is exactly what the 2019 Sycamore experiment did — random circuit sampling — and it is a legitimate way to demonstrate that a device is hard to simulate classically. It is not the same as solving an optimization problem, which requires producing a specific high-quality solution and being able to verify it.

Ask: does the machine output an allocation, and is that allocation better than what a classical solver produces? If the answer is "it samples from a distribution over allocations," the claim is a physics result wearing a finance costume.

First finding. The claim conflates sampling with solving. These are different computational tasks with different success criteria.

Phase 2: The "47 years" baseline

Every advantage claim has an implicit classical comparison, and the comparison is where claims usually break. The press release says "by brute force."

Brute force over 60 binary variables is $2^{60} \approx 1.15 \times 10^{18}$ evaluations. At a billion evaluations per second, that is indeed about 36 years — the 47-year figure is roughly right for brute force.

But nobody solves a 60-variable portfolio problem by brute force. Classical practice uses branch-and-bound, convex relaxation, simulated annealing, or a commercial mixed-integer solver, any of which handles 60 variables in seconds to minutes. The relevant comparison is not "quantum vs. brute force," it is "quantum vs. the best classical method a competent team would actually use."

This is precisely the failure mode that deflated the Sycamore headline: the original claim used one classical simulation strategy, and better strategies shrank the gap by orders of magnitude.

Second finding. The baseline is a straw man. A correct comparison is against a tuned classical solver, and the burden of proof is on the vendor to run it.

Phase 3: Physical versus logical qubits

Eighty-four qubits sounds substantial, but Chapter 1 established the currency conversion. With no error correction, every gate injects error, and circuit fidelity decays roughly as $(1-\epsilon)^{g}$ for $g$ gates at error rate $\epsilon$. At a two-qubit gate error of $10^{-3}$ — competitive today — a circuit of 1,000 two-qubit gates retains fidelity $\approx 0.999^{1000} \approx 0.37$.

So ask: how deep is the circuit, and what is the measured two-qubit gate fidelity? If the vendor will not state both numbers, the claim is unfalsifiable.

Then ask the harder question: how many of these qubits are error-corrected? For an 84-qubit NISQ device the answer is zero, and at surface-code overheads of ~1,000 physical qubits per logical qubit, 84 physical qubits is not one logical qubit.

Third finding. 84 physical qubits, uncorrected, cannot run a deep enough circuit to outclass a classical optimizer on a real instance.

Phase 4: Is the result verifiable?

A crucial asymmetry: for factoring, you can check the answer instantly by multiplying. For sampling tasks, verification is itself classically hard — which is why supremacy experiments rely on statistical cross-entropy benchmarking rather than checking answers.

For an optimization claim, verification is easy: run the classical solver, compare objective values. The fact that a vendor reports a time rather than a solution quality comparison is itself evidence.

Fourth finding. The claim reports the wrong metric. For optimization, the headline number should be objective value at fixed time budget, not time at unspecified quality.

Phase 5: The assessment

Your one-page memo:

Claim status: not substantiated. The announcement describes a sampling demonstration, compares it against a brute-force baseline no practitioner would use, does not report solution quality, does not report gate fidelity or circuit depth, and involves a device with zero error-corrected qubits.

Is our competitive position at risk? No. If competitors purchase access, they acquire a research platform, not an optimization advantage. There is no known quantum algorithm with a proven advantage for portfolio optimization.

What would change this assessment? A peer-reviewed result showing better objective values than a tuned classical solver at equal wall-clock time on a published benchmark instance, reproducible by a third party.

What should we actually do? Two things, neither of which involves buying hardware. First, begin post-quantum cryptography migration planning — that threat is real, dated, and independent of any vendor's optimization claims (Chapter 30). Second, if quantum matters to our roadmap at all, it is through quantum simulation for materials or chemistry (Chapter 17), not optimization.

Discussion Questions

  1. The vendor's 47-year figure was arithmetically correct. Why is an arithmetically correct number still misleading here, and what does that suggest about auditing claims generally?
  2. Sycamore's random circuit sampling task had no practical use whatsoever, yet it is regarded as an important result while this portfolio claim is not. Defend that distinction.
  3. If the vendor had reported "matched the classical solver's objective value in comparable time," would that be interesting? To whom, and why?
  4. What would you need to see before recommending a genuine quantum pilot project?

Your Turn: Extensions

  • Rewrite the press release so that it is honest while still describing a real technical achievement. Notice how much of the excitement survives.
  • Estimate the circuit depth needed for a QAOA instance on 60 variables at $p=3$ (you will be able to do this precisely after Chapter 20) and compare it against the depth budget implied by a $10^{-3}$ gate error rate.
  • Find a real quantum advantage announcement from the past three years and run this five-phase audit on it.

Key Takeaways

  • The two questions that break most advantage claims: compared against which classical algorithm? and what is the task, exactly?
  • Sampling milestones and useful computations are different things; press releases blur them.
  • Physical qubit counts are marketing numbers. Logical qubit counts, gate fidelities, and circuit depths are engineering numbers.
  • Optimization is the most over-claimed quantum application area. Simulation is the most under-claimed.
  • Skepticism about hardware claims is entirely compatible with taking the post-quantum cryptography timeline seriously — those are independent judgments.