Sparse evolution substitution gives the quantum SDP and diagonal LP query bounds

At round $t\ge 1$, retain a list of at most $k_t=2t+1$ original constituent matrices; repetitions may remain. An identity shift adds at most one column per row, so use capacity $D_t=s{k}_t+1=O(st)$. A derived sorted row query scans all $k_{t}s$ raw slots, masks missing entries, sorts column records, merges duplicate columns and sums their coefficient-weighted values. Retain every distinct union column, including summed value zero, and pad missing slots by the supplied sentinel. No real value zero test occurs. The input Hermitian supports and the diagonal are transposition-compatible, so their union is also. A fixed sorting network and finite scans compute the requested answer, XOR-copy it, then reverse the retained history. This is a total reversible oracle with $O(st)$ original location/value calls, including reversal and masked invalid-input handling. A derived entry query sums $k_t$ entries with $O(t)$ value calls. Sorting an individual observable row similarly costs $O(s)$ raw queries. These operations work coherently in row and observable indices.

For a decoded Hermitian $F$ of capacity $d_F$ and entry bound $h_F>0$, [F2] and [F3] simulate signed time $u$ with error $\zeta$ in $O((d_F{h}_F\mathrm{\mid }u\mathrm{\mid }+\log (1\mathrm{/}\zeta ))\log (d_F+1))$ derived location calls and $O(d_F{h}_F\mathrm{\mid }u\mathrm{\mid }+\log (1\mathrm{/}\zeta ))$ value calls. A supplied upper bound suffices; no global maximum-entry computation is needed. The actual inverse and controlled implementations retain this order. Arithmetic, slot preparation, phases, precision and work remain priced separately.

The coefficient $\eta$ and hence the target entries need not be rational. Write $L_t={\sum }_{\mathrm{\ell }\le k_t}{c}_{\mathrm{\ell }}{B}_{\mathrm{\ell }}$, with $\mathrm{\parallel }{B}_{\mathrm{\ell }}\mathrm{\parallel }\le 1$. Freeze real rational ${\widehat{c}}_{\mathrm{\ell }}$ with $\mathrm{\mid }{\widehat{c}}_{\mathrm{\ell }}-c_{\mathrm{\ell }}\mathrm{\mid }\le {\delta }_t\mathrm{/}{k}_t$, and decode the exact finite matrix ${\widehat{L}}_t={\sum }_{\mathrm{\ell }}{\widehat{c}}_{\mathrm{\ell }}{B}_{\mathrm{\ell }}$. Then ${\widehat{L}}_t$ is exactly Hermitian and $\mathrm{\parallel }{\widehat{L}}_t-L_t\mathrm{\parallel }\le {\delta }_t$. Common real coefficient rounding, rather than independent conjugate-entry rounding, preserves Hermiticity. The row union is independent of cancellation and its value oracle agrees exactly with this decoded matrix. Certified coefficient enclosures and exact rational sum arithmetic are factory/bit costs, without matrix queries. If an input oracle itself approximates a different target, add its certified operator error; entrywise error $u$ gives operator error at most $nu$ by the Frobenius bound. Absent such a certificate, the exact decoded input is the input matrix.

Write the Fourier times as $q\omega$, $\mathrm{\mid }q\mathrm{\mid }\le J$, $\omega =\pi \mathrm{/}(2(r_F+\mathrm{\Delta }))$. Implement SELECT by signed binary digits of $q$: at place $\mathrm{\ell }$, apply the evolution at $2^{\mathrm{\ell }}\omega$ controlled on the digit and sign. The ideal factors commute and multiply to $e^{iq\omega F}$. There are $O(\log (J+2))$ slots and their absolute times sum to less than $2(J+1)\mathrm{\mid }\omega \mathrm{\mid }$ per sign branch. Assign each slot error $\zeta \mathrm{/}O(\log (J+2))$. The clean-subspace hybrid proves total SELECT error at most $\zeta$, including shared retained simulator work, inverses and references, without asserting actual work is clean. To use rational times, replace $\omega$ by rational $\widehat{\omega }$ with error at most $\zeta \mathrm{/}[4(J+1)\max (1,\mathrm{\parallel }F\mathrm{\parallel })]$; the spectral scalar inequality $\mathrm{\mid }{e}^{ia}-e^{ib}\mathrm{\mid }\le \mathrm{\mid }a-b\mathrm{\mid }$ bounds its additional error, and split the slot budget accordingly. Thus SELECT costs $\tilde{O}(d_F{h}_F(J+1)\mathrm{\mid }\omega \mathrm{\mid }+1)$ derived queries. For fixed $\mathrm{\Delta }=1\mathrm{/}2$, [F4] makes $(J+1)\mathrm{\mid }\omega \mathrm{\mid }=O(\log (1\mathrm{/}e))$, giving $\tilde{O}(d_F{h}_F+1)$, without multiplying by the frequency count.

For Hermitian $F,\widehat{F}$, differentiating $e^{i(u-v)F}{e}^{iv\widehat{F}}$ and integrating its finite matrix entries gives $\mathrm{\parallel }{e}^{iuF}-e^{iu\widehat{F}}\mathrm{\parallel }\le \mathrm{\mid }u\mathrm{\mid }\mathrm{\parallel }F-\widehat{F}\mathrm{\parallel }$, for either sign of $u$. For positive $G,\widehat{G}$, differentiating $e^{-(a-v)G}{e}^{-v\widehat{G}}$ on $[0,a]$ similarly gives $\mathrm{\parallel }{e}^{-aG}-e^{-a\widehat{G}}\mathrm{\parallel }\le a\mathrm{\parallel }G-\widehat{G}\mathrm{\parallel }$, since spectral calculus makes both factors contractions. No commutation is used. Choose ${\delta }_t\le \min (1\mathrm{/}8,e\mathrm{/}100)$; target Gibbs-amplitude error at $a=1\mathrm{/}2$ is at most $e\mathrm{/}200$. If comparing individual target evolutions, also impose ${\delta }_t\le \zeta \mathrm{/}(4(U_t+1))$ for total absolute time bound $U_t$ and SELECT budget $\zeta$. This increases certified coefficient precision logarithmically, without adding matrix queries. Allocate finite signal and rotation synthesis within the remaining block and hybrid budgets.

The sparse bridge encodes a padded $F\oplus 0$. Prepare ${\mathrm{\Phi }}_n$ on the original labels, rather than a uniform reference on the enlarged register. Ideal evolutions preserve that original subspace, so Fourier accuracy is needed only on the original spectrum; padded zeros outside the Gibbs approximation interval cause no change. Include padded-system and simulator-work leakage in the clean-input isometry error. The hybrid in [F3] then controls it throughout repeated calls.

Apply [F5] once to ${\widehat{L}}_t$. Its rational lower shift $\tilde{\lambda }$ lies between ${\lambda }_{\min }({\widehat{L}}_t)-1\mathrm{/}4$ and ${\lambda }_{\min }({\widehat{L}}_t)$ on the good event. Put ${\widehat{G}}_t={\widehat{L}}_t-\tilde{\lambda }I+3I\mathrm{/}2$ and $G_t=L_t-\tilde{\lambda }I+3I\mathrm{/}2$. The variational quadratic-form characterization gives $\mathrm{\mid }{\lambda }_{\min }({\widehat{L}}_t)-{\lambda }_{\min }(L_t)\mathrm{\mid }\le {\delta }_t$. Hence both minima lie in $[1,2]$, and $\mathrm{\parallel }{G}_t\mathrm{\parallel },\mathrm{\parallel }{\widehat{G}}_t\mathrm{\parallel }\le 2\eta t+2=2K_t$ for $K_t=1+\eta t$: the decoded spectral diameter is at most $2\eta t+2{\delta }_t$ with minimum at most $7\mathrm{/}4$, while the target diameter is at most $2\eta t$ with minimum at most $7\mathrm{/}4+{\delta }_t$. A common scalar shift changes no target normalized Gibbs density. Freeze it and all coefficient, norm, cutoff and synthesis data before constructing indexed trace labels. Constant-total-time QPE and [F5] cost $\tilde{O}(\sqrt{n}{D}_t{K}_t)$ derived queries, or $\tilde{O}(\sqrt{n}{s}^2{t}^2{K}_t)$ raw queries by step 1.1.

For diagonal inputs, evaluate the finite scalar ${\widehat{L}}_t(i)$ using $O(t)$ original diagonal-value queries and no sparse locations. Round its value to error at most $1\mathrm{/}8$, preserve the uniform index, and apply the robust minimum from [F6]. Its good selected label $s$ is at least ${\lambda }_{\min }({\widehat{L}}_t)-1\mathrm{/}8$ by goodness and at most that minimum plus $1\mathrm{/}8$ by nondomination at a minimizing index. It costs $\tilde{O}(\sqrt{n})$ scalar evaluations; comparisons are finite rational comparisons, not exact irrational-energy comparisons. Measure once and freeze this shift. With ${\widehat{g}}_i={\widehat{L}}_t(i)-s+3\mathrm{/}2$, $g_i=L_t(i)-s+3\mathrm{/}2$, and ${\delta }_t\le \min (1\mathrm{/}8,\mu \mathrm{/}100)$, both minima lie in $[1,2]$ and $\mathrm{\mid }{g}_i-{\widehat{g}}_i\mathrm{\mid }\le {\delta }_t$. Thus $Z={\sum }_i{e}^{-g_i}\ge e^{-2}$ and the target Gibbs ratio is unchanged.

Use [F4] for ${\widehat{G}}_t$ with analytic error parameter $e\mathrm{/}10$, fixed extension margin $1\mathrm{/}2$, and interval parameters $x_0=K_t^{+}+1\mathrm{/}2,r_F=K_t^{+}$, where a certified rational enclosure chooses $K_t\le K_t^{+}\le K_t+1$. Its coefficient budget is one, and $K_t^{+}=O(K_t)$ preserves every count. The natural normalization $1+e\mathrm{/}80$ is further diluted by the known scalar $(1+e\mathrm{/}80)\mathrm{/}(1+e\mathrm{/}8)$ to the trace-common $B_G^{+}=1+e\mathrm{/}8$. The analytic approximation, coefficient rounding, finite SELECT, PREPARE and dilution errors are allocated to less than $e\mathrm{/}2$; step 3.1 contributes at most $e\mathrm{/}200$ against the target block. Thus [F6]'s final error at most $e$ holds. The observable $F_A=\frac{1}{2}\sqrt{I+A\mathrm{/}2}$ uses the fixed interval $[-1,1]$, margin $1\mathrm{/}2$, coefficient budget one and the same final $B_A^{+}=1+e\mathrm{/}8$. Its baseline is $I\mathrm{/}(2B_A^{+})$, with the same frozen Gibbs block and normalization. Rational upper enclosures $h_G\ge 2K_t$ with $h_G=O(K_t)$ suffice.

Given diagonal $a_i\in [-1,1]$, compute an approximation to $f_i=(1+a_i\mathrm{/}2)e^{-g_i}\mathrm{/}4$ from the finite values ${\widehat{g}}_i,a_i$, then rotate a flag to that probability with absolute error at most $\mu$. Allocate $\mu \mathrm{/}2$ to finite arithmetic/rotation; the energy perturbation adds at most $(3\mathrm{/}8){\delta }_t<\mu \mathrm{/}2$ by step 3.1. Prepare the original reference, retain arithmetic work, and reverse the entire circuit for its inverse. Orthogonal index labels make its success probability an additive-$\mu$ approximation of $p_A=(4n{)}^{-1}{\sum }_i(1+a_i\mathrm{/}2)e^{-g_i}$; use $a_i=0$ and the same shift for $p_0=Z\mathrm{/}(4n)$. Then $p_0>1\mathrm{/}(32n)$, $p_A\ge p_0\mathrm{/}2$, and $p_A\mathrm{/}{p}_0=1+\mathrm{tr}(A\rho )\mathrm{/}2$. With $\mu \le \theta \mathrm{/}(100000n)$ the same elementary ratio-stability and relative-estimation argument of [F6] applies, with floor $1\mathrm{/}(1024n)$ and $\tilde{O}(\sqrt{n}\mathrm{/}\theta )$ complete scalar flag calls.

Step 2.2 and step 5.1 give $\tilde{O}(D_t{K}_t)$ derived Gibbs queries and $\tilde{O}(s)$ observable queries per complete flag circuit. Their raw costs are respectively $\tilde{O}(D_t{K}_{t}st)$ and $\tilde{O}(s^2)$ by step 1.1, so $Q_{f,t}=\tilde{O}(s^2{t}^2{K}_t)$. Inverses, coherent controls and the baseline have the same order. By [F6], one trace label costs $\tilde{O}(\sqrt{n}{s}^2{t}^2{K}_t\mathrm{/}\theta )$ raw queries, and two sparse replies cost $\tilde{O}(\sqrt{nm}{s}^2{t}^2(1+\eta t)\mathrm{/}\theta )$ per round. The separate scalar $C$ trace and once-only shift are dominated. Every Gibbs/reference preparation inside relative estimation is counted, using the inverse of its whole circuit, without a normalized postselected-state inverse.

Generate Gibbs Fourier coefficients once per round: their arithmetic count is $\tilde{O}(K_t^5)$, summing to $\tilde{O}(T+{\eta }^5{T}^6)=\tilde{O}(Q^7)$. Their actual bit costs and simulator phase generation remain in $F_t$. The observable coefficient pattern is common to every index and is also generated once; only its evolution SELECT depends on $j$. A length-$J_t=\tilde{O}(K_t)$ coefficient table has a binary-tree PREPARE with $O(J_t)$ conditional rotations: each node splits its incoming amplitude in the ratio of its two subtree weights, giving square-root leaf weights by induction, with fixed completion at zero-weight nodes. Its phases are in SELECT and its norm slack is diluted. This is an explicit rotation/table-use count, with weight arithmetic, precision and synthesis separately charged; its arithmetic order is dominated by $D_t{K}_t$. Each round adds only a constant number of new coefficient records, and no dense list of all matrix rows is materialized.

The scalar exponential requires no factor ${\max }_i{g}_i$. Put $B=\lceil {\log }_2(32\mathrm{/}\mu )\rceil$, found by rational doubling comparisons. When ${\widehat{g}}_i\ge B$, use zero, with error $e^{-B}\le 2^{-B}\le \mu \mathrm{/}32$. Otherwise $1\le {\widehat{g}}_i\le B$. Starting with $n_0=2$, double $n_0$ until the exact rational test $3^B{B}^{n_0}\mathrm{/}{n}_0!\le \mu \mathrm{/}64$ passes, then evaluate the Taylor polynomial through degree $n_0-1$. Its remainder is at most $e^B{B}^{n_0}\mathrm{/}{n}_0!\le \mu \mathrm{/}64$; the elementary exponential series gives $2\le e<3$. For even $n_0\ge 4B^2$, the final half of the factorial gives $B^{n_0}\mathrm{/}{n}_0!\le (2B^2\mathrm{/}{n}_0{)}^{n_0\mathrm{/}2}\le 2^{-n_0\mathrm{/}2}$. Thus any even $n_0\ge \max (4B^2,2\lceil {\log }_2(64\cdot 3^B\mathrm{/}\mu )\rceil )$ passes, and doubling selects $O({\log }^2(1\mathrm{/}\mu ))$ terms. Exact rational evaluation followed by one rounding controls cancellation without assuming unit-cost long integers; bit lengths and work are polynomial in this term count and the actual energy encoding length. Clip the probability to $[0,1]$.

Summing step 6.1 over at most $T$ rounds gives $\tilde{O}(\sqrt{nm}{s}^2{\theta }^{-1}(T^3+\eta T^4))$. Insert [F1]'s $T=\tilde{O}(Q^2)$, $\eta =\tilde{O}(Q^{-1})$, and ${\theta }^{-1}=O(Q)$ to obtain $\tilde{O}(\sqrt{nm}{s}^2{Q}^8)$. Since the present nontrivial regime has $Q>1\mathrm{/}2$, the $Q^7$ term is also $O(Q^8)$; equivalently use $\max (1,Q)$ without changing the order. The outer threshold count is logarithmic. The early-time $1$ in $K_t$ therefore creates no missing query factor.

To implement a finite probability rotation, bisect $[0,\pi \mathrm{/}2]$, approximate its midpoint ${\sin }^2$ to fixed error $\mu \mathrm{/}32$ by bounded-argument Taylor arithmetic, and compare the resulting interval with the target rational probability. If they overlap, that midpoint already has probability error at most $\mu \mathrm{/}16$ after target rounding; otherwise the comparison identifies the correct half. After $O(\log (1\mathrm{/}\mu ))$ iterations its width also suffices, since $\mathrm{\mid }{\sin }^{2}x-{\sin }^{2}y\mathrm{\mid }\le 2\mathrm{\mid }x-y\mathrm{\mid }$. Certified rational enclosures for $\pi$ and finite rotations have their actual arithmetic/synthesis price. Reversibly compute the angle, apply its binary-controlled rotations, and retain or uncompute scratch as declared. There is a fixed finite cap and no equality-dependent refinement. This supplies the scalar flag with $O(t)$ matrix queries, including its actual inverse/control forms; large energies affect encoding/comparison costs rather than matrix-query count.

The primitive counts are $N_{f,t}=\tilde{O}(\sqrt{nm}\mathrm{/}\theta )$ and $N_{s,t}=\tilde{O}(\sqrt{n})$. Multiplying them by their actual complete-circuit prices and adding factory, estimator, score-comparison, memory, output, arithmetic and history costs gives exactly the additive record in the Statement. In particular reference preparation contributes $\tilde{O}(\sqrt{nm}{\theta }^{-1}T{C}_{\mathrm{\Phi }})=\tilde{O}(\sqrt{nm}{Q}^3{C}_{\mathrm{\Phi }})$ per threshold run, rather than one $C_{\mathrm{\Phi }}$. For power-of-two $n$, [F5] supplies $C_{\mathrm{\Phi }}=O(\log n)$; otherwise retain its supplied repeated price and separately budget any reference error. The scan/sort implementation uses $O(st{\log }^2(st+2))$ compare/exchanges per derived row call by padded bitonic sorting, whose recursive half-sorts and logarithmic merge give that recurrence. Each comparison, rational multiplication/addition and reversible history has its actual bit/gate price. A chosen QRAM implementation instead includes its actual construction/update/address-unitary prices. Therefore the stated conditional gate boundary follows, without deriving bit efficiency from an oracle count.

The diagonal trace label consequently costs $\tilde{O}(\sqrt{n}t\mathrm{/}\theta )$ raw queries. The once-per-round approximate minimum costs $\tilde{O}(\sqrt{n}t)$ and is dominated. Two robust minima give round cost $\tilde{O}(\sqrt{nm}t\mathrm{/}\theta )$, so summation yields $\tilde{O}(\sqrt{nm}{\theta }^{-1}{T}^2)=\tilde{O}(\sqrt{nm}{Q}^5)$. This scalar construction removes both sparse-row growth and the $K_t$ evolution factor; it is not a consequence of setting $s=1$ in step 7.1. All repeated reference, scalar arithmetic, compilation, comparison, classical control, output and optional memory prices remain in step 8.1's additive record. The source-like same-order diagonal gate conclusion is therefore conditional on these prices fitting that model and envelope. This proves both query bounds and the stated gate-cost boundary.