Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-080
A lower bound on the Toffoli count of exact NCT networks implementing χ₅
For every exact NOT/CNOT/Toffoli network N implementing χ₅ with clean ancillas, #Toffoli(N) ≥ MC(χ₅⁻¹) = 6
Published 2026-08-29
For everyone
Plain summary
Implementing the five-bit χ/Ascon transformation with reversible logic requires at least six Toffoli gates. Any exact circuit built purely from NOT, CNOT, and Toffoli gates hits this floor, even when using clean ancillas—extra work bits that start at 0 and return to 0.
The lower bound comes from running the circuit backwards. Reversing a reversible circuit computes the inverse transformation without changing the gate count. In a standard Boolean calculation, each Toffoli gate supplies one AND operation. Because the inverse transformation has multiplicative complexity 6, meaning it requires at least six AND operations, no five-Toffoli forward circuit can exist. This result applies strictly to the NOT/CNOT/Toffoli model; it doesn't bound Clifford+T circuits or designs using measurement or internal Hadamard gates. The register records no separate prior-art claim for this bound.
Result
Let P = χ_5 denote the 5-bit χ/Ascon permutation. For every exact NOT/CNOT/Toffoli network N implementing P, including networks with clean ancillas,
#Toffoli(N) >= MC(χ_5^{-1}) = 6.
The bound applies to the forward network via reversal. The register records MC(χ_5) = 5 and MC(χ_5^{-1}) = 6.
If an exact forward network used t < 6 Toffoli gates, reversing it would yield a straight-line computation for χ_5^{-1} using at most t AND gates, contradicting MC(χ_5^{-1}) = 6. The contradiction holds in the presence of clean ancillas. MF-080 establishes only the lower bound; it records no matching six-Toffoli forward synthesis.
Setting and definitions
An NCT network is a reversible network over the gate set {NOT, CNOT, Toffoli}. The permutation inverse is χ_5^{-1}. The function #Toffoli(N) counts Toffoli gates in N. A clean ancilla is an auxiliary bit initialized to 0 and returned to 0 upon completion. The quantity MC(f) denotes the multiplicative complexity of f, defined as the minimum number of AND gates in a straight-line Boolean computation of f.
Exactness requires realization of the permutation on every 5-bit input. Reversing an NCT network reverses its gate sequence and computes the inverse function without altering its Toffoli count.
Method
The reduction reverses an exact forward NCT network N. The reversed network computes χ_5^{-1} using #Toffoli(N) gates. In a straight-line simulation, each Toffoli gate contributes one AND operation, so a network with t Toffoli gates yields an inverse computation with at most t AND gates. Because the register establishes MC(χ_5^{-1}) = 6, t >= 6.
The reduction exploits the asymmetry between the forward and inverse complexities: MC(χ_5) = 5, whereas MC(χ_5^{-1}) = 6. Reversing the network applies the higher inverse bound directly to the forward implementation without requiring MC(χ_5) = 6.
The full derivation is recorded in this paper's downloadable evidence pack. No separate artifact is attached to MF-080.
Discussion
The floor applies strictly to exact NCT networks with clean ancillas. It does not establish an unrestricted Clifford+T T-count bound, nor does it constrain circuits employing measurement or internal Hadamards. While forward multiplicative complexity is MC(χ_5) = 5, the six-Toffoli floor arises entirely from the inverse complexity under circuit reversal.
Corrections: NONE. The register records no correction, retraction, or addendum for MF-080.
The entry establishes a lower bound on Toffoli count within the NCT model, not a total gate-count minimum, an unrestricted quantum circuit optimum, or an explicit six-Toffoli forward realization. The exact inverse value MC(χ_5^{-1}) = 6 is imported from MF-079. No separate prior-art work is recorded.
For everyone — the takeaway
What this means
If you build the 5-bit χ/Ascon transformation out of standard reversible logic gates, you cannot get away with fewer than six Toffoli gates. Even if you bring in extra workspace bits that start and end at zero, five Toffoli gates won't work. Because running a reversible circuit backwards calculates its inverse with the exact same gates, the higher demand of the inverse step sets a hard limit on the forward design. This rule applies specifically to NOT, CNOT, and Toffoli setups. It doesn't restrict broader quantum settings that allow measurement or Hadamard gates.
Attribution and prior art
Prior art: No separate prior-art claims are made. This bound is derived from the exact six-AND inverse complexity and applies strictly to NCT networks.
Register references
- MF-080
- Receipt: zkgolf-transfer-studies\03-mc-lower-bounds-tcount\REPORT.md §1, §3.3
- Related register entry named in the claim: MF-079
- Prior-art work: the register does not record this.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 1 of 1 receipt files bundled (10 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.