16.3 All functions on at most three inputs
On this page · Permalink · Source line 360
Theorem 16.5: Exact small restored-oracle calibration
For every Boolean function on one, two, or three logical inputs, the bound in Theorem 15.3 is attained by an explicit restored implementation. The optimum Toffoli counts are zero for affine functions, one for nonaffine quadratics, and three for three-input cubics.
Proof
An affine function is added to the target using only NOT and CNOT gates, so its optimum is zero.
A nonaffine quadratic on at most three variables has an alternating polar matrix of rank two. In suitable invertible linear coordinates, its quadratic part is a product of two linear forms; the remaining part is affine. A single Toffoli, together with affine preparation and restoration, computes the oracle. The degree bound requires at least one.
A cubic on three variables has the form
with \(q\) quadratic and \(\ell\) affine. Translating \(x_i\mapsto x_i+c_i\) adjusts independently the coefficients of \(x_jx_k\), so all quadratic terms can be cancelled. The resulting function is a three-variable monomial plus an affine function. Affine input changes and affine output additions cost no Toffolis. Corollary 15.7 gives both the lower bound three and a matching restored construction.
There are \(4+16+256=276\) functions over the three input sizes. The distribution is
The source constructs and checks the actual circuits. Optimality is obtained from the written lower bounds and matching constructions, not from exhaustive enumeration of all reversible circuits.