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

1 · Prerequisites

2 · Summary

This page specifies the state-output QLSP task, a rectangular Hermitian dilation, and the finite sine-window HHL circuit in the signed-eigenvalue convention. It proves the sine-window kernel moment, reciprocal-filter stability, postselection normalization, capped amplification, and the resulting conditional state error under explicit preparation and simulator error budgets. The direct simulator resource sum is proved. The sparse-row query specialization follows from the explicit sorted-XOR access bridge and the clean-workspace simulation mode.

The sparse-query specialization is proved through the costed sorted-XOR block encoding and the QA25 clean-input simulator. The access definition retains full-operator simulation and additionally permits the explicit clean-workspace mode; its proof includes actual inverse circuits and error accumulation without assuming intermediate work is clean. Classical table generation, arithmetic, phase compilation, gate and bit-time resources remain separate.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Odd-well and even-ill reciprocal filter

Definition

For $κ \geq 1$ and real estimate $z$ , put $u = ∣ z ∣$ and define the odd well amplitude $f_{κ}$ and even ill amplitude $g_{κ}$ by $f_{κ} (z) = {\begin{cases} sgn (z) / (2 κ u), & u \geq 1 / κ, \\ \frac{1}{2} sgn (z) \sin (π κ (u - 1 / (2 κ))), & 1 / (2 κ) \leq u < 1 / κ, \\ 0, & u < 1 / (2 κ), \end{cases} g_{κ} (z) = {\begin{cases} 0, & u \geq 1 / κ, \\ \frac{1}{2} \cos (π κ (u - 1 / (2 κ))), & 1 / (2 κ) \leq u < 1 / κ, \\ 1 / 2, & u < 1 / (2 κ), \end{cases}$ where $sgn (z) = 1$ for $z > 0$ , $- 1$ for $z < 0$ , and $0$ for $z = 0$ . The three flag amplitudes are $(h (z), f_{κ} (z), g_{κ} (z))$ , where $h (z) = \sqrt{1 - f_{κ} (z)^{2} - g_{κ} (z)^{2}}$ . Labels are nothing, well, ill, respectively. This definition applies to every real decoded grid point, including points outside the supported spectrum.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite sine-window phase state

Definition

For a power of two $T \geq 2$ , the sine-window vector is $∣ Ψ_{T} ⟩ = \sqrt{\frac{2}{T}} \sum_{τ = 0}^{T - 1} \sin ⁣ (\frac{π (τ + 1 / 2)}{T}) ∣ τ ⟩ .$ For any integer interval $0 \leq a \leq b \leq T$ , define its unnormalized sine mass $W_{T} (a, b) : = \sum_{τ = a}^{b - 1} \sin^{2} ⁣ (\frac{π (τ + 1 / 2)}{T}) .$ The closed trigonometric formula for $W_{T} (a, b)$ is proved by the assigned prefix-mass lemma. The chosen OP5 table variant stores these interval masses and their conditional split angles; it charges its full $O (T)$ table and rotation size, arithmetic, interval-refinement, angle-bit, and finite gate-synthesis costs. This definition does not assign a polylogarithmic implementation cost.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Hermitian dilation for a rectangular linear system

Statement

For $A : C^{n} \to C^{m}$ , define $H_{A} : C^{m} \oplus C^{n} \to C^{m} \oplus C^{n}$ using the adjoint $A^{*}$ of The adjoint $T^{*} : W \to V$ is characterised by $⟨ T v, w ⟩_{W} = ⟨ v, T^{*} w ⟩_{V}$ by $H_{A} (x, y) = (A y, A^{*} x)$ . Then $H_{A}$ is Hermitian; its nonzero eigenvalues are $+ σ_{j}, - σ_{j}$ for the positive singular values of $A$ , its kernel is $\ker (A^{*}) \oplus \ker (A)$ , and $H_{A}^{+} (b, 0) = (0, A^{+} b)$ . When $A$ has positive rank, its nonzero condition number is preserved; the output is tagged in the domain summand.

Facts & Assumptions

Given: A finite-dimensional map $A$ and its singular system.

[F1]

Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition: $A$ has orthonormal singular pairs $(u_{j}, v_{j})$ with positive values $σ_{j}$ ; in these bases its matrix is diagonal with entries $σ_{j}$ and zero on the remaining coordinates.

[F2]

The adjoint $T^{*} : W \to V$ is characterised by $⟨ T v, w ⟩_{W} = ⟨ v, T^{*} w ⟩_{V}$ : $⟨ A x, y ⟩ = ⟨ x, A^{*} y ⟩$ , so the adjoint of a block matrix swaps the blocks and takes their adjoints.

[F3]

The Moore--Penrose pseudoinverse $A^{+}$ as the solution of the four Penrose equations: a pseudoinverse $G$ satisfies $H G H = H$ , $G H G = G$ , and $H G, G H$ are self-adjoint; Every finite real or complex matrix has a unique Moore--Penrose pseudoinverse: each finite matrix has exactly one such pseudoinverse.

Proof

1.1givenF2algebra

The block matrix of $H_{A}$ is $(\begin{array}{cc} 0 & A \\ A^{*} & 0 \end{array})$ . Its adjoint, by [F2], is the same block matrix, so $H_{A}^{*} = H_{A}$ .

1.2F1algebra

Multiplying the SVD in [F1] gives $A v_{j} = σ_{j} u_{j}$ and $A^{*} u_{j} = σ_{j} v_{j}$ . Therefore $H_{A} (u_{j}, v_{j}) = σ_{j} (u_{j}, v_{j})$ and $H_{A} (u_{j}, - v_{j}) = - σ_{j} (u_{j}, - v_{j})$ . After division by $\sqrt{2}$ these are unit eigenvectors. Orthonormality of the singular pairs makes all such vectors mutually orthogonal.

1.3F1F3algebra

In the SVD bases, write $A = U Σ V^{*}$ with positive diagonal entries $σ_{j}$ . The diagonal matrix $Σ^{+}$ that replaces each positive entry by $1 / σ_{j}$ and leaves zero entries zero satisfies $Σ Σ^{+} Σ = Σ$ , $Σ^{+} Σ Σ^{+} = Σ^{+}$ , and both products $Σ Σ^{+}$ and $Σ^{+} Σ$ are diagonal projections. Unitary transport shows $V Σ^{+} U^{*}$ satisfies the four equations in [F3], so uniqueness gives $A^{+} = V Σ^{+} U^{*}$ and $A^{+} u_{j} = v_{j} / σ_{j}$ .

2.1step 1.2algebra

The equation $H_{A} (x, y) = 0$ is equivalent to $A y = 0$ and $A^{*} x = 0$ , so $\ker H_{A} = \ker (A^{*}) \oplus \ker (A)$ . Together with step 1.2, the nonzero eigenvalue magnitudes are exactly the positive singular values, each appearing with both signs. Thus when there is positive rank their maximum-to-minimum ratio is unchanged.

3.1F1F3step 1.2step 2.1step 1.3algebra∎

The vectors from step 1.2 together with orthonormal bases of $\ker (A^{*})$ and $\ker (A)$ form an orthonormal eigenbasis of the direct sum. Define $G$ on this basis by $G w_{j, +} = w_{j, +} / σ_{j}$ , $G w_{j, -} = - w_{j, -} / σ_{j}$ , and $G = 0$ on the kernel. Then $H_{A} G$ and $G H_{A}$ are self-adjoint projections, while diagonal multiplication gives $H_{A} G H_{A} = H_{A}$ and $G H_{A} G = G$ . Thus $G$ satisfies [F3], and uniqueness gives $G = H_{A}^{+}$ . Since $(u_{j}, 0) = (w_{j, +} + w_{j, -}) / \sqrt{2}$ , this definition gives $H_{A}^{+} (u_{j}, 0) = (0, v_{j} / σ_{j})$ . Complete the positive left singular vectors to the left singular basis from [F1]. The remaining basis vectors have zero singular coordinates, so the diagonal SVD gives $A^{*} u_{j} = 0$ for each; hence they span the complementary part $\ker (A^{*})$ . Thus every $b \in C^{m}$ has a decomposition $b = \sum_{j : σ_{j} > 0} β_{j} u_{j} + b_{0}$ with $b_{0} \in \ker (A^{*})$ . Since $A^{*} b_{0} = 0$ , its positive left-singular coordinates vanish, so $Σ^{+} U^{*} b_{0} = 0$ and the formula in step 1.3 gives $A^{+} b_{0} = 0$ . By step 2.1 $(b_{0}, 0) \in \ker (H_{A})$ , so $H_{A}^{+} (b_{0}, 0) = G (b_{0}, 0) = 0$ . Applying the positive-pair calculation to the other summands gives $H_{A}^{+} (b, 0) = (0, A^{+} b)$ for arbitrary $b$ , including $b \notin ran (A)$ .

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

The reciprocal filter defines valid three-outcome amplitudes

Statement

For every real $z$ and $κ \geq 1$ , $f_{κ} (z)^{2} + g_{κ} (z)^{2} \leq 1 / 4$ . Hence $h (z)$ in Odd-well and even-ill reciprocal filter is real, and the three displayed amplitudes have squared moduli summing to one.

Facts & Assumptions

Given: The piecewise functions in Odd-well and even-ill reciprocal filter.

[F1]

Odd-well and even-ill reciprocal filter and Parity and the Pythagorean identity for sine and cosine: in the transition band the two nonzero functions are one half times sine and cosine of the same angle; on each plateau they are constants or one reciprocal term.

Proof

1.1F1algebra

If $∣ z ∣ \geq 1 / κ$ , then $g_{κ} (z) = 0$ and $∣ f_{κ} (z) ∣ = 1 / (2 κ ∣ z ∣) \leq 1 / 2$ , so their squared sum is at most $1 / 4$ .

2.1F1algebra∎

If $1 / (2 κ) \leq ∣ z ∣ < 1 / κ$ , the identity $\sin^{2} θ + \cos^{2} θ = 1$ gives $f_{κ} (z)^{2} + g_{κ} (z)^{2} = 1 / 4$ . If $∣ z ∣ < 1 / (2 κ)$ , the sum is $0 + (1 / 2)^{2} = 1 / 4$ . Thus all cases give the bound, and $1 - f^{2} - g^{2} \geq 3 / 4 > 0$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Quantum linear-systems state-output task

Definition

Let $A : C^{n} \to C^{m}$ be a finite-dimensional linear map, $m, n \geq 1$ , and let $b \in ran (A) ∖ {0}$ , where $ran (A)$ is the image defined in Kernel and image of a linear map. The quantum linear-systems state-output task (QLSP) is to prepare the normalized domain-register state $∣ x ⟩ : = \frac{A^{+} b}{∥ A^{+} b ∥} \in C^{n},$ where $A^{+}$ is the Moore–Penrose pseudoinverse. By Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition, write $b = \sum_{j : σ_{j} > 0} β_{j} u_{j}$ in left singular vectors; the promised support gap is a supplied rational or exactly represented $γ > 0$ such that every $j$ with $β_{j} \neq 0$ has singular value $σ_{j} \geq γ$ . The input includes a costed unitary $B$ mapping its designated all-zero input to $∣ b / ∥ b ∥ ⟩$ in the codomain register, tensored with a fixed work state. Its inverse, controlled access, and resource coordinates are specified in the separate HHL access model. If $b$ is multiplied by $c \neq 0$ , the normalized representative is multiplied by $c / ∣ c ∣$ , so its pure-state ray is unchanged. The task returns a quantum state (and may return a success flag); it does not promise a classical list of coordinates.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Relative stability of the HHL filter on supported eigenvalues

Statement

Let $κ \geq 1$ , $t_{0} > 0$ , and $λ, δ \in R$ with $1 / κ \leq ∣ λ ∣ \leq 1$ . Set $\tilde{λ} = λ - δ / t_{0}$ . For the well/ill amplitude pair $m (z) = (f_{κ} (z), g_{κ} (z))$ from Odd-well and even-ill reciprocal filter, $∥ m (\tilde{λ}) - m (λ) ∥_{2} \leq 10 κ \frac{∣ δ ∣}{t_{0}} ∣ f_{κ} (λ) ∣ .$

Facts & Assumptions

Given: The supported eigenvalue and filter definition.

[F1]

Odd-well and even-ill reciprocal filter and The reciprocal filter defines valid three-outcome amplitudes: $∥ m (z) ∥_{2} \leq 1 / 2$ ; on the transition band its coordinates are one half times sine and cosine with angle slope $π κ$ .

[F2]

Sine and cosine are $1$ -Lipschitz on $R$ : each of sine and cosine changes by at most the change in its real argument.

[F3]

Rational bounds for pi used in finite schedules: $3 < π < 16 / 5$ .

[F4]

Quarter-turn values and shifts by pi/2 and pi: $\sin (π / 2) = 1$ and $\cos (π / 2) = 0$ .

[F5]

The derivatives of sine and cosine are cosine and minus sine: $\sin 0 = 0$ and $\cos 0 = 1$ .

Proof

1.1F1F2F3F4F5algebra

At $u = 1 / (2 κ)$ the transition angle is $0$ , so [F5] makes the transition values $(0, 1 / 2)$ , matching the lower plateau; at $u = 1 / κ$ the angle is $π / 2$ , so [F4] makes them $(sgn (z) / 2, 0)$ , matching the reciprocal branch. Hence $m$ is continuous on each fixed-sign half-line. On the reciprocal branch, for $u, u^{'} \geq 1 / κ$ , $∣ \frac{1}{2 κ u} - \frac{1}{2 κ u^{'}} ∣ = \frac{∣ u - u^{'} ∣}{2 κ u u^{'}} \leq \frac{κ}{2} ∣ u - u^{'} ∣ .$ On the transition branch, [F2] bounds each coordinate change by $(π κ / 2) ∣ u - u^{'} ∣$ , so the two-coordinate norm changes by at most $(π κ / \sqrt{2}) ∣ u - u^{'} ∣$ . The lower plateau is constant, and $κ / 2 \leq π κ / \sqrt{2}$ by [F3]. Splitting any same-sign interval at the two breakpoints and adding these bounds proves the global same-sign Lipschitz estimate $∥ m (z) - m (z^{'}) ∥_{2} \leq (π κ / \sqrt{2}) ∣ z - z^{'} ∣$ .

2.1F1step 1.1algebra

Write $Δ = ∣ \tilde{λ} - λ ∣ = ∣ δ ∣ / t_{0}$ . If $\tilde{λ}$ has the same sign as $λ$ and $∣ \tilde{λ} ∣ \geq 1 / κ$ , both values use the reciprocal branch, and $\frac{∥ m (\tilde{λ}) - m (λ) ∥_{2}}{∣ f_{κ} (λ) ∣} = \frac{Δ}{∣ \tilde{λ} ∣} \leq κ Δ .$ If the signs differ (including zero), then $Δ \geq ∣ λ ∣$ , and the norm difference is at most $1 / 2 + ∣ f_{κ} (λ) ∣$ by [F1]. Dividing by $∣ f_{κ} (λ) ∣ = 1 / (2 κ ∣ λ ∣)$ gives at most $1 + κ ∣ λ ∣ \leq 2 κ Δ$ .

3.1F1F2F3step 1.1algebra∎

It remains that the signs agree and $∣ \tilde{λ} ∣ < 1 / κ$ . If $∣ λ ∣ \leq 2 / κ$ , step 1.1 gives a norm difference at most $π κ Δ / \sqrt{2}$ . Since $∣ f_{κ} (λ) ∣ = 1 / (2 κ ∣ λ ∣) \geq 1 / 4$ , the ratio is at most $2 \sqrt{2} π κ Δ < (48 / 5) κ Δ < 10 κ Δ$ , using $\sqrt{2} < 3 / 2$ and [F3]. If $∣ λ ∣ > 2 / κ$ , crossing below $1 / κ$ implies $Δ > ∣ λ ∣ / 2$ and $κ Δ > 1$ . By [F1] the ratio is at most $1 + κ ∣ λ ∣ < 1 + 2 κ Δ < 3 κ Δ < 10 κ Δ$ . These cases establish the claimed inequality.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Sine-window normalization and positive prefix weights

Statement

For a power of two $T \geq 2$ and integers $0 \leq a \leq b \leq T$ , $W_{T} (a, b) = \frac{b - a}{2} - \frac{\sin (2 π b / T) - \sin (2 π a / T)}{4 \sin (π / T)} .$ In particular, $W_{T} (0, T) = T / 2$ , so $∣ Ψ_{T} ⟩$ is normalized, and every nonempty interval has $W_{T} (a, b) \geq T^{- 2}$ .

Facts & Assumptions

Given: The sine window and interval mass in Finite sine-window phase state.

[F1]

Finite geometric sum for phase-estimation amplitudes: finite geometric sums satisfy $\sum_{j = 0}^{n - 1} z^{j} = (1 - z^{n}) / (1 - z)$ when $z \neq 1$ .

[F2]

Finite sine-window phase state: $W_{T} (a, b)$ is the sum of the indicated nonnegative sine squares.

[F3]

Double-angle and quadratic power-reduction identities: $\sin^{2} x = (1 - \cos (2 x)) / 2$ .

[F4]

$\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ , $\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential, and The addition formulas for sine and cosine: $e^{i x} = \cos x + i \sin x$ , $e^{i π} = - 1$ , the exponential is multiplicative, and sine/cosine satisfy their addition formulas.

[F5]

Sine chord and linear bounds: $\sin (π u) \geq 2 u$ for $0 \leq u \leq 1 / 2$ .

[F6]

Cofunction, supplementary, quarter-turn, and reflection identities for the six trigonometric functions: $\sin (π - x) = \sin x$ .

Proof

1.1F1F2F3F4F5algebra

Put $z = e^{2 π i / T}$ . By [F4], $z^{T} = e^{2 π i} = 1$ . Also [F5] gives $\sin (π / T) \geq 2 / T > 0$ , so $1 - z \neq 0$ . Reindexing [F1] gives $\sum_{τ = a}^{b - 1} e^{2 π i (τ + 1 / 2) / T} = e^{2 π i (a + 1 / 2) / T} \frac{1 - z^{b - a}}{1 - z} = e^{i π (a + b) / T} \frac{\sin (π (b - a) / T)}{\sin (π / T)} .$ The real part of the last expression is $[\sin (2 π b / T) - \sin (2 π a / T)] / [2 \sin (π / T)]$ by the sine addition formula [F4]. Applying [F3] to the defining sum [F2] proves the displayed formula for $W_{T} (a, b)$ .

2.1step 1.1algebra

Setting $a = 0, b = T$ in the formula of step 1.1 makes its sine difference zero, so $W_{T} (0, T) = T / 2$ . The squared norm of $∣ Ψ_{T} ⟩$ is $(2 / T) W_{T} (0, T) = 1$ .

3.1F2F5F6algebra∎

If $a < b$ , choose an integer $τ$ in $[a, b)$ . Then $τ + 1 / 2$ lies between $1 / 2$ and $T - 1 / 2$ , so its angle lies in $[π / (2 T), π - π / (2 T)]$ . The chord bound [F5] gives $\sin (π / (2 T)) \geq 1 / T$ , and [F6] reflects this lower bound to the upper half of the interval. That summand is at least $T^{- 2}$ and all other summands are nonnegative by [F2].

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

The QLSP target is nonzero

Statement

Under the hypotheses in Quantum linear-systems state-output task, $A^{+} b \neq 0$ , so the normalized target is well-defined.

Facts & Assumptions

Given: A finite-dimensional map $A$ and $b \in ran (A) ∖ {0}$ .

[F1]

Kernel and image of a linear map: $b \in ran (A)$ means that some $x$ satisfies $b = A x$ .

[F2]

The Moore--Penrose pseudoinverse $A^{+}$ as the solution of the four Penrose equations: $A A^{+} A = A$ ; Every finite real or complex matrix has a unique Moore--Penrose pseudoinverse: this pseudoinverse exists and is unique.

Proof

1.1givenF1F2choosealgebra

By [F1], choose $x$ with $b = A x$ . The Penrose equation in [F2] gives $A A^{+} b = A A^{+} A x = A x = b$ .

2.1givenstep 1.1algebra∎

If $A^{+} b = 0$ , then $A A^{+} b = 0$ , contradicting step 1.1 and the hypothesis $b \neq 0$ . Hence $A^{+} b \neq 0$ and the normalized QLSP target is defined.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Operator error for the finite sine-prefix rotation table

Statement

Let $T = 2^{L} \geq 2$ , and let $W_{T} (a, b)$ and $∣ Ψ_{T} ⟩$ be as in Finite sine-window phase state. In the binary prefix tree, order the register bits from root to leaf. At level $ℓ = 0, \dots, L - 1$ , each interval node $[a, b)$ has midpoint $m = (a + b) / 2$ and split $r = W_{T} (a, m) / W_{T} (a, b)$ . Apply $R_{y} (2 \arcsin \sqrt{r})$ to the next bit, controlled on the preceding prefix that names $[a, b)$ , encoding bit $1$ as the left child and bit $0$ as the right child. Starting from $∣ 0^{L} ⟩$ , this ideal prefix circuit prepares $∣ Ψ_{T} ⟩$ . If a finite state-preparation circuit contains $N$ controlled $Y$ rotations and each implemented rotation differs from its ideal rotation by operator norm at most $δ$ , the product unitary differs from the ideal product by operator norm at most $N δ$ . In the OP5 table variant let $ϵ_{Ψ} > 0$ , $N = T - 1$ and $δ = ϵ_{Ψ} / (100 T)$ , so the preparation error is less than $ϵ_{Ψ} / 100$ ; using the same bound for its inverse gives the stated unpreparation cost.

Facts & Assumptions

Given: A finite list of controlled rotations and a per-rotation operator-error bound.

[F1]

Linear isometries, and orthogonal or unitary operators on finite-dimensional inner product spaces: unitary operators preserve vector norm.

[F2]

The inner-product norm is definite, homogeneous, and satisfies the triangle inequality: the norm of a finite sum is at most the sum of the norms.

[F3]

Sine chord and linear bounds: $\sin x \leq x$ for $x \geq 0$ , and $\sin x \geq 2 x / π$ for $0 \leq x \leq π / 2$ .

[F4]

Parity and the Pythagorean identity for sine and cosine: sine is odd and $\sin^{2} u + \cos^{2} u = 1$ .

[F5]

The addition formulas for sine and cosine: the sine and cosine addition formulas hold; substituting them into the displayed rotation matrices gives the corresponding angle-addition rule.

[F6]

Finite sine-window phase state: the leaf weights are $w_{τ} = \sin^{2} (π (τ + 1 / 2) / T)$ and the target amplitudes are $\sqrt{2 / T} \sin (π (τ + 1 / 2) / T)$ .

[F7]

Sine-window normalization and positive prefix weights: $W_{T} (0, T) = T / 2$ , and every nonempty interval has positive mass.

[F8]

Cofunction, supplementary, quarter-turn, and reflection identities for the six trigonometric functions: $\sin (π - x) = \sin x$ for every real $x$ .

Proof

1.1givenF1F3F4F5algebra

The real $Y$ -rotation matrix is $R_{y} (θ) = (\begin{array}{cc} \cos (θ / 2) & - \sin (θ / 2) \\ \sin (θ / 2) & \cos (θ / 2) \end{array})$ . For any unit vector $x$ , [F5] and [F4] give $∥ (R_{y} (β) - R_{y} (α)) x ∥^{2} = ∥ (R_{y} (β - α) - I) x ∥^{2} = 4 \sin^{2} ((β - α) / 4) .$ Taking the supremum over unit $x$ and using [F3] and [F4] yields $∥ R_{y} (β) - R_{y} (α) ∥ \leq ∣ β - α ∣$ . A controlled rotation is block diagonal with identity and this rotation on its control subspaces, so its operator error obeys the same bound.

1.2givenF3F6F7F8algebrainduction

For each leaf $τ$ , put $x_{τ} = π (τ + 1 / 2) / T \in (0, π)$ . If $x_{τ} \leq π / 2$ , [F3] gives $\sin x_{τ} \geq 2 x_{τ} / π > 0$ ; if $x_{τ} > π / 2$ , [F8] reduces positivity to $π - x_{τ} \in (0, π / 2)$ and the same bound. Thus each leaf weight is positive, and [F7] makes every split ratio lie in $(0, 1)$ . The rotation sends $∣ 0 ⟩$ to $\sqrt{1 - r} ∣ 0 ⟩ + \sqrt{r} ∣ 1 ⟩$ , so its branch amplitudes are exactly the square roots of the right- and left-child mass fractions. Induction from the root shows that leaf $τ$ has amplitude $\sqrt{w_{τ} / W_{T} (0, T)} = \sqrt{2 / T} \sin x_{τ}$ , by [F6] and [F7]. With left encoded by $1$ , interval leaf $τ$ has computational label $T - 1 - τ$ . Its amplitude equals that of label $τ$ because $x_{T - 1 - τ} = π - x_{τ}$ and [F8] gives $\sin x_{T - 1 - τ} = \sin x_{τ}$ . Hence the ideal circuit prepares $∣ Ψ_{T} ⟩$ .

2.1F1F2step 1.1step 1.2algebra∎

For products ${\tilde{U}}_{N} \dots {\tilde{U}}_{1}$ and $U_{N} \dots U_{1}$ , insert and subtract one factor at a time. This writes their difference as a sum of $N$ terms, each containing one ${\tilde{U}}_{j} - U_{j}$ between unitary products. By [F1] the outer products preserve norm, and [F2] bounds the sum by $N δ$ . For $ϵ_{Ψ} > 0$ , $N = T - 1$ and $δ = ϵ_{Ψ} / (100 T)$ this is less than $ϵ_{Ψ} / 100$ . Applying the same estimate to the inverse rotation list, whose ideal angles are negated and whose synthesis uses the same per-angle tolerance, gives the same bound for inverse preparation.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

HHL state-preparation and simulation access model

Definition

For a Hermitian $H$ on a finite-dimensional register, with operator norm as in The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, the HHL access instance supplies: (i) a unitary $B$ with $B ∣ 0_{I, W} ⟩ = ∣ b / ∥ b ∥ ⟩_{I} ∣ g_{B} ⟩_{W}$ for a fixed normalized work state $∣ g_{B} ⟩$ (which may be $∣ 0_{W} ⟩$ ) and declared costs for $B, B^{†}$ and any controlled forms used; (ii) for every requested real $t$ and tolerance $η$ , a controlled simulation circuit $S_{H} (t, η)$ with operator-norm error at most $η$ from $e^{+ i H t}$ , and separately declared inverse/negative-time costs; and (iii) separate actual resource functions $C_{B}, C_{B^{†}}$ , $C_{s i m} (t, η)$ , $C_{Ψ} (T, ϵ_{Ψ})$ for each forward or inverse sine-table preparation, $G_{Ψ} (T, ϵ_{Ψ})$ for its one-time classical table generation/data bits, $C_{Q F T}^{+ / -} (T)$ , $C_{f l a g} (κ, η_{R})$ , $C_{a r i t h} (T, κ, ϵ)$ , $C_{r e f}$ , and $C_{v e r}$ , and costs for reversible arithmetic, registers and finite-precision gate synthesis. Here $C_{Q F T}^{-}$ is the negative-sign Fourier circuit and $C_{Q F T}^{+}$ its positive-sign inverse, $C_{a r i t h}$ is the per-attempt reversible decode/filter arithmetic cost, and $C_{r e f}, C_{v e r}$ are the per-call reflection and well-verification costs. These functions count the stated circuit implementation in the chosen gate/access model; they assert no polylogarithmic bound on table generation or rotation synthesis. The positive exponential sign is the OP5 convention. An implementation of $H$ from matrix entries or a sparse oracle is additional data and must include its own proof and cost. A bare matrix, sparsity promise, or list of amplitudes is not a circuit. A rational scale $Λ \geq ∥ H ∥$ may be supplied; after replacing $H$ by $H / Λ$ , the supported gap $γ$ gives $κ = Λ / γ$ .

Clean-workspace simulation mode. The original full-operator-norm access mode remains admissible. Alternatively, supply a unitary dilation $S$ with a fixed clean-work embedding $J$ and $∥ S J - J e^{+ i H t} ∥_{o p} \leq η$ , including arbitrary timing/control/reference registers. The ideal operation leaves this simulator workspace in zero; other ideal HHL operations do not touch it. Actual output work may be dirty. Supply actual circuit inverses and controls and charge their full workspace and query costs. Unitary hybrids on a preserved clean-work subspace proves the same clean-input error for the actual adjoint, coherent controls and arbitrary references, and proves accumulation along the ideal all-clean trajectory. The inverse used in HHL uncomputation/amplification is the literal reverse physical circuit, not a separately approximated negative-time routine. Include simulator work in the joint output comparison and the ideal all-zero algorithm registers. A full-space error on arbitrary dirty inputs is neither required nor inferred in this alternative mode.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Second moment of the signed sine-window phase kernel

Statement

Let $t_{0} = 2048 κ / ϵ$ , $0 < ϵ \leq 1$ , $κ \geq 1$ , and let $T$ be the least power of two at least $8 (t_{0} + 1)$ . For any $λ \in [- 1, 1]$ , prepare Finite sine-window phase state, apply the controlled phases $e^{i λ τ t_{0} / T}$ and the negative-sign Fourier transform, then decode $y$ to signed $k$ . With probability $p_{k} (λ)$ , put $δ_{k} = λ t_{0} - 2 π k$ . Then $\sum_{k = - T / 2}^{T / 2 - 1} p_{k} (λ) δ_{k}^{2} < 300.$

Facts & Assumptions

Given: The sine-window circuit and OP5 parameter range.

[F1]

Exact binary QFT circuit correctness: the negative-sign Fourier transform has basis amplitudes $T^{- 1 / 2} e^{- 2 π i k τ / T}$ , so the measured amplitude is the finite Fourier sum of the prepared coefficients.

[F2]

Finite geometric sum for phase-estimation amplitudes: finite exponential sums equal their geometric-series quotient when the ratio is not one; the coincident-ratio case is their continuous finite-sum limit.

[F3]

Rational bounds for pi used in finite schedules: $3 < π < 22 / 7 < 16 / 5$ .

[F4]

Sine chord and linear bounds: $\sin v \leq v$ for $v \geq 0$ .

[F5]

Sine and cosine are $1$ -Lipschitz on $R$ : cosine changes by at most the change in its real argument.

[F6]

The derivatives of sine and cosine are cosine and minus sine: $\cos 0 = 1$ .

[F7]

Sine chord and linear bounds: $\sin (π u) \geq 2 u$ for $0 \leq u \leq 1 / 2$ .

Proof

1.1givenF1F2algebra

Put $θ = λ t_{0} / (2 π)$ and $δ = 2 π (θ - k)$ . Expanding sine into its two exponentials and summing the two geometric series from [F2] gives the amplitude $α_{k} = - \frac{\sqrt{2}}{T} e^{i δ (1 - 1 / T) / 2} \frac{\cos (δ / 2) \cos (δ / (2 T)) \sin (π / (2 T))}{\sin ((δ + π) / (2 T)) \sin ((δ - π) / (2 T))} .$ At a removable zero this formula means its continuous limit. By [F1], $p_{k} = ∣ α_{k} ∣^{2}$ and $\sum_{k} p_{k} = 1$ .

2.1F3F4F5F6F7step 1.1algebra

For $∣ δ ∣ \geq 2 π$ , set $x = ∣ δ ∣ / (2 T)$ and $a = π / (2 T)$ . Signed decoding and $∣ λ ∣ \leq 1$ give $x \leq π / 2 + t_{0} / (2 T) < π / 2 + 1 / 16$ ; also $x \geq 2 a$ . Since $t_{0} \geq 2048$ , $a < 1 / 100$ , hence $x + a < π / 2 + 1 / 10$ . On $[0, π / 2 + 1 / 10]$ one has $\sin u \geq u / 2$ : on $[0, π / 2]$ put $s = v / π \in [0, 1 / 2]$ and apply [F7] to get $\sin v \geq 2 v / π > v / 2$ using [F3]; on the remaining interval, $\sin u = \cos (u - π / 2) \geq 1 - 1 / 10 = 9 / 10$ by [F5] and [F6], while $u / 2 < (16 / 5) / 4 + 1 / 20 = 17 / 20 < 9 / 10$ . Therefore $∣ \sin^{2} x - \sin^{2} a ∣ = \sin (x + a) \sin (x - a) \geq \frac{1}{4} (x^{2} - a^{2}) \geq \frac{3 δ^{2}}{64 T^{2}} .$ Using $∣ \cos ∣ \leq 1$ and $\sin a \leq a$ in step 1.1 yields $p_{k} \leq (2048 π^{2} / 9) δ^{- 4}$ .

3.1F3step 2.1algebra∎

The outcomes with $∣ δ ∣ < 2 π$ contribute at most $4 π^{2}$ because their total probability is at most one. For the rest, group integers by $n \leq ∣ θ - k ∣ < n + 1$ , $n \geq 1$ ; each shell has at most two integers. Step 2.1 gives $\sum_{∣ δ_{k} ∣ \geq 2 π} p_{k} δ_{k}^{2} \leq \frac{2048 π^{2}}{9} \frac{2}{4 π^{2}} \sum_{n = 1}^{\infty} \frac{1}{n^{2}} \leq \frac{2048}{9},$ where $\sum_{n \geq 1} n^{- 2} \leq 1 + \int_{1}^{\infty} x^{- 2} d x = 2$ . By [F3], $4 π^{2} < 4 (16 / 5)^{2} < 41$ , so the total is less than $41 + 2048 / 9 < 300$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Signed phase decoding has no alias on the promised spectrum

Statement

Let $0 < ϵ \leq 1$ , $κ \geq 1$ , $t_{0} = 2048 κ / ϵ$ , and let $T$ be the least power of two with $T \geq 8 (t_{0} + 1)$ . For $H = H^{*}$ with $∥ H ∥ \leq 1$ , phase estimation using powers of $e^{+ i H t_{0} / T}$ has exact eigenphase angle $λ t_{0} / T$ on an eigenvector of eigenvalue $λ$ . This lies strictly in $(- π, π)$ ; signed decoding $k = y$ for $y < T / 2$ and $k = y - T$ otherwise uses the unique centered representative. Its eigenvalue grid is $\tilde{λ} = 2 π k / t_{0}$ , with spacing $2 π / t_{0}$ .

Facts & Assumptions

Given: A self-adjoint finite-dimensional $H$ , the OP5 scale, and $T$ as above.

[F1]

Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: a normal finite-dimensional complex endomorphism has an orthonormal eigenbasis; $H = H^{*}$ implies $H$ is normal.

[F2]

Unitary and differential identities for finite matrix dynamics: $U_{H} (t) = e^{- i t H}$ ; on an eigenvector with eigenvalue $λ$ , replacing $t$ by $- s$ gives $e^{+ i s λ}$ .

[F3]

Quantum phase estimation and Exact binary QFT circuit correctness: phase estimation uses Fourier-basis labels modulo $T$ .

[F4]

Rational bounds for pi used in finite schedules: $π > 3$ .

Proof

1.1givenF1algebra

By [F1], choose an orthonormal eigenbasis and let $H ∣ u ⟩ = λ ∣ u ⟩$ . The root inner product is linear in its first argument and conjugate-linear in the second (Dirac Notation Conversion). Self-adjointness therefore gives $λ ∥ u ∥^{2} = ⟨ H u, u ⟩ = ⟨ u, H^{*} u ⟩ = ⟨ u, H u ⟩ = \overline{λ} ∥ u ∥^{2},$ so $λ$ is real. Also $∣ λ ∣ ∥ u ∥ = ∥ H u ∥ \leq ∥ H ∥ ∥ u ∥ \leq ∥ u ∥$ , so $λ \in [- 1, 1]$ .

2.1F2F3step 1.1

On this eigenvector, $e^{+ i H t_{0} / T}$ has eigenvalue $e^{i λ t_{0} / T} = e^{2 π i θ}$ , where $θ$ is the unique representative of $λ t_{0} / (2 π T)$ modulo $1$ in $[0, 1)$ . Each controlled power has eigenphase $λ 2^{j} t_{0} / T$ , so phase estimation encodes this same phase modulo one.

3.1givenF4step 1.1step 2.1algebra∎

Since $T \geq 8 (t_{0} + 1)$ , $∣ λ t_{0} / T ∣ \leq t_{0} / T < 1 / 8 < π$ by [F4]. Thus the centered representative of the phase angle is exactly $λ t_{0} / T$ , with no alias by a multiple of $2 π$ . Centered decoding gives the stated signed integer $k$ and adjacent eigenvalue grid values differ by $2 π / t_{0}$ .

LemmaStatement: Literature-sourcedProof: AI-generatedOpen item page →

Finite capped amplification succeeds with a supplied lower bound

Statement

Let a unitary flagged preparation $V$ have well probability $p \geq p_{0} : = 1 / (16 κ^{2})$ , $κ \geq 1$ , and exact inverse access. Set $K = ⌈ 4 κ ⌉$ , $R = ⌈ 16 \ln (1 / ρ) ⌉ + 16$ for $0 < ρ < 1$ . In each of $R$ fresh rounds, draw $b = ⌈ \log_{2} K ⌉$ uniform bits; reject the round without queries if the resulting integer $j \geq K$ , and otherwise run $j$ amplitude-amplification iterations from $V ∣ 0 ⟩$ , then verify the well flag. The probability that all rounds fail is at most $ρ$ . The conditional well state in every successful round is the same pure-state ray as the normalized well component of $V ∣ 0 ⟩$ . The total number of $V, V^{†}$ calls is at most $2 R K$ .

Facts & Assumptions

Given: A fixed unitary state preparation, its inverse, and an orthogonal well-flag projection.

[F1]

Amplitude-amplification invariant plane: the initial good and bad components span an invariant plane for the amplification iterate.

[F2]

Exact success probability after amplitude amplification: if $p = \sin^{2} θ$ , after $j$ rounds the success probability is $\sin^{2} ((2 j + 1) θ)$ .

[F3]

Amplitude amplification with a fixed integer iteration count: one iterate consists of the supplied preparation, its inverse, and the two declared reflections.

[F4]

Inverse Unitary Access: every inverse call is an explicitly supplied access with a separately chargeable cost.

[F5]

Sine chord and linear bounds: $\sin v \geq 2 v / π$ for $0 \leq v \leq π / 2$ .

[F6]

The addition formulas for sine and cosine and Double-angle and quadratic power-reduction identities: sine addition gives $\sin (a + b) - \sin (a - b) = 2 \cos (a) \sin (b)$ , and the double-angle formulas give $\sin^{2} x = (1 - \cos (2 x)) / 2$ and $\cos^{2} x = (1 + \cos (2 x)) / 2$ .

[F7]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\ln x = \int_{1}^{x} d t / t$ for $x > 0$ .

Proof

1.1givenF2F5F6algebra

For $0 < \sin (2 ϕ)$ , the addition identity in [F6] gives $\sin ((4 j + 4) ϕ) - \sin (4 j ϕ) = 2 \cos ((4 j + 2) ϕ) \sin (2 ϕ)$ . Summing over $j = 0, \dots, K - 1$ telescopes, so $\sum_{j} \cos ((4 j + 2) ϕ) = \sin (4 K ϕ) / (2 \sin (2 ϕ))$ . The double-angle identities in [F6] therefore give $\sum_{j = 0}^{K - 1} \sin^{2} ((2 j + 1) ϕ) = K / 2 - \sin (4 K ϕ) / (4 \sin (2 ϕ))$ , and the corresponding cosine-square sum has a plus sign. Here the denominators are positive except at the separately treated endpoint $p = 1$ . Put $θ = \arcsin \sqrt{p}$ . For $p \leq 1 / 2$ , $\sin (2 θ) = 2 \sqrt{p (1 - p)} \geq \sqrt{2 p} \geq 1 / (2 \sqrt{2} κ)$ . The finite sine-square identity from [F6] gives average success $\frac{1}{K} \sum_{j = 0}^{K - 1} \sin^{2} ((2 j + 1) θ) = \frac{1}{2} - \frac{\sin (4 K θ)}{4 K \sin (2 θ)} \geq \frac{1}{2} - \frac{1}{4 K \sin (2 θ)} \geq \frac{1}{2} - \frac{1}{4 \sqrt{2}} > \frac{1}{4} .$ For $1 / 2 < p < 1$ , put $θ^{'} = π / 2 - θ \in [0, π / 4)$ . The cosine-square version of [F6] gives average success $\frac{1}{2} + \frac{\sin (4 K θ^{'})}{4 K \sin (2 θ^{'})}$ . If its sine numerator is nonnegative this is at least $1 / 2$ . If it is negative, then $4 K θ^{'} > π$ , and [F5] gives $\sin (2 θ^{'}) \geq 4 θ^{'} / π$ , so the magnitude of the fraction is at most $π / (16 K θ^{'}) < 1 / 4$ . The average is again greater than $1 / 4$ . At $p = 1$ , every iteration succeeds. Thus uniform accepted $j$ has average success at least $1 / 4$ for every $p \geq p_{0}$ .

2.1givenF7step 1.1algebra

Since $K \leq 2^{b} < 2 K$ , the random-bit draw is accepted with probability $K / 2^{b} > 1 / 2$ and, conditioned on acceptance, is uniform on ${0, \dots, K - 1}$ . Each fresh round therefore succeeds with probability at least $1 / 8$ . Independence of fresh preparation, bits and verification gives total failure at most $(7 / 8)^{R} \leq e^{- R / 8}$ , since [F7] gives $\ln (8 / 7) = \int_{1}^{8 / 7} d t / t \geq (1 / 7) (7 / 8) = 1 / 8$ and $R \geq 16 \ln (1 / ρ)$ . Therefore the failure is at most $e^{- 2 \ln (1 / ρ)} = ρ^{2} \leq ρ$ .

3.1F1F2F3F4step 2.1algebra∎

At most $K - 1$ iterations occur in one round, each using one $V$ and one $V^{†}$ besides the initial $V$ ; hence each call count is at most $R K$ , and their sum is at most $2 R K$ . The good component remains collinear by [F1, F3]; its scalar rotation coefficient may be negative, but every positive-probability well branch therefore has the same pure-state ray as the normalized initial well component.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

HHL finite sine-window phase-estimation algorithm

Definition

Input a self-adjoint $H$ with $∥ H ∥ \leq 1$ , a unit input state $∣ b ⟩$ supported only on eigenvalues satisfying $1 / κ \leq ∣ λ ∣ \leq 1$ , and a supplied finite exact representation of the cutoff $κ \geq 1$ that supports certified arithmetic and rational comparisons. Supply costed $B, B^{†}$ and controlled/inverse simulation access as in HHL state-preparation and simulation access model. The accuracy and failure inputs are exact rational values $ϵ = p_{ϵ} / q_{ϵ}$ and $ρ = p_{ρ} / q_{ρ}$ , with positive binary-encoded integers and $0 < p_{ϵ} \leq q_{ϵ}$ , $0 < p_{ρ} < q_{ρ}$ . Rectangular systems $A : C^{n} \to C^{m}$ use Hermitian dilation for a rectangular linear system: choose a supplied rational scale $Λ \geq ∥ H_{A} ∥$ , use $H = H_{A} / Λ$ , and set $κ = Λ / γ$ from the QLSP support gap $γ$ . The QLSP definition supplies $σ_{j} \geq γ$ whenever the left singular coefficient of $b$ is nonzero; the dilation eigenvalues on this input support are $\pm σ_{j} / Λ$ , so $1 / κ \leq ∣ λ ∣ \leq 1$ . On $(C^{m} \otimes W) \oplus (C^{n} \otimes W)$ prepare the normalized codomain-supported input $(b / ∥ b ∥, 0)$ with the tagged preparation $B_{A} : = B \oplus I_{C^{n} \otimes W}$ . Implement its $B$ block with the supplied tag-controlled form of $B$ and charge that controlled preparation cost. The QLSP promise $b \in ran (A)$ removes the kernel component, and the output is tagged in the domain summand. All parameter comparisons, reversible arithmetic and finite-precision synthesis use the separately charged routines in the access model. The algorithm is the finite OP5 program:

Apply the supplied $B$ (or $B_{A}$ for a rectangular system) to prepare the input and its fixed work state, set $t_{0} = 2048 κ / ϵ$ , choose the least power of two $T \geq 8 (t_{0} + 1)$ by certified comparisons, and let $L = \log_{2} T$ . Initialize the phase register to $∣ 0^{L} ⟩$ in big-endian order $q_{L - 1} \dots q_{0}$ . This carrier chooses OP5's explicit table variant for preparing Finite sine-window phase state. Build the complete binary prefix tree on the $T$ leaves. At each level $ℓ = 0, \dots, L - 1$ and for each interval node $[a, b)$ at that level, put $m = (a + b) / 2$ and compute the child masses $W_{T} (a, m)$ and $W_{T} (m, b)$ from the formula in Sine-window normalization and positive prefix weights. Store $r = W_{T} (a, m) / W_{T} (a, b)$ and apply $R_{y} (2 \arcsin \sqrt{r})$ to wire $q_{L - 1 - ℓ}$ , controlled on the preceding $ℓ$ wires matching the path to $[a, b)$ ; encode bit $1$ as the left child and bit $0$ as the right child. The root has no controls. Thus the ideal circuit prepares $∣ Ψ_{T} ⟩$ by Operator error for the finite sine-prefix rotation table. Put $ϵ_{Ψ} = ϵ / (4096 κ)$ . Each nonempty mass is at least $T^{- 2}$ by Sine-window normalization and positive prefix weights. Use certified interval arithmetic with absolute mass error at most $ϵ_{Ψ}^{2} / (10^{6} L^{2} T^{4})$ ; refine until each stored angle and its finite gate synthesis together give controlled-rotation operator error at most $ϵ_{Ψ} / (100 T)$ . The cases $r = 0$ and $r = 1$ use the identity and $π$ rotations, respectively. Store each other angle with at least $⌈ \log_{2} (100 π T / ϵ_{Ψ}) ⌉ + 2$ bits. There are $T - 1$ rotations; Operator error for the finite sine-prefix rotation table bounds their total operator error by $ϵ_{Ψ} / 100$ from the displayed combined per-node operator tolerance. The table contains $O (T \log (T / ϵ_{Ψ}))$ bits and $T - 1$ controlled rotations. Charge its one-time construction/data cost $G_{Ψ} (T, ϵ_{Ψ})$ and each forward/inverse preparation cost $C_{Ψ} (T, ϵ_{Ψ})$ from HHL state-preparation and simulation access model, including reversible lookup, control and finite gate synthesis. Thus the sine-preparation unitary and its inverse each have operator error at most $ϵ_{Ψ}$ ; this variant pays linear-in- $T$ table and rotation resources rather than assuming a loaded amplitude table.
In either the original full-space or alternative clean-workspace simulation mode, initialize all simulator work in zero and retain it coherently. For $j = 0, \dots, L - 1$ , set $t_{j} = 2^{j} t_{0} / T$ and allocate $η_{j} = ϵ / (8192 κ L)$ to both its forward controlled call $S_{H} (t_{j}, η_{j})$ and its reverse call. Apply $S_{H} (t_{j}, η_{j})$ to the system controlled on wire $q_{j}$ being $1$ , and act as identity on its $0$ branch. In the declared order $q_{L - 1} \dots q_{0}$ , a phase label $τ$ has bits $x_{j}$ with $τ = \sum_{j = 0}^{L - 1} 2^{j} x_{j}$ , so the ideal controlled list applies $e^{+ i H τ t_{0} / T}$ . Apply the negative-sign QFT, decode $y$ to signed $k = y$ for $y < T / 2$ and $k = y - T$ otherwise, and set $\tilde{λ} = 2 π k / t_{0}$ . The total forward evolution time is $\sum_{j < L} t_{j} = t_{0} (1 - 1 / T) < t_{0}$ , and the sum of the $2 L$ simulation error allocations is $ϵ / (4096 κ)$ . This uses the signed convention in Signed phase decoding has no alias on the promised spectrum.
Reversibly compute the flag angles and sign from $\tilde{λ}$ using Odd-well and even-ill reciprocal filter. Use the two-qubit computational basis $∣ q_{1} q_{0} ⟩$ with labels $∣ n o t h i n g ⟩ = ∣ 00 ⟩$ , $∣ w e l l ⟩ = ∣ 01 ⟩$ , $∣ i l l ⟩ = ∣ 10 ⟩$ , and unused label $∣ 11 ⟩$ . Write $p = ∣ f_{κ} (\tilde{λ}) ∣$ , $r = \sqrt{1 - p^{2}}$ , $α = 2 \arcsin p$ , and $β = 2 \arcsin (g_{κ} (\tilde{λ}) / r)$ . These are defined at every decoded grid point because The reciprocal filter defines valid three-outcome amplitudes gives $p \leq 1 / 2$ , $0 \leq g \leq 1 / 2$ , and $r \geq \sqrt{3} / 2$ , so $g / r \leq 1 / \sqrt{3} < 1$ . First apply $R_{y} (α)$ to $q_{0}$ conditioned on $q_{1} = 0$ , acting as identity on the $q_{1} = 1$ subspace. Next apply $R_{y} (β)$ to $q_{1}$ conditioned on $q_{0} = 0$ , acting as identity on the $q_{0} = 1$ subspace. Here $R_{y} (θ) = \exp (- i θ Y / 2)$ with the exact convention and unitary formula of Exact one-qubit gates and rotations and Pauli formula for an axis rotation. Finally apply $D_{s} = diag (1, s, 1, 1)$ in the ordered flag basis, where $s = - 1$ if $\tilde{λ} < 0$ and $s = + 1$ otherwise (in particular at zero, where $f_{κ} (0) = 0$ ). The resulting full flag unitary is $D_{s} G_{02} (β) G_{01} (α)$ : the two conditional rotations act as $R_{y}$ on the indicated two-label subspaces and as identity on their orthogonal complements, and $D_{s}$ is diagonal unitary. All three factors fix the unused label $∣ 11 ⟩$ . On $∣ 00 ⟩$ the product gives $h (\tilde{λ}) ∣ 00 ⟩ + f_{κ} (\tilde{λ}) ∣ 01 ⟩ + g_{κ} (\tilde{λ}) ∣ 10 ⟩$ , since $\cos (β / 2) = h / r$ and $\sin (β / 2) = g / r$ . Uncompute the arithmetic. Synthesize the phase-controlled map with uniform operator error at most $η_{R} : = ϵ / (4096 κ)$ , charged through $C_{f l a g}$ and $C_{a r i t h}$ .
Reverse the QFT, every actual controlled simulation circuit, and sine preparation, retaining the flag and all simulator work. In clean-workspace mode the ideal trajectory has this work in zero; Unitary hybrids on a preserved clean-work subspace bounds the complete attempt on that ideal trajectory without assuming actual intermediate work is clean. This gives a unitary flagged preparation $V$ and its exact circuit inverse $V^{†}$ . Let $Π_{g o o d}$ be the well-flag projection in Hermitian mode and the product of the well-flag projection and tagged domain projection in rectangular mode; these two projections act on distinct registers and commute. Let $p = ∥ Π_{g o o d} V ∣ 0 ⟩ ∥^{2}$ . Apply the finite capped amplification procedure proved in Finite capped amplification succeeds with a supplied lower bound with success projection $Π_{g o o d}$ , lower bound $p_{l o w} = 1 / (16 κ^{2})$ and failure target $ρ$ . Its success reflection and verification test both the well flag and the domain tag in rectangular mode; charge their actual costs to $C_{r e f}$ and $C_{v e r}$ . Measure ${Π_{g o o d}, I - Π_{g o o d}}$ and return the conditional state, tagged output and success bit on success; return FAIL otherwise.

The circuit uses no uniform-register phase-tail estimate: its phase distribution is the sine-window kernel proved in Second moment of the signed sine-window phase kernel. Its $G_{Ψ}, C_{Ψ}, C_{s i m}, C_{Q F T}^{+ / -}, C_{f l a g}$ , reflection, verification and $B / B^{†}$ costs remain separate inputs.

LemmaStatement: Literature-sourcedProof: AI-generatedOpen item page →

Ideal inverse amplitude and HHL postselection probability

Statement

For the ideal exact-eigenvalue version of HHL finite sine-window phase-estimation algorithm, on a normalized $∣ b ⟩$ supported on $1 / κ \leq ∣ λ ∣ \leq 1$ , the well-flag vector is $v = (2 κ)^{- 1} H^{+} ∣ b ⟩$ . Its probability $p = ∥ v ∥^{2}$ satisfies $1 / (4 κ^{2}) \leq p \leq 1 / 4$ , and its normalized state is the QLSP target.

Facts & Assumptions

Given: A self-adjoint $H$ , a normalized $∣ b ⟩$ , and the support promise.

[F1]

[F2]

The Moore--Penrose pseudoinverse $A^{+}$ as the solution of the four Penrose equations and Every finite real or complex matrix has a unique Moore--Penrose pseudoinverse: the pseudoinverse is the unique matrix satisfying $H H^{+} H = H$ , $H^{+} H H^{+} = H^{+}$ , and self-adjointness of $H H^{+}$ and $H^{+} H$ .

[F3]

Odd-well and even-ill reciprocal filter: on the supported spectrum $f_{κ} (λ) = 1 / (2 κ λ)$ and $g_{κ} (λ) = 0$ .

[F4]

Quantum linear-systems state-output task: the target is the normalized pseudoinverse action on the supported input.

[F5]

The adjoint $T^{*} : W \to V$ is characterised by $⟨ T v, w ⟩_{W} = ⟨ v, T^{*} w ⟩_{V}$ and Dirac Notation Conversion: $⟨ H x, y ⟩ = ⟨ x, H^{*} y ⟩$ , and the root inner product is linear in its first argument and conjugate-linear in its second.

Proof

1.1F1F2F5algebra

In the eigenbasis from [F1], if $H u_{j} = λ_{j} u_{j}$ , self-adjointness and [F5] give $λ_{j} ∥ u_{j} ∥^{2} = ⟨ H u_{j}, u_{j} ⟩ = ⟨ u_{j}, H^{*} u_{j} ⟩ = ⟨ u_{j}, H u_{j} ⟩ = \overline{λ_{j}} ∥ u_{j} ∥^{2},$ so every $λ_{j}$ is real. Define $G u_{j} = λ_{j}^{- 1} u_{j}$ for $λ_{j} \neq 0$ and $G u_{j} = 0$ for $λ_{j} = 0$ . Diagonal multiplication gives $H G H = H$ , $G H G = G$ , and $H G = G H$ equal to the orthogonal projection onto the nonzero-eigenvalue span; both products are self-adjoint. Thus $G$ satisfies [F2], and uniqueness gives $H^{+} = G$ .

2.1F1F3F4step 1.1algebra

Expand $∣ b ⟩ = \sum_{j} β_{j} ∣ u_{j} ⟩$ in [F1], with $\sum_{j} ∣ β_{j} ∣^{2} = 1$ . Put $J = {j : β_{j} \neq 0}$ ; then $\sum_{j \in J} ∣ β_{j} ∣^{2} = 1$ and every $j \in J$ has $1 / κ \leq ∣ λ_{j} ∣ \leq 1$ , so [F3] multiplies it by $(2 κ λ_{j})^{- 1}$ . Step 1.1 therefore gives the well vector $v = \sum_{j \in J} β_{j} (2 κ λ_{j})^{- 1} ∣ u_{j} ⟩ = (2 κ)^{- 1} H^{+} ∣ b ⟩$ . Its normalization is the state in [F4].

3.1step 2.1algebra∎

Orthonormality gives $p = \sum_{j \in J} ∣ β_{j} ∣^{2} / (4 κ^{2} ∣ λ_{j} ∣^{2})$ . For $j \in J$ , $1 \leq ∣ λ_{j} ∣^{- 1} \leq κ$ , so each weight factor lies in $[1 / (4 κ^{2}), 1 / 4]$ . Their convex average lies in the same interval, proving $1 / (4 κ^{2}) \leq p \leq 1 / 4$ .

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

HHL capped postselection amplification cost

Statement

For the OP5 HHL attempt with $p \geq 1 / (16 κ^{2})$ and failure target $0 < ρ < 1$ , the capped schedule uses at most $2 R K = O (κ (1 + \log (1 / ρ)))$ calls in total to $V$ and $V^{†}$ , where $K = ⌈ 4 κ ⌉$ and $R = ⌈ 16 \ln (1 / ρ) ⌉ + 16$ . Thus it uses $O (κ (1 + \log (1 / ρ)))$ calls to the supplied preparation form (the tagged $B_{A}$ in dilation mode) and separately to its inverse, multiplied by their actual supplied costs.

Facts & Assumptions

Given: OP5 access costs and the lower success bound.

[F1]

Finite capped amplification succeeds with a supplied lower bound: each round uses at most $K$ calls to $V$ and at most $K$ calls to $V^{†}$ , over $R$ rounds.

[F2]

HHL finite sine-window phase-estimation algorithm: each $V$ contains one call to the supplied preparation form and each $V^{†}$ one call to its inverse. In rectangular mode this form is the tagged $B_{A}$ from the Definition, and its controlled/gate cost is the actual declared cost for that access.

[F3]

Circuit-family and computation cost model: sequential costs add and every inverse or controlled access has its own declared cost.

Proof

1.1F1algebra

By [F1], the total number of preparation and inverse-preparation calls is bounded separately by $R K$ each. Since $K = ⌈ 4 κ ⌉ \leq 5 κ$ for $κ \geq 1$ and $R \leq 16 \ln (1 / ρ) + 17$ , each count is $O (κ (1 + \log (1 / ρ)))$ with an absolute constant.

2.1F2F3step 1.1algebra∎

Each preparation call invokes the supplied preparation form once, and each inverse preparation invokes its actual inverse once by [F2]. Their circuit/query/gate costs therefore multiply the two counts separately and add by [F3]. No call to a controlled form, simulator, reflection, or verifier is included unless it appears in the declared circuit.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

HHL cost under direct controlled-simulation access

Statement

Let $L = \log_{2} T$ , $t_{j} = 2^{j} t_{0} / T$ , $K = ⌈ 4 κ ⌉$ , and $R = ⌈ 16 \ln (1 / ρ) ⌉ + 16$ . The capped HHL circuit uses at most $R K$ calls to each of $V$ and $V^{†}$ , at most $R K$ calls to each supplied preparation form (the tagged $B_{A}$ in dilation mode) and its inverse, and one table construction $G_{Ψ} (T, ϵ_{Ψ})$ . Each $V$ or $V^{†}$ contains two sine-table preparation/unpreparation circuits, one forward and one inverse QFT, the flag circuit, and $2 L$ controlled simulation calls at signed times $\pm t_{j}$ ; its absolute evolution times sum to less than $2 t_{0}$ . Therefore the total absolute simulation time is less than $4 R K t_{0} = O (κ^{2} ϵ^{- 1} (1 + \log (1 / ρ)))$ . More precisely, the simulation charge is the actual sum over all $V, V^{†}$ calls of $\sum_{j < L} (C_{s i m} (t_{j}, η_{j}) + C_{s i m} (- t_{j}, η_{j}))$ . The remaining charge is $G_{Ψ} (T, ϵ_{Ψ}) + n_{V} C_{B} + n_{V^{†}} C_{B^{†}} + 2 (n_{V} + n_{V^{†}}) C_{Ψ} (T, ϵ_{Ψ}) + (n_{V} + n_{V^{†}}) (C_{Q F T}^{+} (T) + C_{Q F T}^{-} (T) + C_{f l a g} (κ, η_{R}) + C_{a r i t h} (T, κ, ϵ)) + N_{r e f} C_{r e f} + N_{v e r} C_{v e r},$ where $n_{V}, n_{V^{†}} \leq R K$ and $N_{r e f}, N_{v e r}$ are the actual reflection and verification counts. The table itself has $O (T \log (T / ϵ_{Ψ}))$ data bits and $T - 1$ 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.

[F1]

HHL finite sine-window phase-estimation algorithm: the attempt uses the signed times $t_{j} = 2^{j} t_{0} / T$ , reverses each phase and prepares/unprepares the sine table.

[F2]

Finite capped amplification succeeds with a supplied lower bound: at most $R K$ calls are made in each direction.

[F3]

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 $B_{A}$ in dilation mode), QFT, table, reflection, verifier, and gate resources are separate additive cost coordinates.

Proof

1.1F1F2algebra

The geometric sum of forward times is $\sum_{j = 0}^{L - 1} 2^{j} t_{0} / T = (T - 1) t_{0} / T < t_{0}$ . The reverse list has the same absolute times, so one $V$ or $V^{†}$ call uses less than $2 t_{0}$ . By [F2], there are at most $R K$ calls in each direction, giving total absolute time below $4 R K t_{0}$ . Since $K \leq 5 κ$ , $R \leq 16 \ln (1 / ρ) + 17$ , and $t_{0} = 2048 κ / ϵ$ , the stated order follows.

2.1F1F3step 1.1algebra∎

Each $V$ or $V^{†}$ 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 $G_{Ψ}$ is generated once, and every B, inverse B, reflection, and verifier use is counted in its own coordinate.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Normalization is stable under a small flagged-vector error

Statement

Let $v$ be an ideal flagged vector with $∥ v ∥ \geq 1 / (2 κ)$ . If $0 < ϵ \leq 1$ and either $∥ u - v ∥ \leq ϵ / (8 κ)$ or $∥ u - v ∥ \leq (9 ϵ / 100) ∥ v ∥$ , then $u \neq 0$ and $∥ u / ∥ u ∥ - v / ∥ v ∥ ∥ \leq ϵ$ .

Facts & Assumptions

Given: The two vectors and the stated lower and error bounds.

[F1]

Ideal inverse amplitude and HHL postselection probability: the ideal well vector has norm at least $1 / (2 κ)$ .

[F2]

The inner-product norm is definite, homogeneous, and satisfies the triangle inequality: $∥ x + y ∥ \leq ∥ x ∥ + ∥ y ∥$ ; applying it to $u = (u - v) + v$ and $v = (v - u) + u$ gives $∣ ∥ u ∥ - ∥ v ∥ ∣ \leq ∥ u - v ∥$ .

Proof

1.1givenF1F2algebra

Under the absolute-error alternative, the reverse triangle inequality from [F2] gives $∥ u ∥ \geq ∥ v ∥ - ∥ u - v ∥ \geq (1 / 2 - 1 / 8) / κ = 3 / (8 κ) > 0$ . Under the relative alternative, $∥ u ∥ \geq (1 - 9 ϵ / 100) ∥ v ∥ > 0$ because $9 ϵ / 100 < 1$ . Thus both normalizations exist.

2.1givenF1F2step 1.1algebra∎

Add and subtract $u / ∥ v ∥$ and use [F2]: $∥ \frac{u}{∥ u ∥} - \frac{v}{∥ v ∥} ∥ \leq \frac{∣ ∥ v ∥ - ∥ u ∥ ∣}{∥ v ∥} + \frac{∥ u - v ∥}{∥ v ∥} \leq \frac{2 ∥ u - v ∥}{∥ v ∥} .$ The absolute alternative makes this at most $2 (ϵ / (8 κ)) / (1 / (2 κ)) = ϵ / 2$ . The relative alternative makes it at most $18 ϵ / 100 < ϵ$ .

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

OP5 HHL returns the QLSP state within the requested error

Statement

Under the promises and precision allocations in HHL finite sine-window phase-estimation algorithm, let $u = Π_{g o o d} V ∣ 0 ⟩$ be the actual joint success vector for one prepared attempt, where rectangular-mode success includes the domain-tag projection. Write $v_{s y s} = (2 κ)^{- 1} H^{+} ∣ b ⟩$ and $v = v_{s y s} \otimes ∣ g_{B} ⟩ \otimes ∣ 0_{a l g} ⟩ \otimes ∣ w e l l ⟩$ for the ideal joint vector, including the unchanged preparation work and clean algorithmic registers. For $0 < ϵ \leq 1$ and $0 < ρ < 1$ , the conditional returned joint pure-state ray (including unchanged preparation work) has a unit representative within vector norm $ϵ$ of the normalized QLSP target tensored with the preparation work, clean algorithmic registers and well flag, and the capped amplification returns FAIL with probability at most $ρ$ . The same assertion holds for the Hermitian dilation, with the output in its tagged domain summand.

Facts & Assumptions

Given: The OP5 algorithm, a normalized input supported on $1 / κ \leq ∣ λ ∣ \leq 1$ , and the stated ideal simulator and circuit-error contracts.

[F1]

Ideal inverse amplitude and HHL postselection probability: $v_{s y s} = (2 κ)^{- 1} H^{+} ∣ b ⟩$ and $∥ v_{s y s} ∥ \geq 1 / (2 κ)$ ; tensoring the unit work, clean-register and well-flag factors gives $∥ v ∥ = ∥ v_{s y s} ∥$ .

[F2]

Second moment of the signed sine-window phase kernel: conditional on each eigenvalue, the signed kernel obeys $E δ^{2} < 300$ .

[F3]

Relative stability of the HHL filter on supported eigenvalues: the well/ill flag-amplitude perturbation is at most $10 κ ∣ δ ∣ / t_{0}$ times the ideal well amplitude.

[F4]

Finite capped amplification succeeds with a supplied lower bound: probability at least $1 - ρ$ of a verified well outcome, and its normalized good component is preserved.

[L1]

Normalization is stable under a small flagged-vector error: relative flagged-vector error at most $9 ϵ / 100$ gives normalized-vector error at most $ϵ$ .

[F5]

HHL finite sine-window phase-estimation algorithm: the forward and actual inverse simulation calls have total full-space operator error, or total clean-input isometry error in the alternative mode, at most $ϵ / (4096 κ)$ and the flag rotation has operator error at most this amount.

[F6]

Operator error for the finite sine-prefix rotation table: the sine preparation and its inverse each have operator error at most $ϵ_{Ψ} = ϵ / (4096 κ)$ .

[F7]

Unitary hybrids on a preserved clean-work subspace accumulates local clean-input errors along the ideal all-clean workspace trajectory, including actual adjoints, controls and reference systems.

[F8]

Hermitian dilation for a rectangular linear system: $H_{A}^{+} (b, 0) = (0, A^{+} b)$ . For $H = H_{A} / Λ$ , $Λ > 0$ , the diagonal Penrose construction gives $H^{+} (b, 0) = Λ (0, A^{+} b)$ . Thus the ideal well vector is fixed by the domain-tag projection.

Proof

1.1F1F2F3algebra

First take the exact sine preparation, exact simulations and exact flag rotation. Before reversing phase estimation, different decoded labels are orthogonal. For a fixed eigenvalue $λ$ , the well-flag projection keeps only the $f_{κ}$ coordinate, so the squared error is $\sum_{y} p_{y} (λ) ∣ f_{κ} ({\tilde{λ}}_{y}) - f_{κ} (λ) ∣^{2} \leq \sum_{y} p_{y} (λ) ∥ m ({\tilde{λ}}_{y}) - m (λ) ∥_{2}^{2} .$ By [F2] and [F3], this is at most $(10 κ / t_{0})^{2} 300 ∣ f_{κ} (λ) ∣^{2}$ . Summing with the eigenbasis weights shows that the exact-kernel well vector differs from $v$ by at most $(10 \sqrt{300} κ / t_{0}) ∥ v ∥$ . Reversing the phase transform is unitary and preserves this norm bound.

2.1F1F5F6F7F8step 1.1algebra

Replacing the exact preparation, simulations and flag map by their implementations changes the attempt on its clean initial input by at most the sum of their norm errors. In the full-space mode this is ordinary unitary telescoping; in the clean-workspace mode [F7] applies because all ideal other gates leave simulator work untouched and ideal simulations return it to zero. The actual intermediate work need not be clean. In either mode the sum consists of two sine-table preparation uses, the total forward/reverse simulation budget, and one flag map, at most $4 ϵ / (4096 κ)$ . The success projection is contractive and fixes $v$ : in rectangular mode this follows from [F8], and otherwise it is just the well flag. Applying it to both the exact-kernel comparison and the implementation error therefore gives $\frac{∥ u - v ∥}{∥ v ∥} \leq \frac{10 \sqrt{300} κ}{t_{0}} + \frac{4 ϵ / (4096 κ)}{1 / (2 κ)} < (\frac{180}{2048} + \frac{1}{512}) ϵ < 0.09 ϵ = : q,$ using $t_{0} = 2048 κ / ϵ$ and $\sqrt{300} < 18$ . Hence $∥ u ∥ \geq (1 - q) ∥ v ∥ > 1 / (4 κ)$ and the implemented well probability exceeds $1 / (16 κ^{2})$ .

3.1F1F4F8L1step 2.1algebra∎

The exact filter on supported eigenvalues is $v = (2 κ)^{- 1} H^{+} ∣ b ⟩$ , so $v / ∥ v ∥$ is the target. The normalization inequality in [L1] applies because step 2.1 gives relative error below $0.09 ϵ$ : directly, $∥ u / ∥ u ∥ - v / ∥ v ∥ ∥ \leq 2 q / (1 - q) < ϵ$ . By [F4], every successful amplified branch is the same ray as $u / ∥ u ∥$ ; choose the representative $u / ∥ u ∥$ to obtain the stated distance. The preparation work factors as $∣ g_{B} ⟩$ and is untouched by the HHL circuit; the ideal uncomputation leaves the other algorithmic registers zero and the measured flag in $∣ w e l l ⟩$ . Tensoring these unit vectors does not change any norm above. For a rectangular map with $H = H_{A} / Λ$ and $Λ > 0$ , Hermitian dilation for a rectangular linear system gives $H_{A}^{+} (b, 0) = (0, A^{+} b)$ ; the singular values of the scaled dilation are $σ_{j} / Λ$ , so $H^{+} (b, 0) = Λ (0, A^{+} b)$ . This positive scalar cancels on normalization, leaving the ideal QLSP ray in the tagged domain summand. The actual successful vector $u$ also lies in that summand because $Π_{g o o d}$ includes its domain projection. Tracing out work gives the corresponding output density state.

TheoremStatement: AI-adaptedProof: AI-generatedOpen item page →

HHL sparse-query and state-preparation cost

Statement

With the exact sorted QA20 XOR location/value interface and separately supplied uniform preparation, value-decoding, flag arithmetic and the certified QA25 phase-generation mode, the sparse-oracle specialization is: for a $d$ -sparse Hermitian instance with $∥ H ∥ \leq 1$ , supported gap $1 / κ$ , and target state error $ϵ$ , the phase-estimation HHL method uses $O (d κ^{2} ϵ^{- 1} polylog (2 + d κ / ϵ))$ sparse-row/value queries and $O (κ (1 + \log (1 / ρ)))$ calls to $B$ and separately to $B^{†}$ , multiplied by their supplied costs. For fixed constant $ρ$ , this specializes to the displayed query order without an additional failure logarithm; for variable $ρ$ , include the factor $1 + \log (1 / ρ)$ . Arithmetic, gate/bit time, phase generation, uniform preparation, reflections and the OP5 sine table remain separately charged; the displayed asymptotic concerns sparse-oracle calls. Padding to the register of the sorted-access construction extends $H$ by zero, and the supplied input preparation remains supported on the original labels. Under direct simulation access, the simulator contribution is instead the explicit sum in HHL cost under direct controlled-simulation access.

Facts & Assumptions

Given: The finite OP5 parameters, exact sorted sparse access, norm/gap promise, and separately charged operations in the Statement.

[F1]

Clean sparse-state preparation from sorted XOR locations constructs an exact block encoding of $H \oplus 0$ with normalization $d$ by taking entry bound $h = 1$ , using $O (\log (d + 1))$ location calls and $O (1)$ value calls per encoding, adjoint or coherent control.

[F2]

Qubitization query and gate resources and Correctness of the small-time-aware simulator give clean-input simulation error at most $η$ and $O (d ∣ t ∣ + \log (1 / η))$ signal calls for each nontrivial signed time, with exact identity on the stated small-time branch. Classical phase generation and other gate costs are separate.

[F3]

Unitary hybrids on a preserved clean-work subspace supplies coherent-control, reference and actual-adjoint bounds and a hybrid along the ideal clean-work trajectory.

[F4]

HHL finite sine-window phase-estimation algorithm and HHL cost under direct controlled-simulation access give $t_{0} = 2048 κ / ϵ$ , $T$ the least power of two at least $8 (t_{0} + 1)$ , $L = \log_{2} T$ , $K = ⌈ 4 κ ⌉$ , $R = ⌈ 16 \ln (1 / ρ) ⌉ + 16$ , fewer than $2 t_{0}$ absolute simulation time per $V$ or $V^{†}$ , and at most $R K$ calls in each direction.

[F5]

OP5 HHL returns the QLSP state within the requested error gives the requested state and amplification success guarantee with the declared OP5 precision budgets, including clean-workspace simulation.

[F6]

Unitary and differential identities for finite matrix dynamics: $e^{+ i H t} = U_{H} (- t)$ is unitary and differentiable with derivative $i H e^{+ i H t}$ . With $∥ H ∥ \leq 1$ , the inner-product norm triangle inequality (The inner-product norm is definite, homogeneous, and satisfies the triangle inequality) gives $∥ e^{+ i H t} - e^{+ i H q} ∥_{o p} \leq ∣ t - q ∣$ by integrating the derivative on each unit vector and taking the operator-norm supremum.

[F7]

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: $∥ H ∥ \leq 1$ bounds $∥ H ψ ∥$ for every unit vector $ψ$ .

Proof

1.1givenF1algebra

Apply [F1] with $h = 1$ , valid because $∣ H_{i j} ∣ \leq ∥ H ∥ \leq 1$ . The extra padded system labels carry zero eigenvalues; the input remains in the original supported subspace, so its nonzero gap and inverse-state target do not change. The full unitary oracle circuits, controls and reversals act on all physical labels, including invalid labels, as constructed in [F1]; no padded-branch overlap contributes a matrix value.

2.1F2F3F4F5F6F7step 1.1algebra

Put $η = ϵ / (8192 κ L)$ . For each phase time $t_{j}$ , certified arithmetic selects a rational $q_{j} \in [0, t_{j}]$ with $t_{j} - q_{j} \leq η / 2$ and a rational simulator tolerance $ζ_{j}$ with $η / 4 \leq ζ_{j} \leq η / 2$ ; their construction cost remains in the separately charged arithmetic/phase-generation coordinates. Invoke QA25 at rational signed time $- q_{j}$ and tolerance $ζ_{j}$ . By [F2], its clean-input error from $e^{+ i H q_{j}}$ is at most $ζ_{j}$ , and by [F6]–[F7] the time-rounding error from $e^{+ i H t_{j}}$ is at most $t_{j} - q_{j}$ . Thus each effective forward call has clean-input error at most $η$ . Use its actual adjoint for the reverse call; [F3] gives the same clean-input error without assuming full-space accuracy on dirty inputs. The $2 L$ effective errors sum to $ϵ / (4096 κ)$ as required in OP5, so [F5] applies with the stated state and failure guarantees.

3.1F1F2F3F4step 2.1algebra

In one $V$ or $V^{†}$ , sum the loose signal-call bound in [F2] over all signed rational times $\pm q_{j}$ . Since $q_{j} \leq t_{j}$ , their absolute values sum to less than $2 t_{0}$ by [F4], so this uses $O (d t_{0} + L \log (32768 κ L / ϵ))$ signal calls; also $ζ_{j} \geq η / 4$ makes $\log (1 / ζ_{j}) = O (\log (1 / η))$ . Multiplying by [F1]'s location/value conversion and then by the at most $2 R K$ preparation/inverse-preparation calls gives $O ⁣ (R κ [d t_{0} + L \log (32768 κ L / ϵ)] \log (d + 1))$ sparse-oracle calls, with a possibly smaller constant value-query count. Literal reversals and coherent controls change only constants already covered by [F1]–[F3].

4.1givenF1F4F5step 3.1algebra∎

Since $T < 16 (t_{0} + 1)$ , $L = O (\log (2 + κ / ϵ))$ . With $d, κ \geq 1$ , $0 < ϵ \leq 1$ , and $t_{0} = 2048 κ / ϵ$ , the expression in step 3.1 is $O (d κ^{2} ϵ^{- 1} (1 + \log (1 / ρ)) polylog (2 + d κ / ϵ))$ . For fixed constant $ρ$ this gives the displayed order. The separate $B$ and $B^{†}$ counts are at most $R K$ each by [F4]. Padding only appends clean high index bits to their input/output register convention; no extra sparse query is needed for this embedding. Their actual implementation and any controls used remain charged as supplied costs. All other direct-simulation resource coordinates stay in [F4]'s explicit sum, so no table, phase-generation, gate or bit-time claim is inferred from the sparse-query bound.

5 · Examples, counterexamples and false statements

None yet.

Phase-Estimation Linear-System Algorithms

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Odd-well and even-ill reciprocal filter

Definition

Finite sine-window phase state

Definition

Hermitian dilation for a rectangular linear system

Statement

Facts & Assumptions

Proof

The reciprocal filter defines valid three-outcome amplitudes

Statement

Facts & Assumptions

Proof

Quantum linear-systems state-output task

Definition

Relative stability of the HHL filter on supported eigenvalues

Statement

Facts & Assumptions

Proof

Sine-window normalization and positive prefix weights

Statement

Facts & Assumptions

Proof

The QLSP target is nonzero

Statement

Facts & Assumptions

Proof

Operator error for the finite sine-prefix rotation table

Statement

Facts & Assumptions

Proof

HHL state-preparation and simulation access model

Definition

Second moment of the signed sine-window phase kernel

Statement

Facts & Assumptions

Proof

Signed phase decoding has no alias on the promised spectrum

Statement

Facts & Assumptions

Proof

Finite capped amplification succeeds with a supplied lower bound

Statement

Facts & Assumptions

Proof

HHL finite sine-window phase-estimation algorithm

Definition

Ideal inverse amplitude and HHL postselection probability

Statement

Facts & Assumptions

Proof

HHL capped postselection amplification cost

Statement

Facts & Assumptions

Proof

HHL cost under direct controlled-simulation access

Statement

Facts & Assumptions

Proof

Normalization is stable under a small flagged-vector error

Statement

Facts & Assumptions

Proof

OP5 HHL returns the QLSP state within the requested error

Statement

Facts & Assumptions

Proof

HHL sparse-query and state-preparation cost

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources