Case Study 2: The Circuit That Was Exactly Big Enough
The habit
Allocate what you need. It is good engineering everywhere else, it is what every tutorial models, and on a machine where qubits are the scarcest resource in the world it feels obviously correct.
An oracle needs $n$ inputs and one scratch qubit, so:
qc = QuantumCircuit(n + 1)
qc.append(MCXGate(n), list(range(n + 1)))
Tight. Clean. No waste.
And it costs 12,002 T gates at $n = 6$, where the same gate in a roomier circuit costs 39.
The measurement
Identical MCXGate, identical transpiler settings, identical Clifford+T basis. The only difference is
how many qubits the surrounding circuit happens to have:
n = 6, MCXGate in a 7-qubit circuit (no spare) 12,002 T gates
n = 6, MCXGate in a 12-qubit circuit (5 spare) 39 T gates
n = 8, MCXGate in a 9-qubit circuit (no spare) 26,978 T gates
n = 8, MCXGate in a 16-qubit circuit (7 spare) 55 T gates
A 308× difference at $n = 6$ and 491× at $n = 8$, from a constructor argument.
Nothing about the gate changed. Nothing about the algorithm changed. The circuit was declared with
spare qubits, and Qiskit's HighLevelSynthesis — which runs on every transpilation, always — found a
completely different decomposition.
Why the transpiler cannot do this on its own
§19.6's V-chain needs somewhere to put intermediate results:
$$a_1 = x_1 \wedge x_2, \quad a_2 = a_1 \wedge x_3, \quad \dots$$
With $n+1$ qubits declared, every qubit is spoken for, and the synthesizer has no choice but to use a construction that repeatedly recomputes partial products because there is nowhere to store them. That construction exists, it is correct, and it is catastrophically more expensive.
Given spare qubits, the synthesizer chains Toffolis at 7 T gates each — linear in $n$ — and uncomputes them afterwards, leaving the ancillas clean.
The transpiler was always willing to do this. It had nowhere to put the ancillas.
Why it is easy to miss
Four things conspire, and none of them is anyone's mistake.
The tight allocation is the natural one. Declaring extra qubits looks like a bug — unused wires in a circuit diagram, wasted space on a machine where space is precious. A code reviewer would flag it.
Nothing warns you. The circuit is valid, the transpilation succeeds, the result is correct. There is no error, no warning, and no output that differs.
The cost is invisible unless you measure Clifford+T. With rz in the basis — the default — the
same gate reports zero T gates at $n=3$ (§19.5). A team measuring casually would see a small
number and stop.
And the difference does not show up on a simulator. The circuit gives identical answers either way. It is only under error correction, where T gates are the currency (Chapter 15 §15.8), that a 308× difference becomes a 308× difference in machine size.
The general shape: a resource decision made for good reasons at one level of abstraction, silently determining a cost at a level nobody was looking at.
This book has now hit that repeatedly — Chapter 14's
appendrefactor that tripled circuit depth, Chapter 13's DD pass placed where no idle time existed, Chapter 17's device swap that hid a 3.18× overhead. Every one was a locally sensible choice with a non-local cost.
The practical rule, and its limits
Leave the transpiler room.
n_ancilla = max(n - 2, 0)
qc = QuantumCircuit(n + 1 + n_ancilla) # room for the cheap synthesis
The limits are real, and stating them matters as much as the rule:
Spare qubits are not free on hardware. Chapter 12 measured that qubit quality varies 288× across one chip; more qubits means more of them, and a longer chain to route. §19.6's trade is favourable because T gates are so expensive under error correction — on a NISQ device today, where there is no error correction and T gates are just gates, the calculation is different.
They must be clean. The V-chain assumes ancillas start in $|0\rangle$. If they hold other data,
synth_mcx_n_dirty_i15 handles it at slightly higher cost — 46 versus 39 T gates at $n = 6$ — which
is a small price for not needing fresh qubits.
And they must be returned clean. §19.4: an ancilla left entangled makes the input register mixed and destroys interference. The synthesis does uncompute them; anything you allocate by hand is your responsibility.
What to check
cost_tight = oracle_cost(QuantumCircuit(n + 1)) # as declared
cost_roomy = oracle_cost(QuantumCircuit(2 * n)) # with spares
print(cost_tight.t_count / cost_roomy.t_count)
Two transpilations and a division. If the ratio is large, your circuit is exactly big enough and that is the problem.
compare_ancilla_strategies(n) in §19.6's checkpoint does this, and one of its tests asserts the
reduction exceeds 10× — a property of the synthesis rather than of the implementation, and therefore
safe to depend on.
The lessons
"Allocate exactly what you need" is wrong here, and it is wrong for a reason worth generalizing. The resource you are conserving (qubits) and the resource that dominates the cost (T gates) are different, and they trade against each other at a rate of roughly 300:1 in your favour.
Know which resource actually dominates. Chapter 15 §15.8 established that T gates are essentially the entire cost of a fault-tolerant computation. Optimizing qubit count while ignoring T count is optimizing the cheap axis.
A tool's default behaviour depends on context you may not realize you are setting. The circuit's width is not obviously an input to gate synthesis, and it is.
Measure the ratio, not the absolute number. 12,002 T gates means nothing on its own. 12,002 versus 39 for the same gate means everything, and costs one extra transpilation to discover.
And the deprecated API pointed the wrong way. The old advice was "call mcx(mode='v-chain')" — an
explicit request for a specific synthesis. The current advice is better: give the transpiler room
and let it choose. Occasionally an API deprecation improves the guidance rather than just moving it.
Reproduce it: code/example-04-ancilla-tradeoff.py measures the trade across sizes;
compare_ancilla_strategies() in code/project-checkpoint.py runs it for your own $n$.