Ancilla-free Clifford+T Rz approximation

Inputs are exact reals $\theta \in \mathbb{R}$ and $\epsilon >0$, exact-real arithmetic and comparisons for the grid predicates, and the exact integer part operation needed to compute $q=\lfloor 2\theta \mathrm{/}\pi +1\mathrm{/}2\rfloor$; the integer part is the one defined in Integer part: for every real $x$ there is exactly one integer $m$ with $m\le x<m+1$. Also choose a norm mode: COMPLETE uses either a valid full integer-factorization oracle or the complete finite-search norm solver; BOUNDED uses the calibrated capped-prime attempt only. Supply a total candidate limit $B\in {\mathbb{N}}_0\cup \{\mathrm{\infty }\}$, defaulting to $\mathrm{\infty }$; $B$ counts grid candidates on which a norm call is started. Output is either a finite chronological Clifford+T word or TIMEOUT. No bit encoding for arbitrary reals is implicit. In the randomized modes use an independent random stream for the grid iterator and fresh independent streams for each randomized norm call; candidate order depends only on the grid stream, not on norm-call outcomes.

Let $c=\mathrm{\mid }1-e^{i\pi \mathrm{/}8}\mathrm{\mid }$.

1. If $\epsilon \ge c$, compute the nearest integer $q=\lfloor 2\theta \mathrm{/}\pi +1\mathrm{/}2\rfloor$, with ties rounded upward, and return the chronological word with scalar phase ${\omega }^{-q}I$ first and $S^q$ second, omitting identity factors. Reduce the scalar exponent modulo $8$ and the $S$ exponent modulo $4$. It has T-count zero.
2. Otherwise $\epsilon <c<1\mathrm{/}2$. Set $j=0$ and enumerate $u$ from Cyclotomic scaled grid and norm-equation solver in increasing denominator exponent. Before starting a norm call for a candidate, if $j=B$ return TIMEOUT; otherwise increment $j$. Compute $\xi =1-\mathrm{\mid }u{\mathrm{\mid }}^2$. In COMPLETE mode invoke the selected complete norm solver, obtaining a valid complete integer factorization when that solver requires one. In BOUNDED mode use only the calibrated capped-prime attempt, which accepts an exact certificate and otherwise may return FACTOR_TIMEOUT.
3. If the norm solver returns FACTOR_TIMEOUT or NO_SOLUTION, continue to the next candidate. For each returned $t$ with $t^{\ast }t=\xi$, form $U=\left(\begin{array}{cc}u& -\bar{t}\\ t& \bar{u}\end{array}\right)$ and $U^{\mathrm{\prime }}=TU{T}^{†}$.
4. Run Exact single-qubit Clifford+T synthesis on both matrices. Return the word with smaller exact T-count; break ties by lexicographic gate word.

The exact grid-to-error equivalence is proved in The exact operator-norm epsilon region for determinant-one Rz candidates. The unbounded factoring-oracle mode uses the complete efficient solver from the norm procedure, or the finite alternative Constructive decision of the dyadic cyclotomic norm equation. Successful termination (almost surely for the randomized efficient mode) under the stated terminating exact-real comparisons is proved in The Rz approximation procedure is correct when it returns ↗. A finite-budget call can return TIMEOUT. The zero-T branch is the construction in Determinant-one reduction for optimal Rz approximation. The complete finite-search norm mode gives no polynomial arithmetic-time guarantee.