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 , and let be the number of fresh standalone preparations of and the number of controlled Grover rounds using it. Also let range over the supplied unrotated sampler preparations used for coarse measurements, with such fresh preparations. If each controlled Grover round for is the explicit product of one controlled call, one controlled call, one controlled initial-state reflection, one controlled good-state reflection, and its control phase, then the exact primitive-call cost is where every is the declared cost of that operation. The preparation counts exclude the controlled and occurrences inside Grover rounds, which are already included in the terms. With a single , no unrotated coarse preparations, and , this reduces to the homogeneous formula . 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.
Coherent finite sampler and observable value requires explicit forward, inverse, controlled, data, value, rotation, and reflection access.
Controlled Unitary Access: controlled access is a separately declared operation and does not follow from ordinary access.
Inverse Unitary Access: inverse access and its charge are recorded separately from forward access.
Circuit-family and computation cost model keeps named queries, ordinary gates, circuit description, width, ancillas, precision, and classical computation as separate coordinates.
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- 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
For each , [F1]–[F3] show that one controlled Grover round contains exactly its five declared components. Repeating that product times contributes calls to each corresponding component cost. The standalone preparations contribute , and the separate coarse sampler preparations contribute . Summing these disjoint operation occurrences gives the displayed exact primitive-call cost.
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.
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 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
- Amplitude-estimation expectation estimator
- Quantum bounded-expectation guarantee and query cost
- Variance-aware quantum Monte Carlo
- Variance-aware quantum Monte Carlo guarantee
- Coherent finite sampler and observable value
- Controlled Unitary Access
- Inverse Unitary Access
- Circuit-family and computation cost model
- QFT-based amplitude estimation
- Amplitude estimation and counting input/output contract
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
- Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum Amplitude Amplification and Estimation, Section 4 (standard reference, not scraped)
- Ashley Montanaro, Quantum speedup of Monte Carlo methods, Theorems 3 and 5 (standard reference, not scraped)