Reduced Hadamard words and their exact denominators

Replace $Y$ by $iXZ$, and move all $X$ factors to the right using $X{T}^r={\omega }^r{T}^{-r}X$ and $XH=HZ$. Combine adjacent diagonal powers. For an even interior exponent, use $H^2=I$, $H{T}^{4}H=X$, $H{T}^{2}H=\omega T^{-2}H{T}^{-2}$, or $H{T}^{6}H={\omega }^{-1}{T}^{2}H{T}^2$. Each replacement strictly decreases the H count and introduces only free diagonal Clifford or Pauli factors. Repeat until all interior exponents are odd. Combining powers never increases the number of odd powers, since the parity of a sum is at most the sum of the parities. Thus both counts never increase. Exact scalar exponents are updated modulo $8$. A stack of diagonal blocks and H symbols implements this reduction in linear time in the input word length: each interior even-block replacement removes at least one H symbol and requires only bounded local stack updates.

For a unit column $(u,v{)}^T$, set $x=2\mathrm{Re}(\bar{u}v)$, $y=2\mathrm{Im}(\bar{u}v)$, $z=\mathrm{\mid }u{\mathrm{\mid }}^2-\mathrm{\mid }v{\mathrm{\mid }}^2$. Direct matrix multiplication gives the H action $(x,y,z)\mapsto (z,-y,x)$ and the $T^r$ action $(x,y,z)\mapsto (x\cos (r\pi \mathrm{/}4)-y\sin (r\pi \mathrm{/}4),x\sin (r\pi \mathrm{/}4)+y\cos (r\pi \mathrm{/}4),z)$. For odd $r$, its sine and cosine are independently signed $1\mathrm{/}\sqrt{2}$. The rightmost $T^c{X}^e$ starts the column at $(0,0,(-1{)}^e)$, and the leftmost $T^a$ does not change the final $z$.

Ignore these endpoint factors temporarily. After one H the triple is $(\pm 1,0,0)$. After two H gates with an odd intervening power it is $(0,\pm 1\mathrm{/}\sqrt{2},\pm 1\mathrm{/}\sqrt{2})$. After three it has $x=\pm 1\mathrm{/}\sqrt{2}$, $y=\pm 1\mathrm{/}2$, $z=\pm 1\mathrm{/}2$, so the respective least exponents are $1,2,2$. If two nonzero elements have unequal least exponents, their sum and difference have exponent equal to the larger one: scale by that larger power; one summand is primitive modulo $\sqrt{2}O$ and the other is divisible by $\sqrt{2}$, so their sum cannot be divisible. Inductively, after $h\ge 3$ H gates the exponents of $(x,y,z)$ are $(h-2,h-1,h-1)$. Indeed an odd rotation makes both new transverse coordinates have exponent $h$, and H makes the new exponents $(h-1,h,h)$. The same transition from the displayed two-H triple establishes the induction base.

Since $\mathrm{\mid }u{\mathrm{\mid }}^2=(1+z)\mathrm{/}2$, the positive exponent $h-1$ of $z$ for $h\ge 2$ gives exponent $h+1$ for $\mathrm{\mid }u{\mathrm{\mid }}^2$ by the same primitive-numerator argument. For one H, $z=0$ and $\mathrm{\mid }u{\mathrm{\mid }}^2=1\mathrm{/}2$ has exponent $2$; for zero H the column is a basis vector. Thus the squared-entry exponent distinguishes every possible reduced H count, including $0,1$. Any competing word reduces by step 1.1 without increasing H count, and its squared-entry exponent is unchanged by scalar phase. Its reduced H count therefore equals that of the given reduced word. This proves H minimality.