TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Quantum bounded-expectation guarantee and query cost

Statement

Let $g : X \to [a, b]$ be exactly encoded with $a \leq b$ , let $V$ be the coherent sampler of Coherent finite sampler and observable value, and let $μ = \sum_{x} p_{x} g (x)$ . If $a = b$ , the algorithm Amplitude-estimation expectation estimator returns $a = μ$ exactly. If $a < b$ , then for rational $0 < ε \leq b - a$ and $0 < δ < 1$ it returns $\tilde{μ}$ with $∣ \tilde{μ} - μ ∣ \leq ε$ with probability at least $1 - δ$ . Writing $q = (μ - a) / (b - a)$ and $M$ for its QA13 phase-register size, the median output also obeys $∣ \tilde{μ} - μ ∣ \leq (b - a) (\frac{2 π \sqrt{q (1 - q)}}{M} + \frac{π^{2}}{M^{2}})$ with probability at least $1 - δ$ in either declared QA13 access mode. For $a < b$ , in repeated controlled- $Q$ access it uses exactly $r (M - 1)$ controlled-Grover calls, where $M$ and $r$ are the current QA13 median-interface parameters. In this mode its controlled-sampler/reflection query count is $O ((b - a) ε^{- 1} (1 + \ln (1 / δ)))$ for all $0 < δ < 1$ , and $O ((b - a) ε^{- 1} \ln (1 / δ))$ when $0 < δ \leq 1 / 2$ . If $a = b$ , the algorithm returns $a$ exactly with no quantum query.

For $a < b$ , in supplied controlled-power access it instead uses exactly $r m$ controlled-power queries, where $M = 2^{m}$ ; sum their separately declared costs over all $r$ runs. No $M - 1$ constituent-call expansion is inferred for a supplied power.

The query bound is an oracle statement. Every controlled or inverse sampler call, good-state reflection, initial-state reflection, rotation, arithmetic operation, state preparation, and classical order-statistic computation retains its separately supplied cost.

Facts & Assumptions

Given: The finite coherent sampler, exact finite value encoding, the bounded interval $[a, b]$ , the parameters $ε, δ$ in the Statement, and either declared QA13 access mode. The controlled-sampler/reflection bound assumes repeated controlled- $Q$ access.

[F1]

Coherent finite sampler and observable value supplies $V ∣ 0 ⟩ = \sum_{x} \sqrt{p_{x}} ∣ x ⟩ ∣ g (x) ⟩ ∣ w_{x} ⟩$ with unit work vectors; Measurement law of a coherent sampler proves sample outcome probability $p_{x}$ .

[F2]

Amplitude-estimation expectation estimator computes $q (x) = (g (x) - a) / (b - a)$ , rotates a flag with good probability $q (x)$ , runs the QA13 median estimator, and returns $a + (b - a) \tilde{q}$ .

[F3]

Amplitude-estimation additive error and success probability: for a single QFT estimate and $M \geq 4$ , $∣ \tilde{q} - q ∣ \leq 2 π \sqrt{q (1 - q)} / M + π^{2} / M^{2}$ with probability at least $8 / π^{2}$ .

[F4]

Median confidence amplification for amplitude estimation chooses the least power of two $M \geq 88 / (7 η)$ for target $η$ and the least positive odd $r$ satisfying $2^{r} \geq (2 / δ)^{8}$ , then returns the median of $r$ fresh runs.

[F5]

Explicit median confidence guarantee for amplitude estimation states that this median has additive error at most $η$ with probability at least $1 - δ$ .

[F6]

In repeated controlled- $Q$ access, Median amplitude-estimation query cost gives exactly $r (M - 1)$ controlled- $Q$ calls and its stated logarithmic query bounds. The median threshold also gives $M < 176 / (7 η)$ .

[F7]

Chernoff bound for independent bernoulli trials gives $\Pr (∣ S - E S ∣ \geq u) \leq 2 e^{- 2 u^{2} / r}$ for a sum of $r$ independent Bernoulli indicators.

[F8]

Rational bounds for pi used in finite schedules gives $π < 22 / 7$ and $8 / π^{2} > 98 / 121$ .

[F9]

The natural logarithm as the inverse of the exponential function defines the natural logarithm, and The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t gives $\ln 2 = \int_{1}^{2} d t / t$ , hence $0 < \ln 2 < 1$ .

[F10]

Controlled Unitary Access and Inverse Unitary Access keep controlled and inverse calls explicit; Circuit-family and computation cost model separates oracle, gate, width, precision, and classical bit costs. Quantum query algorithm specifies fresh independent executions.

[F11]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm gives strict increase, $\ln (x y) = \ln x + \ln y$ and $\ln (1 / x) = - \ln x$ for positive inputs. Iterating the product identity gives $\ln (x^{n}) = n \ln x$ for a positive integer $n$ . The natural logarithm as the inverse of the exponential function gives $\ln (\exp u) = u$ .

[F12]

Amplitude-estimation query and precision complexity gives exactly $m$ supplied controlled-power queries per QFT run at $M = 2^{m}$ , with their separately declared costs.

Proof

1.1givenF1F2algebra

Since $q (x) = (g (x) - a) / (b - a)$ , the interval promise gives $q (x) \in [0, 1]$ . By [F1]–[F2], the good-flag probability after the controlled rotation is $\sum_{x} p_{x} q (x) = (\sum_{x} p_{x} g (x) - a \sum_{x} p_{x}) / (b - a) = (μ - a) / (b - a) = q$ .

1.2givenF3F4

For one QAE run, [F3] gives the stated probability-error radius $E = 2 π \sqrt{q (1 - q)} / M + π^{2} / M^{2}$ with success at least $8 / π^{2}$ . Since fresh runs in [F4] are independent, if the median is outside $[q - E, q + E]$ , at least $(r + 1) / 2$ of their failure indicators are one.

1.3givenF3F4F6F10F12algebra

Suppose $a < b$ . In repeated controlled- $Q$ access, [F4] and [F6] give exactly $r (M - 1)$ controlled-Grover calls, $M < 176 / (7 η)$ , and the stated logarithmic query bounds. Substitute $η = ε / (b - a)$ . In supplied controlled-power access, [F4] and [F12] give $r$ runs of $m$ power queries, hence exactly $r m$ such queries with their declared costs summed. Neither access choice changes the ideal QFT output law in [F3]. The separate input-access costs in [F10] are not converted into gates without the supplied implementations.

2.1givenF7F8step 1.2algebra

Set $p_{0} = 98 / 121$ . By [F8], each failure indicator has mean at most $1 - p_{0}$ . If $S$ is their sum, the median-failure event entails $S - E S \geq r (p_{0} - 1 / 2)$ . Applying [F7] to this containing event bounds its probability by $2 e^{- c r}$ , where $c = 2 (75 / 242)^{2} = 5625 / 29282$ and $8 c > 1$ .

3.1givenF4F9F11step 2.1algebra

Put $L = \ln (2 / δ) > 0$ . Taking logarithms of the positive threshold $2^{r} \geq (2 / δ)^{8}$ in [F4] and applying the product law repeatedly as in [F11] gives $r \ln 2 \geq 8 L$ . Because $0 < \ln 2 < 1$ by [F9], $r > 8 L$ , and $8 c > 1$ gives $c r > L$ . By [F11], $\ln (δ / 2) = - L$ and $\ln (e^{- c r}) = - c r < - L$ , so strict increase implies $2 e^{- c r} < δ$ . Therefore the median error radius is at most $E$ with probability at least $1 - δ$ . The same event implies error at most $η$ whenever $M \geq 88 / (7 η)$ and $0 < η \leq 1$ , because $\sqrt{q (1 - q)} \leq 1 / 2$ , $π / M \leq η / 4$ , and $π^{2} / M^{2} \leq η^{2} / 16 \leq η / 16$ .

4.1givenF2F5step 3.1algebra

For the algorithm choose $η = ε / (b - a) \leq 1$ . By [F2], $∣ \tilde{μ} - μ ∣ = (b - a) ∣ \tilde{q} - q ∣$ . The median guarantee [F5] gives the requested additive error; step 3.1 supplies the stronger radius, and multiplication by $b - a$ gives the Statement.

5.1givenF1algebra∎

If $a = b$ , the value is constant $g (x) = a$ for every $x$ , so $μ = a$ by the probability normalization and the exact-return branch has zero error and zero quantum calls.

Depends on

Used by

Bernoulli mean as a good-state probability Example
Dyadic positive-mean estimator under an L2 bound Lemma
Coherent query-to-circuit cost translation Theorem
SDP matrix-expectation estimation error and cost Theorem
Variance-aware quantum Monte Carlo guarantee Theorem

Dependency tree · two levels

113 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ashley Montanaro, Quantum speedup of Monte Carlo methods, Theorem 3 (standard reference, not scraped)
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum Amplitude Amplification and Estimation, Theorem 12 (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms, Section 19.3 (standard reference, not scraped)