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.

Block-Encoding Linear Systems and Variable-Time Amplification — Examples

1 · Prerequisites

2 · Summary

The diagonal example gives an exact one-ancilla block encoding of $diag (1, 1 / 2)$ , a degree-one bounded odd polynomial with an explicit QSP phase list, its scalar error on the promised gap, two input-dependent success probabilities, and a finite Bernstein reciprocal certificate. The second example gives a three-stage stopping distribution, computes $T_{\max}$ , $T_{a v}$ , and $p_{s u c c}$ , then evaluates the cost expressions for a successful phase-certified fixed-time attempt and the variable-time profile. The arithmetic does not claim the variable-time expression is faster for every instance.

3 · Logical flowchart

4 · Definitions, theorems and proofs

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

Sparse diagonal block-encoded linear system

Example

Let $A = diag (1, 1 / 2)$ , $α = 1$ , $γ = δ = 1 / 2$ , and $∣ b ⟩$ be either basis vector. Take the exact one-ancilla block encoding $S = \sqrt{I - A^{2}} = diag (0, \sqrt{3} / 2), U = (\begin{array}{cc} A & S \\ S & - A \end{array}) .$ For the inverse target use the odd polynomial $p (x) = x / 2$ , degree one, and error $e = 1 / 4$ . A supplied real-QSVT extraction phase list is $Φ = (0, π / 3)$ together with its conjugate list $- Φ$ .

Facts & Assumptions

Given: The matrix, block, input states, $δ = 1 / 2$ , and the supplied phase lists specified in the Example.

[F1]

Finite block encoding: the block encoding is exact when the all-zero ancilla compression equals $A / α$ and the encoding unitary is unitary.

[F2]

QSP signal matrix and ordered phase sequence: $W_{R} (x) = (\begin{array}{cc} x & \sqrt{1 - x^{2}} \\ \sqrt{1 - x^{2}} & - x \end{array})$ and a degree-one sequence is $Z (ϕ_{0}) W_{R} (x) Z (ϕ_{1})$ with $Z (ϕ) = diag (e^{i ϕ}, e^{- i ϕ})$ .

[F3]

QSVT action on singular subspaces: the coherent $Φ / - Φ$ extraction has compressed block equal to the singular-value transform of the real part of the upper-left polynomial.

Verification

1.1givenF1algebra

The matrices $A, S$ are self-adjoint, commute, and satisfy $A^{2} + S^{2} = I$ . Thus $U^{*} = U$ and $U^{2} = (\begin{array}{cc} A^{2} + S^{2} & A S - S A \\ S A - A S & S^{2} + A^{2} \end{array}) = I$ . The all-zero ancilla compression of $U$ is its top-left block $A$ , so [F1] gives an exact $(1, 1, 0)$ block encoding.

1.2givenalgebra

The diagonal entries of $A$ are its singular values. Both inputs are supported on singular values at least $γ = 1 / 2$ , and $∥ A ∥_{o p} = α = 1$ , so $δ = γ / α = 1 / 2$ . For $x \in [1 / 2, 1]$ , $- x \leq 2 x^{2} - 1 \leq x$ because $2 x^{2} + x - 1 = (2 x - 1) (x + 1) \geq 0$ and $x - (2 x^{2} - 1) = (1 - x) (2 x + 1) \geq 0$ . Hence $∣ p (x) - δ / (2 x) ∣ = ∣ 2 x^{2} - 1 ∣ / (4 x) \leq 1 / 4$ . Also $p$ is odd, has degree one, satisfies $p (0) = 0$ , and $∣ p (x) ∣ \leq 1 / 2$ on $[- 1, 1]$ .

1.3givenF2F3algebra

For $Φ = (0, π / 3)$ , [F2] gives upper-left entry $e^{i π / 3} x$ ; the conjugate list gives $e^{- i π / 3} x$ . Their coherent real extraction is $\frac{1}{2} (e^{i π / 3} + e^{- i π / 3}) x = \frac{1}{2} x = p (x)$ by [F3]. Thus the exact response multipliers on the two singular vectors are $p (1) = 1 / 2$ and $p (1 / 2) = 1 / 4$ .

2.1F1F3step 1.2step 1.3algebra∎

For $∣ b ⟩ = ∣ 0 ⟩$ , the QSVT success probability is $∣ p (1) ∣^{2} = 1 / 4$ and the ideal inverse-block probability is $∣ (δ / 2) (1 / 1) ∣^{2} = 1 / 16$ . For $∣ b ⟩ = ∣ 1 ⟩$ , these probabilities are $∣ p (1 / 2) ∣^{2} = 1 / 16$ and $∣ (δ / 2) (1 / (1 / 2)) ∣^{2} = 1 / 4$ . Each successful state is the same basis vector as the normalized QLSP solution because the singular space is one-dimensional and both multipliers are positive. For the optional Bernstein reciprocal check, set $x = (1 + u) / 2$ for $0 \leq u \leq 1$ . Then the two polynomials are $\frac{1}{4} (2 x^{2} + x - 1) = \frac{1}{8} (3 u + u^{2})$ and $\frac{1}{4} (1 + x - 2 x^{2}) = \frac{1}{8} (2 - u - u^{2})$ , with degree-two Bernstein coefficient lists $(0, 3 / 16, 1 / 2)$ and $(1 / 4, 3 / 16, 0)$ . All coefficients are nonnegative, so the finite reciprocal certificate is valid.

ExampleConstruction: AI-adaptedVerification: AI-adaptedOpen item page →

Fixed-time and variable-time solver cost comparison

Example

Assume the fixed-time profile is a successful QSVT inverse attempt with its exact phase-product check passed and its total error below the supported-target threshold in QSVT inverse-state output and success cost. Compare its degree $m = 3$ and good weight $1 / 4$ to three orthogonal stopping branches at times $t_{1} = 1, t_{2} = 2, t_{3} = 4$ with stopping masses $p_{1} = 1 / 2, p_{2} = 1 / 3, p_{3} = 1 / 6$ . Within the first stopping subspace, let half its mass be good, so $p_{s u c c} = 1 / 4$ ; the other two subspaces are bad. One compatible branch vector is $(∣ 1, g ⟩ + ∣ 1, b ⟩) / 2 + ∣ 2, b ⟩ / \sqrt{3} + ∣ 3, b ⟩ / \sqrt{6}$ ; it has norm one, the $t_{1}$ branch is split equally between good and bad, and later stages leave already stopped labels fixed. The variable-time value below is only the production expression from the supplied-certificate regime of Variable-time amplitude-amplification theorem; this example supplies no certificate-construction cost $C_{b u i l d}$ .

Facts & Assumptions

Given: The fixed-time profile $m = 3$ , its good weight $1 / 4$ , and the three stopping times, branch masses, and good-output mass in the variable-time Example.

[F1]

Coherent variable-time algorithm model: $T_{a v} = (\sum_{i} p_{i} t_{i}^{2})^{1 / 2}$ and $T_{\max} = \max_{i} t_{i}$ .

[F2]

Variable-time amplitude-amplification theorem: under its supplied finite probability/schedule certificates, the production term is $O (T_{\max} \sqrt{\ln L_{T}} + (T_{a v} / \sqrt{p_{s u c c}}) (\ln L_{T})^{3 / 2})$ , in addition to $C_{b u i l d}$ , where $L_{T} = \max (2, T_{\max})$ . This example evaluates only that expression.

[F3]

QSVT inverse-state output and success cost: for a successful exact phase-product and total-error certificate, a QSVT attempt of degree $m$ and positive good probability $p_{i m p l}$ has expected amplified signal-query cost $O (m / \sqrt{p_{i m p l}})$ .

Verification

1.1givenF1algebra

The masses sum to $1 / 2 + 1 / 3 + 1 / 6 = 1$ , the maximum time is $T_{\max} = 4$ , and $T_{a v}^{2} = \frac{1}{2} \cdot 1^{2} + \frac{1}{3} \cdot 2^{2} + \frac{1}{6} \cdot 4^{2} = \frac{9}{2}$ , so $T_{a v} = 3 / \sqrt{2}$ . The ordinary mean stopping time is $\sum_{i} p_{i} t_{i} = 11 / 6$ , a different value.

2.1givenF1F2F3step 1.1algebra

The good mass is $p_{s u c c} = 1 / 4$ , so $1 / \sqrt{p_{s u c c}} = 2$ . For the fixed-time QSVT profile, [F3] gives $O (m / \sqrt{p_{s u c c}}) = O (3 \cdot 2) = O (6)$ . For the variable-time formula, $L_{T} = 4$ ; substituting [F1] into [F2] gives $O (4 \sqrt{\ln 4} + 3 \sqrt{2} (\ln 4)^{3 / 2})$ . This evaluates the two stated expressions for the specified distribution.

3.1F2F3step 2.1∎

Both expressions are asymptotic upper bounds with unspecified constants. The arithmetic above does not decide which implementation is faster at this finite instance or establish a universal speedup; the variable-time proof and OP6 resource fit remain separate.

Remarks

The qualified production bound and distinct uniform-floor implementation in Variable-time amplitude-amplification theorem provide context for this expression, rather than a proof premise of this finite arithmetic example. The example establishes the displayed substitutions and does not prove that general theorem.

5 · Examples, counterexamples and false statements

None yet.

Block-Encoding Linear Systems and Variable-Time Amplification — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Sparse diagonal block-encoded linear system

Example

Facts & Assumptions

Verification

Fixed-time and variable-time solver cost comparison

Example

Facts & Assumptions

Verification

Remarks

5 · Examples, counterexamples and false statements

Sources