Variance-aware quantum Monte Carlo guarantee

Suppose $\sigma =0$. By [F10], the fresh measured output has the finite sampler law; [F11] identifies the general expectation in [F1] with its finite weighted sum. Then $\mathbb{E}[(v-\mathbb{E}v{)}^2]=0$. By [F8], this finite expectation is a sum of nonnegative terms, so every outcome of positive probability has $v=\mathbb{E}v$. A fresh measurement therefore returns the mean with probability one.

Now suppose $\sigma >0$ and write $Y=v\mathrm{/}\sigma$, ${\mu }^{\mathrm{\prime }}=\mathbb{E}[Y]$. By [F10]–[F11], the measured coarse value and the general moments have the finite laws and expectations used in [F1]–[F2]. Scaling gives $\mathrm{Var}(Y)\le 1$. In one trial the algorithm observes $m$ from the same law as $Y$; [F2] gives $\mathrm{Pr}(\mathrm{\mid }m-{\mu }^{\mathrm{\prime }}\mathrm{\mid }\ge 3)\le 1\mathrm{/}9$.

Condition on the fixed coarse value $m$ and let $Y$ denote the normalized fresh output specified by [F5]. On the event $\mathrm{\mid }m-{\mu }^{\mathrm{\prime }}\mathrm{\mid }<3$, the centered value $B_m(Y)=Y-m$ satisfies $\mathrm{\parallel }{B}_m(Y)\mathrm{/}4{\mathrm{\parallel }}_2^2=\frac{\mathbb{E}[(Y-m{)}^2\mid m]}{16}=\frac{\mathrm{Var}(Y)+({\mu }^{\mathrm{\prime }}-m{)}^2}{16}<\frac{10}{16}<1.$ The identity follows by writing $Y-m=(Y-{\mu }^{\mathrm{\prime }})+({\mu }^{\mathrm{\prime }}-m)$ and using the conditional mean $\mathbb{E}[Y\mid m]={\mu }^{\mathrm{\prime }}$ to remove the cross term; the fresh draw is independent of $m$. By [F10]–[F11], these conditional expectations are finite weighted sums for the conditional sampler law. Since $0\le h_{\pm ,m}\le \mathrm{\mid }{B}_m\mathrm{\mid }\mathrm{/}4$, both positive parts also have conditional $L^2$ norm less than one.

Here ${\epsilon }_0=7{\epsilon }^{\mathrm{\prime }}\mathrm{/}8$ and $a={\epsilon }_0\mathrm{/}(32\sigma )\le 1\mathrm{/}64$. Condition on any good coarse value $m$. On the good coarse-sample event, [F4] applied to both fresh conditional outputs with ${\rho }_1=1\mathrm{/}9$ yields $\mathrm{\mid }{u}_{\pm }-\mathbb{E}[h_{\pm ,m}(Y)\mid m]\mathrm{\mid }<4a$ except with conditional probability at most $2\mathrm{/}9$. By finite-sum linearity, identified with general linearity by [F11] and [F3], $\mathbb{E}[Y\mid m]=m+4(\mathbb{E}[h_{+,m}(Y)\mid m]-\mathbb{E}[h_{-,m}(Y)\mid m])$. Thus the normalized trial estimate $m+4(u_{+}-u_{-})$ differs from $\mathbb{E}[Y]={\mu }^{\mathrm{\prime }}$ by less than $4(4a+4a)=32a={\epsilon }_0\mathrm{/}\sigma$. Multiplying by $\sigma$ gives error less than ${\epsilon }_0\le {\epsilon }^{\mathrm{\prime }}\le \epsilon$ in the exact coherent-access model.

The coarse-sample failure probability is at most $1\mathrm{/}9$, and conditional on any good coarse value the two positive-estimation failures together have probability at most $2\mathrm{/}9$. A union bound therefore gives each outer trial success probability at least $2\mathrm{/}3$.

The outer trials use fresh independent preparations and measurements. If their odd count is $R_0$, a failed median requires at least $R_0\mathrm{/}2$ trial failures. [F6] bounds that probability by $\exp (-R_0\mathrm{/}18)$ because each trial fails with probability at most $1\mathrm{/}3$; the algorithm sets $R_0\ge \lceil 18U_0\rceil +1$ with $U_0\ge \ln (1\mathrm{/}\rho )$ by [F9], so this is at most $\rho$. This proves the accuracy guarantee.

Let $z_0=\sigma \mathrm{/}{\epsilon }_0=(8\mathrm{/}7)L$. Then $a^{-1}=32z_0=\mathrm{\Theta }(L)$ and $k=\lceil {\log }_2(32z_0)\rceil =\mathrm{\Theta }(\ln L)$ for $L=\max (2,\sigma \mathrm{/}\epsilon )$. By [F4], one positive estimate uses $O(\ln L\ln \ln (e^e+L))$ copies in either access mode and $O(L(\ln L{)}^{3\mathrm{/}2}\ln \ln (e^e+L))$ state reflections in repeated controlled-$Q$ access at confidence $1\mathrm{/}9$. Each outer trial uses two such estimates and one coarse sample; [F9] gives $R_0=O(1+\ln (1\mathrm{/}\rho ))$. This yields the stated preparation bound in either mode and the reflection bound in repeated access; supplied-power implementations retain their separate declared power costs from [F4].

In each binned amplitude-estimation call, the initial-state reflection is for the complete state preparation, including the observable-controlled rotation, by [F12]. The coarse centering measurement is a separate preparation of the unrotated sampler $V$; $V(2\mathrm{\mid }0⟩⟨0\mathrm{\mid }-I)V^{†}$ alone is not a bin reflection unless that complete preparation is exactly $V$. Sampler, inverse, controlled, rotation, value-computation, and reflection implementations remain explicitly supplied and charged. The proof counts copies and state reflections separately and infers no gate or query implementation from the variance promise.