Variance-aware quantum Monte Carlo

Input. A coherent finite sampler $V$ whose decoded real output $v$ has finite range, a known rational upper bound $\sigma \ge 0$ with $\mathrm{Var}(v)\le {\sigma }^2$, rational target $\epsilon >0$, and rational desired failure probability $0<\rho <1$. All sample, value, inverse, controlled, predicate, and rotation circuits are explicit inputs with separately recorded costs. Measurement law of a coherent sampler identifies the distribution of each measured output with the sampler law. Every observable supplied to $\mathrm{PositiveMean}$ is computed on fresh executions of $V$ using its explicitly supplied, costed value, predicate, rotation, inverse, and controlled operations. For an observable depending on a previously measured classical value, the input supplies the corresponding circuits for each admissible value and charges their selection or computation; the measured value is held fixed while those circuits are used.

If $\sigma =0$, measure one fresh output and return it. Otherwise set ${\epsilon }^{\mathrm{\prime }}=\min (\epsilon ,\sigma \mathrm{/}2)$ and reserve ${\epsilon }_0=7{\epsilon }^{\mathrm{\prime }}\mathrm{/}8$ for the ideal estimator. Define the following finite routine for any nonnegative finite-valued output $h$ and rational parameters $a,{\rho }_1$ with $0<a<1\mathrm{/}2$ and $0<{\rho }_1<1$:

1. Let $k$ be the least nonnegative integer with $2^{k}a\ge 1$, and let $M=2^m$ be the least power of two, with $m\ge 0$ an integer, for which $M^2{a}^2\ge {10}^{6}k$. Their exact rational searches terminate by Finite termination of the dyadic estimator parameter searches. Moreover $k\ge 2$ because $2a<1$; since $Ma\ge 0$ and $(Ma{)}^2\ge {10}^{6}k$, Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$ and Squaring is monotone on the nonnegatives give $Ma\ge 1000\sqrt{k}$, hence $M\ge 1000\sqrt{k}\mathrm{/}a>2000$.
2. For $\mathrm{\ell }=0$, define $h_0=h{\mathbf{1}}_{[0,1)}$. For $1\le \mathrm{\ell }\le k$, define $h_{\mathrm{\ell }}=2^{-\mathrm{\ell }}h{\mathbf{1}}_{[2^{\mathrm{\ell }-1},2^{\mathrm{\ell }})}$. Each $h_{\mathrm{\ell }}$ lies in $[0,1)$.
3. Since $M>2000$, the target ${\eta }_M=88\mathrm{/}(7M)$ satisfies $0<{\eta }_M<1$ and $M\ge 4$. For each $\mathrm{\ell }=0,\dots ,k$, run Amplitude-estimation expectation estimator on $h_{\mathrm{\ell }}$ over $[0,1]$ with target ${\eta }_M$ and failure probability $1\mathrm{/}[10(k+1)]$. This selects phase-register size exactly $M$ under the current QA13 interface. Call the result $u_{\mathrm{\ell }}$ and form $P(h)=u_0+{\sum }_{\mathrm{\ell }=1}^k{2}^{\mathrm{\ell }}{u}_{\mathrm{\ell }}$.
4. Repeat this whole binned procedure an odd number $R_1$ of fresh independent circuit executions, as required by Quantum query algorithm, where $R_1$ is the least odd positive integer at least $\lceil 2U_1\mathrm{/}(3\mathrm{/}10{)}^2\rceil +1$. Here $U_1$ is the upper endpoint of the certified logarithm interval for $\ln (1\mathrm{/}{\rho }_1)$ from A terminating rational enclosure for the natural logarithm, computed with interval width at most $1\mathrm{/}4$. Return the median. This defines $\mathrm{PositiveMean}(h,a,{\rho }_1)$ for $0<{\rho }_1<1$.

For one outer trial, measure one fresh sampler output $v_0$ and set $m=v_0\mathrm{/}\sigma$. Holding this coarse value fixed, let $Y=v_1\mathrm{/}\sigma$ be the normalized output of a new sampler execution independent of the coarse measurement and define $B_m(Y)=Y-m,h_{-,m}(Y)=(-B_m(Y)){\mathbf{1}}_{B_m(Y)<0}\mathrm{/}4,h_{+,m}(Y)=B_m(Y){\mathbf{1}}_{B_m(Y)\ge 0}\mathrm{/}4.$ Run $\mathrm{PositiveMean}$ separately on $h_{-,m}$ and $h_{+,m}$ with $a={\epsilon }_0\mathrm{/}(32\sigma )$ and ${\rho }_1=1\mathrm{/}9$, using fresh sampler executions independent of the coarse measurement and of the other call, conditional on the fixed $m$. If the results are $u_{-},u_{+}$, return $\sigma (m-4u_{-}+4u_{+})$. Count the coarse state preparation and all fresh preparations used by both $\mathrm{PositiveMean}$ calls in the total preparation count; every controlled or inverse call remains separately charged. Let $U_0$ be the upper endpoint of the certified logarithm interval for $\ln (1\mathrm{/}\rho )$ from A terminating rational enclosure for the natural logarithm, computed with interval width at most $1\mathrm{/}4$. Repeat the outer trial an odd number $R_0$ of fresh independent circuit executions, as required by Quantum query algorithm, where $R_0$ is the least odd positive integer at least $\lceil 18U_0\rceil +1$, and output the median.

Here $\ln$ is the natural logarithm from The natural logarithm as the inverse of the exponential function. For each logarithm input $x=1\mathrm{/}{\rho }_1$ or $x=1\mathrm{/}\rho$, its rational subroutine runs Rational natural-logarithm enclosure search on $(x,1\mathrm{/}8)$; A terminating rational enclosure for the natural logarithm certifies tail at most $1\mathrm{/}8$ and interval width at most $1\mathrm{/}4$; every ceiling uses the interval's upper endpoint. The procedure is a finite sequence of operations in the supplied exact-access model, and the accuracy theorem assumes exact value, predicate, rotation, and reflection operations. It makes no guarantee for approximate replacements: any finite-gate implementation needs a separate certified error analysis that transfers both output accuracy and success probability, with compilation, gate, precision, bit, and ancilla costs recorded. No state reflection or value-loading operation is free.