Gibbs purification error and resource bound

By the reverse triangle inequality, $\mathrm{\parallel }\tilde{v}\mathrm{\parallel }\ge \mathrm{\parallel }v\mathrm{\parallel }-\mathrm{\parallel }\tilde{v}-v\mathrm{\parallel }\ge \sqrt{p_G}-\zeta \ge \sqrt{p_G}\mathrm{/}2$, so the implemented branch is nonzero and its probability is at least $p_G\mathrm{/}4$. Also $\parallel \frac{\tilde{v}}{\mathrm{\parallel }\tilde{v}\mathrm{\parallel }}-\frac{v}{\mathrm{\parallel }v\mathrm{\parallel }}\parallel \le \frac{\mathrm{\parallel }\tilde{v}-v\mathrm{\parallel }+\mathrm{\mid }\mathrm{\parallel }v\mathrm{\parallel }-\mathrm{\parallel }\tilde{v}\mathrm{\parallel }\mathrm{\mid }}{\mathrm{\parallel }v\mathrm{\parallel }}\le \frac{2\zeta }{\sqrt{p_G}}\mathrm{.}$ This proves the conditional-state bound.

Since $p_G>0$, [F3] supplies a rational $q$ strictly between $p_G\mathrm{/}8$ and $p_G\mathrm{/}4$. Supply this finite rational together with its lower-bound certificate to [F2]; step 1.1 shows $q$ is below the implemented success probability. Apply [F2] with $p_{\mathrm{l}\mathrm{o}\mathrm{w}}=q$ and rational failure target $1\mathrm{/}3$. It returns the same normalized good projection as the conditional branch from step 1.1 with probability at least $2\mathrm{/}3$. Since $q^{-1\mathrm{/}2}<\sqrt{8}{p}_G^{-1\mathrm{/}2}$, its preparation/reflection call count is $O(p_G^{-1\mathrm{/}2})$ for this fixed confidence; supplied QSVT, block, reference-state, inverse, compilation and precision costs, including acquisition and verification of the rational floor certificate, remain additional. Rational density establishes existence, not a free algorithm for comparing an exact real trace.

For the optional normalized branch of [F1], condition on the shift good event. The algorithm gives ${\lambda }_{\min }(G)\le 2$, $B=B_G^{+}=1+e\mathrm{/}8\le 17\mathrm{/}16$, and $p_G=\mathrm{tr}(e^{-G})\mathrm{/}[d(B_G^{+}{)}^2]$. For completeness, choose the orthonormal eigenbasis in [F5], listing eigenvalues with multiplicity as ${\lambda }_1,\dots ,{\lambda }_d$, with ${\lambda }_1={\lambda }_{\min }(G)\le 2$. Then $\mathrm{tr}(e^{-G})={\sum }_{j=1}^d{e}^{-{\lambda }_j}\ge e^{-{\lambda }_1}\ge e^{-2}$ by [F4] and [F5], so $p_G\ge e^{-{\lambda }_{\min }(G)}\mathrm{/}[d(B_G^{+}{)}^2]$. The factorial recursion in [F4] gives $k!\ge 2^{k-1}$ for $k\ge 2$, with $1\mathrm{/}3!=1\mathrm{/}6$ smaller than $2^{-2}=1\mathrm{/}4$ by $1\mathrm{/}12$. For every integer $M\ge 3$, the finite geometric identity ${\sum }_{k=2}^M{2}^{1-k}=1-2^{1-M}$ follows by subtracting half the finite sum from itself. Hence ${\sum }_{k=0}^{M}1\mathrm{/}k!\le 2+(1-2^{1-M})-1\mathrm{/}12\le 35\mathrm{/}12$. The convergent exponential series in [F4] therefore has $\exp (1)\le 35\mathrm{/}12<3$: a larger limit would contradict that bound on all sufficiently late partial sums. The addition law gives $\exp (2)<9$ and $\exp (-2)=1\mathrm{/}\exp (2)>1\mathrm{/}9$, using $\exp (0)=1$ from its series. Consequently $p_G>1\mathrm{/}[9d(17\mathrm{/}16{)}^2]>1\mathrm{/}(16d)$. The algorithm now chooses $e\le \min (1,{\epsilon }_{out})\mathrm{/}(10000\sqrt{d})$; its successful-vector error is at most $e$, so $e<\sqrt{p_G}\mathrm{/}2$. Step 1.1 gives actual probability greater than $1\mathrm{/}(64d)$ and normalized vector error at most $8e\sqrt{d}\le {\epsilon }_{out}$. Hence [F2] applies to its declared rational floor $1\mathrm{/}(64d)$. For failure target $\rho$, this branch uses $O(\sqrt{d}(1+\ln (1\mathrm{/}\rho )))$ amplification calls, conditional on the shift good event; shift failure and all supplied implementation costs are accounted for separately. This fixed floor is not asserted to be a constant fraction of $p_G$.