Bond-one MPS and quadratic tableau construction for Pauli predictions

For an $n$-qubit Pauli string $P$, write $A_P=i^{c_P}\bigotimes_{j<n}P_j$, where $c_P\in\{0,1,2,3\}$ represents its phase in $\mathbb Z/4\mathbb Z$, and $P_j\in\{I,X,Y,Z\}$, with $X=\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)$, $Y=\left(\begin{smallmatrix}0&-i\\i&0\end{smallmatrix}\right)$, and $Z=\operatorname{diag}(1,-1)$. For a tableau $T=(T_j)_{j<n}$, put $\Pi_T=\prod_{j=0}^{n-1}(I+A_{T_j})/2$, in increasing index order. Call $T$ valid when every row phase is $0$ or $2$, all row matrices commute, no row matrix $A_{T_j}$ is $i^c$ times the increasing-order product of any subset of the other rows for any $c\in\{0,1,2,3\}$, and no increasing-order subset product of row matrices equals $-I$. The first assertion is that, for every natural $n$, every valid $T$, every Pauli string $O$ of phase $0$ or $2$, and every subset $A\subseteq\{0,\ldots,n-1\}$,

Here $R_A(X)_{xy}=2^{-(n-|A|)}\sum_zX_{(x|_A,z),(y|_A,z)}$ when the bit strings $x,y$ agree on $A^c$, and $R_A(X)_{xy}=0$ otherwise; $z$ ranges over bit strings on $A^c$. The second assertion is that there exist one finite word-machine program $P$ and one natural constant $C>0$ with the following uniform property. For every natural $n$, every pair of valid tableaux $T,D$ satisfying

and every Pauli string $O$ of phase $0$ or $2$, there is a natural time $t\le C(n+1)^2$ at which $P$ has halted successfully and its output is the following list: first $1$ if $\tau=\operatorname{tr}(A_O\Pi_T)=1$, $2$ if $\tau=-1$, and $0$ otherwise, followed for each site $j$ in increasing order by $(1,1)$ if $O_j=I$ and by $(0,1)$ otherwise. Every memory cell at every natural time $u\le t$ contains a natural number at most $C(n+1)^2$, and $\tau\in\{0,1,-1\}$. The machine input is the natural-number list beginning with $n$, followed by the bit encodings of all rows of $T$, then all rows of $D$, then $O$: each row or string is encoded by its two phase bits $(\mathbf1_{\{2\le c\}},\,c\bmod2)$, followed by the two-bit codes $I\mapsto00$, $X\mapsto10$, $Y\mapsto11$, $Z\mapsto01$ for its factors in site order, with bits represented by $0,1$. Execution starts at instruction $0$, with the input in consecutive memory cells and all remaining cells $0$, allocated count equal to input length, empty output, no halt status, and step count $0$. A nonhalted transition increments the instruction counter and step count before executing an instruction; instructions can set constants, load or store indirectly, perform natural addition, truncated subtraction, multiplication, division, or bitwise exclusive-or, branch according to a comparison $\le$, jump, increase the allocated count, append a memory value to the output, or halt with a Boolean success status. Division by zero or an absent instruction halts unsuccessfully; halted states remain fixed. Both assertions include $n=0$, with empty matrix products interpreted as identities.