Pipeline-generated

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.

Phase-Estimation Linear-System Algorithms — Examples

1 · Prerequisites

2 · Summary

The diagonal example computes the normalized inverse state, ideal success weight, and OP5 grid spacing. The counterexample records the output-length lower bound for requesting every coordinate of an arbitrary solution vector.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

CounterexampleConstruction: Literature-sourcedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

State preparation does not print all coordinates

Statement refuted

A polylogarithmic-time QLSP state-output procedure necessarily returns a full classical description of its $N$ -coordinate solution vector in polylogarithmic time.

Facts & Assumptions

Given: The state-output task in Quantum linear-systems state-output task and the family below.

[F1]

Quantum linear-systems state-output task: the requested output is a quantum state; no classical coordinate list is promised.

Counterexample

For any integer $N \geq 2$ and bit string $x \in {0, 1}^{N}$ , set $a = 1 + x_{1}$ , $c_{j} = 1 + 3 x_{j}$ for $2 \leq j \leq N$ , and $b_{x} = \frac{a e_{1} + \sum_{j = 2}^{N} c_{j} e_{j}}{\sqrt{a^{2} + \sum_{j = 2}^{N} c_{j}^{2}}} .$ Take $A = I_{N}$ . Then $A^{+} b_{x} = b_{x}$ , and the first coordinate of every normalized solution is positive. The coordinate ratios $(b_{x})_{j} / (b_{x})_{1} = c_{j} / a$ lie in ${1, 4, 1 / 2, 2}$ and determine all $N$ bits even when outputs are identified up to global phase.

1.1givenF1algebra

For each $x$ , the ratios $(b_{x})_{j} / (b_{x})_{1} = c_{j} / a$ are $1$ or $4$ when $a = 1$ , and $1 / 2$ or $2$ when $a = 2$ . Since $N \geq 2$ , at least one ratio determines $a$ ; each ratio then determines its corresponding $c_{j}$ . Thus the $2^{N}$ inputs give $2^{N}$ distinct solution rays, with no ambiguity from a global phase.

2.1givenstep 1.1algebra∎

Let $z$ be a classical coordinate output for one of these rays, phase-fixed so that its first coordinate is positive real. If $∣ z_{j} - (b_{x})_{j} ∣ < δ : = 1 / (100 \sqrt{N})$ for every $j$ , then $(b_{x})_{1} \geq 1 / (4 \sqrt{N})$ because $a \geq 1$ and $∥ a e_{1} + \sum_{j \geq 2} c_{j} e_{j} ∥ \leq 4 \sqrt{N}$ . Hence $∣ z_{1} ∣ \geq 6 / (25 \sqrt{N})$ . For each $j \geq 2$ , $∣ \frac{z_{j}}{z_{1}} - \frac{(b_{x})_{j}}{(b_{x})_{1}} ∣ \leq \frac{δ}{∣ z_{1} ∣} (1 + \frac{(b_{x})_{j}}{(b_{x})_{1}}) \leq \frac{5}{24} < \frac{1}{4} .$ The four candidate ratios have pairwise separation at least $1 / 2$ , so nearest-ratio decoding recovers $a$ and every $c_{j}$ , hence all $N$ bits. Any unambiguous classical output code for all these rays therefore needs at least $2^{N}$ codewords and at least $N$ bits. This output-length requirement is independent of the ability to prepare or measure the corresponding quantum state.

ExampleConstruction: Literature-sourcedVerification: AI-generatedOpen item page →

Two-dimensional diagonal HHL inversion

Example

Let $H = diag (1, 1 / κ)$ for $κ \geq 1$ and $∣ b ⟩ = (∣ 0 ⟩ + ∣ 1 ⟩) / \sqrt{2}$ . The support promise holds with gap $1 / κ$ .

Verification

[F1] Ideal inverse amplitude and HHL postselection probability: the ideal well vector is $(2 κ)^{- 1} H^{+} ∣ b ⟩$ and its squared norm is the ideal success probability.

Given: The displayed diagonal matrix and normalized input.

1.1givenalgebra

Direct inversion gives $H^{+} ∣ b ⟩ = (∣ 0 ⟩ + κ ∣ 1 ⟩) / \sqrt{2}$ . Its norm is $\sqrt{1 + κ^{2}} / \sqrt{2}$ , so the target is $(∣ 0 ⟩ + κ ∣ 1 ⟩) / \sqrt{1 + κ^{2}}$ .

2.1F1step 1.1algebra∎

By [F1], the well vector is $(∣ 0 ⟩ + κ ∣ 1 ⟩) / (2 \sqrt{2} κ)$ and its probability is $(1 + κ^{2}) / (8 κ^{2})$ , which satisfies $1 / 8 < p \leq 1 / 4$ . For OP5, the eigenvalue grid spacing is $2 π / t_{0} = π ϵ / (1024 κ)$ . The sine window has nonzero tails, so this spacing is a grid resolution and not a hard error guarantee; the kernel moment and filter proof supply the error bound.