Compare exact and heuristic search
Use an exhaustive reference to evaluate how often faster searches recover the chosen optimum.
Course lessons · 5 of 5
Calculate recovery and regret while distinguishing search guarantees from observed performance.
Useful background: Read the normalized MIP objective
An exact reference answers a finite question
Complete enumeration evaluates every eligible candidate and selects a minimum using the stated tolerance. It becomes expensive as the node count grows exponentially, which is why the recovered experiment uses small systems to establish a reference answer.
A heuristic searches a subset or uses a different traversal. Its output can be compared with the reference through recovery and objective gap. A failed exact recovery can still have a small gap; these metrics answer different questions.
A guarantee has assumptions
Queyranne’s exactness theorem requires the relevant symmetry and submodularity conditions. Dividing an objective by a partition-dependent normalizer can change those properties. A guarantee for an unnormalized function cannot simply be transferred to its normalized ratio.
The recovered comparison also distinguishes independent annealing searches from multiple readout batches of one trained simulated-QAOA circuit. Equal row counts do not make those repetitions statistically equivalent. The original protocol is part of interpreting a recovery rate.
Evaluate a hypothetical five-run search
1Record the reference
Suppose exhaustive search gives J* = 0.5 and three of five independent teaching runs recover it within tolerance.
2Calculate recovery
Divide exact recoveries by completed runs.
3Report a missed run’s gap
If another run returns 0.7, its gap is 0.2. Reporting this alongside recovery shows how far the miss lies from the reference.
Make the idea respond
The laboratory exhaustively enumerates NCut on a small weighted graph. It does not run Queyranne, annealing, or QAOA. Select 2, 3, and 4 nodes to inspect 1, 3, and 7 unique nontrivial splits. Choose a defined candidate row and compare its normalized score with the displayed minimum to calculate its gap manually. A zero-volume candidate remains undefined rather than becoming a successful minimum.
Change one input at a time. Predict what should happen, then compare the computed result with your prediction.
Teaching model · computed in your browser
Find every graph partition
Change a tiny graph and examine every possible split. The minimum is computed by complete enumeration.
A and B are nonempty complementary node sets. cut(A, B) is the sum of edge weights crossing the split, counted once. vol(A) is the sum of weighted degrees of nodes in A, including both ends of internal edges; vol(B) is defined likewise. A zero volume makes this objective undefined. This is a normalized-cut teaching example, not the manuscript’s normalized minimum information partition (MIP). It does not calculate integrated information or benchmark Queyranne, annealing, or QAOA.
Try this: lower the bridge weight to zero. Inspect both the minimum and any undefined partitions. Then switch from two clusters to a cycle.
The default worked example is shown below.
For this split: cut(A, B) = 0.2; vol(A) = 6.2; vol(B) = 6.2. NCut = 0.2 / 6.2 + 0.2 / 6.2 = 0.0645. Every unordered, nonempty bipartition appears once because node A is fixed in the first part.
| Group A | Group B | Cut | vol(A) | vol(B) | NCut |
|---|---|---|---|---|---|
| A | B, C, D, E, F | 2 | 2 | 10.4 | 1.1923 |
| A, B | C, D, E, F | 2 | 4 | 8.4 | 0.7381 |
| A, C | B, D, E, F | 2.2 | 4.2 | 8.2 | 0.7921 |
| A, B, C | D, E, F | 0.2 | 6.2 | 6.2 | 0.0645 · minimum |
| A, D | B, C, E, F | 4.2 | 4.2 | 8.2 | 1.5122 |
| A, B, D | C, E, F | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, C, D | B, E, F | 4 | 6.4 | 6 | 1.2917 |
| A, B, C, D | E, F | 2 | 8.4 | 4 | 0.7381 |
| A, E | B, C, D, F | 4 | 4 | 8.4 | 1.4762 |
| A, B, E | C, D, F | 4 | 6 | 6.4 | 1.2917 |
| A, C, E | B, D, F | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, B, C, E | D, F | 2.2 | 8.2 | 4.2 | 0.7921 |
| A, D, E | B, C, F | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, B, D, E | C, F | 4.2 | 8.2 | 4.2 | 1.5122 |
| A, C, D, E | B, F | 4 | 8.4 | 4 | 1.4762 |
| A, B, C, D, E | F | 2 | 10.4 | 2 | 1.1923 |
| A, F | B, C, D, E | 4 | 4 | 8.4 | 1.4762 |
| A, B, F | C, D, E | 4 | 6 | 6.4 | 1.2917 |
| A, C, F | B, D, E | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, B, C, F | D, E | 2.2 | 8.2 | 4.2 | 0.7921 |
| A, D, F | B, C, E | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, B, D, F | C, E | 4.2 | 8.2 | 4.2 | 1.5122 |
| A, C, D, F | B, E | 4 | 8.4 | 4 | 1.4762 |
| A, B, C, D, F | E | 2 | 10.4 | 2 | 1.1923 |
| A, E, F | B, C, D | 4 | 6 | 6.4 | 1.2917 |
| A, B, E, F | C, D | 4 | 8 | 4.4 | 1.4091 |
| A, C, E, F | B, D | 4.2 | 8.2 | 4.2 | 1.5122 |
| A, B, C, E, F | D | 2.2 | 10.2 | 2.2 | 1.2157 |
| A, D, E, F | B, C | 2.2 | 8.2 | 4.2 | 0.7921 |
| A, B, D, E, F | C | 2.2 | 10.2 | 2.2 | 1.2157 |
| A, C, D, E, F | B | 2 | 10.4 | 2 | 1.1923 |
Inspect the exact adjacency matrix
| Node | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 | 0 |
| B | 1 | 0 | 1 | 0 | 0 | 0 |
| C | 1 | 1 | 0 | 0.2 | 0 | 0 |
| D | 0 | 0 | 0.2 | 0 | 1 | 1 |
| E | 0 | 0 | 0 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 1 | 1 | 0 |
Your turn.
Try an answer before opening a hint. Feedback will explain the result, and you can practice again.
Interactive practice is loading. The lesson, worked example, and printable questions remain available below.
View printable practice and solutions
Use these questions when studying without interactive controls. Opening a written solution does not earn progress.
An optimizer recovers the reference optimum in 8 of 10 teaching runs. What is its recovery percentage?
Read the solution
8/10 × 100 = 80 percent.
A reference score is 0.4 and a valid returned score is 0.55. What is the objective gap?
Read the solution
The gap is 0.15.
A normalized objective has not been shown submodular. Which claim about Queyranne is justified?
- It is automatically exact because the raw objective has the right name.
- It cannot ever find a good answer.
- Its output proves quantum advantage.
- Its performance must be evaluated for that objective; the usual guarantee has not been established.
Read the solution
The algorithm can be tested, but its exactness guarantee cannot be assumed without the required conditions.
In the recovered study, what are multiple QAOA readout batches from one trained circuit?
- Independently trained circuits by definition.
- Quantum-hardware experiments.
- Proof that every network is solved exactly.
- Repeated samples from that trained circuit.
Read the solution
Readout batches sample one trained simulated circuit; they are not independent training repetitions.
Follow the original record
Use the definitions you just practiced to read the project’s own notation, assumptions, and evidence.
The ideas to keep
- Compare recovery and objective gap.
- Verify a theorem’s conditions for the actual objective.
- Describe what each repetition really repeats.
Reading completion is separate from your practice evidence.
Progress is kept in this browser. How learning works