Quantum Sampling, Expectation, and Monte Carlo — Examples

Let $D$ be a classical procedure that, on each call, returns a bit $x\in \{0,1\}$ with $\mathrm{Pr}(x=1)=p$. Its interface is a classical input/output map from a fresh random seed to a bit; it has no quantum-register input and specifies no unitary $V$.

The law of $D$ does not provide a circuit for $V\mathrm{\mid }0⟩=\sqrt{1-p}\mathrm{\mid }0⟩\mathrm{\mid }0⟩\mathrm{\mid }{w}_0⟩+\sqrt{p}\mathrm{\mid }1⟩\mathrm{\mid }1⟩\mathrm{\mid }{w}_1⟩$, nor circuits for $V^{†}$, controlled $V$, value rotations, or reflections. Thus the sample-only object fails the explicit interface required by [F1] and cannot be substituted directly into QA29's coherent-query bound.

This refutes the statement about the interface alone. It does not rule out constructing a separate coherent preparation circuit from additional information about $p$; such a circuit and all its costs would be new supplied inputs.

Here $\mu =(1-p)\cdot 0+p\cdot 1=p$ by [F1] and the two-point law [F3]. The range is $[a,b]=[0,1]$, so [F4] gives $q(x)=x$.

Conditional on sample $x$, the controlled rotation places good probability $x$. Averaging over the sample law, the total good probability is $(1-p)\cdot 0+p\cdot 1=p=\mu$.

Thus the QA13 amplitude estimator is estimating the Bernoulli mean itself; [F5] yields additive error $\epsilon$ with confidence $1-\delta$ in either declared access mode. In repeated controlled-$Q$ access it uses $O({\epsilon }^{-1}(1+\ln (1\mathrm{/}\delta )))$ controlled sampler/reflection rounds; in supplied controlled-power access its power queries retain their separately declared prices. The circuit costs remain those declared by the supplied sampler.