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.
State preparation does not print all coordinates
Statement refuted
A polylogarithmic-time QLSP state-output procedure necessarily returns a full classical description of its -coordinate solution vector in polylogarithmic time.
Facts & Assumptions
Given: The state-output task in Quantum linear-systems state-output task and the family below.
Quantum linear-systems state-output task: the requested output is a quantum state; no classical coordinate list is promised.
Counterexample
For any integer and bit string , set , for , and Take . Then , and the first coordinate of every normalized solution is positive. The coordinate ratios lie in and determine all bits even when outputs are identified up to global phase.
For each , the ratios are or when , and or when . Since , at least one ratio determines ; each ratio then determines its corresponding . Thus the inputs give distinct solution rays, with no ambiguity from a global phase.
Let be a classical coordinate output for one of these rays, phase-fixed so that its first coordinate is positive real. If for every , then because and . Hence . For each , The four candidate ratios have pairwise separation at least , so nearest-ratio decoding recovers and every , hence all bits. Any unambiguous classical output code for all these rays therefore needs at least codewords and at least bits. This output-length requirement is independent of the ability to prepare or measure the corresponding quantum state.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
8 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)