= \sum_{i=0}^{2^m-1} \sqrt{p_\text{GR}^{(m)}(s)}\ket{s},\;\mbox{with}\;
  &p_\text{GR}^{(m)}(s) =\int_{x_s}^{x_{s+1}}p(u)\mathrm{d}u.\end{aligned}$$ The original construct assumes a random variable $x$ in a bounded interval $[a,b]$ subdivided into $2^m$ smaller intervals, labeled by the quantum register states $\ket{s}=\ket{s^1s^2\cdots s^m}.$

A practical application of this encoded state would be the computation of expected values for any observable or function $f(x).$ This requires engineering an observable $\hat{O}^{(m)}_f$ such that $$\bar{f} = \int\! f(x) p(x) \mathrm{d}x \simeq \braket{p_\text{GR}^{(m)}|\hat{O}^{(m)}_f|p_\text{GR}^{(m)}} + \varepsilon_\text{int}.
  \label{eq:expected}$$ Typically, we approximate $\hat{O}^{(m)}_f =\sum_s f(x_s){\ensuremath{\ket{s}\!\bra{s}}},$ and apply a uniform discretization , to have an integration error that decays exponentially with register size, $\varepsilon_\text{int} \sim \mathcal{O}(\delta_m).$

As found by A. Montanaro [@montanaro2015], using amplitude estimation with $U_p$ and the operator $\hat{O}_f,$ one may estimate $\bar{f}$ with a precision that scales better than Monte Carlo algorithms. If the cost of implementing $U_p$ is $T_\text{GR},$ and we aim for a sampling precision $\varepsilon_\text{sample},$ the asymptotic time cost of the ideal amplitude estimation algorithm is roughly $$T_{QCMC}  = \mathcal{O}\left( T_{GR}/\varepsilon_\text{sample}\right).$$ This represents a favorable scaling when compared with traditional Monte Carlo, where the sampling uncertainty goes as $\mathcal{O}(\varepsilon_\text{sample}^{-2}),$ but only if the cost of encoding the probability state $T_\text{GR}$ remains small or weakly dependent on the integration error $\varepsilon_\text{int}.$

![(a) A probability state 