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.
Block-encoding normalization, error, and cost accounting
Statement
For one LCU construction, the normalization is and each additive cost coordinate for the sequential operations is the sum of the declared costs of PREPARE, SELECT, and PREPARE; a SELECT implementation assembled from controlled component unitaries includes those calls and phases in its declared cost. For a two-factor product construction, the normalization is and the query and gate counts are the sums of the two supplied encoding costs in the chosen order. Any explicit wire permutation or control wrapper is included in a supplied operation's cost or charged as a separate operation. The normalized error is bounded by Product block-encoding error bound.
Matrix-data access, coefficient-table access and storage, state preparation and its inverse, controlled access, angle or entry precision, classical preprocessing, and compilation remain separate cost coordinates. This result counts declared primitives; it does not synthesize a circuit from a bare matrix or assign an absent primitive zero cost.
Facts & Assumptions
Given: A supplied access instance as in Block-encoding oracle and implementation cost model, the LCU circuit of LCU block-encoding construction, and the product construction of Product block encoding with separate ancillas.
Block-encoding oracle and implementation cost model: each supplied operation has its own declared cost, and a call to one operation does not imply access to another.
LCU block-encoding construction: the circuit applies , SELECT, and once each in that order.
Product block encoding with separate ancillas: the product circuit applies the supplied and once each in that order.
LCU projected-block correctness: the LCU normalization is .
Product block-encoding error bound: the product normalization and error are as stated there.
Proof
The LCU circuit consists, in chronological order, of one call to , one call to SELECT, and one call to by [F2]. Additivity of the declared sequential cost coordinates in [F1] gives their coordinatewise sum; when SELECT is decomposed, its listed controlled calls and phases are part of that sum. Its normalization is by [F4].
The product circuit calls the two supplied encodings exactly once each, first and then , by [F3]. Their query and gate counts therefore add, with any separately supplied routing or control operations charged in their own coordinates. Its normalization and error are those proved in [F5]. No matrix access, state-preparation circuit, inverse call, or controlled call not explicitly present in the supplied access instance is included for free.
Depends on
Used by
Dependency tree · two levels
28 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
- Andrew M. Childs, Lecture Notes on Quantum Algorithms, Chapters 28–29 (17 April 2025) (standard reference, not scraped)
- András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, Quantum singular value transformation and beyond, Section 4 (standard reference, not scraped)