ExampleConstruction: AI-adaptedVerification: AI-adaptedPipeline-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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

30 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

Andris Ambainis, Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations (standard reference, not scraped)
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, Quantum singular value transformation and beyond (standard reference, not scraped)