Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Coherent query-to-circuit cost translation

Statement

For a QA29 execution, group its complete value-rotated sampler preparations into the distinct supplied unitaries Aj, and let Nj be the number of fresh standalone preparations of Aj and Qj the number of controlled Grover rounds using it. Also let Vt range over the supplied unrotated sampler preparations used for coarse measurements, with Nt0 such fresh preparations. If each controlled Grover round for Aj is the explicit product of one controlled Aj call, one controlled Aj† call, one controlled initial-state reflection, one controlled good-state reflection, and its control phase, then the exact primitive-call cost is ∑jNjCAj,prep+∑tNt0CVt,prep+∑jQj(CAj,c+CAj†,c+CS0,j,c+CSgood,j,c+Cphase,j), where every C is the declared cost of that operation. The preparation counts exclude the controlled Aj and Aj† occurrences inside Grover rounds, which are already included in the Qj terms. With a single Aq, no unrotated coarse preparations, and Nprep=Nq, this reduces to the homogeneous formula NprepCAq,prep+Q(CAq,c+CAq†,c+CS0,c+CSgood,c+Cphase). Value decoding, band comparisons, reversible arithmetic, controlled rotations, uncomputation, phase estimation, ancilla workspace, circuit description, and classical output/median computations add their own declared gate, width, bit, or oracle costs. If a complete reflection is instead supplied as a named oracle, charge that oracle's declared cost separately and do not also expand it into its components. No bare query bound becomes a gate bound without these implementations.

Facts & Assumptions

Given: The finite circuit and access model for Coherent finite sampler and observable value, the QA29 bounded-mean and variance-aware procedures, and the cost coordinates in Circuit-family and computation cost model.

[F1]

Coherent finite sampler and observable value requires explicit forward, inverse, controlled, data, value, rotation, and reflection access.

[F2]

Controlled Unitary Access: controlled access is a separately declared operation and does not follow from ordinary access.

[F3]

Inverse Unitary Access: inverse access and its charge are recorded separately from forward access.

[F4]

Circuit-family and computation cost model keeps named queries, ordinary gates, circuit description, width, ancillas, precision, and classical computation as separate coordinates.

[F5]

QFT-based amplitude estimation and Amplitude estimation and counting input/output contract specify the Grover-iterate factors and separately declared controlled accesses. Quantum bounded-expectation guarantee and query cost counts the exact median rounds for bounded expectation in repeated controlled-Q access; Variance-aware quantum Monte Carlo guarantee counts copies in either mode and state-reflection uses in repeated access. Their supplied controlled-power alternatives retain separate declared prices.

Proof

1.1givenF1F2F3F5algebra

For each Aj, [F1]–[F3] show that one controlled Grover round contains exactly its five declared components. Repeating that product Qj times contributes Qj calls to each corresponding component cost. The standalone preparations contribute ∑jNjCAj,prep, and the separate coarse sampler preparations contribute ∑tNt0CVt,prep. Summing these disjoint operation occurrences gives the displayed exact primitive-call cost.

1.2givenF1F4algebra

The remaining classical and quantum operations form finite subcircuits appended to or interleaved with those rounds. By [F4], their gate, width, ancilla, bit, and description costs are added in the corresponding coordinates, not absorbed into a unit-cost query. If the full reflection is a supplied oracle, the declared alternative counts that one oracle call rather than both implementations.

2.1givenF4F5step 1.1step 1.2∎

Under the Statement’s explicit component-product hypothesis, applying the same occurrence-by-occurrence accounting to the repeated-access counts in [F5] proves the query-to-circuit translation for both QA29 estimators, including their distinct value-rotated preparations and any unrotated coarse samples. In supplied controlled-power mode, sum the actual power-query prices from [F5] instead of expanding them as Qj component rounds; the standalone and coarse preparations are still charged. Since no operation is omitted or assigned zero cost, the conclusion makes no gate-cost claim without a supplied implementation.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

67 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