Theorem: Oai279-A finite exact-output certificate

The circuit specified in Section sec:finite satisfies:

1. It uses only the frozen gate alphabet, with exactly $175$ gates and allocated width $16391$.

2. Its input register is preserved and its three scratch qubits are restored to zero.

3. For every $2\le N<16$,

   $$U_4|N{⟩}_I|0^{16384}{⟩}_Y|000{⟩}_{uvf}=|N{⟩}_I|{\mathrm{enc}}_{128}(N){⟩}_Y|000{⟩}_{uvf}.$$

4. In particular, for the frozen $N_0=12$,

   $$\mathbb{P}\{Y=(2,2,3,0^{125})\}=1,$$

   and the probability of every other output word is zero.

5. The named polynomial (eq:resource-polynomial) bounds the gates and width of the length-uniform partial family just defined. At the frozen length,

   $$175\le P(4)=17936,16391\le P(4)=17936.$$

No order-trial law, value of $p_{\ast }$, general primality algorithm, or external Family 279 theorem is assumed.

Proof. For a fixed input $N$, Lemma lem:row shows that all rows except row $N$ leave the output unchanged. Row $N$ writes exactly the word with one positions $T_N$. All later row blocks have a false equality predicate and all scratch starts and ends zero.

The table and Lemma lem:table identify this output word with ${\mathrm{enc}}_{128}(N)$. This proves (eq:finite-action). The gates are permutations on computational basis states, so the right side is exactly one basis vector of amplitude one, with no unlisted branch.

For $N=12$, the complete final basis vector has one positions

The first two are the preserved input bits. The remaining four encode the three prime entries $2,2,3$. Thus its output marginal is

which proves the probability-one support assertion.

The gate and width ledgers are Lemma lem:gatecount and the register allocation. The polynomial inequalities and the generator were established above.