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.

Grover Search and Invariant-Plane Rotations — Examples

1 · Prerequisites

2 · Summary

The companion calculates the exact integer-iterate probabilities for four addresses with one marked item and gives a two-address counterexample to treating a continuous optimizer as a legal fractional query count. The page is a logical leaf.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Exact Grover rotation for four addresses and one marked item

Example

Take $N = 4$ and $t = 1$ . Compute the exact angle and integer-iterate success probabilities, including the first exact peak and subsequent oscillation.

Facts & Assumptions

Given: $N = 4 = 2^{2}$ , $t = 1$ , and the standard Grover iterate.

[F1]

Exact success probability after an integer number of Grover iterates: $p_{k} = \sin^{2} ((2 k + 1) θ)$ for integer $k \geq 0$ , with $\sin θ = \sqrt{t / N}$ .

[F2]

Principal inverse sine and inverse cosine: the principal inverse sine is the inverse of sine on $[- π / 2, π / 2]$ .

[F3]

Signs, monotonicity intervals, and ranges of sine and cosine: sine is positive and strictly increasing on $(0, π / 2)$ .

[F4]

Pi as twice the smallest positive zero of cosine and Cosine has a smallest positive zero, lying strictly between zero and two: $π > 0$ .

[F5]

Quarter-turn values and shifts by pi/2 and pi: $\sin (π / 2) = 1$ and $\cos (π / 2) = 0$ .

[F6]

The addition formulas for sine and cosine: sine and cosine obey their addition formulas.

[F7]

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

[F8]

The derivatives of sine and cosine are cosine and minus sine: $\sin 0 = 0$ .

Verification

1.1givenF2F3F4F5F6F7F8algebra

Put $x = π / 6$ , $s = \sin x$ , and $c = \cos x$ . Since $0 < π / 6 < π / 2$ , [F3] and [F8] give $s > 0$ . By [F7], $\cos (2 x) = c^{2} - s^{2} = 1 - 2 s^{2}$ , so $c^{2} = 1 - s^{2}$ ; also $\sin (2 x) = 2 s c$ . Using [F6] and [F5], $1 = \sin (π / 2) = \sin (3 x) = \sin (2 x + x) = \sin (2 x) \cos x + \cos (2 x) \sin x = 2 s c^{2} + (c^{2} - s^{2}) s = 3 s - 4 s^{3} .$ Thus $(2 s - 1)^{2} (s + 1) = 0$ . Since $s > 0$ , $s + 1 > 0$ , so $s = 1 / 2$ ; then [F2] gives $\arcsin (1 / 2) = π / 6$ .

2.1step 1.1F1F5F7algebra

Here $\sqrt{t / N} = 1 / 2$ , so $θ = π / 6$ . Formula [F1] gives $p_{0} = \sin^{2} (π / 6) = 1 / 4$ and $p_{1} = \sin^{2} (π / 2) = 1$ . Also, [F5] and [F7] give $\sin (5 π / 6) = \sin (π / 3 + π / 2) = \cos (π / 3) = 1 - 2 \sin^{2} (π / 6) = 1 / 2$ , so $p_{2} = 1 / 4$ . Thus the first integer peak is exact.

3.1step 1.1step 2.1F1F5algebra∎

For every integer $k \geq 0$ , $(2 (k + 3) + 1) π / 6 = (2 k + 1) π / 6 + π$ . The shift by $π$ changes the sine sign and therefore preserves its square, so $p_{k + 3} = p_{k}$ . The integer success pattern repeats $1 / 4, 1, 1 / 4$ .

CounterexampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

A real-valued optimum is not a fractional Grover iteration

Statement refuted

The real-valued optimizer $k_{*} = π / (4 θ) - 1 / 2$ is always a legal number of standard Grover-iterate queries.

Witness

Take $N = 2$ and $t = 1$ . Then $θ = \arcsin (1 / \sqrt{2}) = π / 4$ , so $k_{*} = 1 / 2$ , which is not an integer. Standard Grover circuits apply an integer number of iterates. The exact continuous formula at $k_{*}$ gives $1$ , while the legal integer choices $k = 0$ and $k = 1$ each give success probability $1 / 2$ .

Facts & Assumptions

Given: $N = 2 = 2^{1}$ , one marked item, and the standard Grover iterate.

[F1]

Exact success probability after an integer number of Grover iterates: for integer $k \geq 0$ , $p_{k} = \sin^{2} ((2 k + 1) θ)$ .

[F2]

Principal inverse sine and inverse cosine: $\arcsin$ is the inverse of sine on $[- π / 2, π / 2]$ .

[F3]

Signs, monotonicity intervals, and ranges of sine and cosine: sine and cosine have their usual signs on $(0, π / 2)$ .

[F4]

Pi as twice the smallest positive zero of cosine and Cosine has a smallest positive zero, lying strictly between zero and two: $π > 0$ .

[F5]

Quarter-turn values and shifts by pi/2 and pi: $\sin (π / 2) = 1$ and $\cos (π / 2) = 0$ .

[F6]

The addition formulas for sine and cosine: sine and cosine obey their addition formulas.

[F7]

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

[F9]

Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ : nonnegative square roots are unique.

Refutation

1.1givenF2F3F4F5F7F9algebra

Put $x = π / 4$ , $s = \sin x$ , and $c = \cos x$ . Since $0 < π / 4 < π / 2$ by [F4], [F3] gives $s, c > 0$ . By [F7] and [F5], $0 = \cos (π / 2) = \cos (2 x) = c^{2} - s^{2}$ , so $(c - s) (c + s) = 0$ . Since $c + s > 0$ , we have $c = s$ . Then [F7] and [F5] give $1 = \sin (π / 2) = \sin (2 x) = 2 s c = 2 s^{2}$ , so [F9] gives $s = 1 / \sqrt{2}$ . Thus $\arcsin (1 / \sqrt{2}) = π / 4$ by [F2], and $k_{*} = π / (4 (π / 4)) - 1 / 2 = 1 / 2$ .

2.1givenF1F5F6step 1.1algebra∎

The legal standard query counts are integers, so $k_{*} = 1 / 2$ is not executable. Applying the integer formula [F1] gives $p_{0} = \sin^{2} (π / 4) = 1 / 2$ and $p_{1} = \sin^{2} (3 π / 4) = 1 / 2$ , whereas substituting the noninteger $k_{*}$ into the trigonometric expression would give $\sin^{2} (π / 2) = 1$ . The continuous expression therefore does not describe an allowed standard Grover circuit at this input.

Grover Search and Invariant-Plane Rotations — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Exact Grover rotation for four addresses and one marked item

Example

Facts & Assumptions

Verification

A real-valued optimum is not a fractional Grover iteration

Statement refuted

Witness

Facts & Assumptions

Refutation

Sources