Exercises: Transpilation

Two exercises here will change how you write circuits: 10.7 (routing cost) and 10.11 (the seed). Do those even if you skip the rest.

Difficulty: ⭐ warm-up · ⭐⭐ standard · ⭐⭐⭐ deeper. Solutions: worked answers to the daggered (†) and odd-numbered problems are in appendices/answers-to-selected.md; runnable code in code/exercise-solutions.py.

Part A — Warm-ups ⭐

10.1 † Name the four problems the transpiler solves. Which one is forced by physics rather than by convenience?

10.2 How many two-qubit gates does one SWAP cost? Why does that number make routing the dominant hidden expense?

10.3 † Name the six pass-manager stages in order, and say in one phrase what each decides.

10.4 What does seed_transpiler control, and why does omitting it make a result unreproducible?

10.5 † What is an ISA circuit?

Part B — Measuring the Cost ⭐⭐

10.6 † Read your backend's target: qubit count, operation names, coupling-map edges. Compute what fraction of all-to-all connectivity it has. How many of the gates you have used in this book appear in the operation list?

10.7 † The routing measurement. Build an all-to-all circuit and a linear chain, both on 4, 5, and 6 qubits. Transpile each at all four optimization levels and tabulate two-qubit gate counts against the logical count. Report both ratios. Which circuit pays nothing, and why? What does the ratio do as $n$ grows?

10.8 † Compare trivial, dense, and sabre layout methods on a routing-limited circuit, then compare basic, lookahead, and sabre routing. Report gate counts and depths. By what factor does the worst routing method lose to the best?

10.9 Compare optimization levels on two circuits: one that forces routing and one whose connectivity matches the device. Report two-qubit count, depth, and transpilation time for each. Explain why the two tables tell different stories, and find a case where a higher level produces a worse result.

Part C — Passes and Seeds ⭐⭐⭐

10.10 † Write two custom passes: an analysis pass that records the number of two-qubit gates in property_set, and a transformation pass that cancels adjacent identical CNOT pairs. Verify both. Then write a third that records the number of operations in each DAG layer — what does that tell you that depth() does not?

10.11 † The seed measurement. Transpile a routing-limited circuit at optimization level 3 with eight different seeds. Report two-qubit count, depth, and layout for each. What is the spread? Then implement best-of-$N$ and tabulate the best result and elapsed time for $N = 1, 2, 4, 8, 16$. At what $N$ do the returns stop?

10.12 Produce a unified diff of the QASM at optimization levels 0 and 3 for a small routing-limited circuit. Extract the four audit numbers (physical qubits, two-qubit count, real pulses, depth) at each level and tabulate them.

10.13 † Chapter 8 recommended linear and pairwise entanglement patterns partly on topology grounds. Verify the claim: transpile efficient_su2(8, reps=2) with each of full, linear, circular, and pairwise entanglement, and compare transpiled two-qubit counts against the logical counts from Chapter 8 §8.7. Does full suffer more after routing than the logical table suggested?

Part D — Deeper ⭐⭐⭐

10.14 Write routing_overhead(circuit, backend) that returns the ratio of transpiled to logical two-qubit gates. Apply it to five circuits of your choosing and rank them. What structural property predicts a low ratio?

10.15 † Use initial_layout to pin a two-qubit circuit onto physical qubits that are far apart on the coupling map. Count the inserted SWAPs and verify they equal roughly the graph distance between the qubits. Derive the general relationship between route length and CNOT cost.

10.16 The transpiler's optimization stage iterates to a fixed point. Instrument a transpilation to record the circuit's two-qubit count after each optimization iteration. How many iterations does it take to converge on a circuit of your choosing?

10.17 † Write a custom pass that refuses to transpile a circuit whose transpiled two-qubit count would exceed a budget you specify, raising a clear error instead. Where in the pass manager would you insert it, and why is a pass a better place for this check than a wrapper function?

10.18 Routing is NP-hard, so all methods are heuristics. Construct a small circuit and topology for which you can find the optimal routing by hand or by exhaustive search, then check whether SABRE finds it. How large can you make the instance before exhaustive search becomes impractical?

10.19 Compare transpiling a parameterized circuit against transpiling a bound one. Are the results identical? Should they be? What would it mean for Chapter 7's transpile-once pattern if they were not?

Part E — Project ⭐⭐

10.20 † Implement the Chapter 10 🧱 Project Checkpoint: add prepare_best(), seed_sweep(), two_qubit_count(), and the Compilation provenance record to vqelab/backends.py.

10.21 Run seed_sweep on your project ansatz. Is there a spread? If not, explain why — and say what property of the ansatz makes it insensitive to the seed.

10.22 ⭐⭐⭐ prepare_best scores candidates by two-qubit gate count, tie-broken on depth. Argue for a different scoring function — one using the backend's per-pair error rates rather than a raw count, so that eighteen gates on bad qubits can lose to twenty on good ones. Implement it, and compare the two scorings on a routing-limited circuit. Which layout would you actually run, and how would you check?