H-count and T-count optimality of exact Clifford+T synthesis

By [F2,F3], before the final reduction the compiler has an exact word for $U$. By [F1] its final reduced word is exact and H-optimal, and $n\ge 4$ makes its H count $h=n-1$. Write its endpoint exponents $a,c$ and its trailing Pauli factor $X^e$ as in [F1]. Each of the $h-1$ odd interior powers costs one T, so its T count is $h-1+p(a)+p(c)$, where $p(r)=r<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2\in \{0,1\}$.

Every Clifford block generated by $H,S,X,Y,Z$ reduces by [F1] to at most one H: all diagonal exponents remain even during that reduction. Splitting any word containing $t$ T gates into $t+1$ Clifford blocks therefore proves $h(V)\le t(V)+1$ for every represented $V$. This argument applies to $T^{†}$ equally.

There are $n-3$ descent iterations and a constant-size base lookup. Each trial uses boundedly many coefficient additions, sign permutations, multiplications by fixed ring constants, and denominator tests. At every iteration all embeddings of the current unitary remain unitary, so all embedded entries have modulus at most one. For a positive squared-entry exponent, the complementary squared norm has the same exponent: subtracting its primitive numerator from the positive power of $\sqrt{2}$ leaves it primitive. Thus [F5] bounds every entry exponent by $(n+1)\mathrm{/}2$; the base regime is bounded by [F3]. By [F4] all numerator coefficients have $O(n+1)$ bits. Denominator tests need no integer multiplication: for $x=a_0+a_1\omega +a_2{\omega }^2+a_3{\omega }^3\mathrm{\ne }0$, let $m$ be the minimum of the binary trailing-zero counts of its nonzero coefficients, and put $y=x\mathrm{/}{2}^m$. Its $\sqrt{2}$-valuation is $2m+\delta$, where $\delta =1$ exactly when both opposite-coefficient sums of $y$ are even. Indeed $y$ is not divisible by $2$, so it can contain at most one factor $\sqrt{2}$. For the resulting primitive numerator $z$, its norm has zero or one factor $\sqrt{2}$ by [F5]; this factor occurs exactly when $\sum z_i$ is even, since the rational coefficient of $z\bar{z}$ is $\sum z_i^2$. These parity and trailing-zero scans take $O(n+1)$ bit operations. Every descent trial therefore costs $O(n+1)$ bits and boundedly many ring operations, with coefficient valuations counted as linear binary scans.

Choose $\mathrm{\ell }$ and $j$ with $a+\mathrm{\ell }$ and $c-j$ odd. Then $H{T}^{\mathrm{\ell }}U{T}^{j}H$ has an odd-interior reduced word with $h+2$ H gates: commute $X^e$ past $T^{j}H$ using the identities in [F1], which changes only the sign of $j$ and adds a free terminal $Z$ when $e=1$. Its H count is therefore minimal. Conversely if either parity condition fails, the adjacent even-interior pair reduces, giving strictly fewer than $h+2$ H gates. Thus the extension condition is equivalent to $p(\mathrm{\ell })=1-p(a)$ and $p(j)=1-p(c)$.

Apply step 1.2 to the extended matrix $V=H{T}^{\mathrm{\ell }}U{T}^{j}H$. Multiplication by these endpoint factors gives $t(V)\le t(U)+p(\mathrm{\ell })+p(j)$, while $h(V)=h+2$ gives $t(V)\ge h+1$. Consequently $t(U)\ge h+1-p(\mathrm{\ell })-p(j)=h-1+p(a)+p(c)$. Step 1.1 attains this bound, proving simultaneous optimality and both formulas. The same argument proves the endpoint formula for every reduced word with at least one H, since its extension still has at least three H gates and [F1] applies.

The initial word has $O(n+1)$ gates and its stack reduction is linear by [F1], retaining only exponents modulo eight and a scalar exponent modulo eight. The preceding bounds give $O(n+1)$ ring operations and $O((n+1{)}^2)$ bit operations overall. Any word's total H/T count is at least $h(U)=n-1$; the output has $h+t\le 2h+1=O(n+1)$ by step 1.1. Hence $n+1=\mathrm{\Theta }(n_{\mathrm{o}\mathrm{p}\mathrm{t}}+1)$, proving the claimed bounds.