Extensions: exact local expectations from a product-observable evaluator

For every natural number $s$, there exist a positive natural number $C$ and two families of enhancement programs, $g_{N,S}$ and $c_{N,S,\mathcal C}$, defined for every natural number $N$, every finite set of sites $S\subseteq\{0,\ldots,N-1\}$, and, for the second family, every finite list $\mathcal C$ of the Clifford gates described below, such that the following guarantees hold whenever $N\ge1$ and $|S|\le s$. A scalar program here is a finite instruction list operating on complex memory initially zero, writing successive instruction results at successive addresses starting at zero; its operations are complex constants, input reads, addition, multiplication, division, conjugation, $z\mapsto\exp(i\operatorname{Re}z)$, and calls to a supplied function $\mathrm{base}$ on a family of $N$ complex $2\times2$ matrices assembled from memory entries. Reading an unwritten address gives zero, and division by zero fails. Its call count is the number of these function calls, and its work at parameter $B\in\mathbb N$ charges $4N+1+B$ for each call and $1$ for each other instruction. The program $g_{N,S}$ has at most $4^s$ calls and, for every $B\in\mathbb N$, work at most $C(N+1)^3+4^sB$. For every vector $\psi$ on the Boolean strings of length $N$ with $\|\psi\|=1$, and every function $\mathrm{base}$ satisfying $\mathrm{base}(F)=\langle\psi,P_F\psi\rangle$ for every family $F$, where $(P_F)_{a,b}=\prod_k(F_k)_{a_k,b_k}$, the following holds for every real weight array $w$ satisfying $w_{ij}=w_{ji}$, $w_{ii}=0$, and $0\le w_{ij}<2\pi$, every family of unitary $2\times2$ matrices $V_k$, and every complex matrix $O$ indexed by Boolean assignments on $S$. Define the diagonal matrix $D_w$ by $(D_w)_{b,b}=\exp(i\sum_{i<j,\ b_i=b_j=\mathrm{true}}w_{ij})$, define $W=P_V$, and define $\widetilde O_{a,b}=O_{a|_S,b|_S}$ when $a$ and $b$ agree outside $S$, and $\widetilde O_{a,b}=0$ otherwise. Give the program input values $w_{ij}$, $(V_k)_{a,b}$, and $O_{a,b}$ at their respective phase, rotation, and observable labels. Execution with $\mathrm{base}$ succeeds with some memory function $\mu:\mathbb N\to\mathbb C$, its designated output address is smaller than its instruction-list length, and the value there is $\langle WD_w\psi,\widetilde O\,WD_w\psi\rangle$. For every circuit $\mathcal C$, the program $c_{N,S,\mathcal C}$ likewise has at most $4^s$ calls and, for every $B\in\mathbb N$, work at most $C(N+|\mathcal C|+1)^3+4^sB$. Under the same quantification over normalized $\psi$, exact $\mathrm{base}$, $w$, $V$, and $O$, its execution on those same input labels succeeds with an in-range output address whose value is $\langle\chi,\widetilde O\chi\rangle$, where $\chi=WU_{\mathcal C}\psi$. The permitted circuit gates are a Hadamard on one site, with entries $(-1)^{ab}/\sqrt2$ for bits $a,b$, a one-site phase gate $\operatorname{diag}(1,i)$, and a controlled bit flip with distinct control and target sites; the latter sends a Boolean string $b$ to the string obtained by replacing its target bit by the exclusive-or of its target and control bits. One-site gates act as the identity on all other sites, and $U_{\mathcal C}$ is the product of the gate matrices in reverse list order, so the first listed gate acts first and the empty circuit gives the identity. The second output formula contains no dependence on $w$. Empty $S$, including $s=0$, is allowed, and no Hermitian assumption is made on $O$; the program families are defined also at $N=0$ and $|S|>s$, but the stated guarantees apply only under the displayed bounds.