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

Amplitude Estimation and Counting

1 · Prerequisites

2 · Summary

This page fixes the signed Grover iterate, the amplitude and counting input/output contracts, and separate controlled-power and repeated-controlled-unitary access modes. It proves the eigenphase relation and finite-grid error/confidence bounds, exact query counts, median confidence amplification, and the finite-grid likelihood schedule. Counting uses the uniform Hadamard state and explicitly supplied controlled membership reflection. The relative approximate-counting procedure has its own exact stopping rule, certified integer rounding, success theorem, and expected query cost in repeated controlled- $Q$ access mode; the iterative likelihood variant is specified without a finite-sample success guarantee.

3 · Logical flowchart

4 · Definitions, theorems and proofs

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Rational bounds for pi used in finite schedules

Statement

The circle constant satisfies $3 < π < 22 / 7$ .

Facts & Assumptions

Given: The principal inverse tangent and the usual positive constant $π$ .

[F1]

$\arctan x = \int_{0}^{x} (1 + t^{2})^{- 1} d t$ and $π / 4 = \sum_{n = 0}^{\infty} (- 1)^{n} / (2 n + 1)$ (Principal arctangent: derivative, integral, power series, and the Gregory–Leibniz series). The positive terms $1 / (2 n + 1)$ decrease to zero; the alternating-series test places the sum between consecutive partial sums and bounds the error by the first omitted term (The alternating series test: if $(b_{k})$ is nonincreasing with $b_{k} \to 0$ then $\sum_{k} (- 1)^{k} b_{k}$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_{n}$ , Every complete ordered field is Archimedean).

[F2]

The definition identifies $π / 2$ as the first positive zero of cosine and fixes the same circle constant used in the arctangent identity (Pi as twice the smallest positive zero of cosine).

Proof

1.1givenF1F2algebra

Group the first eight terms of the alternating series in [F1] into four positive pairs. Their sum is $2 / 3 + 2 / 35 + 2 / 99 + 2 / 195 = 33976 / 45045 > 3 / 4$ , since $4 \cdot 33976 = 135904 > 135135 = 3 \cdot 45045$ . The alternating-series remainder after an even partial sum is positive, so $π / 4 > 3 / 4$ and $π > 3$ .

2.1givenF1F2algebra∎

For $0 < x < 1$ , the integrand $x^{4} (1 - x)^{4} / (1 + x^{2})$ is positive. Polynomial division gives $x^{4} (1 - x)^{4} / (1 + x^{2}) = x^{6} - 4 x^{5} + 5 x^{4} - 4 x^{2} + 4 - 4 / (1 + x^{2})$ . Its integral over $[0, 1]$ is $1 / 7 - 2 / 3 + 1 - 4 / 3 + 4 - 4 \arctan (1) = 22 / 7 - π$ by [F1]. The integral is strictly positive, hence $π < 22 / 7$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Two nearest phase labels carry probability at least eight over pi squared

Statement

Let $M = 2^{m}$ with $m \geq 1$ , and let $θ \in [0, 1)$ be an eigenphase measured by the $M$ -label QPE kernel. The two labels $⌊ M θ ⌋$ and $⌈ M θ ⌉$ reduced modulo $M$ (one label when $M θ$ is an integer) have total outcome probability at least $8 / π^{2}$ .

Facts & Assumptions

Given: The QPE eigenphase outcome law with $M = 2^{m}$ , $m \geq 1$ , and phase $θ \in [0, 1)$ .

[F1]

For label $y$ , $P_{θ} (y) = M^{- 2} ∣ \sum_{j = 0}^{M - 1} e^{2 π i j (θ - y / M)} ∣^{2}$ (Phase-estimation finite outcome law).

[F2]

The finite geometric sum reduces to $(1 - z^{M}) / (1 - z)$ when $z \neq 1$ (Finite geometric sum for phase-estimation amplitudes).

[F3]

For $v \geq 0$ , $\sin v \leq v$ (Sine chord and linear bounds).

[F4]

$π$ satisfies $3 < π < 22 / 7$ (Rational bounds for pi used in finite schedules).

[F5]

Sine/cosine derivatives, tangent/secant derivatives, first-quadrant signs, and the Pythagorean identity are given by The derivatives of sine and cosine are cosine and minus sine, Derivatives and fundamental periods of tangent, cotangent, secant, and cosecant, Signs, monotonicity intervals, and ranges of sine and cosine, Pythagorean and parity identities for all six trigonometric functions on their natural domains, The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ , and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ .

[F6]

The mean value theorem converts a derivative sign into monotonicity on a compact interval (The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[F7]

Cofunction and supplementary identities give $\sin (π / 2 - x) = \cos x$ , $\tan (π / 2 - x) = \cot x$ , and $\cos (π - x) = - \cos x$ on their domains (Cofunction, supplementary, quarter-turn, and reflection identities for the six trigonometric functions).

[F8]

$\cos (2 x) = 2 \cos^{2} x - 1$ and $\sin^{2} x + \cos^{2} x = 1$ (Double-angle and quadratic power-reduction identities, Pythagorean and parity identities for all six trigonometric functions on their natural domains).

Proof

1.1givenF1F2F3algebra

If $r = {M θ} = 0$ , write $q = M θ$ . For label $q$ modulo $M$ , every summand in [F1] is $1$ , so its probability is $1$ ; for any other label, the geometric ratio in [F2] is not $1$ but its $M$ th power is $1$ , so the sum is zero. Otherwise $0 < r < 1$ , the floor and ceiling labels have exact probabilities $\sin^{2} (π r) / (M^{2} \sin^{2} (π r / M))$ and $\sin^{2} (π r) / (M^{2} \sin^{2} (π (1 - r) / M))$ by [F1]–[F2]. Applying [F3] to each denominator shows their sum is at least $g (r) / π^{2}$ , where $g (r) = \sin^{2} (π r) (r^{- 2} + (1 - r)^{- 2})$ .

1.2F5F7algebra

The function $g$ is symmetric under $r \mapsto 1 - r$ . For $0 < r < 1 / 2$ , set $t = 1 - 2 r$ , $A = r^{- 2} + (1 - r)^{- 2} > 0$ and $C = r^{- 3} - (1 - r)^{- 3} > 0$ . Differentiation gives $g^{'} (r) = 2 \sin (π r) [π \cos (π r) A - \sin (π r) C]$ , and direct substitution gives $C / A = 2 t (3 + t^{2}) / (1 - t^{4})$ . Since $\sin (π r) > 0$ , $\cos (π r) > 0$ , and $A > 0$ , $g^{'} (r) \leq 0$ exactly when $π \cot (π r) \leq C / A$ . By [F7], this is $\tan (π t / 2) \leq 2 t (3 + t^{2}) / [π (1 - t^{4})]$ .

1.3F4F5F6F7F8algebra

Put $T (t) = \tan (π t / 2)$ on $[0, 1 / 2]$ . Its second derivative is $T^{''} (t) = (π^{2} / 2) \tan (π t / 2) \sec^{2} (π t / 2) \geq 0$ by [F5]. Thus $T^{'}$ is nondecreasing by [F6]; applying the mean value theorem on $[a, t]$ and $[t, b]$ for $a < t < b$ shows $T (t)$ lies below the chord joining $(a, T (a))$ and $(b, T (b))$ . For endpoint values, let $c = \cos (π / 3) > 0$ . By [F7]–[F8], $2 c^{2} - 1 = \cos (2 π / 3) = - c$ , so $(2 c - 1) (c + 1) = 0$ and $c = 1 / 2$ . Hence $\sin (π / 3) > 4 / 5$ because its square is $3 / 4 > 16 / 25$ , so [F7] gives $\tan (π / 6) = \cot (π / 3) < 5 / 8$ . Also $\sin (π / 4) = \cos (π / 4) > 0$ by cofunction symmetry, hence $\tan (π / 4) = 1$ .

2.1F4step 1.2step 1.3algebra

For $0 \leq t \leq 1 / 3$ , the chord from $0$ to $1 / 3$ in step 1.3 gives $T (t) \leq (15 / 8) t$ . For $t > 0$ , the right side of the inequality in step 1.2 is at least $6 t / π > 21 t / 11 > (15 / 8) t$ , using $π < 22 / 7$ and $21 / 11 > 15 / 8$ ; at $t = 0$ both sides are zero.

2.2F4F5F6step 1.2step 1.3algebra

For $1 / 3 \leq t \leq 1 / 2$ , the chord from $0$ to $1 / 2$ in step 1.3 gives $T (t) \leq 2 t$ . Put $R (t) = (3 + t^{2}) / (1 - t^{4})$ . On this interval its denominator is positive, and differentiation gives $R^{'} (t) = 2 t (1 + 6 t^{2} + t^{4}) / (1 - t^{4})^{2} \geq 0$ , so $R (t) \geq R (1 / 3) = 63 / 20 > 22 / 7 > π$ . The right side in step 1.2 is therefore $2 t R (t) / π \geq 2 t$ .

2.3F4F5F6step 1.2algebra

For $1 / 2 \leq t < 1$ , put $α = π (1 - t) / 2$ . The function $u (x) = \tan x - x$ has $u (0) = 0$ and $u^{'} (x) = \tan^{2} x \geq 0$ on $[0, π / 4]$ , so [F5]–[F6] give $\tan α \geq α$ . Hence $\sin α - α \cos α = \cos α (\tan α - α) \geq 0$ . The function $h (α) = \sin α (1 - α^{2} / 3) - α \cos α$ has derivative $(α / 3) (\sin α - α \cos α) \geq 0$ and $h (0) = 0$ , so $h (α) \geq 0$ and $\cot α \leq 1 / α - α / 3$ . After multiplying the desired comparison by $π (1 - t) > 0$ , its right side minus this upper bound is $(1 - t)^{2} [π^{2} / 6 - 2 / ((1 + t) (1 + t^{2}))] > 0$ , since $(1 + t) (1 + t^{2}) \geq 15 / 8$ and $π > 3$ . This proves the inequality in step 1.2 on the last interval.

3.1step 1.1step 2.1step 2.2step 2.3algebra∎

Steps 2.1–2.3 show $g$ is nonincreasing on $(0, 1 / 2]$ ; symmetry then shows its minimum on $(0, 1)$ is $g (1 / 2) = 8$ . Step 1.1 therefore gives probability at least $8 / π^{2}$ , and the exact-grid case in step 1.1 already has probability one.

DefinitionDefinition: Literature-sourcedProof: AI-adaptedOpen item page →

Amplitude estimation and counting input/output contract

Definition

Let $H$ be a nonzero finite-dimensional complex inner-product space, $∣ 0 ⟩$ a specified unit vector, $A : H \to H$ a supplied unitary, and $Π_{g o o d}$ an explicitly supplied orthogonal projection. Put $S_{0} = I - 2 ∣ 0 ⟩ ⟨ 0 ∣, S_{g o o d} = I - 2 Π_{g o o d}, Q = - A S_{0} A^{*} S_{g o o d} .$ Each classical instance has an injective encoding $enc$ from its declared instance set into ${0, 1}^{*}$ , with input size $∣ enc (z) ∣$ ; the promise domain and output obligation are stated for that task. Supplied operator or oracle access is a separate resource declaration.

The success amplitude is $a = ∥ Π_{g o o d} A ∣ 0 ⟩ ∥^{2} \in [0, 1]$ , and $θ = \arcsin \sqrt{a} \in [0, π / 2]$ . Amplitude estimation returns an algebraically encoded estimate of $a$ ; its requested accuracy and failure probability are stated separately.

For counting, let $n$ be a nonnegative integer and set $N = 2^{n}$ with address basis ${∣ x ⟩ : x \in {0, 1}^{n}}$ and a Boolean predicate $f$ . Write $H_{H a d} = 2^{- 1 / 2} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ for the one-qubit Hadamard gate, distinct from the space $H$ , and set $A = H_{H a d}^{\otimes n}$ , $∣ 0 ⟩ = ∣ 0^{n} ⟩$ , $Π_{g o o d} = \sum_{f (x) = 1} ∣ x ⟩ ⟨ x ∣$ , and $t = ∣ {x : f (x) = 1} ∣$ . Then the counting amplitude is $a = t / N$ . The preparation uses exactly $n$ ordinary Hadamard gates. Access to the controlled membership reflection is a separate explicit resource.

Two phase-estimation access modes are allowed. In the power-query mode, the model supplies each $C (Q^{2^{j}})$ for $0 \leq j < m$ as one declared query, with its individual cost recorded. In the repeated-unitary mode the model supplies $C (Q)$ and implements $C (Q^{2^{j}})$ by $2^{j}$ sequential calls, for exactly $2^{m} - 1$ controlled- $Q$ calls. In repeated-unitary mode, each controlled- $Q$ call expands as the composite $C (- I) C (A) C (S_{0}) C (A^{*}) C (S_{g o o d})$ ; controlled $A$ , controlled $A^{*}$ , controlled $S_{0}$ , controlled $S_{g o o d}$ , and the control phase $C (- I)$ must all be supplied or implemented and charged. In power-query mode each supplied controlled power has its own declared cost vector, including any constituent implementations the model uses. An uncontrolled phase query does not supply any of them. Query, ordinary-gate, state-preparation, measurement, and classical bit costs are separate coordinates.

Facts & Assumptions

Given: The finite-dimensional space, supplied unitary and predicate-reflection accesses, task encoding, and one of the two access models just stated.

[F1]

A decision or search task specifies its promise domain and output obligation; correctness outside the promise is not imposed (QA task and promise domain).

[F2]

For an orthogonal projection $Π$ , the sign convention $S_{Π} = I - 2 Π$ is fixed, and controlled reflection access is separately declared (Orthogonal-Projector Reflection and Access Contract).

[F3]

Controlled access means an explicit call to $C (U) = diag (I, U)$ ; an ordinary black-box $U$ call does not silently grant it (Controlled Unitary Access).

[F4]

Inverse-unitary access has its own declaration and cost (Inverse Unitary Access).

[F5]

Gate and query costs are separate operation counts (Finite circuit resource accounting); this task also records measurement and classical-bit costs separately.

[F6]

The one-qubit Hadamard matrix is $2^{- 1 / 2} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ (Exact one-qubit gates and rotations).

[F7]

The reflections $I - 2 P$ of orthogonal projections are self-adjoint unitaries with square $I$ (Projector Reflections Are Hermitian Unitary Involutions).

[F8]

An input encoding is injective, and its string length is the input size (Input encoding and size for algorithmic tasks).

[F9]

Query algorithms count designated oracle calls separately from gates, and controlled access is charged only when the contract supplies it (Quantum query algorithm).

Proof

1.1givenF2F7algebra

The operators $S_{0}$ and $S_{g o o d}$ are the sign-reversed reflections of the projectors $∣ 0 ⟩ ⟨ 0 ∣$ and $Π_{g o o d}$ in [F2]. The reflection-involution result says each is self-adjoint and squares to $I$ ; since $A$ is unitary, $Q = - A S_{0} A^{*} S_{g o o d}$ is a product of unitaries and is unitary.

1.2givenF3F4F5F9algebra

In the repeated-unitary mode, block multiplication gives $C (Q)^{r} = diag (I, Q^{r}) = C (Q^{r})$ for every integer $r \geq 0$ . Summing the $m$ controlled powers gives $\sum_{j = 0}^{m - 1} 2^{j} = 2^{m} - 1$ calls; the power-query mode instead has exactly one declared query for each of the $m$ indices. These counts use [F3], the query convention [F9], and preserve the distinct costs in [F4]–[F5].

1.3givenF6algebra

Since $H_{H a d} ∣ 0 ⟩ = (∣ 0 ⟩ + ∣ 1 ⟩) / \sqrt{2}$ , tensoring its $n$ copies gives $A ∣ 0^{n} ⟩ = N^{- 1 / 2} \sum_{x} ∣ x ⟩$ . The orthonormal address basis and the displayed projector then give $∥ Π_{g o o d} A ∣ 0^{n} ⟩ ∥^{2} = \sum_{f (x) = 1} 1 / N = t / N$ . The circuit applies exactly one $H_{H a d}$ to each address wire, hence $n$ ordinary Hadamards.

2.1givenF1F3F4F5F8F9step 1.2∎

The input encoding and promise obligation are the declared task data of [F1] and [F8]. The definition states its output and separate access costs before any accuracy claim. Thus neither a controlled reflection nor a free power construction is inferred from an uncontrolled oracle call; every use must satisfy [F3]–[F5] and [F9].

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Grover eigenphases encode the good probability

Statement

Let $ψ = A ∣ 0 ⟩$ , $a = ∥ Π_{g o o d} ψ ∥^{2}$ , and $θ = \arcsin \sqrt{a}$ . If $0 < a < 1$ , define the unit vectors $G = Π_{g o o d} ψ / \sqrt{a}$ and $B = (I - Π_{g o o d}) ψ / \sqrt{1 - a}$ . In the ordered basis $(B, G)$ , the Grover iterate $Q$ of Amplitude estimation and counting input/output contract restricts to $(\begin{array}{cc} \cos (2 θ) & - \sin (2 θ) \\ \sin (2 θ) & \cos (2 θ) \end{array}) .$ Its eigenvalues are $e^{2 i θ}$ and $e^{- 2 i θ}$ , and $ψ = \cos θ B + \sin θ G$ has squared overlap $1 / 2$ with each corresponding normalized eigenvector. At $a = 0$ , $ψ$ is a $+ 1$ eigenvector; at $a = 1$ , it is a $- 1$ eigenvector.

Facts & Assumptions

Given: The unitary $A$ , the orthogonal good projection, the state $ψ = A ∣ 0 ⟩$ , and the signed iterate $Q = - A S_{0} A^{*} S_{g o o d}$ .

[F1]

The definitions of $S_{0}$ , $S_{g o o d}$ , $Q$ , $a$ , and $θ$ are fixed in Amplitude estimation and counting input/output contract.

[F2]

The signed iterate leaves the good/bad plane invariant and has matrix $(\begin{array}{cc} \cos (2 θ) & - \sin (2 θ) \\ \sin (2 θ) & \cos (2 θ) \end{array})$ in the ordered $(B, G)$ basis (Amplitude-amplification invariant plane).

Proof

1.1givenF1F2algebra

When $0 < a < 1$ , the definition in [F1] has $\sqrt{1 - a} = \cos θ$ and $\sqrt{a} = \sin θ$ because $θ \in (0, π / 2)$ . The supplier matrix in [F2] therefore applies to the same ordered basis and the same signed $Q$ defined in [F1].

2.1F2step 1.1algebra

For that matrix, the characteristic polynomial is $λ^{2} - 2 \cos (2 θ) λ + 1$ , with roots $\cos (2 θ) \pm i \sin (2 θ) = e^{\pm 2 i θ}$ . The normalized vectors $(B - i G) / \sqrt{2}$ and $(B + i G) / \sqrt{2}$ are eigenvectors for these roots. Their inner products with $ψ = \cos θ B + \sin θ G$ have squared modulus $(\cos^{2} θ + \sin^{2} θ) / 2 = 1 / 2$ .

3.1F2algebra∎

At $a = 0$ , [F2]’s endpoint statement gives $Q ψ = ψ$ , with phase $0$ modulo one. At $a = 1$ , it gives $Q ψ = - ψ = e^{2 π i (1 / 2)} ψ$ , with phase $1 / 2$ . These are the remaining endpoint eigenphases and require no zero component normalization.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Finite exact comparison of real cyclotomic values

Statement

For an integer $s \geq 2$ , let $ζ_{s} = e^{2 π i / s}$ and let $P, R \in Q [X]$ be given coefficient lists such that $P (ζ_{s})$ and $R (ζ_{s})$ are real. There is a terminating deterministic exact procedure to decide which of these two real numbers is larger, or whether they are equal. Its bit-operation cost is charged to the classical cost model; no polynomial bound is asserted.

Facts & Assumptions

Given: The integer $s \geq 2$ , rational polynomials $P, R$ , and the promise that their values at $ζ_{s} = e^{2 π i / s}$ are real.

[F1]

The cyclotomic polynomial $Φ_{s}$ is irreducible over $Q$ and is the minimal polynomial of a primitive $s$ th root ( $Φ_{n}$ is irreducible in $Q [t]$ for every $n \geq 1$ ).

[F2]

Write $S_{n} = \sum_{j = 0}^{n - 1} (- 1)^{j} / (2 j + 1)$ . The arctangent theorem gives $π / 4 = \lim_{n} S_{n}$ , and the alternating-series test gives $∣ π / 4 - S_{n} ∣ \leq 1 / (2 n + 1)$ . For any rational width $η > 0$ , increasing $n$ until $8 / (2 n + 1) < η$ gives the rational interval $[4 S_{n} - 4 / (2 n + 1), 4 S_{n} + 4 / (2 n + 1)]$ of width below $η$ containing $π$ ; exact rational comparisons suffice, and the loop terminates because the natural numbers are unbounded (Principal arctangent: derivative, integral, power series, and the Gregory–Leibniz series, The alternating series test: if $(b_{k})$ is nonincreasing with $b_{k} \to 0$ then $\sum_{k} (- 1)^{k} b_{k}$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_{n}$ , Every complete ordered field is Archimedean).

[F3]

Sine and cosine are given by their convergent power series (Sine and cosine defined by their real power series).

[F4]

Rational arithmetic and exact comparisons are part of the separately charged classical bit-operation model (Classical bit-operation cost).

[F5]

$e^{i x} = \cos x + i \sin x$ for real $x$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ).

[F6]

For an alternating series whose nonnegative terms decrease to zero, the remainder after $r$ terms is at most the first omitted term (The alternating series test: if $(b_{k})$ is nonincreasing with $b_{k} \to 0$ then $\sum_{k} (- 1)^{k} b_{k}$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_{n}$ ).

Proof

1.1givenF1algebra

Form $D = P - R$ and divide it by $Φ_{s}$ over $Q$ . By irreducibility in [F1], $D (ζ_{s}) = 0$ exactly when the remainder is the zero polynomial; that finite rational coefficient test decides equality.

2.1givenF2F3F5F6step 1.1algebra

If the remainder is nonzero, then $d = D (ζ_{s})$ is a nonzero real algebraic number. Put $α = 2 π / s \in (0, 4)$ , using $s \geq 2$ and $π < 22 / 7 < 4$ . For any rational tolerance $η > 0$ , refine the pi enclosure from [F2] until the scaled interval $J$ for $α$ lies in $[0, 4]$ and has width below $η$ ; this terminates because $α \in (0, 4)$ . For $k \geq 4$ and $x \in [0, 4]$ , successive cosine-term magnitudes have ratio at most $16 / ((2 k + 2) (2 k + 1)) < 1$ , and successive sine-term magnitudes have ratio at most $16 / ((2 k + 3) (2 k + 2)) < 1$ . Thus [F3] and [F6] bound the cosine and sine tails after truncation through index $r \geq 4$ by $4^{2 r + 2} / (2 r + 2)!$ and $4^{2 r + 3} / (2 r + 3)!$ . The ratios of these bounds at successive $r$ are $16 / ((2 r + 4) (2 r + 3))$ and $16 / ((2 r + 5) (2 r + 4))$ , both below $1 / 2$ for $r \geq 4$ , so exact rational comparisons find an $r$ with both bounds below $η$ . For this fixed $r$ , refine $J$ until the rational interval evaluations of both truncation polynomials have widths below $η$ ; this exact test terminates because they are fixed polynomials and interval addition and multiplication preserve shrinking widths. Use those intervals with the alternating remainders to enclose $\cos α$ and $\sin α$ , then evaluate $D$ using rational complex interval arithmetic and Euler's formula [F5]. The resulting real intervals contain $d$ and have widths tending to zero as $η \to 0$ , since each sine/cosine interval width and tail bound tends to zero and $D$ is a finite polynomial.

3.1givenF4step 1.1step 2.1algebra∎

Because $d \neq 0$ , its distance from zero is positive. Repeatedly refine the rational interval from step 2.1 until it lies strictly above or below zero; convergence of the interval widths guarantees finite termination, and its sign decides the strict order. Equality was already decided in step 1.1, so this procedure terminates on every promised input. Its finitely many rational operations are charged under [F4].

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Iterative no-QFT amplitude estimation by finite-grid likelihood

Definition

Input. An instance of the task Amplitude estimation and counting input/output contract with the same $H, ∣ 0 ⟩, A, Π_{g o o d}$ supplied under the prepared-success-subspace access contract of Prepared unitary and success subspace for amplitude amplification. That contract supplies and charges the uncontrolled calls to $A, A^{*}, S_{0}, S_{g o o d}$ . Additionally require supplied access to the good/bad projective measurement ${Π_{g o o d}, I - Π_{g o o d}}$ of Finite projective measurements, with each use charged in the measurement coordinate and any implementation costs charged separately; no controlled access is used. Also require integers $K, S, J \geq 1$ .

Set $m_{0} = 0$ and $m_{k} = 2^{k - 1}$ for $1 \leq k \leq K$ . For each $k = 0, \dots, K$ , perform $S$ repetitions: prepare a fresh $A ∣ 0 ⟩$ , apply exactly $m_{k}$ signed Grover iterates using Amplitude amplification with a fixed integer iteration count, measure the good/bad projective measurement, and record the outcome. Let $h_{k}$ be the number of good outcomes at scale $k$ .

Set $s = 2 J$ and $ζ_{s} = e^{2 π i / s}$ . For an integer $q$ , let $ρ_{s} (q)$ be its least residue in ${0, \dots, s - 1}$ . For grid labels $j = 0, \dots, J$ , put $θ_{j} = j π / (2 J)$ and define the likelihood $L_{j} = \prod_{k = 0}^{K} \sin^{2 h_{k}} ((2 m_{k} + 1) θ_{j}) \cos^{2 (S - h_{k})} ((2 m_{k} + 1) θ_{j}),$ where every zeroth power is $1$ . For each label $j$ and scale $k = 0, \dots, K$ , set $r_{k j} = ρ_{s} ((2 m_{k} + 1) j), r_{k j}^{'} = ρ_{s} (- r_{k j}),$ and form the rational polynomials $U_{k j} (X) = \frac{2 - X^{r_{k j}} - X^{r_{k j}^{'}}}{4}, V_{k j} (X) = \frac{2 + X^{r_{k j}} + X^{r_{k j}^{'}}}{4} .$ Put $P_{j} (X) = \prod_{k = 0}^{K} U_{k j} (X)^{h_{k}} V_{k j} (X)^{S - h_{k}}$ , treating every zeroth power as $1$ . The polynomials $P_{j}$ are the exact comparison inputs for the likelihoods $L_{j}$ : compare $P_{i} (ζ_{s})$ and $P_{j} (ζ_{s})$ using Finite exact comparison of real cyclotomic values, and choose the least label $\hat{j}$ attaining the maximum.

Set $E_{\hat{j}} (X) = (2 - X^{\hat{j}} - X^{ρ_{s} (- \hat{j})}) / 4$ and return $\tilde{a} = E_{\hat{j}} (ζ_{s})$ , encoded by the pair $(s, E_{\hat{j}})$ . Each shot uses a fresh state and ordinary measurement. This is a finite-grid likelihood procedure, not a finite-sample $ϵ, δ$ guarantee; no such guarantee is asserted here.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

QFT-based amplitude estimation

Definition

Input. An instance from Amplitude estimation and counting input/output contract, an integer $m \geq 2$ , $M = 2^{m}$ , and either the declared controlled-power access mode or repeated controlled- $Q$ access.

Instructions. Prepare $ψ = A ∣ 0 ⟩$ , run the $M$ -label QPE circuit on $Q$ using controlled powers $Q^{2^{j}}$ , $j = 0, \dots, m - 1$ , and measure its phase register to obtain $y \in {0, \dots, M - 1}$ . Output the exact cyclotomic value $\tilde{a} = \sin^{2} (π y / M) = \frac{2 - ζ_{M}^{y} - ζ_{M}^{- y}}{4}, ζ_{M} = e^{2 π i / M},$ with the real embedding specified by this root. A decimal approximation is postprocessing and is charged separately. The leading minus in $Q$ is retained: on a controlled call it is the control phase $C (- I)$ , not a discarded standalone global phase.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Quantum counting by uniform-state amplitude estimation

Definition

Input. A Boolean predicate $f : {0, 1}^{n} \to {0, 1}$ , an integer $n \geq 0$ , $N = 2^{n}$ , an explicitly supplied controlled membership reflection for $S_{g o o d}$ , a power of two $M = 2^{m} \geq 2$ , and the other controlled accesses in Amplitude estimation and counting input/output contract.

Prepare $N^{- 1 / 2} \sum_{x} ∣ x ⟩ = H^{\otimes n} ∣ 0^{n} ⟩$ , run the $m$ -qubit QPE circuit for $Q$ with $M = 2^{m}$ labels, measure $y$ , and output the exact algebraic fraction estimate $\tilde{a} = \sin^{2} (π y / M)$ and count estimate $\tilde{t} = N \tilde{a}$ . For $M \geq 4$ this is the QFT amplitude-estimation circuit of QFT-based amplitude estimation; for $M = 2$ , use its one-phase-qubit QPE circuit directly, without invoking the $M \geq 4$ error theorem. The fraction and count are real-valued algebraic outputs; integer rounding is optional postprocessing. The controlled membership reflection is an explicit access requirement. In repeated-unitary mode each controlled $Q$ call charges one controlled membership reflection; in power-query mode each supplied controlled power carries its declared cost vector, including any membership-reflection implementations it uses. Neither access mode is inferred from the bare phase oracle $∣ x ⟩ \mapsto (- 1)^{f (x)}$ .

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Median confidence amplification for amplitude estimation

Definition

Input. The amplitude-estimation task, rational $0 < ϵ \leq 1$ and rational $0 < δ < 1$ .

Initialize $m = 0$ and $M = 1$ . Repeatedly increment $m$ and double $M$ while $M < 88 / (7 ϵ)$ , using exact rational comparison, so that $M = 2^{m}$ . Set $r = 1$ and repeatedly increase $r$ by $2$ while $2^{r} < (2 / δ)^{8}$ , using exact rational comparisons. Run $r$ independent fresh copies of the QFT estimator with phase-register size $M$ , and return the middle order statistic of their exact algebraic estimates (ties are ordered by their exact value and identical values are interchangeable).

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Rational-interval rounding of a counting output

Definition

Input. Public integers $N \geq 1$ , even $M \geq 2$ , and $0 \leq y < M$ . The output is an integer $q$ . All sums, factorials, comparisons and ceiling operations below use exact rational or integer arithmetic, charged as classical bit work under Classical bit-operation cost.

If $y = 0$ , return $q = 0$ . Otherwise initialize $r = 4$ . Compute $R_{r} = 8^{2 r + 2} / (2 r + 2)!$ ; while $N R_{r} \geq 1 / 24$ , increment $r$ by one and recompute $R_{r}$ . At the first $r$ with $N R_{r} < 1 / 24$ , set $D_{r} = \sum_{k = 1}^{r} \frac{2 k 8^{2 k - 1}}{(2 k)!} .$

Initialize $h = 1$ . Compute $S_{h} = \sum_{k = 0}^{h - 1} \frac{(- 1)^{k}}{2 k + 1}, e_{h} = \frac{4}{2 h + 1}, [a_{h}, b_{h}] = \frac{2 y}{M} [4 S_{h} - e_{h}, 4 S_{h} + e_{h}] .$ These are the arctangent-series enclosures from Principal arctangent: derivative, integral, power series, and the Gregory–Leibniz series and The alternating series test: if $(b_{k})$ is nonincreasing with $b_{k} \to 0$ then $\sum_{k} (- 1)^{k} b_{k}$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_{n}$ . Set $x_{h} = (a_{h} + b_{h}) / 2$ and $ρ_{h} = (b_{h} - a_{h}) / 2$ . While either $[a_{h}, b_{h}] ⊈ [0, 8]$ or $N D_{r} ρ_{h} \geq 1 / 24 - N R_{r}$ , increment $h$ by one and recompute $S_{h}, e_{h}, a_{h}, b_{h}, x_{h}, ρ_{h}$ .

For the first accepted $h$ , compute $C_{r} (x_{h}) = \sum_{k = 0}^{r} \frac{(- 1)^{k} x_{h}^{2 k}}{(2 k)!}, E = D_{r} ρ_{h} + R_{r},$ $u = \frac{N}{2} (1 - C_{r} (x_{h}) - E), v = \frac{N}{2} (1 - C_{r} (x_{h}) + E) .$ Return $q = ⌈ v - 2 / 3 ⌉$ , computing the rational ceiling by integer division. The termination and error guarantee are established in Terminating certified rounding for a counting estimate ↗.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Terminating certified rounding for a counting estimate

Statement

Given integers $N \geq 1$ , even $M \geq 2$ , and $0 \leq y < M$ , let $z = N \sin^{2} (π y / M)$ . There is a terminating deterministic rational-interval procedure that produces an integer $q$ with $∣ q - z ∣ \leq 2 / 3$ . Its arithmetic work is a classical bit cost; no polynomial bit bound is asserted.

Facts & Assumptions

Given: Integers $N \geq 1$ , even $M \geq 2$ , and a phase label $0 \leq y < M$ .

[F1]

$3 < π < 22 / 7$ , and $π / 4 = \sum_{n = 0}^{\infty} (- 1)^{n} / (2 n + 1)$ . After $n$ terms, the alternating-series error gives $∣ π - 4 S_{n} ∣ \leq 4 / (2 n + 1)$ , where $S_{n} = \sum_{k < n} (- 1)^{k} / (2 k + 1)$ . Increasing $n$ until $8 / (2 n + 1)$ is below a requested rational width yields the rational interval $[4 S_{n} - 4 / (2 n + 1), 4 S_{n} + 4 / (2 n + 1)]$ ; termination follows from the Archimedean property (Rational bounds for pi used in finite schedules, Principal arctangent: derivative, integral, power series, and the Gregory–Leibniz series, The alternating series test: if $(b_{k})$ is nonincreasing with $b_{k} \to 0$ then $\sum_{k} (- 1)^{k} b_{k}$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_{n}$ , Every complete ordered field is Archimedean).

[F2]

Cosine is represented by its everywhere-convergent power series (Sine and cosine defined by their real power series).

[F3]

Rational arithmetic, interval comparison, and output writing are charged classical bit operations (Classical bit-operation cost).

[F4]

For $x = 2 π y / M$ and $ζ_{M} = e^{2 π i / M}$ , the exponential addition law gives $ζ_{M}^{\pm y} = e^{\pm i x}$ ( $\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential). Euler's formula, $∣ e^{i x} ∣ = 1$ , and $e^{- i x} = (e^{i x})^{- 1}$ give $ζ_{M}^{y} + ζ_{M}^{- y} = 2 \cos x$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ). Together with [F5], this proves $\sin^{2} (π y / M) = (2 - ζ_{M}^{y} - ζ_{M}^{- y}) / 4$ for every integer $M \geq 2$ , including $M = 2$ and non-dyadic $M$ .

[F5]

The cosine double-angle identity gives $\cos (2 u) = 1 - 2 \sin^{2} u$ (Double-angle and quadratic power-reduction identities).

[F6]

For $x, y \in [0, 8]$ and $d \geq 1$ , factoring $x^{d} - y^{d} = (x - y) \sum_{j = 0}^{d - 1} x^{d - 1 - j} y^{j}$ gives $∣ x^{d} - y^{d} ∣ \leq d 8^{d - 1} ∣ x - y ∣$ .

[F7]

The alternating-series remainder bounds the tail by the first omitted term when magnitudes decrease to zero (The alternating series test: if $(b_{k})$ is nonincreasing with $b_{k} \to 0$ then $\sum_{k} (- 1)^{k} b_{k}$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_{n}$ ).

[F8]

For $R_{r} = 8^{2 r + 2} / (2 r + 2)!$ , $R_{r + 1} / R_{r} = 64 / ((2 r + 4) (2 r + 3)) \to 0$ . The ratio test gives convergence of $\sum_{r \geq 4} R_{r}$ , and the term test then gives $R_{r} \to 0$ (Ratio test: $lim sup ∣ a_{k + 1} / a_{k} ∣ < 1$ gives absolute convergence and hence convergence, and $lim inf ∣ a_{k + 1} / a_{k} ∣ > 1$ gives divergence, If a series converges then its terms tend to $0$ ).

[F9]

For every real $x$ , there is an integer $m = ⌊ x ⌋$ with $m \leq x < m + 1$ (Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ ).

[F10]

The real absolute value is defined by $∣ x ∣ = x$ for $x \geq 0$ and $∣ x ∣ = - x$ for $x < 0$ (Absolute value in an ordered field).

[F11]

The exact rational-interval instructions, including the $y = 0$ branch, the $r$ and enclosure-index loops, and the output $q = ⌈ v - 2 / 3 ⌉$ for the final interval $[u, v]$ , are defined in Rational-interval rounding of a counting output.

Proof

1.1givenF1F2F6F7F11algebra

If $y = 0$ , [F11] returns $q = 0 = z$ , so assume $0 < y < M$ . Since $π < 22 / 7 < 4$ , the true argument $x = 2 π y / M$ lies in $(0, 8)$ . For any accepted enclosure index $h$ in [F11], write $x_{r} = x_{h}$ , $ρ_{r} = ρ_{h}$ and $I_{r} = [u, v]$ for its output interval. For every $r \geq 4$ , the cosine terms after index $r$ alternate with decreasing magnitudes, so the omitted tail is bounded by $R_{r}$ . For each integer $k \geq 1$ , [F6] bounds $∣ x^{2 k} - x_{r}^{2 k} ∣$ by $2 k 8^{2 k - 1} ∣ x - x_{r} ∣$ ; summing with the factorial coefficients gives $∣ C_{r} (x) - C_{r} (x_{r}) ∣ \leq D_{r} ρ_{r}$ . Thus $∣ \cos x - C_{r} (x_{r}) ∣ \leq D_{r} ρ_{r} + R_{r} = E$ , and the endpoints in [F11] enclose $z = N (1 - \cos x) / 2$ in $I_{r}$ .

2.1givenF1F8F11step 1.1algebra

The ratio of successive $R_{r}$ bounds tends to zero, so $R_{r} \to 0$ and a finite $r$ satisfies $N R_{r} < 1 / 24$ . For that $r$ , the enclosure-index loop in [F11] refines the alternating arctangent enclosure of $π$ until its propagated argument interval is contained in $[0, 8]$ and $N D_{r} ρ_{r} < 1 / 24 - N R_{r}$ : this terminates because the true argument is strictly inside $[0, 8]$ , $D_{r}$ is finite, and the enclosures become arbitrarily narrow. The cosine interval has width at most $2 (D_{r} ρ_{r} + R_{r})$ , so its $z$ interval has width $N (D_{r} ρ_{r} + R_{r}) < 1 / 24 < 1 / 6$ . Both loops terminate.

3.1givenF3F4F5F9F10F11step 2.1algebra∎

Apply [F9] to $z + 1 / 2$ and set $n = ⌊ z + 1 / 2 ⌋$ . Then $n \leq z + 1 / 2 < n + 1$ , so $- 1 / 2 \leq z - n < 1 / 2$ and [F10] gives $∣ z - n ∣ \leq 1 / 2$ . If $I_{r} = [u, v]$ contains $z$ and has width below $1 / 6$ , every $x \in I_{r}$ satisfies $- 1 / 6 < x - z < 1 / 6$ ; adding these bounds gives $- 2 / 3 < x - n < 2 / 3$ . Thus the closed radius- $2 / 3$ interval about $n$ contains all of $I_{r}$ , so an eligible integer exists. Eligibility is exactly $v - 2 / 3 \leq q \leq u + 2 / 3$ , so the least eligible integer is $q = ⌈ v - 2 / 3 ⌉$ , as returned by [F11]. It gives $∣ q - z ∣ \leq 2 / 3$ because $z \in I_{r}$ . All rational operations and output work are charged by [F3]. The identity $z = N \sin^{2} (π y / M)$ follows from the cosine double-angle identity, and its exact encoding is covered by [F4] using [F5].

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Amplitude-estimation additive error and success probability

Statement

For the QFT-based estimator with $M = 2^{m} \geq 4$ and integer $k \geq 1$ , its output satisfies $∣ \tilde{a} - a ∣ \leq \frac{2 π k \sqrt{a (1 - a)}}{M} + \frac{π^{2} k^{2}}{M^{2}}$ with probability at least $8 / π^{2}$ when $k = 1$ , and with probability strictly greater than $1 - 1 / [2 (k - 1)]$ when $k \geq 2$ . In particular the $k = 1$ error is at most $π / M + π^{2} / M^{2}$ . At $a = 0$ the output is exactly zero; at $a = 1$ it is exactly one.

For every allowed access instance and $M = 2^{m} \geq 4$ , the prescribed signed controlled circuit and its exact real cyclotomic output are well-defined, retaining the controlled relative phase and separately charged classical output processing.

Facts & Assumptions

Given: The amplitude task, QFT estimator with $M = 2^{m} \geq 4$ , and integer $k \geq 1$ .

[F1]

The estimator returns $\sin^{2} (π y / M)$ after QPE on the Grover iterate (QFT-based amplitude estimation).

[F2]

The Grover eigenphases are $\pm θ / π$ modulo one with equal weights, where $a = \sin^{2} θ$ (Grover eigenphases encode the good probability).

[F3]

The floor and ceiling phase labels have combined probability at least $8 / π^{2}$ (Two nearest phase labels carry probability at least eight over pi squared).

[F4]

The QPE tail for $K = ⌊ M η ⌋ \geq 2$ is at most $1 / [2 (K - 1)]$ , and exact-grid phases are returned with certainty (Phase-estimation nearest-grid and tail bounds).

[F5]

For $f (x) = \sin^{2} x$ , $f^{'} (x) = \sin (2 x)$ (The derivatives of sine and cosine are cosine and minus sine, The addition formulas for sine and cosine).

[F6]

Sine is $1$ -Lipschitz, so $∣ \sin u - \sin v ∣ \leq ∣ u - v ∣$ (Sine and cosine are $1$ -Lipschitz on $R$ ).

[F7]

The fundamental theorem of calculus evaluates increments of a continuously differentiable function by integrating its derivative (The first fundamental theorem: if $f$ is integrable on $[a, b]$ and continuous at $c$ , then $F^{'} (c) = f (c)$ ; in particular a continuous $f$ has $F$ as a primitive).

[F8]

The finite QPE outcome probability is $P_{ϕ} (y) = M^{- 2} ∣ \sum_{j = 0}^{M - 1} e^{2 π i j (ϕ - y / M)} ∣^{2}$ (Phase-estimation finite outcome law).

[F9]

The geometric sum equals $(1 - z^{M}) / (1 - z)$ when $z \neq 1$ (Finite geometric sum for phase-estimation amplitudes).

[F10]

Circular phase distance takes values in $[0, 1 / 2]$ and identifies the two arcs from a phase to a label (Circular phase distance modulo one).

[F11]

For $0 \leq u \leq 1 / 2$ , $\sin (π u) \geq 2 u$ (Sine chord and linear bounds).

[F12]

Euler's identity gives $e^{i t} = \cos t + i \sin t$ and $∣ e^{i t} ∣ = 1$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ).

[F13]

The complex modulus is multiplicative and satisfies $∣ z + w ∣ \leq ∣ z ∣ + ∣ w ∣$ (Conjugation is an involutive real-field automorphism, $z \overline{z} = ∣ z ∣^{2}$ , and modulus is definite, multiplicative, and subadditive).

[F14]

Sine is odd, cosine is even, and $\sin^{2} x + \cos^{2} x = 1$ (Parity and the Pythagorean identity for sine and cosine).

[F15]

The integer part $j = ⌊ M d ⌋$ satisfies $j \leq M d < j + 1$ (Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ ).

[F16]

On a superposition of eigenspaces, QPE outcome probabilities are the eigenphase-weighted mixture, with no cross terms (Phase estimation on a superposition of eigenspaces).

[F17]

The complex exponential is $2 π i$ -periodic and additive in its exponent ( $\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential, $\ker (\exp) = 2 π i Z$ , and $\exp z = \exp w$ exactly when $z - w \in 2 π i Z$ ).

[F18]

Sine changes sign under a shift by $π$ , and the supplementary identity is $\sin (π - x) = \sin x$ ; iterating the shift gives $\sin (u - q π) = (- 1)^{q} \sin u$ for every integer $q$ (Quarter-turn values and shifts by pi/2 and pi, Cofunction, supplementary, quarter-turn, and reflection identities for the six trigonometric functions).

[F21]

The two Grover eigenphases are $θ / π$ and $1 - θ / π$ , with equal weights in the prepared state for $0 < a < 1$ (Grover eigenphases encode the good probability).

[F22]

QPE uses controlled positive powers and a projective readout of its $M$ -label register (Quantum phase estimation).

[F23]

Controlled and inverse access are explicit capabilities. In repeated-unitary mode the task expands $C (Q)$ into its controlled factors; in power-query mode each supplied $C (Q^{2^{j}})$ is a declared query with its own cost vector, including any constituent implementations used (Controlled Unitary Access, Inverse Unitary Access, Amplitude estimation and counting input/output contract).

[F24]

A standalone global phase leaves outcome probabilities invariant, but a controlled global phase is a relative phase on the control (Standalone Global Phase Leaves Pure-State POVM Probabilities Unchanged, A Controlled Global Phase Becomes a Relative Control Phase).

[F25]

The signed reflections in $Q$ are unitary involutions (Projector Reflections Are Hermitian Unitary Involutions).

[F26]

The phase-estimation access theorem counts $m$ supplied controlled-power queries or $M - 1$ repeated controlled- $Q$ calls (Phase-estimation query and gate costs).

[F27]

Classical algebraic encoding and any decimal refinement are charged separately (Classical bit-operation cost).

[F28]

A real value $P (ζ_{M})$ with $ζ_{M} = e^{2 π i / M}$ has the exact real cyclotomic representation and comparison interface of Finite exact comparison of real cyclotomic values.

Proof

1.1givenF21F22

By [F21], the input state lies in the span of eigenvectors of $Q$ with phases $θ / π$ and $1 - θ / π$ ; the endpoint cases are single eigenphases. QPE is therefore applied to its finite eigenphase decomposition, and the projective measurement returns a label in the finite set ${0, \dots, M - 1}$ by [F22].

1.2givenF23F24F25

In repeated-unitary mode, the task contract expands each controlled $Q$ as $C (- I) C (A) C (S_{0}) C (A^{*}) C (S_{g o o d})$ , with every factor supplied or implemented and charged. In power-query mode the estimator instead uses the supplied controlled powers as declared queries, each with its own cost vector; it does not require separately supplied controlled $A$ or $A^{*}$ . The scalar minus is invisible only in an uncontrolled call by [F24], while under control it is retained as a relative phase. The reflection factors are unitary by [F25]. Thus the circuit instructions are well-defined under either declared access mode.

1.3givenF26F27F28algebra

For $ζ_{M} = e^{2 π i / M}$ , Euler's formula gives $\sin^{2} (π y / M) = (1 - \cos (2 π y / M)) / 2 = (2 - ζ_{M}^{y} - ζ_{M}^{- y}) / 4$ . This is a real algebraic element of the cyclotomic field, so the stated output is exactly encoded; query counts are those in [F26] and decimal/bit processing is charged under [F27].

1.4givenF1F2F5F6F7F14F18algebra

Let $f (x) = \sin^{2} x$ and first suppose $0 < a < 1$ . Fix one Grover eigenphase $ϕ \in {θ / π, 1 - θ / π}$ , put $x = π ϕ$ , and let $d = d_{T} (ϕ - y / M)$ . The difference belongs to $(- 1, 1)$ , so there are an integer $q$ and $σ \in {- 1, 1}$ with $ϕ - y / M = q + σ d$ . Hence $π y / M = x - q π - σ π d$ . By the integer $π$ -shift identity [F18], the estimator output is $\sin^{2} (π y / M) = f (x + h)$ for $h = - σ π d$ . On either eigenphase, $f (x) = a$ : the first has $x = θ$ , and the second has $x = π - θ$ and uses the supplementary identity [F18]. Also $f^{'} (x) = \sin (2 x)$ by [F5], and $∣ f^{'} (x) ∣ = 2 \sqrt{a (1 - a)}$ on both branches: the second branch has $\sin (2 π - 2 θ) = - \sin (2 θ)$ by [F14] and [F18], while $\sin^{2} θ = a$ and $\cos^{2} θ = 1 - a$ by [F14]. For any real $x, h$ , [F5] and [F7] give $f (x + h) - f (x) - h f^{'} (x) = \int_{0}^{h} (\sin (2 x + 2 u) - \sin (2 x)) d u$ . By [F6], the integrand has absolute value at most $2 ∣ u ∣$ , so either orientation gives absolute remainder at most $h^{2}$ . On the phase-success event $d \leq k / M$ , hence $∣ h ∣ \leq π k / M$ , and the displayed error bound follows.

1.5givenF2F4F8F9F10F11F12F13F14F15F16F17algebra

Let $k \geq 2$ and fix one Grover eigenphase $ϕ$ . For a tail outcome at distance $d > 0$ , write $x = ϕ - y / M = ℓ \pm d$ by [F10]. Integer periodicity [F17] and sine parity [F14] reduce the denominator to $∣ 1 - e^{2 π i d} ∣ = 2 \sin (π d)$ by Euler [F12] and the sine addition formula. Thus [F8]–[F9] and [F12]–[F14] give $P_{ϕ} (y) = M^{- 2} ∣ 1 - e^{2 π i M (ϕ - y / M)} ∣^{2} / ∣ 1 - e^{2 π i (ϕ - y / M)} ∣^{2} \leq 1 / (4 M^{2} d^{2})$ , since the numerator modulus is at most $2$ and the denominator is $2 \sin (π d) \geq 4 d$ by [F10]–[F11]. In the tail $d \geq k / M$ , put $j = ⌊ M d ⌋$ ; [F15] gives $k \leq j \leq ⌊ M / 2 ⌋$ . Each annulus $j \leq M d < j + 1$ has at most two arcs of length $1 / M$ , each containing at most one label on the $1 / M$ grid. Thus the tail probability is at most $\frac{1}{2} \sum_{j = k}^{⌊ M / 2 ⌋} j^{- 2} < \frac{1}{2} \sum_{j = k}^{⌊ M / 2 ⌋} [j (j - 1)]^{- 1} \leq 1 / [2 (k - 1)]$ . An empty tail has probability zero, also strictly below this positive bound. This strengthens [F4], so success is strictly greater than $1 - 1 / [2 (k - 1)]$ for each phase and hence for their mixture.

2.1givenF2F3F16step 1.4

For $k = 1$ , both labels from [F3] have circular distance at most $1 / M$ from the relevant Grover phase. Off-grid, floor and ceiling labels have distances strictly below $1 / M$ ; on-grid the distance is zero. Thus the event used in step 1.4 has probability at least $8 / π^{2}$ .

3.1givenF1F2F4step 1.4algebra∎

At $a = 0$ the Grover phase is the exact grid phase $0$ ; at $a = 1$ it is $1 / 2$ , whose label $M / 2$ is integral because $M$ is even. Exact-grid recovery [F4] gives outputs $0$ and $1$ . Finally $2 \sqrt{a (1 - a)} \leq 1$ gives the stated $k = 1$ simplification.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Exact query count for the finite-grid iterative estimator

Statement

Across the finite-grid schedule with $K \geq 1$ and $S \geq 1$ , forward $A$ calls equal $S \sum_{k = 0}^{K} (m_{k} + 1)$ , inverse $A^{*}$ calls equal $S \sum_{k = 0}^{K} m_{k}$ , and both zero-input reflections and good-predicate reflections equal $S \sum_{k = 0}^{K} m_{k}$ . Thus the total number of $A / A^{*}$ calls is $S \sum_{k = 0}^{K} (2 m_{k} + 1) = S (1 + \sum_{k = 1}^{K} (2^{k} + 1)) = O (S 2^{K})$ . This count gives no finite-sample success guarantee.

For all integers $K, S, J \geq 1$ , the finite-grid procedure terminates and returns a uniquely determined exact algebraic output under its least-label tie rule. Its displayed factors are the Bernoulli likelihood factors of the prescribed independent shots; no finite-sample accuracy guarantee is asserted.

Facts & Assumptions

Given: The finite-grid iterative schedule and its explicitly supplied and charged prepared-success-subspace access contract.

[F1]

Stage $k$ has $S$ shots and uses $m_{k}$ Grover iterates after one fresh $A$ preparation (Iterative no-QFT amplitude estimation by finite-grid likelihood).

[F2]

The signed iterate is $Q = - A S_{0} A^{*} S_{g o o d}$ , and the matching prepared-success-subspace contract supplies and charges one call to each of $A, A^{*}, S_{0}, S_{g o o d}$ per uncontrolled iterate (Amplitude estimation and counting input/output contract, Prepared unitary and success subspace for amplitude amplification).

[F3]

The query model counts these oracle uses separately from ordinary gates (Quantum query complexity).

[F21]

The Grover iterate rotates the prepared state so that after $m$ iterates its good probability is $\sin^{2} ((2 m + 1) θ)$ (Grover eigenphases encode the good probability).

[F22]

The measurement outcomes are the two orthogonal good/bad projections (Finite projective measurements).

[F23]

The real likelihood values are finite cyclotomic algebraic numbers and admit terminating exact comparisons (Finite exact comparison of real cyclotomic values).

[F24]

Each oracle/state-preparation call is an explicit query resource (Quantum query algorithm).

[F25]

The fixed-count amplification procedure applies exactly the declared number of signed $Q$ iterates and then the good/bad projective instrument, with no controlled- $A$ call (Amplitude amplification with a fixed integer iteration count).

[F26]

The complex exponential is additive, and its kernel is $2 π i Z$ ( $\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential, $\ker (\exp) = 2 π i Z$ , and $\exp z = \exp w$ exactly when $z - w \in 2 π i Z$ ).

[F27]

For real $x$ , $e^{i x} = \cos x + i \sin x$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ).

[F28]

Sine is odd and cosine is even (Parity and the Pythagorean identity for sine and cosine).

[F29]

$\sin^{2} x = (1 - \cos (2 x)) / 2$ and $\cos^{2} x = (1 + \cos (2 x)) / 2$ (Double-angle and quadratic power-reduction identities).

Proof

1.1givenF21F22algebra

Suppose first that $0 < a < 1$ , so the normalized vectors $B, G$ are defined. Inductively applying the rotation matrix from [F21] to $\cos θ B + \sin θ G$ gives $Q^{m_{k}} ψ = \cos ((2 m_{k} + 1) θ) B + \sin ((2 m_{k} + 1) θ) G$ . Its good projection therefore has squared norm $\sin^{2} ((2 m_{k} + 1) θ)$ , so the listed good/bad measurement has the Bernoulli likelihood factors displayed in the definition.

1.2givenF21F22algebra

If $a = 0$ , then $Π_{g o o d} ψ = 0$ and $θ = 0$ . The endpoint clause of [F21]’s supplier gives $Q ψ = ψ$ , hence $Q^{m_{k}} ψ = ψ$ for every $m_{k} \geq 0$ , including $m_{0} = 0$ . The good/bad probabilities are therefore $0$ and $1$ , equal to $\sin^{2} ((2 m_{k} + 1) 0)$ and $\cos^{2} ((2 m_{k} + 1) 0)$ . Almost surely every $h_{k} = 0$ ; any record with a good outcome has probability zero under this endpoint model. The displayed Bernoulli factors give exactly these probabilities: a positive good exponent gives a zero factor, while the prescribed zero-exponent convention makes $0^{0} = 1$ when no good outcome occurs. No normalized good vector or conditional state on a zero-probability outcome is used.

1.3givenF23F26F27F28F29algebra

Set $s = 2 J$ and $ζ_{s} = e^{2 π i / s}$ . For each $k, j$ , use the residues $r_{k j}, r_{k j}^{'}$ in the algorithm's polynomial factors and put $α = (2 m_{k} + 1) θ_{j}$ . By [F26], $ζ_{s}^{r_{k j}} = e^{2 i α}$ and $ζ_{s}^{r_{k j}^{'}} = e^{- 2 i α}$ ; [F27]–[F28] give their sum as $2 \cos (2 α)$ . Therefore [F29] gives $U_{k j} (ζ_{s}) = \sin^{2} α$ and $V_{k j} (ζ_{s}) = \cos^{2} α$ . It follows that $P_{j} (ζ_{s}) = L_{j}$ for each $j$ . The comparison procedure [F23] decides every pair exactly, including equality; the nonempty finite set ${0, \dots, J}$ therefore has a maximizing label, and the least-label tie rule determines a unique output, including when all $L_{j} = 0$ (then the chosen label is $j = 0$ ). Its output polynomial $E_{\hat{j}} (ζ_{s})$ is exactly $\sin^{2} θ_{\hat{j}}$ by the same identity.

1.4givenF1F2algebra

A shot in stage $k$ uses one initial $A$ and then $m_{k}$ iterates. Each iterate contributes one more $A$ , one $A^{*}$ , one zero-input reflection, and one good reflection by [F2]. Therefore the per-stage counts are respectively $S (m_{k} + 1)$ , $S m_{k}$ , $S m_{k}$ , and $S m_{k}$ .

2.1givenF21F22step 1.1algebra

If $a = 1$ , orthogonality gives $∥ (I - Π_{g o o d}) ψ ∥^{2} = 1 - a = 0$ , so $Π_{g o o d} ψ = ψ$ and $θ = π / 2$ . The other endpoint clause of [F21]’s supplier gives $Q ψ = - ψ$ , hence $Q^{m_{k}} ψ = (- 1)^{m_{k}} ψ$ for every $m_{k} \geq 0$ , including $m_{0} = 0$ . Its good/bad probabilities are $1$ and $0$ , agreeing with $\sin^{2} ((2 m_{k} + 1) π / 2) = 1$ and $\cos^{2} ((2 m_{k} + 1) π / 2) = 0$ . Almost surely every $h_{k} = S$ ; a record containing a bad outcome has probability zero under this model. The bad factor is zero exactly when its exponent is positive, and the same $0^{0} = 1$ convention applies when no bad outcome occurs. No normalized bad vector or conditional state on a zero-probability outcome is used. Together with step 1.1, these cases establish the claimed Bernoulli likelihood factors on the whole task domain.

2.2F1F3step 1.4algebra

Summing over $k = 0, \dots, K$ gives the first four formulas. Since $m_{0} = 0$ and $m_{k} = 2^{k - 1}$ for $k \geq 1$ , $2 m_{k} + 1 = 2^{k} + 1$ for $k \geq 1$ , yielding the stated total. The geometric sum is $O (2^{K})$ , so the total is $O (S 2^{K})$ .

3.1givenF24F25step 1.1step 1.2step 2.1step 1.3

Every stage has finitely many shots and iterates because $K, S$ are finite. Fresh state preparations and measurements are part of the instructions, so no controlled $Q$ or QFT call is used. The likelihood selection is finite by step 1.3, but this argument establishes neither a sample-size error bound nor an $ϵ, δ$ guarantee.

4.1givenF1F3step 1.4step 2.2∎

The call totals established in step 1.4 and step 2.2 only tally explicitly invoked queries. By [F1], the analyzed procedure is a finite-grid likelihood schedule with no finite-sample success guarantee; [F3] counts its declared query actions but supplies no probability or approximation-error bound. Thus this resource count establishes no success theorem.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Exact zero-label probability for counting

Statement

For a fresh Count run with $L = 2^{ℓ} \geq 2$ and $θ = \arcsin \sqrt{t / N}$ , the QPE label is zero exactly when the raw count estimate is zero. If $0 < t < N$ , then $\Pr (y = 0) = \frac{\sin^{2} (L θ)}{L^{2} \sin^{2} θ} .$ For $t = 0$ this probability is $1$ ; when $L = 2$ and $0 < t < N$ it is $\cos^{2} θ$ .

Facts & Assumptions

Given: A fresh Count preparation, a Boolean predicate with $t$ marked elements, and an even power-of-two phase-grid size $L \geq 2$ .

[F1]

For $0 < t < N$ , the prepared state has equal squared overlap with Grover eigenphases $θ / π$ and $1 - θ / π$ ; at $t = 0$ it is a $+ 1$ eigenvector (Grover eigenphases encode the good probability).

[F2]

QPE on an eigenphase has the finite outcome kernel of Phase-estimation finite outcome law.

[F3]

For an eigenphase superposition, measurement probabilities are the eigenphase-weighted mixture with no cross terms (Phase estimation on a superposition of eigenspaces).

[F4]

The geometric sum, Euler formula, and integer periodicity give the label-zero sine quotient (Finite geometric sum for phase-estimation amplitudes, $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ , $\ker (\exp) = 2 π i Z$ , and $\exp z = \exp w$ exactly when $z - w \in 2 π i Z$ ).

[F5]

$\sin (2 θ) = 2 \sin θ \cos θ$ (Double-angle and quadratic power-reduction identities).

[F6]

Sine vanishes exactly at integer multiples of $π$ (The zero sets of sine and cosine and the least positive common period 2 pi).

[F7]

The raw Count estimate for label $y$ is $N \sin^{2} (π y / L)$ (Quantum counting by uniform-state amplitude estimation).

[F8]

Sine changes sign under an integer shift by $π$ , and $\sin (π - θ) = \sin θ$ (Quarter-turn values and shifts by pi/2 and pi, Cofunction, supplementary, quarter-turn, and reflection identities for the six trigonometric functions).

Proof

1.1givenF2F4algebra

For a phase $ϕ$ and label zero, the kernel in [F2] and geometric-sum fact [F4] give $L^{- 2} ∣ \sum_{j = 0}^{L - 1} e^{2 π i j ϕ} ∣^{2} = \sin^{2} (π L ϕ) / (L^{2} \sin^{2} (π ϕ))$ when $ϕ \notin Z$ , by Euler’s formula. At an integer phase all summands are $1$ , so the probability is one.

2.1givenF1F2F3F8step 1.1algebra

For $0 < t < N$ , [F1]–[F3] average this expression over $ϕ = θ / π$ and $1 - θ / π$ with weights $1 / 2$ . For the second branch, [F8] gives $\sin (π - θ) = \sin θ$ and, by iterating the $π$ -shift, $\sin (L π - L θ) = (- 1)^{L + 1} \sin (L θ)$ for the integer $L$ . Squaring these identities shows that both branches have the same squared numerator and denominator, so their mixture is the stated value. For $t = 0$ , the phase is zero and label zero is certain.

3.1givenF5F6F7step 2.1algebra∎

When $L = 2$ , [F5] gives $\sin (2 θ) = 2 \sin θ \cos θ$ , so the quotient in step 2.1 is $\cos^{2} θ$ . By [F6], $\sin^{2} (π y / L) = 0$ for an integer label $0 \leq y < L$ exactly when $y$ is a multiple of $L$ , hence exactly when $y = 0$ . Fact [F7] identifies this with a zero raw count estimate.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Amplitude-estimation query and precision complexity

Statement

For $M = 2^{m} \geq 4$ , repeated controlled- $Q$ access uses exactly $M - 1$ controlled- $Q$ applications in one run; each expands to one call each to controlled $A$ , controlled $A^{*}$ , controlled $S_{0}$ , controlled $S_{g o o d}$ , and the control phase. Supplied controlled-power access uses exactly $m$ power queries and reports their separate costs. With fixed success probability, additive amplitude error $ϵ \in (0, 1]$ is obtained with $M = Θ (1 / ϵ)$ , hence $O (1 / ϵ)$ repeated controlled- $Q$ calls; state preparation, ordinary gates, and classical encoding are separate costs.

Facts & Assumptions

Given: The $M$ -label amplitude-estimation circuit and the access mode from Amplitude estimation and counting input/output contract.

[F1]

The phase-estimation circuit uses one controlled power $Q^{2^{j}}$ for each $j = 0, \dots, m - 1$ (QFT-based amplitude estimation).

[F2]

QPE charges exactly $m$ supplied powers or $M - 1$ repeated controlled-unitary calls (Phase-estimation query and gate costs).

[F3]

The quantum query model counts only declared oracle actions (Quantum query complexity).

[F4]

In repeated-unitary mode, each controlled $Q$ expands into separately declared controlled $A$ , controlled $A^{*}$ , controlled $S_{0}$ , controlled $S_{g o o d}$ , and control phase. In power-query mode each supplied controlled power has its own declared cost vector, including any constituent implementations used (Amplitude estimation and counting input/output contract).

[F5]

The error guarantee is the inequality in Amplitude-estimation additive error and success probability.

Proof

1.1givenF1F2algebra

In repeated access, the $j$ th power takes $2^{j}$ calls by [F2]. Summing gives $\sum_{j = 0}^{m - 1} 2^{j} = 2^{m} - 1 = M - 1$ . In supplied-power access, there is one call for each of $m$ indices, hence $m$ queries.

2.1givenF3F4step 1.1

In repeated-unitary mode, [F4] makes each controlled- $Q$ call the charged product listed in the Statement. In power-query mode, the model instead charges each supplied controlled power and its declared cost vector, without inferring any constituent capability from a bare uncontrolled call.

3.1givenF3F5step 1.1algebra∎

For $0 < ϵ \leq 1$ , choose $M$ the least power of two at least $4 (22 / 7) / ϵ$ . By [F5], the $k = 1$ error is at most $π / M + π^{2} / M^{2} < ϵ / 4 + ϵ^{2} / 16 \leq 5 ϵ / 16 < ϵ$ , with success probability at least $8 / π^{2}$ . The least-power choice gives $M < 8 (22 / 7) / ϵ$ , so [F3] yields the $O (1 / ϵ)$ repeated-call bound; other cost coordinates remain separate.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Quantum counting error and boundary cases

Statement

For an integer $n \geq 0$ , $N = 2^{n}$ , $t$ marked addresses among $N$ , and $M = 2^{m} \geq 4$ , the raw estimate satisfies $∣ \tilde{t} - t ∣ \leq \frac{2 π k \sqrt{t (N - t)}}{M} + \frac{π^{2} k^{2} N}{M^{2}}$ with the same success probabilities as the amplitude-estimation theorem for integer $k \geq 1$ . If $t = 0$ , the raw estimate is zero with certainty. If $t = N$ , the raw estimate is $N$ with certainty because $M$ is even.

For every integer $n \geq 0$ and dyadic $M \geq 2$ , the counting procedure is well-defined, prepares the uniform state with exactly $n$ ordinary Hadamards, specializes the task amplitude to $a = t / N$ , and returns the exact algebraic pair $(\tilde{a}, N \tilde{a})$ with separately charged optional rounding. Its one-phase-qubit $M = 2$ branch is included in this well-definedness claim; the error guarantee above concerns $M \geq 4$ .

Facts & Assumptions

Given: an integer $n \geq 0$ , $N = 2^{n}$ , a predicate with exactly $t$ marked addresses, and the counting estimator with dyadic $M \geq 2$ . The error bound is claimed when $M \geq 4$ .

[F1]

Counting uses fraction amplitude $a = t / N$ and raw count $\tilde{t} = N \tilde{a}$ (Quantum counting by uniform-state amplitude estimation).

[F2]

The amplitude-estimation error and confidence bound are stated in Amplitude-estimation additive error and success probability.

[F3]

The endpoint Grover phases are exactly $0$ for $a = 0$ and $1 / 2$ for $a = 1$ (Grover eigenphases encode the good probability).

[F4]

A phase on the QPE grid is returned at its exact label with probability one (Exact phase recovery on the QPE grid).

[F21]

The amplitude task specializes to $a = t / N$ when the prepared state is uniform on addresses (Amplitude estimation and counting input/output contract).

[F22]

QPE uses $m \geq 1$ phase qubits and controlled powers of the supplied unitary (Quantum phase estimation); for $m \geq 2$ the amplitude-estimator specialization has the output map $\sin^{2} (π y / M)$ (QFT-based amplitude estimation).

[F23]

The Grover phase relation applies to the good-subspace projector defined by $f$ (Grover eigenphases encode the good probability).

[F24]

The exact Hadamard matrix is fixed and each wire receives one ordinary Hadamard in the uniform preparation (Exact one-qubit gates and rotations, Finite circuit resource accounting).

[F25]

Classical algebraic encoding and any integer rounding are charged separately (Classical bit-operation cost).

[F26]

The task charges controlled- $Q$ constituents in repeated-unitary mode and records each supplied controlled power with its own cost vector in power-query mode (Amplitude estimation and counting input/output contract).

Proof

1.1givenF21F22F23F24algebra

For $m = 1$ , the $M = 2$ procedure is the one-qubit instance of [F22]; for $m \geq 2$ it is [F22] specialized by the amplitude-estimation output map. The $n$ Hadamards turn $∣ 0^{n} ⟩$ into the uniform superposition; the definition of $Π_{g o o d}$ makes its squared projection norm $t / N$ by [F21] and [F24]. The eigenphase relation [F23] applies to this projector, and the amplitude-estimation instructions of [F22] use the corresponding $\sin^{2}$ output map. Thus the procedure estimates precisely this fraction and multiplying by $N$ gives the count estimate.

1.2givenF1F2algebra

For $M \geq 4$ , substitute $a = t / N$ in [F2] and multiply its error bound by $N$ . Since $N \sqrt{a (1 - a)} = \sqrt{t (N - t)}$ and $N (a) = t$ , the result is the displayed inequality with unchanged event probability.

2.1givenF22F25F26step 1.1

In repeated-unitary mode, each controlled $Q$ call includes one explicitly supplied or implemented controlled membership reflection. In power-query mode, each supplied controlled power carries its declared cost vector, including any membership-reflection implementation it uses; neither mode infers controlled access from a bare phase query. The exact algebraic result has separate postprocessing cost by [F25].

3.1givenF24F25F26step 1.1step 2.1

The output remains the real-valued pair $(\tilde{a}, \tilde{t})$ unless an integer is explicitly requested. Preparation uses exactly $n$ ordinary Hadamards by [F24]. The access-mode-specific query costs are those declared in [F26], while ordinary gate and bit costs remain separate by [F24]–[F25].

4.1givenF1F3F4step 1.2algebra∎

If $t = 0$ , the phase is the exact grid phase zero, so QPE returns $y = 0$ and $\tilde{t} = 0$ . If $t = N$ , the phase is $1 / 2$ ; the even grid size has exact label $M / 2$ , which returns $\tilde{t} = N$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Explicit median confidence guarantee for amplitude estimation

Statement

For rational $0 < ϵ \leq 1$ and $0 < δ < 1$ , the median procedure of Median confidence amplification for amplitude estimation returns $\tilde{a}$ with $∣ \tilde{a} - a ∣ \leq ϵ$ with probability at least $1 - δ$ .

Both rational scheduling loops terminate at their least prescribed values, and the odd finite list has a well-defined exact algebraic middle order statistic. Its phase-register size is admissible for the one-run estimator; preparations, queries and comparison bit work retain their separately declared costs.

Facts & Assumptions

Given: The median algorithm, its rational $ϵ, δ$ , and the one-run amplitude estimator.

[F1]

The median algorithm uses $M \geq 88 / (7 ϵ)$ and odd $r$ with $2^{r} \geq (2 / δ)^{8}$ (Median confidence amplification for amplitude estimation).

[F2]

A one-run estimate has error at most $π / M + π^{2} / M^{2}$ with probability at least $8 / π^{2}$ (Amplitude-estimation additive error and success probability).

[F3]

Independent Bernoulli variables satisfy $\Pr (∣ S - E S ∣ \geq u) \leq 2 e^{- 2 u^{2} / r}$ for $r$ trials (Chernoff bound for independent bernoulli trials).

[F4]

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

[F5]

$\ln x = \int_{1}^{x} d t / t$ for $x > 0$ , so $\ln$ is strictly increasing and $0 < \ln 2 < 1$ (The natural logarithm as the inverse of the exponential function, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[F6]

The natural logarithm is strictly increasing, satisfies $\ln (x y) = \ln x + \ln y$ and $\ln (1 / x) = - \ln x$ for positive inputs, and is inverse to the exponential (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm as the inverse of the exponential function).

[F21]

The one-run QFT estimator has the finite output and access instructions stated in QFT-based amplitude estimation.

[F22]

$π < 22 / 7$ (Rational bounds for pi used in finite schedules).

[F23]

Exact rational comparisons and output processing are charged as classical bit operations (Classical bit-operation cost).

[F24]

Independent repetitions mean separately prepared and measured runs in the quantum query model (Quantum query algorithm).

[F25]

Exact comparisons of real cyclotomic values terminate (Finite exact comparison of real cyclotomic values).

[F26]

The real field is Archimedean, natural powers obey $2^{j + 1} = 2^{j} \cdot 2$ , and induction holds on the naturals (Every complete ordered field is Archimedean, Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ , The principle of mathematical induction).

Proof

1.1givenF22F23F26algebra

The threshold $88 / (7 ϵ)$ is rational and exceeds $4 π / ϵ$ by [F22]. By [F26], powers of two are unbounded: choose a natural $q$ above any fixed real threshold by the Archimedean property and use induction to get $2^{q} \geq q + 1$ . Thus the doubling loop for $M$ terminates, and its first value above the threshold is the least such power; since $ϵ \leq 1$ and $88 / 7 > 8$ , this value is at least $16$ , so it is an admissible phase-register size and satisfies the one-run precision requirement. The rational target $(2 / δ)^{8}$ is finite. Choose a natural $q > (2 / δ)^{8}$ by [F26]; if $q$ is odd take $r = q$ , and if $q$ is even take $r = q + 1$ . Then $r$ is positive odd and $2^{r} \geq 2^{q} \geq q + 1 > (2 / δ)^{8}$ , so the odd-increment loop for $r$ terminates at the least positive odd solution. Each comparison is exact rational arithmetic after clearing denominators.

1.2givenF21F23F24F25algebra

Each run returns an algebraic estimate in the same real cyclotomic field $Q (ζ_{M} + ζ_{M}^{- 1})$ . Exact finite comparisons determine the middle order statistic; repetitions use independent fresh preparations and readouts by [F24].

1.3givenF1F2F4algebra

From [F1]–[F2] and $ϵ \leq 1$ , a good run has error at most $ϵ / 4 + ϵ^{2} / 16 \leq 5 ϵ / 16 < ϵ$ . Its success probability is at least $p = 8 / π^{2} > p_{0} : = 98 / 121$ , so each failure indicator has mean at most $1 - p_{0}$ .

2.1givenF23step 1.1step 1.2

The output is one of the $r$ finite run estimates, and the odd sample size makes its middle index unique. Thus the procedure is defined for all stated rational inputs, with query and classical comparison costs remaining separate under [F23].

2.2givenF3step 1.3algebra

If the median lies outside $[a - ϵ, a + ϵ]$ , at least $(r + 1) / 2$ runs are failures. For their sum $S$ , this entails $S - E S \geq r (p_{0} - 1 / 2)$ . Applying the two-sided additive bound [F3] to this containing event gives probability at most $2 \exp (- 2 r (p_{0} - 1 / 2)^{2})$ .

3.1givenF1F5F6step 2.2algebra∎

Here $p_{0} - 1 / 2 = 75 / 242$ and $c = 2 (75 / 242)^{2} = 5625 / 29282$ , so $8 c > 1$ . By [F6], monotonicity and the logarithm product law turn $2^{r} \geq (2 / δ)^{8}$ into $r \ln 2 \geq 8 \ln (2 / δ)$ . Put $L = \ln (2 / δ) > 0$ . By [F5], $0 < \ln 2 < 1$ , so $r > 8 L$ and hence $c r > 8 c L > L$ . The reciprocal law in [F6] gives $\ln (δ / 2) = - L$ , while the inverse identity gives $\ln (e^{- c r}) = - c r < \ln (δ / 2)$ . Strict increase of $\ln$ therefore implies $2 e^{- c r} < δ$ . Step 2.2 bounds median failure by this quantity, proving success at least $1 - δ$ .

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Relative approximate counting with unknown marked count

Definition

Input. A Boolean predicate on $N = 2^{n} \geq 1$ addresses with an integer $n \geq 0$ , the fully declared controlled counting access model, and rational $0 < ϵ \leq 1$ .

Set $ℓ = 0$ . Repeatedly increment $ℓ$ , set $L = 2^{ℓ}$ , run a fresh Count $(f, L)$ , and stop exactly when its label $y$ is nonzero or $L^{2} \geq 4 N$ . The test $y \neq 0$ is an exact finite label test. Initialize $m = 0$ and $M = 1$ ; repeatedly increment $m$ and double $M$ while $M < [20 (22 / 7)^{2} / ϵ] L$ , using exact rational comparison, so that $M = 2^{m}$ . Run a fresh Count $(f, M)$ and run Rational-interval rounding of a counting output on $(N, M, y)$ to output an integer within $2 / 3$ of its exact algebraic count estimate, as proved by Terminating certified rounding for a counting estimate. The scale loop returns the least power of two meeting its rational threshold; all scales are powers of two and the multiplier grows as $1 / ϵ$ times $L$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Quantum counting query complexity

Statement

For an integer $n \geq 0$ , $N = 2^{n}$ , and a power of two $M = 2^{m} \geq 4$ , Count uses exactly $M - 1$ repeated controlled-Grover calls, or exactly $m$ supplied controlled-power queries, in addition to its $n$ ordinary Hadamards for uniform-state preparation. At fixed success probability, additive count error $ϵ_{c} \in (0, N]$ is obtained using $O (N / ϵ_{c})$ repeated controlled-Grover calls; additive fraction error $ϵ_{f} \in (0, 1]$ uses $O (1 / ϵ_{f})$ . The count-dependent error bound retains the terms $2 π k \sqrt{t (N - t)} / M$ and $π^{2} k^{2} N / M^{2}$ . Algebraic output encoding and integer rounding have separate classical bit costs.

Facts & Assumptions

Given: The counting algorithm, an integer $n \geq 0$ , $N = 2^{n}$ , a power-of-two $M \geq 4$ , and the declared query mode.

[F1]

The estimator has the phase-estimation circuit and uniform preparation specified in Quantum counting by uniform-state amplitude estimation.

[F2]

Repeated controlled- $Q$ access costs $M - 1$ calls and supplied powers cost $m$ calls (Amplitude-estimation query and precision complexity).

[F3]

The additive amplitude guarantee is the statement of Amplitude-estimation additive error and success probability.

[F4]

Query counts and classical bit operations are separate resources (Quantum query complexity, Classical bit-operation cost).

Proof

1.1givenF1F2F4

The exact controlled-iterate counts follow from [F2]. The uniform address preparation applies one Hadamard to each of the $n$ wires by [F1], in addition to phase-register and QFT gates separately counted in [F4].

2.1givenF3step 1.1algebra

For fraction error $ϵ_{f}$ , set amplitude precision $ϵ = ϵ_{f}$ ; for count error $ϵ_{c}$ , set $ϵ = ϵ_{c} / N$ . Choosing $M$ the least power of two at least $4 (22 / 7) / ϵ$ makes the $k = 1$ error $π / M + π^{2} / M^{2} < ϵ$ for $ϵ \leq 1$ by [F3]. The least-power bound is $M < 8 (22 / 7) / ϵ$ , giving the two asymptotic query bounds.

3.1givenF3F4step 2.1algebra∎

The count-dependent expression is [F3] multiplied by $N$ as in Quantum counting error and boundary cases. Multiplication by $N$ , exact cyclotomic representation, and optional integer rounding are classical bit work and remain separate under [F4].

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Median amplitude-estimation query cost

Statement

In the repeated controlled- $Q$ access mode, the median estimator uses exactly $r (M - 1)$ controlled- $Q$ calls. With the explicit thresholds in Median confidence amplification for amplitude estimation, this is $O (ϵ^{- 1} (1 + \ln (1 / δ)))$ calls. For the conventional range $0 < δ \leq 1 / 2$ , this is $O (ϵ^{- 1} \ln (1 / δ))$ . Controlled $A$ , controlled $A^{*}$ , controlled predicate reflections, state preparation, gate counts, and classical order-statistic work are separately charged.

Facts & Assumptions

Given: The median procedure with its integer parameters $M, r$ and repeated controlled- $Q$ access.

[F1]

The procedure makes $r$ fresh runs with a common $M$ (Median confidence amplification for amplitude estimation).

[F2]

Each run uses exactly $M - 1$ repeated controlled- $Q$ calls (Amplitude-estimation query and precision complexity).

[F3]

The access model charges declared quantum query actions separately from ordinary gates and classical bits (Quantum query complexity).

[F4]

The least power-of-two threshold is $M \geq 88 / (7 ϵ)$ and the least odd sample size satisfies $2^{r} \geq (2 / δ)^{8}$ (Median confidence amplification for amplitude estimation).

[F5]

$\ln$ is strictly increasing, $\ln 2 > 0$ , and $\ln 2 < 1$ (The natural logarithm as the inverse of the exponential function, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[F6]

The natural logarithm is strictly increasing and satisfies the product, reciprocal, and power laws on positive reals (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

Proof

1.1givenF1F2algebra

By [F1] and [F2], each of the $r$ runs makes $M - 1$ calls, so the exact total is $r (M - 1)$ .

2.1givenF4F5F6step 1.1algebra

The least-power rule gives $M < 2 \cdot 88 / (7 ϵ) = 176 / (7 ϵ)$ . Put $X = 2 / δ > 2$ . Since $X^{8} > 256$ , the least positive odd $r$ with $2^{r} \geq X^{8}$ satisfies $r \geq 9$ , so $r - 2$ is a positive odd integer that fails the threshold: $2^{r - 2} < X^{8}$ . By [F6], taking logarithms gives $(r - 2) \ln 2 < 8 \ln X$ , hence $r < 2 + 8 \ln X / \ln 2$ by [F5]. Also $\ln X = \ln 2 + \ln (1 / δ)$ by [F6], so [F5] gives $r = O (1 + \ln (1 / δ))$ . When $δ \leq 1 / 2$ , [F5]–[F6] give $\ln (1 / δ) \geq \ln 2 > 0$ , so this simplifies to $O (\ln (1 / δ))$ . Multiplying these bounds proves both asymptotic counts in the Statement.

3.1givenF3step 1.1step 2.1∎

Each controlled- $Q$ call expands into the separately declared controlled constituents of the task definition; [F3] keeps their gate/query costs distinct, as well as the initial preparations and classical median work.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Relative approximate counting query complexity

Statement

For an integer $n \geq 0$ , $N = 2^{n}$ , a predicate with $0 \leq t \leq N$ marked addresses, and rational $0 < ϵ \leq 1$ , in the repeated controlled- $Q$ access mode the dyadic relative-counting procedure uses expected $O (ϵ^{- 1} \sqrt{N / t})$ controlled- $Q$ calls when $t > 0$ , and exactly one controlled membership-reflection call per such controlled Grover call. Each controlled $Q$ additionally uses its declared controlled $A$ , controlled $A^{*}$ , controlled $S_{0}$ , and control phase. For $t = 0$ , this implementation uses $O (\sqrt{N} / ϵ)$ controlled- $Q$ calls: the rough loop reaches its $L^{2} \geq 4 N$ cutoff, and the final estimator still uses $M = Θ (L / ϵ)$ . State preparation, gates, and certified classical rounding are separate.

Facts & Assumptions

Given: The relative-counting algorithm with $N = 2^{n}$ , an integer $n \geq 0$ , $0 \leq t \leq N$ , rational $0 < ϵ \leq 1$ , and repeated controlled- $Q$ access.

[F1]

The loop uses dyadic rough scales and a final size $M = Θ (L / ϵ)$ (Relative approximate counting with unknown marked count).

[F2]

For $0 < t < N$ , the continuation probability at rough scale $L$ is $P_{0} (L) = \sin^{2} (L θ) / (L^{2} \sin^{2} θ)$ ; for $t = 0$ , the zero label is certain (Exact zero-label probability for counting).

[F3]

One controlled Grover call includes the controlled good reflection as a separate supplied access (Amplitude estimation and counting input/output contract).

[F4]

The declared query model counts each controlled call separately from gates and bit operations (Quantum query complexity).

[F5]

In repeated controlled-unitary access, Count at any phase-register size $L = 2^{ℓ} \geq 2$ uses exactly $L - 1$ controlled- $Q$ calls (Phase-estimation query and gate costs).

[F6]

For every real $X > 0$ , some dyadic scale $2^{ℓ}$ exceeds $X$ : choose a natural $q > X$ by the Archimedean property, prove $2^{q} \geq q + 1$ by induction using the recursion for natural powers, and take $ℓ = q$ (Every complete ordered field is Archimedean, Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ , The principle of mathematical induction).

[F7]

At $t = N$ , the prepared state is a Grover eigenvector with phase $1 / 2$ (Grover eigenphases encode the good probability).

[F8]

An exact-grid phase is returned at its exact QPE label with probability one (Exact phase recovery on the QPE grid).

[F9]

Count at scale $L$ runs QPE on the counting Grover iterate with $L$ phase labels, including the one-qubit circuit when $L = 2$ (Quantum counting by uniform-state amplitude estimation).

Proof

1.1givenF2F7F8F9algebra

If $t = N$ , [F7] gives phase $1 / 2$ ; at the first rough scale $L = 2$ , [F9] and [F8] give label $y = 1 \neq 0$ , so the loop stops at $L = 2$ . For $0 < t < N$ , $\sin^{2} θ = t / N$ , and [F2] gives $P_{0} (L) \leq 1 / (L^{2} \sin^{2} θ) = N / (t L^{2})$ . Once $L \geq 18 π \sqrt{N / t}$ , this is at most $1 / (324 π^{2}) < 1 / 4$ .

2.1givenF5F6step 1.1algebra

Suppose $0 < t < N$ and put $X = 18 π \sqrt{N / t}$ . Choose a natural $q > X$ by [F6]. Induction using the natural-power recursion gives $2^{q} \geq q + 1$ , so a dyadic scale exceeds $X$ ; scanning the rough scales in order reaches a first $L_{*} \geq X$ . Its preceding scale is smaller than $X$ , hence $L_{*} < 2 X = 36 π \sqrt{N / t}$ . By [F5], a rough Count at scale $L$ costs $L - 1 \leq L$ controlled- $Q$ calls. The rough query costs below $L_{*}$ sum to less than $2 L_{*}$ . If the loop reaches $L_{*}$ , each later zero outcome has conditional probability at most $1 / 4$ by step 1.1; reaching the $j$ th later scale costs at most $2^{j} L_{*}$ and has probability at most $4^{- j}$ . Hence the expected tail is bounded by $L_{*} \sum_{j \geq 0} (1 / 2)^{j} = 2 L_{*}$ . If the cutoff occurs before $L_{*}$ , it only removes terms from these upper bounds. Thus the expected rough cost is $O (\sqrt{N / t})$ . If $L$ is the actual stopping scale, its final rough Count costs $L - 1 \geq L / 2$ calls since $L \geq 2$ , so $E L$ is at most twice the expected rough query cost and is also $O (\sqrt{N / t})$ .

3.1F1F5step 1.1step 2.1algebra

The final dyadic $M$ is less than twice its threshold, so $M = O (L / ϵ)$ . By [F5], the final Count uses $M - 1$ calls; for $0 < t < N$ , the bound on $E L$ in step 2.1 therefore gives $O (ϵ^{- 1} \sqrt{N / t})$ expected final controlled- $Q$ calls, while the rough term is absorbed because $ϵ \leq 1$ . If $t = N$ , step 1.1 gives $L = 2$ , so the rough cost is one call and the final size is $M = O (1 / ϵ)$ , matching $O (ϵ^{- 1} \sqrt{N / t})$ . If $t = 0$ , the cutoff scale lies in $[2 \sqrt{N}, 4 \sqrt{N})$ , the geometric rough-call sum is $O (\sqrt{N})$ , and the final schedule uses $M = O (\sqrt{N} / ϵ)$ calls by [F5]. Thus the stated zero-case cost retains the $ϵ$ factor.

4.1givenF3F4step 3.1∎

Each repeated controlled- $Q$ call contains exactly one controlled $S_{g o o d}$ factor by [F3]; [F4] keeps that query count separate from controlled $A / A^{*}$ and other gates. Thus the stated membership-reflection and resource counts follow.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Relative approximate counting success guarantee

Statement

For the dyadic relative-counting procedure with rational $0 < ϵ \leq 1$ , if $t > 0$ its integer output is within $ϵ t$ of $t$ with probability at least $2 / 3$ . If $t = 0$ , every rough and final Count output is exactly zero, the loop stops at its finite cutoff, and the output is zero with certainty.

For every stated input, both dyadic scheduling loops terminate and the final certified integer rounding terminates. The final scale is the least dyadic value at least $T = [20 (22 / 7)^{2} / ϵ] L$ , hence $T \leq M < 2 T$ and $M \geq 20 π^{2} L / ϵ$ . Fresh preparations and all controlled access and bit costs remain as declared.

Facts & Assumptions

Given: The relative-counting algorithm, $N = 2^{n} \geq 1$ , integer $t$ marked addresses, and rational $0 < ϵ \leq 1$ .

[F1]

The rough loop doubles $L$ , stops on nonzero label or $L^{2} \geq 4 N$ , and uses final $M \geq 20 (22 / 7)^{2} L / ϵ$ (Relative approximate counting with unknown marked count).

[F2]

Fresh Count has zero-label probability $\sin^{2} (L θ) / (L^{2} \sin^{2} θ)$ , with exact zero endpoint (Exact zero-label probability for counting).

[F3]

The final Count raw error has the $k = 1$ bound and probability at least $8 / π^{2}$ (Quantum counting error and boundary cases).

[F4]

For $0 \leq u \leq 1 / 2$ , $\sin (π u) \geq 2 u$ , and for $v \geq 0$ , $\sin v \leq v$ (Sine chord and linear bounds).

[F5]

$3 < π < 22 / 7$ (Rational bounds for pi used in finite schedules).

[F6]

The cosine power series and alternating-series remainder apply at $2 / 5$ (Sine and cosine defined by their real power series, The alternating series test: if $(b_{k})$ is nonincreasing with $b_{k} \to 0$ then $\sum_{k} (- 1)^{k} b_{k}$ converges, the sum lies between any two consecutive partial sums, and the error after $n$ terms is at most $b_{n}$ ).

[F7]

$\sin' = \cos$ , sine is nonnegative on $[0, π / 2]$ , cosine is nonnegative and decreasing there, and the mean value theorem turns a nonnegative derivative into monotonicity (The derivatives of sine and cosine are cosine and minus sine, Signs, monotonicity intervals, and ranges of sine and cosine, The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[F8]

The sine double-angle formula is $\sin (2 x) = 2 \sin x \cos x$ (The addition formulas for sine and cosine).

[F21]

Count is defined for every power-of-two label size $L \geq 2$ and uses the explicit controlled membership reflection (Quantum counting by uniform-state amplitude estimation).

[F22]

The exact zero-label probability is the kernel in Exact zero-label probability for counting.

[F23]

The rational upper bound $22 / 7$ exceeds $π$ (Rational bounds for pi used in finite schedules).

[F24]

Certified integer rounding returns an integer within $2 / 3$ of the raw algebraic value (Terminating certified rounding for a counting estimate).

[F25]

The exact label and interval operations are classical postprocessing (Classical bit-operation cost).

[F26]

Proof

1.1givenF21F22F25F26algebra

The rough loop starts at $L = 2$ and doubles each round. By [F26] choose a natural $q > 4 N$ . Induction gives $2^{j} \geq j + 1$ for every natural $j$ : it is equality at $j = 0$ , and $2^{j + 1} = 2^{j} + 2^{j} \geq (j + 1) + (j + 1) \geq j + 2$ . Thus after at most $q$ rounds the scale $L = 2^{q} > 4 N$ has been reached, so $L^{2} \geq 4 N$ ; the other stopping condition can only make the loop stop earlier. By [F21]–[F22], $y \neq 0$ is exactly a nonzero raw estimate test.

1.2givenF1F2F26algebra

Suppose $t > 0$ and put $θ = \arcsin \sqrt{t / N}$ . Let $m$ be the largest nonnegative index such that $2^{j} θ \leq 1 / 5$ for every $1 \leq j \leq m$ ; the condition is vacuous for $m = 0$ . This index is finite because $θ > 0$ and the powers of two are unbounded by [F26]. For each rough scale $L = 2^{j}$ with $1 \leq j \leq m$ , one has $L θ \leq 1 / 5$ and $L^{2} \leq 1 / (25 θ^{2}) \leq N / 25 < 4 N$ , because $θ \geq \sin θ = \sqrt{t / N} \geq 1 / \sqrt{N}$ . Thus cutoff cannot occur during these $m$ rounds.

2.1givenF23F24F25F26step 1.1algebra

The threshold $T = [20 (22 / 7)^{2} / ϵ] L$ is a positive rational. By [F26] and the induction argument in step 1.1, some power of two exceeds $T$ , so the doubling loop terminates; its first value $M \geq T$ is the least such power and satisfies $M < 2 T$ . Since $L \geq 2$ and $ϵ \leq 1$ , $T > 2$ , so $M$ is even and at least $2$ , as required by Count and the rounding lemma. Since $22 / 7 > π$ , $M \geq 20 π^{2} L / ϵ$ and $M < 40 (22 / 7)^{2} L / ϵ$ . The rounding step [F24] terminates and makes the integer output explicit; its bit work is covered by [F25].

2.2F2F4F7F8step 1.2algebra

For $0 \leq x \leq 2 / 5$ , define $H (x) = \sin x - x \cos x$ . By [F7], $H (0) = 0$ and $H^{'} (x) = x \sin x \geq 0$ , so the mean value theorem gives $\sin x \geq x \cos x$ . At each rough scale $L θ \leq 1 / 5$ , this and $\sin θ \leq θ$ yield $P_{0} (L) \geq \cos^{2} (L θ)$ by [F2]. Fresh runs make their zero events independent. If $m \geq 1$ , then $θ \leq 1 / 10$ and [F8] gives $\prod_{j = 1}^{m} \cos^{2} (2^{j} θ) = [\sin (2^{m + 1} θ) / (2^{m + 1} \sin θ \cos θ)]^{2} \geq \cos^{2} (2 / 5)$ , using $\sin x \geq x \cos x$ , $\sin θ \cos θ \leq θ$ , $2^{m + 1} θ \leq 2 / 5$ , and the decrease of nonnegative cosine from [F7]. If $m = 0$ , the empty product is $1 \geq \cos^{2} (2 / 5)$ .

2.3F1F3F4step 1.2algebra

On the event that the first $m$ rough labels are zero, the loop cannot terminate before rough scale $2^{m + 1}$ : none of scales $2^{j}$ , $1 \leq j \leq m$ , triggers the cutoff by step 1.2, and the first $m$ labels are zero. By maximality of $m$ , $2^{m + 1} θ > 1 / 5$ , so $2^{m + 1} > 1 / (5 θ)$ . The loop therefore terminates at some scale $L \geq 2^{m + 1} > 1 / (5 θ)$ , whether by a nonzero label or by the cutoff. Thus [F1] gives $M \geq 20 (22 / 7)^{2} L / ϵ > 4 π^{2} / (ϵ θ)$ , in particular $M \geq 4$ . Applying [F3], using $\sqrt{t (N - t)} = N \sin θ \cos θ$ and $θ \leq (π / 2) \sin θ$ , gives $∣ \tilde{t} - t ∣ \leq ϵ t / 4 + ϵ^{2} t / 64$ . The trigonometric inequality follows from [F4] with $u = θ / π$ .

3.1givenF21F22step 1.1step 2.1

Each Count call uses a fresh preparation; the algorithm uses only the supplied access capabilities in [F21]. It is a finite procedure with exact finite stopping tests and certified final output, but no success or query-cost bound follows from this definition alone.

3.2F3F5F6step 2.3algebra

Since $\cos (2 / 5) \geq 1 - (2 / 5)^{2} / 2 = 23 / 25$ by the alternating cosine series [F6], [F5] gives $\cos^{2} (2 / 5) 8 / π^{2} > (23 / 25)^{2} (8 \cdot 49 / 484) > 2 / 3$ , where the last comparison is $622104 > 605000$ after cross multiplication. The final Count is a fresh run, so conditionally on the rough outcomes it succeeds with probability at least $8 / π^{2}$ ; multiplying by the rough-event probability proves joint probability greater than $2 / 3$ .

3.3F1F3step 2.3algebra

The output integer differs from $\tilde{t}$ by at most $2 / 3$ by [F1]. If $ϵ t < 1$ , raw error plus rounding is at most $(ϵ / 4 + ϵ^{2} / 64) t + 2 / 3 < 17 / 64 + 2 / 3 < 1$ , so the integer equals $t$ . If $ϵ t \geq 1$ , then $2 / 3 \leq 2 ϵ t / 3$ and $ϵ^{2} t \leq ϵ t$ , so total error is at most $(1 / 4 + 1 / 64 + 2 / 3) ϵ t = 179 ϵ t / 192 < ϵ t$ .

4.1F1F2step 3.3∎

If $t = 0$ , every Count phase is exactly zero by [F2], so rough labels are zero and cutoff $L^{2} \geq 4 N$ eventually terminates. The final Count is also exactly zero, and certified rounding returns zero. This proves the zero-count branch and completes the success guarantee.

5 · Examples, counterexamples and false statements

None yet.