Stored Cost Refinement
Exercise LA-212
nl bridge from inspected source. Current content-bound mathematical second pass accepted. No new Lean verification is claimed for this NL view.
Assumptions and conventions
- A single run returns the chain and its full ledger of ordinary and named integer counters
- The four integer counters take the stated closed forms
- The named integer counters cover only those operations; no finite-bit or whole-machine runtime, and the source is unnormalized
- Original derivation from inspected local source; no fresh Lean verification
Question
A stored Hermite raw-source assembly builds a scalar-boundary tensor-train chain for a state-preparation amplitude. One single run of the assembly returns the chain together with a work ledger carrying both the eight ordinary exact-real counters and four separately named integer counters (quotient calls, remainder calls, integer doublings, integer additions), plus a count of exponential-function calls. For parameters k and n it is proved on the same run that the chain denotes the explicit raw-source kernel chain, that the ordinary total is bounded by a stated polynomial in k and n, that the exponential calls are at most 3*(n+1)+1, and that the four integer counters equal (n+1)*(n+2), (n+1)-squared, n, and 4*(n+1) respectively. Prove that the four integer counters sum to 2*n-squared + 10*n + 7, and explain carefully which costs this certificate does and does not account for, especially regarding finite-bit arithmetic and normalization.
Hint: mathematical route
Prove the four named integer counters of the stored Hermite raw-source run sum to 2*n-squared+10*n+7, and delineate the same-run scope excluding finite-bit runtime and normalization.
- The four certified integer-counter values expand and sum to 2*n-squared+10*n+7.
- The certificate is a same-run guarantee tying the denoted chain to its costs.
- The counters exclude general integer/bit work and make no finite-bit or normalized-loader claim.
Reference solution
Substitute the four certified integer-counter values and add: quotient (n+1)*(n+2) = n-squared + 3*n + 2; remainder (n+1)-squared = n-squared + 2*n + 1; integer doublings n; integer additions 4*(n+1) = 4*n + 4. Summing: (n-squared + 3*n + 2) + (n-squared + 2*n + 1) + n + (4*n + 4) = 2*n-squared + 10*n + 7. Scope: the certificate is a same-run guarantee, so the identical run that is proved to denote the raw-source kernel chain is the one whose costs are bounded; it does not build a second chain or substitute a hypothetical dimension-only budget. The ordinary total counts exact-real field, square-root, trigonometric, comparison and stored-word operations, including every materialization pass and the per-node records. The four integer counters count only those four named integer operations arising in the cache construction; they explicitly do not count every index manipulation, arbitrary-precision bit-level work, proof checking or counter bookkeeping. The exponential-call cap counts calls to the exponential primitive and is at most 3*(n+1)+1 because disabled guards contribute zero injections. Crucially the certificate makes no finite-bit running-time claim and no normalized state-preparation-compiler claim: the returned chain is an unnormalized source, so one may not read the bound as a complete machine runtime or as a normalized amplitude loader.
Assessment rubric
- Correctly expand and sum the four integer counters to 2*n-squared+10*n+7 (1 weight)
- State the same-run scope: the certified run is the one that denotes the kernel chain (1 weight)
- Explain the exclusions: not all integer/bit work, no finite-bit runtime, unnormalized source not a normalized loader (1 weight)
Graph-grounded prerequisites
These are support/source anchors, not an automatically extracted theorem-dependency proof.
Lean view and evidence boundary
No aligned Lean view has been admitted for this native core in this textbook checkpoint. This is not a claim that the underlying mathematics lacks a formal proof. Contributions must preserve this exact target contract and split.
Sources and provenance
- QuantumBlockEncoding/StoredHermiteRawCost.lean
raw_quotientCalls193-195; raw_remainderCalls197-199; raw_integerDoublings201-203; raw_integerAdditions205-207; raw_selected_integer_total210-214; raw_certified218-227
Source SHA-256:315e9f210c44c15e41742ef673ac93b191dfbbe48bb4ba84cd9abdd35f6adf62· MIT (repository LICENSE)
Contract: 7c470c2bdaf81967d2b212a205313720a868e6429f9e87a72b96cbd10180dd16
Item digest: 3b06beca17d084d5e8dfc81822d969d9e1271b530e70525a1fb4f0e7713a7c24
Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a
Authored support steps: 3. This is not measured graph distance or model difficulty.