Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-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 upper-bound query cost

Statement

For every N≥1, Fixed-one Grover search with candidate verification uses at most 32N standard bit queries, including the final candidate verification. Hence its query cost is O(N). Address comparison, reversible computation, recurrence evaluation, state preparation, reflection gates, and all other nonoracle work are separate costs; no polynomial-time claim is made.

Facts & Assumptions

Given: The fixed-one algorithm, the Grover-iterate query count, exact zero-completion simulation, and the worst-case query-cost convention.

[F1]

Fixed-one Grover search with candidate verification: the chosen iteration count satisfies k≤K=⌈M⌉, and one verification query is made.

[F2]

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

[F3]

Zero-completed query simulation is exact and uses one raw query: each padded bit query, including verification, uses exactly one raw standard bit query.

[F4]

Quantum query complexity: the query coordinate counts designated oracle invocations and excludes gates and classical work.

[F5]

Fixed-one Grover search with candidate verification: the padded domain size obeys N≤M<2N.

Proof

1.1F1F2F3

The procedure of [F1] makes k Grover iterates and one verification. By [F2] each iterate needs one padded bit query, and [F3] replaces every one of those calls and the verification with exactly one raw query. Therefore the total raw query count is at most K+1.

2.1F4F5step 1.1algebra∎

Since K=⌈M⌉≤M+1, we have K+1≤M+2≤3M because M≥1. By [F5], 3M<32N. Thus the worst-case standard bit-query cost is at most 32N by [F4]. None of the reversible address tests, classical recurrence steps, or gates were counted as oracle invocations, so this estimate makes no claim about their cost.

Depends on

Used by

Dependency tree · two levels

21 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