LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

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.

The rational Grover recurrence equals the success probability

Statement

Let $N = 2^{n}$ , let $1 \leq t \leq N$ , put $q = 1 - 2 t / N$ and $θ = \arcsin \sqrt{t / N}$ . If $T_{0} (q) = 1$ , $T_{1} (q) = q$ , and $T_{r + 1} (q) = 2 q T_{r} (q) - T_{r - 1} (q)$ , then for every integer $k \geq 0$ , $(1 - T_{2 k + 1} (q)) / 2 = \sin^{2} ((2 k + 1) θ) .$ Thus the exact rational values used by the known-count Grover schedule equal its actual marked-address probabilities.

Facts & Assumptions

Given: $N = 2^{n}$ , $1 \leq t \leq N$ , the recurrence above, and $θ = \arcsin \sqrt{t / N}$ .

[F1]

Known-count Grover search by exact integer maximization: the known-count schedule uses $q = 1 - 2 t / N$ and computes $T_{0} = 1$ , $T_{1} = q$ , $T_{r + 1} = 2 q T_{r} - T_{r - 1}$ and $p_{k} = (1 - T_{2 k + 1} (q)) / 2$ .

[F2]

Exact success probability after an integer number of Grover iterates: after $k$ Grover iterates the marked-address probability is $\sin^{2} ((2 k + 1) θ)$ .

[F3]

The addition formulas for sine and cosine: $\cos (x + y) = \cos x \cos y - \sin x \sin y$ .

[F4]

The subtraction formulas for sine and cosine: $\cos (x - y) = \cos x \cos y + \sin x \sin y$ .

[F5]

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

Proof

1.1givenF1F5algebra

Since $\sin^{2} θ = t / N$ , [F5] gives $\cos (2 θ) = 1 - 2 t / N = q$ . Define $c_{r} = \cos (2 r θ)$ . Then $c_{0} = 1 = T_{0} (q)$ and $c_{1} = q = T_{1} (q)$ .

2.1F1F3F4step 1.1induction

For every integer $r \geq 1$ , applying [F3] and [F4] with $x = 2 r θ$ and $y = 2 θ$ and adding the identities gives $c_{r + 1} = 2 \cos (2 θ) c_{r} - c_{r - 1} = 2 q c_{r} - c_{r - 1}$ . This is the same recurrence as $T_{r} (q)$ ; the initial values in step 1.1 and induction on $r$ give $c_{r} = T_{r} (q)$ for every $r \geq 0$ .

3.1F2F5step 2.1algebra∎

Setting $r = 2 k + 1$ in step 2.1 and applying the power-reduction identity [F5] gives $(1 - T_{2 k + 1} (q)) / 2 = (1 - \cos ((4 k + 2) θ)) / 2 = \sin^{2} ((2 k + 1) θ)$ . By [F2] this is the actual Grover success probability.

Depends on

Used by

Grover search upper-bound success guarantee Theorem

Dependency tree · two levels

31 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

Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum Amplitude Amplification and Estimation (standard reference, not scraped)