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.
HHL cost under direct controlled-simulation access
Statement
Let , , , and . The capped HHL circuit uses at most calls to each of and , at most calls to each supplied preparation form (the tagged in dilation mode) and its inverse, and one table construction . Each or contains two sine-table preparation/unpreparation circuits, one forward and one inverse QFT, the flag circuit, and controlled simulation calls at signed times ; its absolute evolution times sum to less than . Therefore the total absolute simulation time is less than . More precisely, the simulation charge is the actual sum over all calls of . The remaining charge is where and are the actual reflection and verification counts. The table itself has data bits and controlled rotations; no polylogarithmic table-generation or finite-rotation synthesis bound is asserted.
Facts & Assumptions
Given: The finite OP5 circuit and its declared simulator resource function.
HHL finite sine-window phase-estimation algorithm: the attempt uses the signed times , reverses each phase and prepares/unprepares the sine table.
Finite capped amplification succeeds with a supplied lower bound: at most calls are made in each direction.
Hamiltonian simulation error and resources, Circuit-family and computation cost model, and HHL state-preparation and simulation access model: simulator, the actual supplied preparation form (including in dilation mode), QFT, table, reflection, verifier, and gate resources are separate additive cost coordinates.
Proof
The geometric sum of forward times is . The reverse list has the same absolute times, so one or call uses less than . By [F2], there are at most calls in each direction, giving total absolute time below . Since , , and , the stated order follows.
Each or circuit contains one forward and one inverse QFT, two sine-table circuits, one flag circuit, and one forward/reverse simulation list by [F1]. Multiplying their actual counts by the separate cost functions in [F3] gives the displayed additive charge; the fixed table is generated once, and every B, inverse B, reflection, and verifier use is counted in its own coordinate.
Depends on
Used by
Dependency tree · two levels
42 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
- Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, Quantum algorithm for linear systems of equations (standard reference, not scraped)
- Andrew M. Childs, Robin Kothari, and Rolando D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision (standard reference, not scraped)
- Andrew M. Childs, Lecture Notes on Quantum Algorithms (standard reference, not scraped)