Sparse-oracle Gibbs-state purification

Input a finite Hermitian matrix $H$, a nonnegative coefficient $\eta$, a rational certified bound $K\ge \mathrm{\parallel }\eta H\mathrm{\parallel }$, dimension $d\ge 1$, costed reference preparation ${\mathrm{\Phi }}_d$, controlled sparse evolution circuits and their inverses, an output accuracy, and shift-confidence and implementation budgets. For the optional normalized-output branch, supply ${\epsilon }_{out}>0$ and a rational amplification failure target $0<\rho <1$. All access, coefficient generation, rotations, arithmetic, precision synthesis, reference preparation and memory operations have declared costs. The supplied finite decoded matrix may approximate the target matrix only with a stated operator-norm error budget included below.

1. Freeze the energy shift. Choose $0<e\le 1\mathrm{/}2$ and an exact finite decoded Hermitian $\widehat{L}$ with $\mathrm{\parallel }\widehat{L}-\eta H\mathrm{\parallel }\le \delta \le \min (1\mathrm{/}8,e\mathrm{/}100)$ and certified norm bound $K+\delta$. Run the explicit finite coherent spectral sampler and capped generalized minimum procedure in Coherent spectral minimum and a frozen Gibbs energy shift on $\widehat{L}$. Measure its rational output once, set $\tilde{\lambda }=s-1\mathrm{/}8$, and freeze the decoded $\widehat{G}=\widehat{L}-(\tilde{\lambda }-3\mathrm{/}2)I$ and target $G=\eta H-(\tilde{\lambda }-3\mathrm{/}2)I$, their norm certificates and all ensuing circuit parameters. On the shift good event the decoded minimum is in $[3\mathrm{/}2,7\mathrm{/}4]$; the variational bound $\mathrm{\mid }{\lambda }_{min}(\widehat{L})-{\lambda }_{min}(\eta H)\mathrm{\mid }\le \delta$ puts the target minimum in $[1,2]$. For $\eta =0$ the normalized output is the supplied ${\mathrm{\Phi }}_d$ directly. A shift failure belongs to the declared confidence budget.
2. Generate the finite block. Choose $0<e\le 1\mathrm{/}2$ and a rational $K_G\ge \max (\mathrm{\parallel }G\mathrm{\parallel },\mathrm{\parallel }\widehat{G}\mathrm{\parallel })\mathrm{/}2$. Construct the block for $\widehat{G}$ and include its target perturbation $\mathrm{\parallel }{e}^{-\widehat{G}\mathrm{/}2}-e^{-G\mathrm{/}2}\mathrm{\parallel }\le \delta \mathrm{/}2$ in the allocated error. For $f(x)=e^{-x\mathrm{/}2}$ use $x_0=K_G+1\mathrm{/}2$, $r=K_G$, $\mathrm{\Delta }=1\mathrm{/}2$, $B=1$. Its Taylor coefficients are $a_k=e^{-x_0\mathrm{/}2}(-1\mathrm{/}2{)}^k\mathrm{/}k!$. Execute the finite arcsine convolution, truncation, signed-binomial coefficient construction, coefficient rounding and normalization in Certified finite smooth Fourier approximation and LCU normalization. Use its explicit finite $K,L,M$ cutoffs, enlarged by certified upper enclosures when necessary. Prepare the finite coefficient vector, apply the signed-frequency controlled evolutions, unprepare it and dilute the clean flag to common normalization $B_G^{+}=1+e\mathrm{/}8$. Allocate coefficient, rotation, evolution and decoded-matrix errors so the final successful compression differs from $e^{-G\mathrm{/}2}\mathrm{/}{B}_G^{+}$ by at most $e$. Their sum is an input certificate, and every circuit is retained with its actual adjoint and controlled implementation.
3. Unmeasured flag interface. Prepare ${\mathrm{\Phi }}_d$ and apply the block on its first factor. The ideal zero-work vector is $((e^{-G\mathrm{/}2}\mathrm{/}{B}_G^{+})\otimes I){\mathrm{\Phi }}_d$, with probability $\mathrm{tr}(e^{-G})\mathrm{/}[d(B_G^{+}{)}^2]$. Return this entire unmeasured circuit and its actual inverse when a coherent flagged sampler is requested. A caller constructing indexed trace samplers reuses these frozen parameters; it does not rerun ShiftMin within that sampler.
4. Optional normalized output. To output a normalized purification, use step 2 with accuracy $0<e\le \min (1,{\epsilon }_{out})\mathrm{/}(10000\sqrt{d})$, invoke the finite direct-sample/random-iteration capped amplification construction of Capped randomized amplitude amplification preserves a flagged output with lower floor $1\mathrm{/}(64d)$ and failure target $\rho$, and measure only its supplied good/bad flag. On a good outcome return the normalized flag branch; on cap failure return explicit FAIL. Do not measure score, label, or work registers in this branch. The amplification lemma supplies the finite success and branch-state contract; no exact Grover peak or unbounded rejection loop is used. A caller needing an inverse uses the unmeasured circuit from step 3, rather than an inverse of this measured conditional output.

The identity energy shift changes no normalized Gibbs state. Non-power-of-two dimensions use the declared $C_{\mathrm{\Phi }}$ input. The algorithm supplies no uncharged matrix exponential, spectral projector, coefficient oracle or sparse-sum oracle. Its successful-vector and normalized-state bounds are proved separately in Gibbs purification error and resource bound ↗.