Case Study 1: The Algorithm That Did Not Fit

"We counted the gates. We were counting the wrong gates."

Executive Summary

A team plans a six-qubit variational experiment. They count the two-qubit gates in their circuit — thirty, comfortably inside a budget of a hundred — and submit. The results are noise.

The circuit they wrote has thirty CNOTs. The circuit that ran has ninety, because their ansatz entangles every pair and the device connects each qubit to at most three neighbors. The extra sixty are SWAPs, inserted silently, at three CNOTs each.

This case study works through the diagnosis, then fixes it three ways — measuring each — and ends with the design rule that would have prevented it. The fix that works best costs nothing and changes one keyword argument.

Skills applied: routing cost (§10.3); optimization levels (§10.5); entanglement patterns (Ch. 8 §8.7); the transpiled-count audit (Ch. 6 §6.5).

Reproducibility. FakeSherbrooke, seed_transpiler=42, entirely local.

The Plan

from qiskit.circuit.library import efficient_su2

ansatz = efficient_su2(6, entanglement="full", reps=2)
print(f"logical two-qubit gates: {dict(ansatz.decompose().count_ops())['cx']}")

logical two-qubit gates: 30

The team's reasoning, and it is not unreasonable:

"Thirty two-qubit gates. Chapter 1 said the budget is a few hundred. At a 0.75% two-qubit error rate, thirty gates gives $(1-0.0075)^{30} \approx 80\%$ chance of an error-free run. Comfortable."

Every number in that paragraph is correct. The conclusion is wrong.

The Diagnosis

pm = generate_preset_pass_manager(optimization_level=1, backend=backend, seed_transpiler=42)
isa = pm.run(ansatz)
print(f"transpiled two-qubit gates: {two_qubit_count(isa)}")

transpiled two-qubit gates: 90

Ninety, not thirty. Redo the success arithmetic: $(1-0.0075)^{90} \approx 51\%$, not 80% — and that is before the depth-driven decoherence that sixty extra gates also bring.

The reason is visible the moment you compare the circuit's connectivity to the device's.

entanglement="full" on six qubits means every one of the fifteen pairs must interact. The device's qubits have at most three neighbors. Most of those fifteen pairs are not adjacent, so each one requires the router to walk the qubits together — and every step costs a SWAP, and every SWAP costs three CNOTs.

The general measurement, from §10.3:

   n | logical | all-to-all transpiled | ratio | chain transpiled | ratio
  ---|---------|-----------------------|-------|------------------|------
   4 |       6 |                    12 |  2.0x |                3 |  1.0x
   5 |      10 |                    18 |  1.8x |                4 |  1.0x
   6 |      15 |                    33 |  2.2x |                5 |  1.0x
   7 |      21 |                    44 |  2.1x |                6 |  1.0x

The ratio grows with $n$ for the mismatched circuit and stays at exactly 1.0 for the matched one.

Fix 1: Raise the Optimization Level (free, partial)

The first thing to try, because it costs one integer.

  level | 2q gates | vs logical 30
  ------|----------|---------------
    0   |    114   |     3.8x
    1   |     90   |     3.0x
    2   |     80   |     2.7x
    3   |     83   |     2.8x

Level 0 to level 2 removed thirty-four two-qubit gates — a 30% reduction, from nothing but better layout and routing. Note also that level 3 is worse than level 2 here (83 vs 80), which is §10.5's warning arriving in practice.

This is real and it is nowhere near enough. Eighty is still 2.7× the logical count, and the circuit is still overwhelmingly routing-dominated.

Verdict: always do this, never stop here.

Fix 2: Best-of-N Seeds (nearly free, small)

From §10.9: SABRE is randomized, so sample it.

best = min((pm_with_seed(s).run(ansatz) for s in range(8)),
           key=lambda c: (two_qubit_count(c), c.depth()))

On the routing-limited circuit of §10.9 this bought about 10% for 31 milliseconds. On this ansatz the gain is similar — a few gates, essentially free.

Verdict: always do this too. It is milliseconds against a circuit you will run thousands of times. But it does not change the shape of the problem.

Fix 3: Change the Entanglement Pattern (free, decisive)

The actual fix, and it is one keyword.

ansatz = efficient_su2(6, entanglement="linear", reps=2)     # was "full"

Measured at $n = 6$, reps=2, all four optimization levels:

From eighty transpiled gates to ten. An eightfold reduction, and the routing overhead vanishes entirely — linear transpiles to exactly its logical count at every optimization level, because a chain maps onto a chain with no movement required.

Note circular, which is instructive. Chapter 8's logical table made it look cheap: twelve gates against full's thirty. After routing it needs forty — still less than full's eighty in absolute terms, but with the worst ratio of all four, because that single wrap-around link from qubit $n-1$ back to qubit 0 requires walking a qubit the entire length of the chain.

A logical gate count cannot tell you which pattern is cheap. Only the transpiled count can.

And it gets worse with size

   n | full logical -> transpiled | ratio | linear logical -> transpiled | ratio
  ---|----------------------------|-------|------------------------------|------
   4 |         12 ->  21          | 1.75x |            6 ->   6          | 1.00x
   6 |         30 ->  80          | 2.67x |           10 ->  10          | 1.00x
   8 |         56 -> 156          | 2.79x |           14 ->  14          | 1.00x
  10 |         90 -> 284          | 3.16x |           18 ->  18          | 1.00x

At ten qubits, full needs 284 two-qubit gates and linear needs 18 — a factor of nearly sixteen. Against Chapter 1's few-hundred budget, full at ten qubits is already out of reach and linear has room for a great deal more depth.

⚠️ Common Pitfall — But is the cheaper ansatz still good enough?

This is the question that makes the fix a design decision rather than a free win, and it must be asked.

full entanglement is more expressive: it can reach states linear cannot at the same depth. So the honest comparison is not "10 gates versus 30" but "10 gates and less expressiveness versus 30 gates and more."

Three things make the trade favorable here, and it is worth knowing all three rather than just taking the cheap option:

1. Depth substitutes for connectivity. A linear ansatz at reps=4 has 20 two-qubit gates — still below full at reps=2 — and entanglement propagates across the whole register through the extra layers.
2. More expressiveness is not free on the optimization side. Chapter 32 §32.5's barren-plateau result says highly expressive ansätze have flatter landscapes; the expressiveness that lets an ansatz represent the answer can make the answer harder to find. Chapter 16 §16.6 puts a number on how much relief a shallower ansatz buys: a constant factor, and no change in the exponent.
3. You can measure it. Chapter 4's reachable_entanglement() tells you whether the cheaper ansatz reaches the kind of state you need. Run it before committing.

The rule is not "always use linear." It is: know what your entanglement pattern costs after routing, and buy expressiveness with depth rather than with connectivity when the topology is sparse.

What Would Have Prevented It

One line, at design time:

def routing_overhead(circuit, backend, level=2, seed=42):
    """Transpiled two-qubit gates divided by logical. 1.0 means no routing cost."""
    pm = generate_preset_pass_manager(optimization_level=level, backend=backend,
                                      seed_transpiler=seed)
    logical = sum(v for k, v in circuit.count_ops().items() if k in TWO_Q)
    physical = two_qubit_count(pm.run(circuit))
    return physical / max(1, logical), logical, physical

Run it on any candidate ansatz before committing to it. A ratio near 1.0 means the circuit fits the device; a ratio of 2 or more means you are paying for routing and a structural change will help far more than any amount of compiler tuning.

Budget in transpiled gates, always. The number in your source file is a wish.

🔬 Honest Assessment — How often is this the real problem?

Often enough to check first.

When a variational experiment returns noise, the usual suspects are noise itself, ansatz expressiveness, and barren plateaus — all real, all discussed at length in the literature, and all harder to diagnose than routing overhead. Routing is the cheapest hypothesis to test: one transpilation and a division.

It is also the one most likely to be missed, because nothing tells you. The transpiler does not warn that it inserted thirty-nine SWAPs; it just does its job. The gate count in your source stays reassuringly small. And the symptom — a result that is noisier than expected — looks exactly like the symptoms of every other cause.

The broader pattern, and it is the third time this book has hit it: check the pipeline before the physics. Chapter 7's Case Study 1 was a layout that silently measured the wrong qubits; Chapter 8's was a parameter ordering that silently scrambled the angles; this one is a routing overhead that silently tripled the gate count. All three produce "the answer is worse than expected," all three are diagnosed in under a minute, and all three are usually diagnosed last.

Lessons

1. Count transpiled gates, not written gates. Thirty in the source; ninety on the device.
2. A SWAP costs three CNOTs, and there is no cheaper construction.
3. Routing overhead scales with connectivity mismatch — exactly 1.0× for a chain, 1.75× to 3.16× and growing for all-to-all.
4. A logical gate count cannot rank patterns. circular looks cheap logically (12 vs 30) and has the worst routing ratio of all four (3.33×).
5. Raise the optimization level first. Level 0 → 2 removed 30% here. Free, never sufficient alone — and level 3 was worse than level 2.
6. Best-of-N seeds next. Milliseconds, a few percent.
7. Then change the structure. full → linear went from 80 transpiled gates to 10, and eliminated routing entirely.
8. Buy expressiveness with depth, not connectivity, when the topology is sparse.
9. Measure routing_overhead at design time. A ratio near 1 means the circuit fits; 2 or more means structure, not tuning.
10. Check the pipeline before the physics. Three chapters, three silent pipeline failures, all diagnosed in under a minute and all diagnosed last.

Questions

1. Reproduce the measurement: efficient_su2(6, entanglement="full", reps=2) at all four optimization levels. Report logical and transpiled two-qubit counts.

2. Implement routing_overhead and apply it to full, linear, circular, and pairwise at $n = 4, 6, 8, 10$. At what $n$ does full become clearly infeasible on a 100-gate budget?

3. The chapter suggests buying expressiveness with depth. Compare linear at reps=4 against full at reps=2: transpiled gate counts, and reachable_entanglement() from Chapter 4's checkpoint. Which would you run?

4. Use initial_layout to pin the full ansatz onto a set of qubits you choose by hand. Can you beat the transpiler's layout? What would you need to know about the coupling map to try?

5. The team's original arithmetic — 30 gates at 0.75% error giving ~80% success — was correct given its premise. Redo it with the transpiled count at each optimization level. What success probability were they actually running at?

6. Construct a circuit for which full entanglement transpiles with a ratio near 1.0. What must be true of the device? (Chapter 17.)

7. Hardest. Routing overhead depends on the order in which two-qubit gates appear, not just on which pairs interact — a router can sometimes reuse a SWAP for several subsequent gates. Construct two circuits with identical pair sets but different gate orders, and measure whether the transpiled counts differ. If they do, what does that suggest about how you should write an all-to-all ansatz that you cannot avoid?