Quantum Sampling, Expectation, and Monte Carlo

A finite expectation-estimation task consists of a nonempty finite set $X$, a probability law $p:X\to [0,1]$ with ${\sum }_{x\in X}{p}_x=1$, and an exactly encoded real-valued function $g:X\to [a,b]$, where $a\le b$ are finite rationals. Its target is $\mu :={\mathbb{E}}_p[g]={\sum }_{x\in X}{p}_{x}g(x)\mathrm{.}$

For rational parameters $\epsilon >0$ and $0<\delta <1$, an $(\epsilon ,\delta )$ estimator is a randomized or quantum procedure that outputs a real number $\tilde{\mu }$ satisfying $\mathrm{Pr}(\mathrm{\mid }\tilde{\mu }-\mu \mathrm{\mid }\le \epsilon )\ge 1-\delta \mathrm{.}$ The task specifies the target law and success event only. A particular procedure must state how it accesses samples or coherent state preparation and must charge those resources separately.

A value that approximates an underlying real-valued observable to error $\tau$ defines a different task with target ${\mathbb{E}}_p[\tilde{g}]$; any claim about ${\mathbb{E}}_p[g]$ must add the encoding error $\tau$ to its error budget.

Let $R\ge 1$ be an integer, let $Z_1,\dots ,Z_R$ be independent Bernoulli random variables on a finite probability space with $\mathbb{E}[Z_i]\le p<1\mathrm{/}2$, and put $S={\sum }_{i=1}^R{Z}_i$. For every $t\ge 0$, $\mathrm{Pr}(S-\mathbb{E}S\ge t)\le e^{-2t^2\mathrm{/}R}\mathrm{.}$ Consequently, let $R$ be odd and let $T_1,\dots ,T_R$ be independent finite-valued real estimates on a finite probability space. If $I\subseteq \mathbb{R}$ is an interval and $\mathrm{Pr}(T_i\in I)\ge 1-p$ for every $i$, then their median (the middle order statistic) lies in $I$ except with probability at most $\exp (-2R(1\mathrm{/}2-p{)}^2)\mathrm{.}$

Input. Rational numbers $x>0$ and $\tau >0$. Output. A positive integer $N$ and a rational interval $[L,U]$.

Compute $y=(x-1)\mathrm{/}(x+1)$ and initialize $N=1$. At each iteration compute, by exact rational arithmetic, $S_N=2{\sum }_{j=0}^{N-1}\frac{y^{2j+1}}{2j+1},T_N=\frac{2\mathrm{\mid }y{\mathrm{\mid }}^{2N+1}}{(2N+1)(1-y^2)}\mathrm{.}$ If $T_N\le \tau$, return $N$ and $[L,U]=[S_N-T_N,S_N+T_N]$. Otherwise replace $N$ by $N+1$ and repeat. Each comparison is an exact rational comparison. Arithmetic and integer bit costs are charged separately; no running-time bound is part of this definition.

For a rational $x>0$, put $y=(x-1)\mathrm{/}(x+1)$. For each integer $N\ge 1$, define the rational partial sum and remainder bound $S_N(x):=2{\sum }_{j=0}^{N-1}\frac{y^{2j+1}}{2j+1},T_N(x):=\frac{2\mathrm{\mid }y{\mathrm{\mid }}^{2N+1}}{(2N+1)(1-y^2)}\mathrm{.}$ Then $\mathrm{\mid }y\mathrm{\mid }<1$ and $\mathrm{\mid }\ln x-S_N(x)\mathrm{\mid }\le T_N(x)\mathrm{.}$ For every rational tolerance $\tau >0$, the algorithm Rational natural-logarithm enclosure search terminates using rational comparisons. It returns the certified interval $[S_N(x)-T_N(x),S_N(x)+T_N(x)]$, whose width is at most $2\tau$ and which contains $\ln x$.

Let $a>0$ and $C>0$ be rational and let $k\ge 1$ be an integer. Each of the following exact rational searches terminates:

1. increase an integer $j\ge 0$ until $2^{j}a\ge 1$;
2. after fixing $k$, increase an integer $m\ge 0$ until $2^{2m}{a}^2\ge Ck$.

The first successful exponent is the least one satisfying its comparison. The second returns the least power of two $M=2^m$ with $M^2{a}^2\ge Ck$.

Let $G$ be a finite real random variable taking values in a finite interval $[a,b]$ with $a\le b$, and let $X_1,\dots ,X_n$ be independent copies of $G$, with $n\ge 1$. For ${\bar{X}}_n=n^{-1}{\sum }_{i=1}^n{X}_i$ and $\mu =\mathbb{E}[G]$, $\mathbb{E}[{\bar{X}}_n]=\mu ,\mathrm{Var}({\bar{X}}_n)=\frac{\mathrm{Var}(G)}{n}\le \frac{(b-a{)}^2}{4n}\mathrm{.}$ Consequently, for every $\epsilon >0$, $\mathrm{Pr}(\mathrm{\mid }{\bar{X}}_n-\mu \mathrm{\mid }>\epsilon )\le \frac{(b-a{)}^2}{4n{\epsilon }^2}\mathrm{.}$ The procedure uses exactly $n$ independent samples. If each draw and data load costs $C_{\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}}$ and $C_{\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}$, their total is $n(C_{\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{w}}+C_{\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}})$; arithmetic for the encoded values is an additional separately charged cost. When $a=b$, every sample equals $\mu =a$ and the failure probability is zero.

Let $X$ be a finite nonempty set with $p_x=1\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$ for each $x$, let $S\subseteq X$, and define $g(x)=1$ for $x\in S$ and $g(x)=0$ otherwise. Then the expectation task for $(X,p,g)$ has target $\mu =\mathbb{E}[g]=\frac{\mathrm{\mid }S\mathrm{\mid }}{\mathrm{\mid }X\mathrm{\mid }}\mathrm{.}$

Let $X$ be a finite nonempty set with probability law $p_x\ge 0$, ${\sum }_{x\in X}{p}_x=1$, and let the value register contain an exact finite encoding of a real function $g:X\to [a,b]$, where $a\le b$ are finite rationals. A coherent finite sampler for $(X,p,g)$ is an explicitly supplied finite-dimensional unitary $V$ on ordered sample, value, and work registers such that $V\mathrm{\mid }0⟩={\sum }_{x\in X}\sqrt{p_x}\mathrm{\mid }x⟩\mathrm{\mid }g(x)⟩\mathrm{\mid }{w}_x⟩,$ where the sample labels $\mathrm{\mid }x⟩$ are distinct computational-basis vectors and each work state $\mathrm{\mid }{w}_x⟩$ has norm one. Zero-probability labels may occur and need no special branch. The registers and their order use Finite registers and their ordered computational bases and Ordered tensor registers, their inner product, and wire permutations; each output is a pure state in the sense of Pure state and ray. The separate item Measurement law of a coherent sampler verifies the induced measurement law.

The access contract lists the actual circuits or oracle interfaces for $V$, $V^{†}$, controlled $V$ and controlled $V^{†}$, value decoding, reversible arithmetic, any coherent predicate and controlled rotation, and the reflections used by the chosen estimator. Their availability is explicit under Controlled Unitary Access and Inverse Unitary Access. A forward unitary alone does not grant an inverse or a controlled call.

The resource record follows Circuit-family and computation cost model: charge state preparation, inverse and controlled access, data loading, value comparison and arithmetic, controlled-rotation synthesis and precision, good-state and initial-state reflections, gates, width, ancillas, and classical postprocessing separately. The state-preparation circuit and its costs are inputs; a state description is not a free QRAM or preparation oracle.

For a coherent sampler $V$ with output state $\mathrm{\mid }\psi ⟩={\sum }_x\sqrt{p_x}\mathrm{\mid }x⟩\mathrm{\mid }g(x)⟩\mathrm{\mid }{w}_x⟩$ as in Coherent finite sampler and observable value, projective measurement of the sample register returns $x$ with probability $p_x$. If the value register is measured too, the pair $(x,g(x))$ has the same probability. The work register is not required to be measured, and work states for different labels need not be orthogonal.

Input. A Boolean domain $X=\{0,1{\}}^n$ with $N=2^n$, a predicate $f:X\to \{0,1\}$, a phase-register size $M=2^m$ for an integer $m\ge 2$ (so $M\ge 4$), and the uniform coherent access and controlled membership reflection required by Quantum counting by uniform-state amplitude estimation. Let $S=\{x:f(x)=1\}$.

Use the unchanged QA13 counting estimator Quantum counting by uniform-state amplitude estimation with this $M$ and its supplied access model, and return its exact algebraic fraction estimate $\tilde{\mu }=\tilde{t}\mathrm{/}N={\sin }^2(\pi y\mathrm{/}M)$ for the expectation task. Its real-valued count estimate $\tilde{t}=N\tilde{\mu }$ may also be reported, with count and expectation outputs explicitly distinguished. Do not round to an integer unless that additional postprocessing and its cost are explicitly requested. By Uniform counting is finite indicator expectation, this is the QA29 expectation task for the uniform law and observable $g={\mathbf{1}}_S$; the applicable count guarantee is Quantum counting error and boundary cases, whose phase-size hypothesis $M\ge 4$ is met. Divide its count-error radius by $N$ for the expectation-error radius, with the same success event and probability. This item defines no second amplitude-estimation or counting routine.

Input. A finite expectation-estimation task with an exact encoded observable $g:X\to [a,b]$, a coherent sampler $V$ for its law, rational target $\epsilon >0$, and rational failure probability $0<\delta <1$. For $a<b$, require $\epsilon \le b-a$. The supplied access model must include every forward, inverse, controlled, value, predicate, and reflection operation that the chosen QA13 amplitude-estimation circuit invokes.

If $a=b$, return $a$. Otherwise compute the exact affine value $q(x)=\frac{g(x)-a}{b-a}\in [0,1]\mathrm{.}$ Append a good flag to the coherent sampler. Reversibly compute $q(x)$ in the declared value workspace, apply the supplied one-qubit rotation $\mathrm{\mid }0⟩⟼\sqrt{1-q(x)}\mathrm{\mid }0⟩+\sqrt{q(x)}\mathrm{\mid }1⟩$ controlled by the sample/value registers, and uncompute all scratch used only for $q$. Let $A_q$ denote the resulting state-preparation unitary, including $V$ and the controlled rotation; let $P_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ project onto flag $\mathrm{\mid }1⟩$. Run the unchanged median-confidence estimator Median confidence amplification for amplitude estimation on $(A_q,P_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}})$ with amplitude tolerance $\eta =\epsilon \mathrm{/}(b-a)$ and failure probability $\delta$, and call its estimate $\tilde{q}$. Return $\tilde{\mu }=a+(b-a)\tilde{q}\mathrm{.}$

For $a=b$, the exact-return branch has no quantum call. When $a<b$, the input is a costed finite circuit/oracle description. Charge each use of $A_q$, $A_q^{†}$, controlled versions, the good and initial-state reflections, value decoding, reversible arithmetic and uncomputation, the controlled rotation and its precision, phase estimation, state preparation, gates, width, ancillas, and classical output processing according to Circuit-family and computation cost model. No operation is free because it is described by the law $p$ or observable $g$.

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$.