TheoremStatement: Literature-sourcedProof: 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.

Finite adiabatic path simulation from term access

Statement

Let $H (s)$ be a finite-dimensional Hermitian path with an access instance from Adiabatic path access and resource model, a supplied exact preparation isometry $A_{0}$ of cost $C_{i n i t}$ , and finite rational certificates $M_{1} \geq \sup_{s} ∥ H^{'} (s) ∥$ and $B$ as required by Discretized adiabatic path simulation schedule. Suppose all coefficient evaluations, supported term-time calls, and their certified errors are available. For every nonnegative finite exact time code $T$ supported by the term-list access model and rational $0 < ε \leq 1$ , the algorithm in Discretized adiabatic path simulation schedule yields a finite access schedule whose unitary evolution block ${\tilde{U}}_{T} (1)$ satisfies $∥ {\tilde{U}}_{T} (1) - U_{T} (1) ∥ \leq ε$ . Before any declared output procedure, its composition with the preparation obeys $∥ {\tilde{U}}_{T} (1) A_{0} - U_{T} (1) A_{0} ∥ \leq ε$ . When all required term operations have full-list uniform circuit-family providers and the resulting circuit generator, including coefficient evaluation and wrapper construction, runs in polynomial time, the schedule expands to a full-list uniform circuit family. If named-oracle providers are used, the schedule records and charges each such query. Its cost record contains $C_{i n i t}$ plus all grid, term-query, gate, ancillary-wire, coefficient-bit, description-bit, and generator-time costs supplied by the access instance.

Facts & Assumptions

Given: A uniformly described finite path access instance, its exact preparation circuit and costs, $T$ , $ε$ , and the certificates required by the discretized simulator.

[F1]

The finite path evolution and preparation interface are specified by Finite adiabatic path model and Adiabatic path access and resource model.

[F2]

The discretized algorithm specifies the grid, rational coefficient approximations, product-formula calls, provider errors, finite loop bounds and resource coordinates (Discretized adiabatic path simulation schedule).

[F3]

For self-adjoint summands, the first-order formula with $r$ steps has error at most $t^{2} / (2 r)$ times the sum of pairwise commutator norms (First-order Lie product formula, First-order commutator error).

[F4]

Finite Hermitian evolutions and term-exponential providers are unitary; the operator norm is submultiplicative and invariant under unitary multiplication (Finite Hermitian matrix dynamics, Term-list Hamiltonian access, The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2).

[F5]

The vector norm satisfies the triangle inequality, so the operator norm does also: for every unit $v$ , $∥ (A + B) v ∥ \leq ∥ A v ∥ + ∥ B v ∥ \leq ∥ A ∥ + ∥ B ∥$ , and taking the maximum gives $∥ A + B ∥ \leq ∥ A ∥ + ∥ B ∥$ (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, The inner-product norm is definite, homogeneous, and satisfies the triangle inequality). For a continuous finite-matrix-valued function, the same triangle inequality on finite Riemann sums and passage to the limit gives $∥ \int F (u) d u ∥ \leq \int ∥ F (u) ∥ d u$ .

Proof

1.1F1F2

If $T = 0$ , the exact evolution is $I$ , so the supplied preparation and output procedure have zero evolution error. Suppose $T > 0$ . Let $M$ be the finite term count and use the finite rational certificates in [F2] to compute $q, τ, r_{P F}$ .

1.2F1F2F4F5constructalgebra

In physical time $u \in [0, T]$ , the generator is $H (u / T)$ . On the $j$ th interval $[a, b]$ of length $τ$ , compare it with the frozen generator $H (s_{j})$ , $s_{j} = j / q$ . For the exact propagator $U (b, u)$ and frozen propagator $V (u, a)$ , differentiating $U (b, u) V (u, a)$ and integrating gives $V (b, a) - U (b, a) = i \int_{a}^{b} U (b, u) (H (u / T) - H (s_{j})) V (u, a) d u$ . Unitarity [F4] and the integral norm bound [F5] bound the segment operator error by $\int_{a}^{b} ∥ H (u / T) - H (s_{j}) ∥ d u \leq M_{1} τ^{2} / (2 T)$ . The derivative certificate and coordinatewise fundamental theorem of calculus give $∥ H (s) - H (s_{j}) ∥ \leq M_{1} ∣ s - s_{j} ∣$ . Summing over $q$ intervals gives $T M_{1} / (2 q) \leq ε / 6$ by the definition of $q$ (and it is zero when $M_{1} = 0$ ).

2.1F2F4F5step 1.2algebra

Replacing each frozen $H (s_{j})$ by its certified rational approximation ${\tilde{H}}_{j}$ changes its time- $τ$ propagator by at most $τ ε / (3 T)$ by the same Duhamel estimate. Telescoping the $q$ unitary segments using [F5] bounds the total coefficient-approximation error by $q τ ε / (3 T) = ε / 3$ .

3.1F2F3F4F5step 2.1algebra

The summands ${\tilde{c}}_{j k} H_{k}$ are self-adjoint because the coefficients are real. By [F3], the ideal first-order product formula for each frozen segment has error at most $τ^{2} B / (2 r_{P F}) \leq ε / (6 q)$ ; if $B = 0$ , the error is zero. Telescoping over the $q$ unitary segments using [F5] gives product-formula error at most $ε / 6$ .

4.1F1F2F4F5step 1.2step 2.1step 3.1algebra

There are exactly $q M r_{P F}$ term-exponential calls. Replacing each by its declared unitary provider changes the composed schedule's evolution block by at most the sum of the call errors, using [F4]–[F5], so this contribution is at most $q M r_{P F} \cdot ε / (6 q M r_{P F}) = ε / 6$ . The total evolution error is at most $ε / 6 + ε / 3 + ε / 6 + ε / 6 = 5 ε / 6 \leq ε$ . Since $A_{0}$ is an isometry, $∥ A_{0} ∥ = 1$ , and submultiplicativity gives $∥ {\tilde{U}}_{T} (1) A_{0} - U_{T} (1) A_{0} ∥ \leq ε$ .

5.1F1F2step 1.1algebra∎

Each computed loop count is a finite integer fixed by the exact finite inputs, and every requested time code, coefficient approximation and provider has a finite supported description under the stated availability conditions. The algorithm therefore terminates with the access schedule specified in [F2]. When its circuit-family and polynomial-generation conditions hold, it expands to the uniform circuit family in the Statement; named-oracle calls remain charged query steps. Its preparation, queries, gates, ancillas, precision bits, circuit-description bits and generation costs are charged as stated in [F1]–[F2]. For $T = 0$ termination and exactness were established in step 1.1.

Depends on

Used by

Circuit-to-adiabatic simulation Theorem

Dependency tree · two levels

52 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

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, Adiabatic Computation is Equivalent to Standard Quantum Computation (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (standard reference, not scraped)