Theorem: Certified thresholds for the three-step model

Within the declared horizon $T=3$:

1. for $0\le ϵ<3/4$, $t_{\mathrm{IT}}(ϵ)=3$;

2. for $0\le ϵ<1/2$ and any gate budget, $t_{\mathrm{op}}(1,G_0,ϵ)=+\infty$;

3. for $N\ge 2$, $G_0\ge 7$, and $0\le ϵ<3/4$, $t_{\mathrm{op}}(N,G_0,ϵ)=3$;

4. for $G_0\ge 3$ and $1/2\le ϵ<3/4$, $t_{\mathrm{op}}(1,G_0,ϵ)=3$.

Proof. The early prefixes have unrestricted error $3/4$, so no programme can cross these targets before step $3$. At step $3$, use Theorems thm:C3 and thm:C4.