Choose baselines that answer the question
Use exact and simple references before interpreting a sophisticated method.
Course lessons · 2 of 5
Select comparison methods and metrics that match the same problem.
Useful background: Compare exact and heuristic search
A baseline supplies a meaningful reference
The normalized MIP experiment can enumerate all eligible partitions on small instances, giving a reference optimum. Uniform sampling provides a simple search baseline. More elaborate methods are then compared against the same objective and candidate set.
A baseline must be implemented and measured under an explicit protocol. Comparing one method’s best case with another method’s average, or comparing different objectives without labeling them, changes the question and can make a ranking misleading.
In the teaching lab, NCut equals cut(A,B)/vol(A) + cut(A,B)/vol(B), where a side’s volume is its weighted-degree sum. It is a different defined baseline problem from the manuscript’s normalized information objective. Keep that distinction when translating the experimental procedure between them.
Separate optimization quality from computational cost
Recovery rate measures how often a method finds the reference optimum under the selected tolerance. Objective gap measures the quality of a miss. Runtime and evaluation count describe resources. None of these quantities automatically replaces the others.
The recovered study includes distinct budgets and repetition types. Circuit training, objective-table preparation, and sampling have different costs. Report the scope of timing instead of implying that a small timed substep represents every cost of a method.
Design a small search comparison
1Fix the problem
Choose one four-node teaching graph, the laboratory’s explicit normalized-cut objective, and the seven unique nontrivial bipartitions. Compute every valid NCut score, preserving undefined zero-volume cases as such.
2Define simple and advanced searches
A uniform baseline samples eligible candidates according to a stated policy. A heuristic selects candidates using its rule. Both must return a valid split scored by the same NCut function; a raw cut sum cannot silently replace that function.
3Compare outcomes and resources
Record recovery, gap, number of objective evaluations, and timing scope. The example does not claim any new benchmark result; it specifies how one should be measured.
Make the idea respond
The laboratory enumerates normalized cut, not raw cut alone. Select 4 nodes, Chain, and bridge weight 2: the edges are 1, 2, 1. The split {0,1} | {2,3} has cut 2, side volumes 4 and 4, and NCut 1. Use the same objective and graph for every comparison. This laboratory does not run the manuscript’s information objective or its heuristic benchmark methods.
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 eight-node set has how many unique nontrivial bipartitions under the fixed-anchor convention?
Read the solution
There are 128 − 1 = 127 candidates.
Which comparison isolates search quality on a chosen objective?
- Give each method a different objective and hide the difference.
- Compare the fastest run of one with the slowest of the other only.
- Rank methods by the complexity of their names.
- Evaluate both methods on the same instances, objective, and valid candidate set.
Read the solution
The same defined problem supports an interpretable search comparison.
A method uses 20 objective evaluations per run for 5 runs. How many evaluations are recorded in total?
Read the solution
The total is 100 objective evaluations.
Why include uniform sampling when testing an elaborate optimizer?
- It removes the need for an exact reference.
- It establishes real quantum-hardware performance.
- It shows performance relative to a simple explicit search policy.
- It guarantees the elaborate method must lose.
Read the solution
Uniform sampling provides a simple measured reference for the same candidate space.
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 the same problem.
- Use both simple and exact references where feasible.
- Report timing and evaluation budgets with their scope.
Reading completion is separate from your practice evidence.
Progress is kept in this browser. How learning works