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

1 · Prerequisites

2 · Summary

This page derives the invariant marked/unmarked plane and the exact success law after an integer number of Grover iterates. It keeps the exact-maximizer known-count procedure separate from the fixed nine-round randomized known-count search and the BBHT unknown-count schedule. Oracle queries, one-qubit preparation, reflection gates, classical bit work, and candidate verification remain separate resource costs. Exact maximization can require exponential classical preprocessing, and unknown-count search does not give a finite-time emptiness decision.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite marked-item search and its bit oracle

Definition

Fix an integer $n \geq 0$ , put $N = 2^{n}$ , and let $D_{n} = {0, \dots, N - 1}$ . The big-endian encoding ${enc}_{n} : {0, 1}^{n} \to D_{n}$ is a bijection by Big-endian bit-string indices are bijective, so identify each address word $w$ with its slot $x = {enc}_{n} (w)$ . A search instance is a total Boolean function $f : D_{n} \to {0, 1}$ , equivalently the word-indexed function $w \mapsto f ({enc}_{n} (w))$ . Its marked set is $M = {x \in D_{n} : f (x) = 1}$ and its marked count is $t = ∣ M ∣$ . The standard bit query is the coherent XOR action $U_{f} ∣ x, b ⟩ = ∣ x, b \oplus f (x) ⟩$ ; the associated phase query is $O_{M} ∣ x ⟩ = (- 1)^{f (x)} ∣ x ⟩$ . One standard bit query implements this phase action with a response qubit prepared in $∣ - ⟩$ , by One standard query implements one phase query. A measured candidate $x$ is verified by a separate standard bit query. Knowing $t$ is additional classical input; no count promise is made in the unknown-count version. A correct search output is a verified $x \in M$ . The distinguished output none is used only by a procedure whose input includes the exact fact $t = 0$ ; it is not a finite-time test for emptiness when $t$ is unknown.

The number $n$ may be zero, so $N = 1$ and the address register then has its one-dimensional empty-word basis. The phase query is uncontrolled; no controlled-query capability is part of this definition.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

One Grover iterate in the standard bit-query model

Definition

Gate model. The declared nonoracle model permits exact callable $H$ and $X$ , each occurrence charged as one elementary gate. It supplies the exact reflection $R_{s}$ either as an explicitly costed primitive or through a declared costed circuit over the selected gate alphabet; for the displayed Hadamard conjugation, the all-zero reflection and both Hadamard layers must be supplied and charged. Standard bit queries are charged separately.

For a marked-search instance on $D_{n}$ , let $∣ s ⟩ = H^{\otimes n} ∣ 0^{n} ⟩ = N^{- 1 / 2} \sum_{x \in D_{n}} ∣ x ⟩$ and $R_{s} = 2 ∣ s ⟩ ⟨ s ∣ - I$ . Prepare a response qubit from $∣ 0 ⟩$ by applying $X$ and then $H$ , giving $∣ - ⟩$ . Apply the standard bit query $U_{f}$ to the address and response registers; phase kickback applies $O_{M}$ to the address and leaves the response in $∣ - ⟩$ . Then apply $R_{s}$ to the address register. This defines $G = R_{s} O_{M}$ with one standard bit query and no intermediate measurement. Repeated iterates reuse the response qubit in $∣ - ⟩$ . The query count is separate from the preparation and reflection gate costs. A reflection about $∣ s ⟩$ may be represented as $H^{\otimes n} (2 ∣ 0^{n} ⟩ ⟨ 0^{n} ∣ - I) H^{\otimes n}$ , whose reflection cost must be charged under the declared gate model.

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

Orthogonal marked and unmarked components of the uniform state

Statement

Let $M \subseteq D_{n}$ have size $t$ with $0 < t < N$ . Define $∣ G ⟩ = t^{- 1 / 2} \sum_{x \in M} ∣ x ⟩, ∣ B ⟩ = (N - t)^{- 1 / 2} \sum_{x \notin M} ∣ x ⟩ .$ Then $∣ G ⟩$ and $∣ B ⟩$ are orthonormal. For $θ = \arcsin \sqrt{t / N} \in (0, π / 2)$ , the uniform state is $∣ s ⟩ = \sin θ ∣ G ⟩ + \cos θ ∣ B ⟩,$ with $\sin^{2} θ = t / N$ .

Facts & Assumptions

Given: $n \geq 0$ , $N = 2^{n}$ , a marked set $M \subseteq D_{n}$ , and $0 < t = ∣ M ∣ < N$ . Here the uniform state denotes the equal-positive-amplitude vector $∣ s ⟩ = N^{- 1 / 2} \sum_{x \in D_{n}} ∣ x ⟩$ .

[F1]

Finite marked-item search and its bit oracle: $D_{n}$ is a finite address set with marked subset $M$ and marked count $t$ .

[F2]

The computational basis is orthonormal: distinct address basis vectors are orthogonal and every address basis vector has norm $1$ .

[F3]

Real and complex inner product spaces, with the inner product linear in the first argument: the inner product is linear in the first argument, conjugate-linear in the second, and positive definite.

[F4]

Dirac Notation Conversion: kets denote vectors and the Dirac pairing is the reversed-argument root inner product.

[F5]

Principal inverse sine and inverse cosine: $\arcsin$ takes values in $[- π / 2, π / 2]$ and $\sin (\arcsin y) = y$ for $y \in [- 1, 1]$ .

[F6]

Signs, monotonicity intervals, and ranges of sine and cosine: cosine is strictly decreasing on $[0, π]$ and sine is strictly increasing on $[- π / 2, π / 2]$ .

[F7]

Parity and the Pythagorean identity for sine and cosine: $\sin^{2} u + \cos^{2} u = 1$ for every real $u$ .

[F8]

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

[F9]

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

[F10]

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

[F11]

Squaring is monotone on the nonnegatives: on nonnegative reals, strict and non-strict order are equivalent to the corresponding order of squares; applied to nonnegative roots, this compares their order.

Proof

1.1givenF1F2F3F4algebra

Orthonormality of the address basis [F2] gives $⟨ G, G ⟩ = t^{- 1} \sum_{x, y \in M} ⟨ x, y ⟩ = 1$ and $⟨ B, B ⟩ = (N - t)^{- 1} \sum_{x, y \notin M} ⟨ x, y ⟩ = 1$ . The sets $M$ and $D_{n} ∖ M$ are disjoint, so every cross term in $⟨ G, B ⟩$ is zero. Thus the two vectors are orthonormal.

2.1givenF1F5F6F7F8F9F10F11step 1.1algebra∎

Put $a = t / N \in (0, 1)$ and $θ = \arcsin \sqrt{a}$ . By [F5], $\sin θ = \sqrt{a}$ ; since $\sqrt{a} > 0$ and $\sin 0 = 0$ by [F9], strict increase [F6] implies $θ > 0$ . Also $\sqrt{a} < 1$ by [F11] because $a < 1$ , while $1 = \sin (π / 2)$ by [F10]; strict increase gives $θ < π / 2$ . Since cosine is strictly decreasing on $[0, π]$ by [F6], we have $\cos θ > \cos (π / 2) = 0$ by [F10]. The Pythagorean identity [F7] and square-root uniqueness [F8] give $\cos θ = \sqrt{1 - a}$ . Splitting the uniform sum into $M$ and its complement now gives $∣ s ⟩ = \sqrt{t / N} ∣ G ⟩ + \sqrt{(N - t) / N} ∣ B ⟩ = \sin θ ∣ G ⟩ + \cos θ ∣ B ⟩$ and $\sin^{2} θ = t / N$ .

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

One Grover iterate uses one standard bit query

Statement

One execution of One Grover iterate in the standard bit-query model makes exactly one standard bit-query call, through phase kickback. The response-qubit preparation and the reflection about $∣ s ⟩$ make no oracle calls and are charged separately as gates or explicitly supplied reflection operations.

Facts & Assumptions

Given: The Grover iterate and the worst-case query-count convention.

[F1]

One Grover iterate in the standard bit-query model: one standard bit query is applied to a response qubit in $∣ - ⟩$ , after which the address reflection is applied.

[F2]

Quantum query complexity: the query coordinate counts designated oracle invocations and keeps ordinary gates outside those calls separate.

[F3]

One standard query implements one phase query: one prepared-response standard query induces the phase query and uses exactly one query invocation.

Proof

1.1givenF1F2F3

The algorithm contains one invocation of $U_{f}$ ; [F3] identifies that invocation with the phase mark on the address register. By [F2], this designated oracle invocation contributes one query.

2.1step 1.1F1F2∎

The response preparation and $R_{s}$ are operations outside $U_{f}$ , so they add no oracle invocation. The iterate therefore uses exactly one query, with no gate-cost bound inferred.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Known-count Grover search by exact integer maximization

Definition

Gate model. Use the nonoracle model of One Grover iterate in the standard bit-query model, with exact callable $H$ and $X$ charged per occurrence and an explicitly supplied, costed exact reflection implementation. Each invoked Grover iterate retains its separate standard-bit-query and nonoracle costs.

Input $N = 2^{n}$ , standard bit-query access to $f = 1_{M}$ , and the exact integer $t = ∣ M ∣$ . If $t = 0$ , return none without a query. If $t > 0$ , find $K$ as the least positive integer with $t K^{2} \geq N$ : start with $l o = 0, h i = 1$ , repeatedly set $l o = h i, h i = 2 h i$ while $t {h i}^{2} < N$ , then use upper-midpoint binary search on the false/true interval until $h i - l o = 1$ . Thus $K = h i = ⌈ \sqrt{N / t} ⌉$ . Prepare $∣ s ⟩ = H^{\otimes n} ∣ 0^{n} ⟩$ , set $q = 1 - 2 t / N$ , and compute exactly the rational recurrence $T_{0} (q) = 1, T_{1} (q) = q, T_{m + 1} (q) = 2 q T_{m} (q) - T_{m - 1} (q) (1 \leq m \leq 2 K) .$ Compute the recurrence through index $m = 2 K + 1$ . For each integer $k = 0, \dots, K$ , compute $p_{k} = (1 - T_{2 k + 1} (q)) / 2$ . Choose the least $k$ attaining the maximum of this finite rational list, apply One Grover iterate in the standard bit-query model exactly $k$ times, measure the address register, and make one separate standard bit query to verify the candidate. Return the candidate if marked and the failure symbol otherwise. The state preparation, all-zero reflection, classical recurrence and comparison work, and oracle queries are distinct costs; this definition makes no polynomial-time preprocessing claim.

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

The Grover iterate rotates the marked/unmarked plane

Statement

Assume $0 < t < N$ and use the orthonormal ordered basis $(∣ B ⟩, ∣ G ⟩)$ of Orthogonal marked and unmarked components of the uniform state. Let $Π_{M}$ project onto the marked-address span, $S_{M} = I - 2 Π_{M}$ , and $R_{s} = 2 ∣ s ⟩ ⟨ s ∣ - I$ . The Grover iterate $G = R_{s} S_{M}$ preserves $span {∣ B ⟩, ∣ G ⟩}$ , and in this basis has matrix $(\begin{array}{cc} \cos (2 θ) & - \sin (2 θ) \\ \sin (2 θ) & \cos (2 θ) \end{array}), θ = \arcsin \sqrt{t / N} .$ The initially prepared state has coordinate column $(\cos θ, \sin θ)^{T}$ .

Facts & Assumptions

Given: $0 < t < N$ and the normalized vectors in the marked/unmarked decomposition.

[F1]

Orthogonal marked and unmarked components of the uniform state: $∣ B ⟩, ∣ G ⟩$ are orthonormal and $∣ s ⟩ = \cos θ ∣ B ⟩ + \sin θ ∣ G ⟩$ .

[F2]

Orthogonal-Projector Reflection and Access Contract: $R_{Π} = 2 Π - I$ and $S_{Π} = I - 2 Π$ have the displayed opposite signs.

[F3]

One Grover iterate in the standard bit-query model: $G = R_{s} S_{M}$ and $R_{s} = 2 ∣ s ⟩ ⟨ s ∣ - I$ .

[F4]

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

Proof

1.1givenF1F2algebra

The mark $S_{M}$ fixes each unmarked basis vector and negates each marked basis vector. Thus its matrix on $(∣ B ⟩, ∣ G ⟩)$ is $diag (1, - 1)$ and it preserves the plane.

1.2F1F3F4algebra

In the same basis, [F1] and the rank-one convention [F3] give $R_{s} = 2 (\begin{array}{cc} \cos^{2} θ & \cos θ \sin θ \\ \cos θ \sin θ & \sin^{2} θ \end{array}) - I = (\begin{array}{cc} \cos 2 θ & \sin 2 θ \\ \sin 2 θ & - \cos 2 θ \end{array})$ by [F4].

2.1step 1.1step 1.2F1algebra∎

Multiplying the matrix in step 1.2 by $diag (1, - 1)$ from step 1.1 gives the stated rotation matrix. Its columns lie in the same two-dimensional plane, so the plane is invariant; the initial coordinate column is $(\cos θ, \sin θ)^{T}$ by [F1].

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Known-count search by randomized Grover iteration

Definition

Input $N = 2^{n}$ , exact count $t$ , and standard bit-query access to $f = 1_{M}$ . If $t = 0$ , return none without a query. If $t > N / 2$ , perform at most nine independent rounds: prepare a fresh address register by $H^{\otimes n} ∣ 0^{n} ⟩$ , measure an address, make one standard bit query to verify it, and return it if marked; after nine failures return the failure symbol.

If $0 < t \leq N / 2$ , find the least positive integer $K$ satisfying $t K^{2} \geq N$ by binary search. Initialize $l o = 0$ and $h i = 2^{⌈ n / 2 ⌉}$ ; while $h i - l o > 1$ , put $m i d = l o + ⌈ (h i - l o) / 2 ⌉$ , replace $h i$ by $m i d$ if $t {m i d}^{2} \geq N$ , and otherwise replace $l o$ by $m i d$ . Set $b$ to the least nonnegative integer with $2^{b} \geq K$ . In each of nine independent rounds, draw $b$ fair bits to obtain $j \in {0, \dots, 2^{b} - 1}$ . Reject the round without a query if $j \geq K$ . Otherwise prepare a fresh $∣ s ⟩ = H^{\otimes n} ∣ 0^{n} ⟩$ and a fresh response qubit $∣ - ⟩$ using $X$ then $H$ , apply One Grover iterate in the standard bit-query model exactly $j$ times, measure the address register, and make one separate bit query to verify the measured candidate. Return it if marked. After nine unsuccessful rounds, return the failure symbol. Uniform-state preparation uses exactly $n$ Hadamards; each iterate uses one query and a separately charged reflection. No query, state-preparation, reflection-gate, or classical-bit cost is conflated.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

BBHT search when the marked count is unknown

Definition

Input $N = 2^{n}$ and standard bit-query access to $f = 1_{M}$ , with no input giving $t = ∣ M ∣$ . Fix $c = 3 / 2$ and initialize $ℓ = 0$ . In each round increment $ℓ$ and put $M_{ℓ} = ⌈ c^{ℓ} ⌉$ . First draw one uniform address $x \in D_{n}$ and verify it by one standard bit query; if $f (x) = 1$ , return $x$ . Otherwise choose $j$ uniformly from ${1, \dots, M_{ℓ}}$ , prepare a fresh address register as $∣ s ⟩ = H^{\otimes n} ∣ 0^{n} ⟩$ and a fresh response qubit as $∣ - ⟩$ using $X$ then $H$ , apply the Grover iterate exactly $j$ times, measure the address register, and verify the candidate by a separate standard bit query. Return a verified marked item and otherwise begin the next round. Every random choice and quantum register is fresh in each round. The algorithm has no false positive; when $t = 0$ it continues forever and does not produce a finite-time emptiness decision. The gate and state-preparation costs are charged separately from the bit-query count.

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

Exact success probability after an integer number of Grover iterates

Statement

For $0 < t < N$ , let $θ = \arcsin \sqrt{t / N}$ . After an integer $k \geq 0$ Grover iterates starting from $∣ s ⟩$ , the probability of measuring a marked address is $p_{k} = \sin^{2} ((2 k + 1) θ) .$ For $t = 0$ this probability is $0$ , and for $t = N$ it is $1$ for every integer $k \geq 0$ ; these endpoint cases are direct one-dimensional branches and do not normalize a nonexistent marked or unmarked state.

Facts & Assumptions

Given: The finite marked-search instance and the Grover iterate.

[F1]

Orthogonal marked and unmarked components of the uniform state: for $0 < t < N$ , $∣ s ⟩$ has coordinate column $(\cos θ, \sin θ)^{T}$ in the ordered basis $(∣ B ⟩, ∣ G ⟩)$ .

[F2]

The Grover iterate rotates the marked/unmarked plane: $G$ acts on that plane by the matrix $(\begin{array}{cc} \cos 2 θ & - \sin 2 θ \\ \sin 2 θ & \cos 2 θ \end{array})$ .

[F3]

One Grover iterate in the standard bit-query model: each iteration applies $G = R_{s} O_{M}$ to the address and leaves the phase-kickback response in $∣ - ⟩$ .

[F4]

One standard query implements one phase query: phase kickback applies the phase mark and returns the response qubit to $∣ - ⟩$ .

[F5]

The addition formulas for sine and cosine: sine and cosine of a sum obey their addition formulas.

[F6]

Normalized output law for finite quantum query branches: a terminal address outcome has weight equal to the sum of the diagonal state weights over all unmeasured register values.

[F7]

Parity and the Pythagorean identity for sine and cosine: $\sin^{2} x + \cos^{2} x = 1$ .

[F8]

A unit-vector outer product is a density operator: for a unit vector $u$ , $∣ u ⟩ ⟨ u ∣$ is a density operator.

[F9]

Real and complex inner product spaces, with the inner product linear in the first argument: the root inner product is conjugate-symmetric and linear in its first argument.

[F10]

The computational basis is orthonormal: the full address/response computational basis is orthonormal.

[F11]

Dirac Notation Conversion: $∣ u ⟩ ⟨ v ∣ z = ⟨ z, v ⟩_{r o o t} u$ .

[F12]

Finite registers and their ordered computational bases: the address and response registers form an ordered tensor-product register.

[F13]

The product basis is orthonormal and tensor dimensions multiply: the product basis is orthonormal and the tensor-product pairing is the product of factor pairings.

[F14]

One standard query implements one phase query: the response is prepared by $X$ then $H$ into $∣ - ⟩$ and is returned unchanged by phase kickback.

[F15]

Exact one-qubit gates and rotations: $X$ and $H$ are the exact unitary one-qubit gates in the ordered computational basis.

Proof

1.1givenF1algebra

For $k = 0$ , the address coordinate column is $(\cos θ, \sin θ)^{T}$ by [F1], which is $(\cos ((2 k + 1) θ), \sin ((2 k + 1) θ))^{T}$ .

2.1step 1.1F2F5induction

If after $k$ iterations the column is $(\cos ((2 k + 1) θ), \sin ((2 k + 1) θ))^{T}$ , multiplication by the matrix in [F2] and the addition formulas [F5] gives $(\cos ((2 k + 3) θ), \sin ((2 k + 3) θ))^{T}$ . Induction therefore gives the marked amplitude $\sin ((2 k + 1) θ)$ for every integer $k \geq 0$ .

3.1step 2.1F1F3F4F7F8F10F12F13F14F15algebra

The address vector at step 2.1 is unit by [F1] and [F7]. The response starts in the unit basis vector $∣ 0 ⟩$ and the gates $X, H$ in [F15] are unitary, so the response state $∣ - ⟩$ supplied by [F14] is unit. Their tensor product $u$ is unit by the product pairing [F12]–[F13], and [F8] makes $ρ = ∣ u ⟩ ⟨ u ∣$ a density operator.

4.1step 2.1step 3.1F1F6F9F10F11F13F14F15algebra

For each product-basis vector $e_{x, b}$ , [F9] and [F11] give the diagonal weight $⟨ ρ e_{x, b}, e_{x, b} ⟩ = ∣ ⟨ e_{x, b}, u ⟩ ∣^{2}$ . By step 2.1, the address coordinate along $∣ G ⟩$ is $\sin ((2 k + 1) θ)$ ; the definition $∣ G ⟩ = t^{- 1 / 2} \sum_{x \in M} ∣ x ⟩$ in [F1] therefore gives coefficient $\sin ((2 k + 1) θ) / \sqrt{t}$ at each marked $x$ . The squared response coordinates sum to $1$ because $∣ - ⟩$ is unit and the qubit computational basis is orthonormal by [F10], [F14]–[F15]. Summing over the $t$ marked addresses and both response values gives $t (\sin^{2} ((2 k + 1) θ) / t) \cdot 1 = \sin^{2} ((2 k + 1) θ)$ . The terminal output law [F6] sums precisely over the unmeasured response register, so this is the measured marked probability.

5.1givenF3algebra∎

If $t = 0$ , $O_{M} = I$ and $R_{s} ∣ s ⟩ = ∣ s ⟩$ , so all iterates remain in the unmarked subspace and the marked probability is $0$ . If $t = N$ , $O_{M} = - I$ and each iterate maps $∣ s ⟩$ to $- ∣ s ⟩$ ; every address is marked, so the probability is $1$ .

PropositionStatement: Literature-sourcedProof: AI-generatedOpen item page →

Bit cost of exact known-count iteration selection

Statement

For $t > 0$ , put $K = ⌈ \sqrt{N / t} ⌉$ and $q = 1 - 2 t / N$ . The exact selection procedure in Known-count Grover search by exact integer maximization computes the recurrence $T_{0} = 1, T_{1} = q, T_{m + 1} = 2 q T_{m} - T_{m - 1}$ through $m = 2 K + 1$ and compares $p_{k} = (1 - T_{2 k + 1} (q)) / 2$ for $0 \leq k \leq K$ . If $n \geq 1$ , the recurrence numerators and denominators have $O (K n)$ bits and schoolbook arithmetic selects the least maximizing $k$ in $O (K^{2} n^{2})$ classical bit operations. For $n = 0$ , necessarily $N = t = 1$ and the selection costs $O (1)$ . Since $K = Θ (\sqrt{N})$ when $t = 1$ , the preprocessing can be exponential in $n$ ; this query bound supplies no end-to-end polynomial-time claim.

Facts & Assumptions

Given: $N = 2^{n}$ , exact $t$ with $1 \leq t \leq N$ , and the recurrence and finite candidate list in the known-count algorithm.

[F1]

Known-count Grover search by exact integer maximization: the algorithm finds $K$ by doubling and binary search for the least positive integer with $t K^{2} \geq N$ , forms $q = 1 - 2 t / N$ , computes $T_{m} (q)$ through $m = 2 K + 1$ , and selects the least maximizer of $p_{k} = (1 - T_{2 k + 1} (q)) / 2$ for $0 \leq k \leq K$ .

[F2]

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

[F3]

Ceilings give the least positive integer meeting a real threshold: $⌈ x ⌉$ is the least integer at least $x$ , and is monotone in the threshold.

[F4]

Principal inverse sine and inverse cosine: $\sin (\arcsin y) = y$ on $[- 1, 1]$ .

[F5]

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

[F6]

The addition formulas for sine and cosine: $\cos (u + v) = \cos u \cos v - \sin u \sin v$ for real $u, v$ .

[F7]

Classical bit-operation cost: classical bit cost counts the transitions used for arithmetic, comparisons, reading and writing bits; oracle calls are a separate coordinate.

[F8]

Parity and the Pythagorean identity for sine and cosine: $∣ \cos x ∣ \leq 1$ for every real $x$ .

[F9]

Squaring is monotone on the nonnegatives: squaring preserves order on nonnegative reals, so $m \mapsto t m^{2}$ is nondecreasing for integers $m \geq 0$ when $t > 0$ .

Proof

1.1givenF1F2F3F9algebra

For $t > 0$ , $P (m) : t m^{2} \geq N$ is monotone on nonnegative integers by [F9], and its least positive true index is $K = ⌈ \sqrt{N / t} ⌉$ by [F2]–[F3]. The doubling loop starts with false endpoint $l o = 0$ and doubles $h i$ until $P (h i)$ is true; it terminates because powers of two are unbounded. If $K = 1$ it stops immediately. If $K > 1$ , the first true power of two satisfies $K \leq h i < 2 K$ , and the preceding power $l o = h i / 2$ is false. Upper-midpoint binary search preserves the false/true invariant and reduces each interval of width $d > 1$ to width at most $⌈ d / 2 ⌉$ , so it reaches width one after $O (\log (K + 1))$ evaluations and returns the least positive true index $K$ . Since $K \leq ⌈ \sqrt{N} ⌉$ , the endpoints have $O (n)$ bits for $n \geq 1$ .

1.2givenF1F2F4F5F6inductionalgebra

Put $a = t / N$ and $θ = \arcsin \sqrt{a}$ . Then $q = 1 - 2 a = \cos (2 θ)$ by [F4]–[F5]. The recurrence has base values $T_{0} = \cos 0 = 1$ and $T_{1} = \cos (2 θ) = q$ . By [F6], $\cos (2 (m + 1) θ) + \cos (2 (m - 1) θ) = 2 \cos (2 θ) \cos (2 m θ),$ so induction in the recurrence gives $T_{m} (q) = \cos (2 m θ)$ for every computed index. Therefore $p_{k} = (1 - \cos ((4 k + 2) θ)) / 2 = \sin^{2} ((2 k + 1) θ)$ , and the rational list in [F1] is the actual integer-iterate success list.

2.1step 1.2F1F8algebra

Write $u = N - 2 t$ , so $q = u / N$ , and define $A_{m} = N^{m} T_{m} (q)$ . Then $A_{0} = 1$ , $A_{1} = u$ , and the recurrence gives $A_{m + 1} = 2 u A_{m} - N^{2} A_{m - 1},$ so each $A_{m}$ is an integer. By step 1.2 and [F8], $∣ A_{m} ∣ \leq N^{m}$ . Thus for $n \geq 1$ and $m \leq 2 K + 1$ , both numerator $A_{m}$ and denominator $N^{m}$ have $O (K n)$ bits. For $n = 0$ , $N = t = 1$ , $K = 1$ , and all recurrence values have constant bit length.

3.1F7step 1.1step 2.1algebra

At recurrence index $m$ , multiplying the $O (m n)$ -bit integer $A_{m}$ by the $O (n)$ -bit integer $u$ costs $O (m n^{2})$ schoolbook bit operations; multiplication by $N^{2}$ is a binary shift, and addition costs $O (m n)$ . Summing over $m \leq 2 K$ gives $O (K^{2} n^{2})$ . Each predicate evaluation in step 1.1 uses $O (n)$ -bit operands and schoolbook arithmetic, hence $O (n^{2})$ bit operations; the $O (\log (K + 1))$ evaluations cost $O (n^{2} \log (K + 1)) \subseteq O (K^{2} n^{2})$ .

4.1F1step 2.1step 3.1F7algebra

For odd $m = 2 k + 1$ , write $p_{k} = (N^{m} - A_{m}) / (2 N^{m})$ . Advancing from $k - 1$ to $k$ scales the previous running-best numerator by $N^{2}$ to put it over the new denominator, then compares the two integers and updates only on strict increase. Each comparison costs $O (K n)$ bit operations by step 2.1, and there are $K + 1$ candidates, so all comparisons cost $O (K^{2} n)$ , within step 3.1's bound. Strict updates retain the least $k$ in a tie.

5.1F2F3step 3.1step 4.1algebra

If $t = 1$ , then $\sqrt{N} \leq K = ⌈ \sqrt{N} ⌉ \leq \sqrt{N} + 1 \leq 2 \sqrt{N}$ , so $K = Θ (2^{n / 2})$ . The preprocessing bound can therefore be exponential in $n$ , and it supplies no polynomial-time conclusion from the query bound.

6.1givenF1step 2.1step 3.1step 4.1algebra∎

If $n = 0$ , necessarily $N = t = 1$ , so $K = 1$ and the direct selection branch and finite recurrence take constant work, as stated.

PropositionStatement: Literature-sourcedProof: AI-generatedOpen item page →

Classical bit cost of randomized known-count search

Statement

For $0 < t \leq N / 2$ , the procedure Known-count search by randomized Grover iteration computes $K = ⌈ \sqrt{N / t} ⌉$ by $O (n)$ binary-search predicate evaluations on integers with $O (n)$ bits, costing $O (n^{3})$ deterministic bit operations by schoolbook arithmetic. Computing $b$ and drawing the nine $b$ -bit iteration labels uses $O (n)$ further classical bit operations and random bits. The direct-sampling branch $t > N / 2$ uses $O (n)$ classical bit operations in total for address and output bookkeeping across at most nine rounds; its address samples are obtained by quantum measurement, not by generating $9 n$ classical fair bits. These bounds are for $n \geq 1$ ; when $n = 0$ , only the direct branch occurs and its bookkeeping is constant. Quantum measurements, state preparation, gates, and oracle calls are separate costs.

Facts & Assumptions

Given: The known-count randomized algorithm, $N = 2^{n}$ , exact integer $1 \leq t \leq N$ , and the classical bit-cost convention.

[F1]

Known-count search by randomized Grover iteration: in the $t \leq N / 2$ branch, binary search finds the least $K \geq 1$ with $t K^{2} \geq N$ , then samples nine labels using $b$ fair bits.

[F2]

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

[F3]

Ceilings give the least positive integer meeting a real threshold: $K = ⌈ \sqrt{N / t} ⌉$ is the least positive integer meeting $t K^{2} \geq N$ .

[F4]

Classical bit-operation cost: classical bit work includes random-bit generation and address bookkeeping, while each oracle invocation is charged separately.

[F5]

Squaring is monotone on the nonnegatives: square roots preserve order on nonnegative reals.

[F6]

Squaring is monotone on the nonnegatives: squaring preserves order on nonnegative reals, so $P (m) : t m^{2} \geq N$ is monotone for $m \geq 0$ and $t > 0$ .

Proof

1.1givenF1F2F3F5F6algebra

Since $t \geq 1$ , $\sqrt{N / t} \leq \sqrt{N}$ by [F5], hence $K \leq ⌈ \sqrt{N} ⌉ \leq 2^{⌈ n / 2 ⌉} = h i$ . The predicate $P (m) : t m^{2} \geq N$ is false at $l o = 0$ , true at $h i$ , and monotone by [F6]. At each step with width $d = h i - l o > 1$ , the upper midpoint $l o + ⌈ d / 2 ⌉$ lies strictly between the endpoints; replacing the endpoint with the same predicate value preserves the invariant and leaves width at most $⌈ d / 2 ⌉$ . Thus after $O (n)$ steps the width is one and $h i$ is the least positive integer satisfying $P$ , namely $K$ by [F3].

2.1step 1.1F4algebra

The initial endpoint has $O (n)$ bits, so each midpoint does as well. A schoolbook square and multiplication compute $t m^{2}$ in $O (n^{2})$ bit operations, and comparison with $N$ takes $O (n)$ more. The $O (n)$ predicate evaluations therefore cost $O (n^{3})$ .

2.2givenF1step 1.1F4algebra

The least $b \geq 0$ with $2^{b} \geq K$ satisfies $b \leq ⌈ n / 2 ⌉$ . The nine labels consume $9 b = O (n)$ random bits and comparisons; forming or writing each at-most- $n$ -bit address uses $O (n)$ more bookkeeping. Hence this work is within $O (n^{3})$ .

3.1givenF1F4∎

If $t > N / 2$ , each of at most nine rounds measures the freshly prepared uniform quantum address. Handling these returned $n$ -bit addresses and writing the result takes $O (n)$ classical bit operations in total; the state preparation and measurements are separate quantum operations, and no classical fair address bits are generated. For $n = 0$ , $N = t = 1$ and the bookkeeping is constant. The bit-query invocations remain separately charged by [F4].

PropositionStatement: Literature-sourcedProof: AI-generatedOpen item page →

Gate and reflection accounting for randomized known-count search

Statement

Each uniform-state preparation uses exactly $n$ Hadamard gates. Write $R_{0} = 2 ∣ 0^{n} ⟩ ⟨ 0^{n} ∣ - I$ and let $C (R_{0})$ be its declared gate cost if implemented or supplied as a named reflection. Conjugation gives $R_{s} = H^{\otimes n} R_{0} H^{\otimes n}$ , so an iterate uses $2 n$ Hadamards, cost $C (R_{0})$ , and one bit-oracle query. For the $0 < t \leq N / 2$ branch, the total nonoracle gate cost is at most $9 [n + 2 + (K - 1) (2 n + C (R_{0}))], K = ⌈ \sqrt{N / t} ⌉,$ up to measurement and output handling. For $t > N / 2$ it is at most $9 n$ Hadamards plus measurement/output handling. The reflection is not a free oracle.

Facts & Assumptions

Given: The nine-round known-count algorithm, the exact one-qubit gate alphabet, and the declared circuit resource model.

[F1]

Known-count search by randomized Grover iteration: each accepted randomized round prepares a fresh uniform state, uses at most $K - 1$ iterates when $t \leq N / 2$ , and the direct branch uses only uniform preparation before verification.

[F2]

Exact one-qubit gates and rotations: $H$ is the exact Hadamard matrix with $H ∣ 0 ⟩ = (∣ 0 ⟩ + ∣ 1 ⟩) / \sqrt{2}$ and $H^{2} = I$ .

[F3]

Orthogonal-Projector Reflection and Access Contract: a prepared-state reflection is $U R_{0} U^{†}$ , and its cost includes the preparation, reflection, and inverse preparation unless a different declared primitive is supplied.

[F4]

Projector Reflections Are Hermitian Unitary Involutions: both reflection signs are unitary involutions with the declared signs.

[F5]

Finite circuit resource accounting: gate occurrences, queries, and classical bit operations are separate resource coordinates.

[F6]

Circuit-family and computation cost model: a cost record keeps gate and query coordinates separate and assigns no zero cost to an unspecified oracle or controlled access.

Proof

1.1givenF1F2F5

Applying $H$ to each of the $n$ address wires sends $∣ 0^{n} ⟩$ to $2^{- n / 2} \sum_{x} ∣ x ⟩ = ∣ s ⟩$ by the tensor-product action, using exactly $n$ occurrences of $H$ by [F2] and [F5]. The $n = 0$ case has no such occurrences.

2.1step 1.1F2F3F4F6algebra

Since $H^{\otimes n} ∣ 0^{n} ⟩ = ∣ s ⟩$ and $(H^{\otimes n})^{†} = H^{\otimes n}$ , conjugating $R_{0}$ gives $H^{\otimes n} R_{0} H^{\otimes n} = 2 ∣ s ⟩ ⟨ s ∣ - I = R_{s}$ . This costs $2 n$ Hadamards plus the declared $C (R_{0})$ ; [F3]–[F4] do not make the all-zero reflection free.

3.1givenF1step 1.1step 2.1F5F6algebra

In the $t \leq N / 2$ branch each round has at most one fresh preparation, two gates $X, H$ for the response qubit, and at most $K - 1$ iterates. Each iterate has the nonoracle cost in step 2.1; its query is excluded from this gate total by [F5]–[F6]. Multiplying the per-round bound by nine gives the stated upper bound, including rejected rounds as zero-cost cases.

4.1givenF1step 1.1F5F6∎

When $t > N / 2$ , each of at most nine direct rounds only prepares $∣ s ⟩$ and measures/verifies, so there are at most $9 n$ Hadamards and no diffusion reflection. The t=0 branch returns before preparation.

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

Constant BBHT stage success beyond the threshold scale

Statement

Let $0 < a = t / N < 3 / 4$ , $θ = \arcsin \sqrt{a}$ , and let $J$ be uniform on ${1, \dots, M}$ . If the positive integer $M$ satisfies $M \geq 4 / \sqrt{a}$ , then $E [\sin^{2} ((2 J + 1) θ)] \geq \frac{3}{8} .$

Facts & Assumptions

Given: $0 < a < 3 / 4$ , $\sin θ = \sqrt{a}$ , $θ \in (0, π / 2)$ , and an integer $M \geq 4 / \sqrt{a}$ .

[F1]

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

[F3]

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

[F4]

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

[F5]

Principal inverse sine and inverse cosine and Signs, monotonicity intervals, and ranges of sine and cosine: the principal angle is in $[- π / 2, π / 2]$ , sine is strictly increasing there, and cosine is positive on $(0, π / 2)$ .

[F6]

Parity and the Pythagorean identity for sine and cosine: $\sin^{2} θ + \cos^{2} θ = 1$ .

[F7]

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

[F8]

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

[F9]

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

[F10]

Squaring is monotone on the nonnegatives: square roots preserve order on nonnegative reals.

Proof

1.1givenF4F5F6F7F8F9F10algebra

Since $0 < a < 3 / 4$ , [F7] and [F10] give $0 < \sqrt{a} < 1$ . From [F4], $\sin θ = \sqrt{a}$ and $θ \in [- π / 2, π / 2]$ . By [F8], $\sin 0 = 0$ , so strict increase [F5] gives $θ > 0$ . Since $\sin (π / 2) = 1$ by [F9], strict increase and $\sin θ < 1$ give $θ < π / 2$ ; then $\cos θ > 0$ by [F5]. The Pythagorean identity [F6] gives $\cos θ = \sqrt{1 - a}$ .

1.2givenF1F4algebra

By [F1] and [F4], the average equals $\frac{1}{2} - \frac{1}{2 M} \sum_{j = 1}^{M} \cos ((4 j + 2) θ)$ .

2.1step 1.2F3algebra

By [F3], for every $j$ , $2 \sin (2 θ) \cos ((4 j + 2) θ) = \sin ((4 j + 4) θ) - \sin (4 j θ)$ . Summing from $j = 1$ to $M$ and using $\sin u - \sin v = 2 \sin ((u - v) / 2) \cos ((u + v) / 2)$ gives $\sum_{j = 1}^{M} \cos ((4 j + 2) θ) = \sin (2 M θ) \cos ((2 M + 4) θ) / \sin (2 θ)$ . Thus the average in step 1.2 is $\frac{1}{2} - \frac{\sin (2 M θ) \cos ((2 M + 4) θ)}{2 M \sin (2 θ)}$ .

3.1givenstep 1.1step 2.1F4F5F6F7F10algebra∎

Since $a < 3 / 4$ , $1 - a > 1 / 4$ , so [F10] gives $\sqrt{1 - a} > 1 / 2$ . Steps 1.1 and [F4]–[F7] then give $\sin (2 θ) = 2 \sqrt{a} \sqrt{1 - a} > \sqrt{a}$ . Therefore $M \sin (2 θ) > 4$ and the absolute value of the correction in step 2.1 is less than $1 / 8$ . The average is greater than $3 / 8$ , hence at least $3 / 8$ .

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

Unknown-count search halts almost surely when a marked item exists

Statement

For $t > 0$ , the BBHT algorithm halts with probability $1$ and returns an element of $M$ ; the probability it has not returned a marked item after $r$ rounds tends to zero. For $t = 0$ , it never halts and never outputs an element.

Facts & Assumptions

Given: The BBHT algorithm with fresh randomness and a fresh quantum register in every round.

[F1]

BBHT search when the marked count is unknown: each round directly tests a uniform candidate, then uses $j$ uniformly distributed on ${1, \dots, M_{ℓ}}$ , measures, verifies with a bit query, and continues after failure.

[F2]

Finite marked-item search and its bit oracle: when $t = 0$ , the marked set $M$ is empty; when $t > 0$ , a successful output is a verified element of $M$ .

[F3]

Constant BBHT stage success beyond the threshold scale: for $0 < a < 3 / 4$ , every round with $M_{ℓ} \geq 4 / \sqrt{a}$ has conditional quantum-search success at least $3 / 8$ .

Proof

1.1givenF1F2

If $t = 0$ , then $M = \emptyset$ by [F2]. Every directly sampled and every quantum-measured candidate is therefore unmarked, and [F1] verifies each before returning. Thus no round returns and the loop does not halt.

1.2givenF1F2algebra

Suppose $t > 0$ and write $a = t / N$ . If $a \geq 3 / 4$ , the initial uniform sample in every round is marked with probability $a \geq 3 / 4$ . Fresh independent samples imply failure through $r$ rounds is at most $(1 / 4)^{r}$ , which tends to zero.

1.3givenF1F3algebra

If $0 < a < 3 / 4$ , the schedule $M_{ℓ} = ⌈ (3 / 2)^{ℓ} ⌉$ tends to infinity, so some finite $L$ satisfies $M_{L} \geq 4 / \sqrt{a}$ . From round $L$ onward, conditional on reaching that round and on the direct sample having failed, [F3] gives quantum-search success at least $3 / 8$ ; fresh random labels and registers make this conditional law independent of the direct sample. Thus a round succeeds with probability at least $a + (1 - a) (3 / 8) \geq 3 / 8$ . Fresh rounds then give failure through round $r \geq L$ at most $(5 / 8)^{r - L + 1}$ .

2.1step 1.1step 1.2step 1.3F1F2algebra∎

The verification query returns the actual value $f (x)$ , so any returned address is marked by [F1]–[F2]. The bounds in steps 1.2 and 1.3 tend to zero; therefore the algorithm returns a marked element with probability $1$ whenever $t > 0$ .

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

Integer rounding gives a high-success Grover iterate

Statement

Put $a = t / N$ and $θ = \arcsin \sqrt{a}$ . If $0 < a \leq 1 / 2$ , some integer $k$ with $0 \leq k \leq K = ⌈ 1 / \sqrt{a} ⌉$ has $p_{k} = \sin^{2} ((2 k + 1) θ) \geq 1 - a .$ If $1 / 2 < a \leq 1$ , $k = 0$ lies in this range and $p_{0} = a > 1 / 2$ . The real-valued optimizer $k_{*} = π / (4 θ) - 1 / 2$ is not in general an integer.

Facts & Assumptions

Given: $N = 2^{n}$ , exact $t$ with $1 \leq t \leq N$ , $a = t / N$ , and $θ = \arcsin \sqrt{a}$ .

[F1]

Exact success probability after an integer number of Grover iterates: for $0 < t < N$ and each integer $k \geq 0$ , $p_{k} = \sin^{2} ((2 k + 1) θ)$ . For $t = N$ , every integer iteration count has marked probability $1$ .

[F2]

Principal inverse sine and inverse cosine: $\sin (\arcsin x) = x$ and $\arcsin x \in [- π / 2, π / 2]$ .

[F3]

Signs, monotonicity intervals, and ranges of sine and cosine: sine is strictly increasing on $[- π / 2, π / 2]$ , and cosine is strictly decreasing on $[0, π]$ .

[F4]

Sine and cosine are $1$ -Lipschitz on $R$ : $∣ \sin u - \sin v ∣ \leq ∣ u - v ∣$ .

[F5]

Quarter-turn values and shifts by pi/2 and pi: $\sin (π / 2) = 1$ and the sine/cosine shift identities by $π / 2$ hold.

[F7]

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

[F8]

Parity and the Pythagorean identity for sine and cosine: sine is odd and $\sin^{2} x + \cos^{2} x = 1$ .

[F9]

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

[F10]

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

[F11]

Pi as twice the smallest positive zero of cosine and Cosine has a smallest positive zero, lying strictly between zero and two: $π = 2 γ$ with $0 < γ < 2$ , so $0 < π < 4$ .

[F12]

Ceilings give the least positive integer meeting a real threshold: $K = ⌈ 1 / \sqrt{a} ⌉$ is an integer at least $1 / \sqrt{a}$ .

[F13]

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

[F14]

Squaring is monotone on the nonnegatives: nonnegative square roots preserve order.

Proof

1.1givenF2F3F4F5F7F8F9F11F13F14algebra

Suppose $0 < a \leq 1 / 2$ . Put $x = π / 4$ , $s = \sin x$ , and $c = \cos x$ . By [F11], $0 < π < 4$ , so $0 < x < π / 2$ ; [F3] gives $s > 0$ , and its cosine monotonicity together with [F5] gives $c > \cos (π / 2) = 0$ . The double-angle identity [F7] and quarter-turn value [F5] give $2 s c = \sin (2 x) = \sin (π / 2) = 1$ , while [F8] gives $s^{2} + c^{2} = 1$ . Thus $(s - c)^{2} = s^{2} + c^{2} - 2 s c = 0$ , so $s = c$ ; hence $2 s^{2} = 1$ and $s = 1 / \sqrt{2}$ by [F9]. Since $a \leq 1 / 2$ , [F14] gives $\sqrt{a} \leq 1 / \sqrt{2} = s$ , and strict increase in [F3] implies $θ \leq π / 4$ . Also $\sin θ = \sqrt{a} > 0 = \sin 0$ , and $θ \in [- π / 2, π / 2]$ by [F2], so strict increase [F3] gives $θ > 0$ . The Lipschitz estimate [F4] then yields $\sqrt{a} = ∣ \sin θ - \sin 0 ∣ \leq ∣ θ ∣ = θ$ .

2.1step 1.1F2F3F10constructalgebra

Put $k_{*} = π / (4 θ) - 1 / 2$ . Since $θ \leq π / 4$ , $k_{*} \geq 1 / 2$ . Let $m = ⌊ k_{*} ⌋$ and choose $k = m$ if $k_{*} - m \leq 1 / 2$ , otherwise choose $k = m + 1$ . By [F10], $k$ is a nonnegative integer and $∣ k - k_{*} ∣ \leq 1 / 2$ . For $a = 1 / 2$ , the value of $\sin (π / 4)$ from step 1.1 and injectivity in [F3] give $θ = π / 4$ , hence $k_{*} = 1 / 2$ , exhibiting a noninteger optimizer.

3.1step 1.1step 2.1F11F12algebra

The choice in step 2.1 gives $k \leq k_{*} + 1 / 2 = π / (4 θ) \leq π / (4 \sqrt{a}) < 1 / \sqrt{a} \leq K$ , using [F11]–[F12].

3.2F1step 1.1step 2.1F2F3F5F8F11algebra

By the definition of $k_{*}$ , $(2 k_{*} + 1) θ = π / 2$ . Therefore $1 - p_{k} = \cos^{2} ((2 k + 1) θ) = \sin^{2} (2 (k - k_{*}) θ)$ . The angle magnitude is at most $θ \leq π / 4$ by step 2.1. Oddness and monotonicity of sine imply $∣ \sin (2 (k - k_{*}) θ) ∣ \leq \sin θ$ ; hence $1 - p_{k} \leq \sin^{2} θ = a$ and $p_{k} \geq 1 - a$ .

4.1givenF1F2F9F12algebra∎

If $1 / 2 < a < 1$ , then $K \geq 1$ and $k = 0$ is in the candidate range; [F1] and [F2] give $p_{0} = \sin^{2} θ = a > 1 / 2$ . If $a = 1$ , then $K = 1$ by [F12] and [F9], and the endpoint clause of [F1] gives $p_{0} = 1 = a > 1 / 2$ .

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

Average Grover success for a uniform integer iteration count

Statement

For $0 < t \leq N / 2$ , put $a = t / N$ , $θ = \arcsin \sqrt{a}$ , and $K = ⌈ 1 / \sqrt{a} ⌉$ . If $J$ is uniform on ${0, \dots, K - 1}$ , then $E [\sin^{2} ((2 J + 1) θ)] = \frac{1}{2} - \frac{\sin (4 K θ)}{4 K \sin (2 θ)} \geq \frac{1}{4} .$

Facts & Assumptions

Given: $0 < a \leq 1 / 2$ , $θ = \arcsin \sqrt{a}$ , and $K = ⌈ 1 / \sqrt{a} ⌉$ .

[F1]

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

[F2]

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

[F3]

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

[F4]

Principal inverse sine and inverse cosine: $θ \in [- π / 2, π / 2]$ and $\sin θ = \sqrt{a}$ .

[F5]

Parity and the Pythagorean identity for sine and cosine: $\sin^{2} θ + \cos^{2} θ = 1$ .

[F6]

Ceilings give the least positive integer meeting a real threshold: $K \geq 1 / \sqrt{a}$ .

[F7]

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

[F8]

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

[F9]

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

[F10]

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

[F11]

Squaring is monotone on the nonnegatives: square roots preserve order on nonnegative reals.

Proof

1.1givenF4F5F7F8F9F10F11algebra

Since $0 < a \leq 1 / 2$ , [F7] gives a nonnegative root and [F11] gives $0 < \sqrt{a} < 1$ . By [F4], $\sin θ = \sqrt{a}$ . Since $\sin 0 = 0$ by [F8] and sine is strictly increasing by [F10], $θ > 0$ . Also $\sin (π / 2) = 1$ by [F9], so strict increase and $\sin θ < 1$ give $θ < π / 2$ ; hence $\cos θ > 0$ by [F10]. The Pythagorean identity [F5] gives $\cos θ = \sqrt{1 - a}$ .

1.2givenF1F3algebra

Using [F1] and the identity $\sin^{2} x = (1 - \cos 2 x) / 2$ from [F3], the average is $\frac{1}{2} - \frac{1}{2 K} \sum_{j = 0}^{K - 1} \cos ((4 j + 2) θ)$ .

2.1step 1.2F2algebra

For each $j$ , [F2] gives $2 \sin (2 θ) \cos ((4 j + 2) θ) = \sin ((4 j + 4) θ) - \sin (4 j θ)$ . Summing from $j = 0$ to $K - 1$ telescopes to $\sum_{j = 0}^{K - 1} \cos ((4 j + 2) θ) = \sin (4 K θ) / (2 \sin (2 θ))$ . Substitution in step 1.2 proves the displayed identity.

3.1step 1.1step 2.1F3F6F7F11algebra∎

Since $1 - a \geq 1 / 2$ , [F11] gives $\sqrt{1 - a} \geq 1 / \sqrt{2}$ . By [F3] and step 1.1, $\sin (2 θ) = 2 \sqrt{a} \sqrt{1 - a} \geq \sqrt{2 a}$ . Hence $K \sin (2 θ) \geq \sqrt{2}$ by [F6]. The absolute value of the correction term in step 2.1 is at most $1 / (4 \sqrt{2}) < 1 / 4$ , so the average is at least $1 / 4$ .

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

Expected bit-query cost of unknown-count BBHT search

Statement

For $t > 0$ , the BBHT algorithm has expected standard bit-query cost $O (\sqrt{N / t})$ . The bound includes the direct membership test and a separate verification query in each attempted round, plus one query per Grover iterate through phase kickback. If $t = 0$ , it never halts and the expected query cost from finite execution prefixes is infinite.

Facts & Assumptions

Given: The BBHT algorithm with $c = 3 / 2$ , the expected-query definition, and $t > 0$ .

[F1]

BBHT search when the marked count is unknown: stage $ℓ$ uses $M_{ℓ} = ⌈ (3 / 2)^{ℓ} ⌉$ , one direct sample query, at most $M_{ℓ}$ iterate queries, and one verification query.

[F2]

Constant BBHT stage success beyond the threshold scale: when $0 < a = t / N < 3 / 4$ and $M_{ℓ} \geq 4 / \sqrt{a}$ , conditional stage success is at least $3 / 8$ .

[F3]

Unknown-count search halts almost surely when a marked item exists: for $t > 0$ the algorithm returns a verified marked element almost surely.

[F4]

One Grover iterate uses one standard bit query: every Grover iterate uses one standard bit query.

[F5]

Expected query cost from finite execution prefixes: expected cost is the supremum of expected query counts over finite execution prefixes; no infinite-history measure is assumed.

[F6]

Ceilings give the least positive integer meeting a real threshold and Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ : ceilings are least integer upper bounds and $\sqrt{a}$ is the nonnegative root.

[F7]

Squaring is monotone on the nonnegatives: for $0 < a \leq 1$ , $1 \leq 1 / \sqrt{a}$ .

[F8]

Quantum query complexity: query calls are a separate resource coordinate from gates and classical bit operations.

Proof

1.1givenF1F4F6algebra

In a round with stage size $M_{ℓ}$ , there is one direct test, at most $M_{ℓ}$ iterate queries by [F4], and one candidate verification. Thus the round makes at most $M_{ℓ} + 2 \leq (3 / 2)^{ℓ} + 3$ bit queries.

1.2givenF1F2F6F7algebra

Now let $0 < a < 3 / 4$ and let $L$ be the first stage with $M_{L} \geq 4 / \sqrt{a}$ , which exists because $(3 / 2)^{ℓ} \to \infty$ . Minimality gives $(3 / 2)^{L - 1} < 4 / \sqrt{a}$ and $M_{L} \leq (3 / 2)^{L} + 1 < 6 / \sqrt{a} + 1 \leq 7 / \sqrt{a} .$ Also $(3 / 2)^{m} \geq 1 + m / 2$ by induction, so the threshold is reached by $m = ⌈ 8 / \sqrt{a} ⌉$ ; thus $L = O (1 / \sqrt{a})$ . The absorptions of the additive constants use [F7].

2.1step 1.1F1F5F7algebra

First suppose $a \geq 3 / 4$ . Each round succeeds at least on its direct uniform sample, with probability at least $3 / 4$ by [F1]. The probability of reaching round $ℓ$ is at most $(1 / 4)^{ℓ - 1}$ . Hence the expected total query count over any finite number of rounds is bounded by $\sum_{ℓ \geq 1} (1 / 4)^{ℓ - 1} ((3 / 2)^{ℓ} + 3),$ a convergent geometric series because $(3 / 2) / 4 = 3 / 8 < 1$ . It is an absolute constant, hence $O (1 / \sqrt{a})$ by [F7].

2.2step 1.1step 1.2algebra

Before stage $L$ , bound every reach probability by $1$ . The geometric sum of $(3 / 2)^{ℓ}$ over $ℓ < L$ is at most $3 (3 / 2)^{L - 1} < 12 / \sqrt{a}$ , while the additive $3$ per round contributes $3 (L - 1) = O (1 / \sqrt{a})$ by step 1.2. Thus the early-stage expected query count is $O (1 / \sqrt{a})$ .

2.3step 1.1step 1.2F2F5F7algebra

At every stage $ℓ \geq L$ , [F2] bounds the conditional failure probability by $5 / 8$ . Therefore the probability of reaching $L + k$ is at most $(5 / 8)^{k}$ . Since $M_{L + k} \leq (3 / 2)^{k} M_{L} + 1,$ the tail expected query count is at most $\sum_{k \geq 0} (5 / 8)^{k} ((3 / 2)^{k} M_{L} + 3),$ which is $16 M_{L} + 8 = O (1 / \sqrt{a})$ because $(5 / 8) (3 / 2) = 15 / 16 < 1$ , $M_{L} \leq 7 / \sqrt{a}$ by step 1.2, and $8 = O (1 / \sqrt{a})$ by [F7].

3.1step 1.1step 1.2step 2.1step 2.2step 2.3F1F3F5F6F7F8algebra∎

Any finite $M$ -step execution prefix can begin at most $M$ rounds because each attempted round starts with a direct sample query; if the prefix ends inside a round, its query count is bounded by that completed round's bound in step 1.1. Summing the reach-probability-weighted round bounds through the prefix is therefore at most the full sums in steps 1.2 and 2.2–2.3, uniformly in $M$ . The supremum over finite prefixes in [F5] is bounded by those convergent geometric sums. [F3] gives almost-sure termination for $t > 0$ ; the expected bound is for bit queries only, with other coordinates separate by [F8]. Since $1 / \sqrt{a} = \sqrt{N / t}$ , the expected bit-query cost is $O (\sqrt{N / t})$ . If $t = 0$ , every round issues a direct sample query and continues, so a finite prefix after $R$ completed rounds has expected query count at least $R$ ; the supremum is infinite.

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

Success guarantee and boundary behavior of known-count Grover search

Statement

For exact known count $t > 0$ , the procedure Known-count Grover search by exact integer maximization outputs a marked item with probability at least $\max {t / N, 1 - t / N}$ . It returns none with certainty when $t = 0$ and returns a marked item with certainty when $t = N$ .

Facts & Assumptions

Given: $N = 2^{n}$ , a marked set $M$ , and exact count $t = ∣ M ∣$ supplied to the algorithm.

[F1]

Known-count Grover search by exact integer maximization: if $t = 0$ it returns none; otherwise it chooses the least maximizer of the rational values $r_{k} = (1 - T_{2 k + 1} (q)) / 2$ over $0 \leq k \leq K = ⌈ \sqrt{N / t} ⌉$ , where $q = 1 - 2 t / N$ . It applies that many Grover iterates, measures an address, and verifies it with the exact bit oracle for $f = 1_{M}$ .

[F2]

Exact success probability after an integer number of Grover iterates: for $0 < t < N$ and $θ = \arcsin \sqrt{t / N}$ , after $k$ iterates the marked probability is $p_{k} = \sin^{2} ((2 k + 1) θ)$ . For $t = 0, N$ it is respectively $0, 1$ for every integer $k \geq 0$ .

[F3]

Integer rounding gives a high-success Grover iterate: for $0 < t / N \leq 1 / 2$ , an integer $k \leq K$ has $p_{k} \geq 1 - t / N$ ; for $t / N > 1 / 2$ , $k = 0$ has $p_{0} = t / N$ .

[F4]

Bit cost of exact known-count iteration selection: exact selection computes $T_{0} = 1$ , $T_{1} = q$ , $T_{m + 1} = 2 q T_{m} - T_{m - 1}$ through $2 K + 1$ and compares the finite rational list $(1 - T_{2 k + 1} (q)) / 2$ .

[F5]

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

[F6]

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

[F7]

Parity and the Pythagorean identity for sine and cosine: cosine is even and sine is odd.

[F8]

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

[F9]

Principal inverse sine and inverse cosine: $\sin (\arcsin y) = y$ for $y \in [- 1, 1]$ .

[F10]

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

Proof

1.1givenF1F2

If $t = 0$ , [F1] returns none. If $t = N$ , [F2] gives marked probability one for every integer iteration count, and the exact verification in [F1] accepts every address. Thus the two endpoint claims hold.

1.2givenF1F2F4F5F6F7F8F9F10inductionalgebra

For $0 < t < N$ , put $a = t / N$ and $θ = \arcsin \sqrt{a}$ . By [F9]–[F10], $\sin^{2} θ = a$ , so [F5] gives $q = 1 - 2 a = \cos (2 θ)$ . The recurrence in [F4] starts with $T_{0} = \cos 0 = 1$ and $T_{1} = \cos (2 θ)$ by [F8]. Expanding cosine at $2 m θ \pm 2 θ$ using [F6]–[F7] gives $\cos (2 (m + 1) θ) + \cos (2 (m - 1) θ) = 2 \cos (2 θ) \cos (2 m θ)$ . Induction in that recurrence therefore gives $T_{m} (q) = \cos (2 m θ)$ at every computed index. Consequently $r_{k} = (1 - \cos ((4 k + 2) θ)) / 2 = \sin^{2} ((2 k + 1) θ) = p_{k}$ for every candidate $0 \leq k \leq K$ , by [F5] and [F2].

2.1givenF1F3step 1.2algebra

If $0 < a \leq 1 / 2$ , the witness $k \leq K$ from [F3] belongs to the algorithm's finite candidate list and has $p_{k} \geq 1 - a$ . Step 1.2 identifies each rational candidate value with its actual marked probability, so the selected maximizer has success at least $1 - a = \max {a, 1 - a}$ . Exact verification accepts every marked measurement by [F1].

3.1givenF1F3step 1.1step 1.2algebra∎

If $1 / 2 < a < 1$ , the candidate $k = 0$ in [F3] has success $a > 1 / 2$ . Step 1.2 identifies the maximized list with actual marked probabilities, so the selected iterate succeeds with probability at least $a = \max {a, 1 - a}$ . Exact verification again accepts every marked measurement by [F1]. Together with step 1.1, this proves every branch of the guarantee.

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

Nine-round randomized known-count search succeeds with probability at least two-thirds

Statement

For every exact known count $t > 0$ , the randomized known-count procedure returns a marked item with probability at least $2 / 3$ . If $0 < t \leq N / 2$ , each round succeeds with probability at least $1 / 8$ and nine-round failure is at most $(7 / 8)^{9} < 1 / 3$ . If $t > N / 2$ , each direct-sampling round succeeds with probability greater than $1 / 2$ , so nine-round failure is less than $1 / 512$ . For $t = 0$ the procedure returns none exactly.

Facts & Assumptions

Given: The nine-round algorithm with its exact $K$ , rejection sampling, and candidate verification.

[F1]

Known-count search by randomized Grover iteration: for $0 < t \leq N / 2$ , each round draws $b$ fair bits, accepts $j < K$ , applies $j$ Grover iterates, and verifies the measured candidate; for $t > N / 2$ it makes a direct uniform sample; for $t = 0$ it returns none.

[F2]

Average Grover success for a uniform integer iteration count: conditional on a uniform $J \in {0, \dots, K - 1}$ , average Grover success is at least $1 / 4$ .

Proof

1.1givenF1algebra

If $0 < t \leq N / 2$ , the algorithm's accepted labels are exactly $0, \dots, K - 1$ . If $K = 1$ , then $b = 0$ and acceptance has probability $1$ . If $K > 1$ , minimality of $b$ gives $2^{b - 1} < K \leq 2^{b}$ , so acceptance probability $K / 2^{b} > 1 / 2$ and, conditional on acceptance, each accepted $j$ is equally likely.

2.1step 1.1F1F2algebra

By [F2], an accepted round succeeds with probability at least $1 / 4$ . Multiplying by the acceptance probability gives per-round success at least $1 / 8$ . Fresh random bits, registers, and measurements make the nine rounds independent conditional on the fixed oracle, so total failure is at most $(7 / 8)^{9}$ . Since $3 \cdot 7^{9} = 121060821 < 134217728 = 8^{9}$ , this is less than $1 / 3$ .

3.1givenF1algebra∎

If $t > N / 2$ , a uniform address is marked with probability $t / N > 1 / 2$ . Nine fresh direct samples therefore fail with probability $(1 - t / N)^{9} < (1 / 2)^{9} = 1 / 512 < 1 / 3$ . If $t = 0$ , the algorithm's explicit branch returns none. Every returned item in the other branches is verified by a standard bit query, so no unmarked item is returned.

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

Known-count Grover search uses O of the square root of N over t bit queries

Statement

For $0 < t \leq N$ , the exact known-count procedure uses $O (\sqrt{N / t})$ standard bit queries: one query for each Grover iterate and at most one separate verification query. If $t = 0$ and the exact count is supplied, it returns none with no query. This is only a query bound; exact classical maximization can cost exponentially many bit operations in $n$ .

Facts & Assumptions

Given: The exact known-count algorithm and the worst-case quantum query-cost convention.

[F1]

Known-count Grover search by exact integer maximization: if $t = 0$ , the algorithm returns none without a query. If $t > 0$ , it computes the recurrence and every candidate value for $0 \leq k \leq K = ⌈ \sqrt{N / t} ⌉$ , chooses the least maximizer, applies $k$ iterates, then makes one verification query.

[F2]

One Grover iterate uses one standard bit query: each iterate uses exactly one standard bit query.

[F3]

Quantum query complexity: query cost counts the designated oracle invocations, separately from gates and classical work.

[F4]

Success guarantee and boundary behavior of known-count Grover search: the finite maximization has the stated success guarantee and the $t = 0$ branch returns none.

[F5]

Ceilings give the least positive integer meeting a real threshold and Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ : $K = ⌈ \sqrt{N / t} ⌉ \leq \sqrt{N / t} + 1$ and $\sqrt{N / t} \geq 1$ .

[F6]

Squaring is monotone on the nonnegatives: since $N / t \geq 1$ , its nonnegative square root is at least $1$ .

Proof

1.1F1F2

For $t > 0$ , [F1] uses at most $K$ iterates; by [F2] they contribute at most $K$ bit queries, and the separate verification contributes at most one.

2.1step 1.1F1F3F5F6algebra

By [F5]–[F6], $K + 1 \leq \sqrt{N / t} + 2 \leq 3 \sqrt{N / t}$ . This is the claimed worst-case query bound; no nonoracle gate or classical preprocessing cost is included by [F3]. For $t = 1$ , [F1] explicitly computes $K + 1 \geq \sqrt{N} = 2^{n / 2}$ candidate values, so its classical work can be exponential in $n$ .

3.1givenF1F3F4∎

For $t = 0$ , [F4] gives the correct output none, and the explicit early return in [F1] executes it without any oracle invocation. Thus its query cost is zero by [F3].

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

Query cost of randomized known-count Grover search

Statement

For $0 < t \leq N / 2$ , the nine-round randomized known-count procedure uses at most $9 K = O (\sqrt{N / t})$ standard bit queries, where $K = ⌈ \sqrt{N / t} ⌉$ ; rejected rounds use no oracle query and each accepted round uses $j \leq K - 1$ iterate queries plus one verification query. For $t > N / 2$ it uses at most nine queries, and for $t = 0$ it uses none. This is a query count only, not a gate or classical preprocessing bound.

Facts & Assumptions

Given: The randomized known-count algorithm, exact $K$ , and worst-case quantum query convention.

[F1]

Known-count search by randomized Grover iteration: there are nine rounds; rejected labels use no query, accepted labels use $j < K$ iterates and one verification, the direct branch makes one query per round, and $t = 0$ returns none.

[F2]

Quantum query complexity: query cost counts oracle calls and excludes gates and classical work.

[F3]

One Grover iterate uses one standard bit query: one Grover iterate uses one bit query.

[F4]

[F5]

Squaring is monotone on the nonnegatives: since $N / t \geq 1$ , its nonnegative square root is at least $1$ .

Proof

1.1givenF1F3

In the branch $0 < t \leq N / 2$ , an accepted round uses at most $K - 1$ iterate queries by [F3] and one verification query by [F1], hence at most $K$ queries; rejected rounds use zero. Nine rounds use at most $9 K$ .

2.1step 1.1F1F2F4F5algebra∎

Since $\sqrt{N / t} \geq 1$ by [F5], [F4] gives $K \leq 2 \sqrt{N / t}$ , so $9 K = O (\sqrt{N / t})$ . In the direct branch there are at most nine queries, and for $t = 0$ none; [F2] keeps these counts separate from gates and classical work.

5 · Examples, counterexamples and false statements

None yet.