Manuscript Oai279-A@1 · Oai279-A.tex · lemma · a1abc73f

Lemma: The gate ledger

Stage 6: the explicit circuit for the frozen input › Exact resources · lines 934–960 · proof included or linked

Oai279-A@1#lem:gatecount

The circuit $U_{4}$ contains exactly

50 NOT gates, 84 Toffoli gates, 41 CNOT gates .

Its total gate count is $175$ , with no intermediate measurements, no retries, and three scratch qubits returned to zero.

Proof. Each row uses $2∣ Z_{m} ∣$ NOTs, six Toffolis, and $∣ T_{m} ∣$ CNOTs. The table gives

m = 2 \sum^{15} ∣ Z_{m} ∣ = 25, m = 2 \sum^{15} ∣ T_{m} ∣ = 41.

Thus the total is

2 \cdot 25 + 6 \cdot 14 + 41 = 175.

Scratch restoration follows from Lemma lem:row. The gate list has fixed length, independent of the input.

Displayed formulas in this passage

unlabeled · line 937
$50 NOT gates, 84 Toffoli gates, 41 CNOT gates .$
unlabeled · line 949
$m = 2 \sum^{15} ∣ Z_{m} ∣ = 25, m = 2 \sum^{15} ∣ T_{m} ∣ = 41.$
unlabeled · line 955
$2 \cdot 25 + 6 \cdot 14 + 41 = 175.$