Part VIII. Applications and Strategy · Chapter 67
Optimization: Where Caution Is Required
Optimization is where quantum ambition meets its strongest opponent: decades of tuned classical heuristics. This chapter gives you the checks that separate a real quantum advantage from a benchmark that was rigged by accident.
In this chapter 9 sections
A credible optimization result fixes the instance distribution, constraint semantics, quality-time-cost objective, strongest tuned classical comparator, parameter and shot budget, and held-out evaluation before the quantum result is inspected.
Optimization comparisons are unusually easy to bias because a solver can look strong by changing the instance mix, feasibility rule, tuning budget, time boundary, or reported statistic. The protocol must be frozen before the test set is opened. Otherwise the experiment measures the research team’s ability to select favorable cases.
Write the optimization contest before choosing a solver
The contest uses paired instances and a lexicographic outcome: feasibility first, then objective quality at a declared time or cost. Both solvers receive equivalent preprocessing information and a recorded tuning budget. Quantum shots, queue time, parameter search, and post-processing belong inside the quantum entry; classical presolve and tuning belong inside the comparator entry.
- Objective
- The quantity actually scored, including penalties.
- Feasibility
- The constraint test applied to every returned sample.
- Comparator
- A named, tuned classical method under the same time and quality budget.
- Uncertainty
- Intervals over seeds, instances, and quantum sampling.
Benchmark protocol for quality, time, and feasibility
QAOA supplies a particular variational algorithm, Grover supplies an oracle-model query result, and the polynomial lower-bound paper shows why the access model matters. The NISQ review and benchmarking perspective explain the extra experimental boundaries. None supports deleting failed or infeasible instances from an application comparison.
Held-out routing instances reveal selection bias
ROW_FIELDS = {"instance": str, "classical_cost": int, "quantum_cost": int,
"cost_unit": str, "quantum_feasible": bool}
def score_benchmark(card, win_threshold):
errors = []
if card.get("scenario") != "held-out routing benchmark" or not card.get("source_ids"):
errors.append("scenario_or_sources")
if type(card.get("test_frozen")) is not bool or type(card.get("tuning_minutes")) is not int:
errors.append("freeze_or_tuning_type")
if card.get("tuning_unit") != "minutes" or not card.get("test_frozen"):
errors.append("freeze_or_tuning_unit")
winners = []
for row in card.get("rows", []):
missing = [name for name, kind in ROW_FIELDS.items()
if name not in row or type(row[name]) is not kind]
if missing or row.get("cost_unit") != "route-cost units":
errors.append(row.get("instance", "row") + "_schema")
continue
winners.append("quantum" if row["quantum_feasible"] and
row["quantum_cost"] < row["classical_cost"] else "classical")
wins = winners.count("quantum")
decision = "invalid" if errors else ("retest" if wins >= win_threshold else "no-advantage")
return {"decision": decision, "errors": sorted(set(errors)), "winners": winners,
"quantum_wins": wins, "reported_tuning_minutes": card.get("tuning_minutes")}
card = {"scenario": "held-out routing benchmark", "source_ids": ["benchmarking-2025"],
"test_frozen": True, "tuning_minutes": 47, "tuning_unit": "minutes",
"rows": [{"instance": "route-a", "classical_cost": 101, "quantum_cost": 99,
"cost_unit": "route-cost units", "quantum_feasible": True},
{"instance": "route-b", "classical_cost": 108, "quantum_cost": 106,
"cost_unit": "route-cost units", "quantum_feasible": False},
{"instance": "route-c", "classical_cost": 95, "quantum_cost": 98,
"cost_unit": "route-cost units", "quantum_feasible": True}]}
base_result = score_benchmark(card, 2)
bad = {**card, "rows": [{key: value for key, value in card["rows"][0].items()
if key != "quantum_feasible"}, *card["rows"][1:]]}
bad_result = score_benchmark(bad, 2)
improved = {**card, "rows": [*card["rows"][:2], {**card["rows"][2], "quantum_cost": 94}]}
improved_result = score_benchmark(improved, 2)
assert base_result["winners"] == ["quantum", "classical", "classical"]
assert bad_result["decision"] == "invalid" and "route-a_schema" in bad_result["errors"]
assert improved_result["decision"] == "retest" and improved_result["quantum_wins"] == 2
print(f"PASS: 67 benchmark base_wins={base_result['quantum_wins']} invalid={bad_result['errors']} counterfactual={improved_result['decision']} tuning={base_result['reported_tuning_minutes']}min")In the paired routing record, the quantum candidate wins objective value on two instances but returns one infeasible route. Under the pre-registered rule that result is a loss, not a row to omit. The classical heuristic wins two of three paired decisions. A best-run plot could tell the opposite story; the full table cannot.
Artifact contract. A dated instance split, comparator contract, feasibility metric, and executable paired-result evaluator. The evaluator rejects infeasible solutions, computes paired wins without dropping losses, and prevents test-set tuning.
| Instance | Classical cost | Quantum cost | Quantum feasible | Paired winner |
|---|---|---|---|---|
| route-a | 101 | 99 | yes | quantum |
| route-b | 108 | 106 | no | classical |
| route-c | 95 | 98 | yes | classical |
Exact validation command: python3 tools/validate_briefs.py --briefs data/editorial_briefs_64_87.json --from 64 --through 87 --check-rewritten-sources --execute-artifacts
Sampling and tuning belong in the resource account
The appropriate response is to preserve the benchmark and improve the candidate without touching the held-out set. A new algorithm or tuning policy gets a new registered run, including all costs. Reopening the instance set after seeing losses creates a new experiment and must be labeled as such. This discipline is more valuable than a premature advantage label.
Design a comparator that can win
Prompt. Pre-register a 20-instance benchmark for a constrained routing or scheduling task.
Deliverable. Train/test split, feasibility rule, quality-time metric, tuned classical comparator, shot and tuning budget, and paired decision rule.
Pass condition. The test set remains untouched until freeze, infeasible answers cannot win on objective value, and all solver tuning time enters the reported cost.
Model answer: no advantage on the declared routing set
Format. Reference paired benchmark in which the classical heuristic wins the declared end-to-end metric.
The model answer reports zero infeasible classical solutions, one infeasible quantum solution, and a 2–1 paired win for the classical baseline. It states that three instances are too few for a general performance claim. The output supports a narrow engineering conclusion: this candidate did not beat the declared comparator on the frozen set. It says nothing about every QAOA variant or every routing distribution.
Verification. The executable fixture retains every registered instance, verifies feasibility before scoring, and reproduces the decision from the table.
Companion work
Artifacts for this chapter
These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.
evidence dossier
Pre-registered optimization benchmark
Reproduce or test
python3 tools/validate_briefs.py --briefs data/editorial_briefs_64_87.json --from 64 --through 87 --check-rewritten-sources --execute-artifacts
Provenance
Sources and review
- Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv. 2014primary preprint
- Lov K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of STOC. 1996primary paper
- Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM. 2001primary paper
- U.S. Government Accountability Office. Quantum Computing and Communications: Status and Prospects. GAO. 2021government technology assessment
- OpenQASM Technical Steering Committee. OpenQASM 3 specification. Linux Foundation Joint Development Foundation. 2026official technical specification
- IBM Quantum. Qiskit documentation. IBM. 2026official documentation
- Timothy Proctor et al.. Benchmarking quantum computers. Nature Reviews Physics. 2025peer-reviewed perspective
- Kishor Bharti et al.. Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics. 2022peer-reviewed review
The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.