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.

Adiabatic Computation and Circuit Equivalence

1 · Prerequisites

2 · Summary

This page gives a finite-dimensional account of adiabatic evolution and its circuit relationship. It states the path, spectral-band, preparation and access data explicitly, proves a finite reversible-chain Cheeger bound and a large clock-penalty perturbation estimate, and derives the finite-rank Jansen–Ruskai–Seiler projector bound with endpoint and gap terms.

The history-path construction uses a unary clock with a linear clock potential. Its restricted clock gap is proved by a ground-state transform and a reversible birth-death chain; the input penalty and illegal-clock penalty then give a full-space gap of order $N^{- 3}$ . A separate discretization argument accounts for path variation, product-formula error, coefficient precision and every term-exponential call. Circuit simulation requires the term-access and preparation costs declared by the instance.

3 · Logical flowchart

4 · Definitions, theorems and proofs

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

Finite reversible Cheeger inequality

Statement

Let $Ω$ be a finite set with $∣ Ω ∣ \geq 2$ . Let $P = (P (x, y))_{x, y \in Ω}$ be an irreducible row-stochastic matrix and let $π$ be a strictly positive stationary probability satisfying detailed balance $π (x) P (x, y) = π (y) P (y, x) .$ For $S \subseteq Ω$ , put $Q (S, S^{c}) = \sum_{x \in S, y \notin S} π (x) P (x, y)$ , and define the conductance $ϕ = \min_{0 < π (S) \leq 1 / 2} \frac{Q (S, S^{c})}{π (S)} .$ If $1 = λ_{1} > λ_{2} \geq \dots$ are the eigenvalues of $P$ in the weighted inner product $⟨ f, g ⟩_{π} = \sum_{x} π (x) f (x) \overline{g (x)}$ , then the algebraic gap satisfies $1 - λ_{2} \geq \frac{ϕ^{2}}{2} .$ No absolute-gap or aperiodicity assertion is made.

Facts & Assumptions

Given: A finite state set, a row-stochastic irreducible matrix $P$ , and a strictly positive stationary probability $π$ satisfying the displayed detailed-balance equations.

[F1]

A transition matrix is row-stochastic: $P (x, y) \geq 0$ and $\sum_{y} P (x, y) = 1$ (Transition matrices and n-step probabilities).

[F2]

Stationarity means $\sum_{x} π (x) P (x, y) = π (y)$ (Invariant and stationary distribution for a Markov kernel).

[F3]

Detailed balance makes $π (x) P (x, y)$ symmetric in $x, y$ (Reversible measure and detailed balance).

[F4]

A self-adjoint endomorphism of a finite-dimensional complex inner-product space has an orthonormal eigenbasis (Self-adjoint and normal endomorphisms of a finite-dimensional real or complex inner product space, Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

[F5]

Cauchy–Schwarz holds in the weighted finite-dimensional inner-product space (Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs).

Proof

1.1givenF1F2F3algebra

Set $q_{x y} = π (x) P (x, y)$ . By [F3], $q_{x y} = q_{y x}$ ; by [F1] its row sums are $π (x)$ , and by [F2] its column sums are also $π (y)$ . For a real-valued function $f$ define $E (f) = \frac{1}{2} \sum_{x, y} q_{x y} (f (x) - f (y))^{2} .$ Expanding the square and using these row and column sums gives $E (f) = ⟨ f, (I - P) f ⟩_{π}$ .

2.1givenF1F2F5step 1.1algebra

Suppose $f \geq 0$ and its support has $π$ -mass at most $1 / 2$ . For $t \geq 0$ , let $S_{t} = {x : f (x)^{2} > t}$ . The finite layer-cake identities give $\int_{0}^{\infty} π (S_{t}) d t = \sum_{x} π (x) f (x)^{2}$ and $\int_{0}^{\infty} Q (S_{t}, S_{t}^{c}) d t = \frac{1}{2} \sum_{x, y} q_{x y} ∣ f (x)^{2} - f (y)^{2} ∣$ . Every nonempty $S_{t}$ is admissible in the definition of $ϕ$ , so the latter integral is at least $ϕ ∥ f ∥_{2, π}^{2}$ . Apply [F5] to the finite weighted sum with weights $q_{x y} / 2$ and the factors $f (x) - f (y)$ and $f (x) + f (y)$ . It bounds the integral above by $\sqrt{E (f) \cdot \frac{1}{2} \sum_{x, y} q_{x y} (f (x) + f (y))^{2}}$ ; using $(a + b)^{2} \leq 2 a^{2} + 2 b^{2}$ and the row and column sums makes the second factor at most $2 ∥ f ∥_{2, π}^{2}$ . If $f \neq 0$ , division yields $E (f) \geq (ϕ^{2} / 2) ∥ f ∥_{2, π}^{2}$ ; for $f = 0$ it is immediate.

2.2givenF1F2F3step 1.1choosealgebra

Let $g$ be a real function with $\sum_{x} π (x) g (x) = 0$ . A weighted median $m$ exists by sorting the finitely many values of $g$ until their cumulative $π$ -mass reaches $1 / 2$ ; hence each of $g_{+} = (g - m)_{+}$ and $g_{-} = (m - g)_{+}$ has support mass at most $1 / 2$ . For every pair $x, y$ , $((g - m) (x) - (g - m) (y))^{2} \geq (g_{+} (x) - g_{+} (y))^{2} + (g_{-} (x) - g_{-} (y))^{2}$ . Therefore step 1.1 gives $E (g) = E (g - m) \geq E (g_{+}) + E (g_{-})$ .

3.1step 2.1step 2.2algebra

Apply steps 2.1 and 2.2 to $g_{+}$ and $g_{-}$ . Their squared norms sum to $∥ g - m ∥_{2, π}^{2} = ∥ g ∥_{2, π}^{2} + m^{2} \geq ∥ g ∥_{2, π}^{2}$ because $g$ has mean zero. Thus $E (g) \geq (ϕ^{2} / 2) ∥ g ∥_{2, π}^{2}$ .

4.1givenF2F3F4F5step 3.1algebra∎

Detailed balance makes $P$ self-adjoint for $⟨ \cdot, \cdot ⟩_{π}$ , since exchanging $x, y$ in the finite sum proves $⟨ f, P g ⟩_{π} = ⟨ P f, g ⟩_{π}$ . Constants are $1$ -eigenvectors. For any complex-valued $f$ , weighted Cauchy–Schwarz and the row sums give $∣ P f (x) ∣^{2} = ∣ \sum_{y} P (x, y) f (y) ∣^{2} \leq \sum_{y} P (x, y) ∣ f (y) ∣^{2}$ . Summing against $π (x)$ and using stationarity gives $∥ P f ∥_{2, π} \leq ∥ f ∥_{2, π}$ . Thus every eigenvalue is at most $1$ and $1$ is the top eigenvalue. If a real function satisfies $P f = f$ , choose a state where it attains its maximum. Its value is a convex average of neighboring values, so every state reached with positive transition probability has the same maximum; irreducibility propagates this to every state. Thus the real $1$ -eigenspace consists only of constants. For a complex $1$ -eigenvector, its real and imaginary parts are real $1$ -eigenvectors, so the same conclusion holds. By [F4], choose an orthonormal eigenbasis with first vector the normalized constant vector and eigenvalues $1 = λ_{1} > λ_{2} \geq \dots$ . Expanding any mean-zero vector in the remaining basis vectors shows directly that its Rayleigh quotient for $I - P$ is a weighted average of $1 - λ_{j}$ , whose minimum is $1 - λ_{2}$ . Step 3.1 bounds every real mean-zero quotient below by $ϕ^{2} / 2$ ; applying that inequality to the real and imaginary parts gives the same bound for complex vectors. This proves the claim. A possible negative eigenvalue near $- 1$ does not affect the algebraic gap.

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

Large clock-penalty perturbation

Statement

Let $H = S \oplus S^{⊥}$ be finite-dimensional, let $H_{1} = H_{1}^{*}$ with $∥ H_{1} ∥ \leq K$ , and let $H_{2} = H_{2}^{*} \geq 0$ satisfy $H_{2} ∣_{S} = 0$ and $H_{2} ∣_{S^{⊥}} \geq I$ . For $J > 2 K$ , set $H_{J} = H_{1} + J H_{2}$ , and let $μ_{1} \leq μ_{2} \leq \dots$ be the eigenvalues of the compression $A = P_{S} H_{1} ∣_{S}$ , where $\dim S \geq 2$ . With $ϵ_{J} = K^{2} / (J - 2 K)$ , the two smallest eigenvalues of $H_{J}$ obey $μ_{k} - ϵ_{J} \leq λ_{k} (H_{J}) \leq μ_{k} (k = 1, 2) .$ Consequently $λ_{2} (H_{J}) - λ_{1} (H_{J}) \geq (μ_{2} - μ_{1}) - ϵ_{J}$ ; positivity of this bound requires the separate condition $ϵ_{J} < μ_{2} - μ_{1}$ . Every unit eigenvector $x = s + t$ of $H_{J}$ with eigenvalue $λ \leq K$ also satisfies $∥ t ∥ \leq K ∥ s ∥ / (J - 2 K)$ . Thus $J > 2 K$ alone supplies no general gap conclusion.

Facts & Assumptions

Given: The orthogonal splitting $S \oplus S^{⊥}$ , the operators and bounds in the Statement, and the ordered eigenvalues of the finite-dimensional Hermitian compressions.

[F1]

$H_{1}$ and $H_{2}$ are self-adjoint, with their finite-dimensional eigenvalues characterized by Self-adjoint and normal endomorphisms of a finite-dimensional real or complex inner product space and Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely.

[F2]

The operator norm is the maximum of $∥ T v ∥$ over unit vectors (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

Proof

1.1givenF1F2algebra

Write $H_{J}$ in blocks as $(\begin{array}{cc} A & B \\ B^{*} & D \end{array})$ for $S \oplus S^{⊥}$ . Then $∥ B ∥ \leq K$ and $D = Q_{S} H_{1} Q_{S} + J Q_{S} H_{2} Q_{S} \geq (J - K) I$ by [F1]–[F2]. For real $λ \leq K$ , $D - λ I \geq (J - 2 K) I > 0$ , so the Schur complement $S_{λ} = A - λ I - B (D - λ I)^{- 1} B^{*}$ is defined and $0 \leq B (D - λ I)^{- 1} B^{*} \leq ϵ_{J} I$ .

2.1step 1.1constructalgebra

The invertible block triangular change of variables completing the square in $⟨ (H_{J} - λ) x, x ⟩$ gives the direct sum quadratic form of $S_{λ}$ and $D - λ I$ . Since the latter is positive definite, the largest dimension of a subspace on which $H_{J} - λ I$ is negative definite equals the corresponding dimension for $S_{λ}$ . This follows directly because the triangular change is an invertible linear map and hence preserves subspace dimension and signs of the quadratic form.

2.2givenF1step 1.1algebra

For $k = 1, 2$ , the span of the first $k$ eigenvectors of $A$ is a $k$ -dimensional subspace of $S$ on which the Rayleigh quotient of $H_{J}$ is at most $μ_{k}$ . If $H_{J}$ had fewer than $k$ eigenvalues at most $μ_{k}$ , that subspace would contain a nonzero vector orthogonal to its first $k - 1$ eigenvectors, whose Rayleigh quotient would be strictly larger than $μ_{k}$ , a contradiction. Thus $λ_{k} (H_{J}) \leq μ_{k} \leq K$ .

3.1step 1.1step 2.1step 2.2algebra

Fix $k = 1$ or $2$ and suppose $λ < μ_{k} - ϵ_{J}$ . Then $λ < K$ , and step 1.1 gives $S_{λ} \geq A - (λ + ϵ_{J}) I$ . Since $λ + ϵ_{J} < μ_{k}$ , at most $k - 1$ eigenvalues of $S_{λ}$ are negative. By step 2.1, at most $k - 1$ eigenvalues of $H_{J} - λ I$ are negative. Letting $λ$ increase to $μ_{k} - ϵ_{J}$ proves $λ_{k} (H_{J}) \geq μ_{k} - ϵ_{J}$ . The gap estimate follows by subtracting the bounds for $k = 1, 2$ .

4.1givenF1F2step 1.1algebra∎

If $x = s + t$ is a unit eigenvector of eigenvalue $λ \leq K$ , its $S^{⊥}$ block equation is $B^{*} s + (D - λ I) t = 0$ . By step 1.1, $∥ (D - λ I)^{- 1} ∥ \leq 1 / (J - 2 K)$ ; then [F2] yields $∥ t ∥ \leq K ∥ s ∥ / (J - 2 K)$ . No lower bound on the compressed gap was used in this leakage estimate. For a counterexample to any gap conclusion from $J > 2 K$ alone, take $\dim S = 2$ , $H_{1} = 0$ , and $H_{2} = 0$ on $S$ and $I$ on $S^{⊥}$ ; then $K = 0$ , every $J > 0$ satisfies $J > 2 K$ , and the lowest eigenvalue of $H_{J}$ has multiplicity two. Hence the separate compressed-gap condition is necessary.

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

Partial trace contracts trace distance

Statement

Let $H_{A}, H_{B}$ be nonzero finite-dimensional complex inner-product spaces and let $ρ, σ$ be density operators on $H_{A} \otimes H_{B}$ . Then $D ({Tr}_{H_{B}} ρ, {Tr}_{H_{B}} σ) \leq D (ρ, σ) .$

Facts & Assumptions

Given: The finite-dimensional spaces, density operators $ρ, σ$ , the partial trace over the second factor, and trace distance.

[F1]

In ordered product orthonormal bases, $({Tr}_{H_{B}} X)_{i i^{'}} = \sum_{j} X_{(i, j), (i^{'}, j)}$ , and the partial trace satisfies $tr (({Tr}_{H_{B}} X) A) = tr (X (A \otimes I_{H_{B}}))$ (Partial trace over a finite tensor factor, The partial trace is characterized by the trace pairing and is basis-independent).

[F2]

The partial trace of a nonnegative operator is nonnegative and it preserves total trace, so it maps density operators to density operators (The partial trace preserves non-negativity and total trace).

[F3]

Trace distance is one half of the trace norm of the state difference; the trace norm is the sum of singular values and equals $tr \sqrt{X^{*} X}$ (Trace Distance, Trace Norm, Trace Norm Spectral Formula).

[F4]

A finite-dimensional Hermitian operator has an orthonormal eigenbasis with real eigenvalues (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

[F5]

$A \otimes I_{H_{B}}$ acts by $A$ on the first factor and identity on the second; the product basis is orthonormal (Tensor products of finitely many linear maps, Ordered tensor registers, their inner product, and wire permutations, The product basis is orthonormal and tensor dimensions multiply).

[F6]

The operator norm is the maximum of $∥ T v ∥$ over unit vectors on a nonzero domain (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

[F7]

Cauchy–Schwarz gives $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ (Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs).

Proof

1.1givenF1F2algebra

Put $X = ρ - σ$ and $Y = {Tr}_{H_{B}} X$ . Both are Hermitian. For $Y$ , this follows directly from [F1]: conjugating its $(i, i^{'})$ entry and using $X_{(i, j), (i^{'}, j)} = \overline{X_{(i^{'}, j), (i, j)}}$ gives $\overline{Y_{i i^{'}}} = Y_{i^{'} i}$ . By [F2], the two partial traces of $ρ, σ$ are density operators, so their trace distance is defined.

1.2givenF3F4F6F7algebra

For any finite-dimensional Hermitian $Z$ , diagonalize it in an orthonormal basis with eigenvalues $λ_{i} \in R$ . If $A = A^{*}$ and $∥ A ∥ \leq 1$ , then each diagonal entry $⟨ A e_{i}, e_{i} ⟩$ is real and lies in $[- 1, 1]$ : [F7] gives $∣ ⟨ A e_{i}, e_{i} ⟩ ∣ \leq ∥ A e_{i} ∥ ∥ e_{i} ∥ \leq ∥ A ∥ \leq 1$ , where the middle inequality follows from [F6] by scaling a unit vector. Hence $∣ tr (Z A) ∣ = ∣ \sum_{i} λ_{i} ⟨ A e_{i}, e_{i} ⟩ ∣ \leq \sum_{i} ∣ λ_{i} ∣ = ∥ Z ∥_{1}$ by [F3]–[F4]. Equality is attained by the self-adjoint contraction $A = \sum_{λ_{i} > 0} P_{i} - \sum_{λ_{i} < 0} P_{i}$ , so $∥ Z ∥_{1} = \max_{A = A^{*}, ∥ A ∥ \leq 1} tr (Z A)$ .

2.1F1F4F5F6F7step 1.2algebra

For every self-adjoint contraction $A$ on $H_{A}$ , [F4] gives an orthonormal eigenbasis of $A$ . If $A e = λ e$ for a unit eigenvector, then [F7] and [F6] give $∣ λ ∣ = ∣ ⟨ A e, e ⟩ ∣ \leq ∥ A e ∥ ∥ e ∥ \leq ∥ A ∥ \leq 1$ . By [F5], the product basis diagonalizes $A \otimes I_{H_{B}}$ with each eigenvalue repeated, so this tensor operator is a self-adjoint contraction as well. The pairing identity [F1] gives $tr (Y A) = tr (X (A \otimes I_{H_{B}}))$ , whose absolute value is at most $∥ X ∥_{1}$ by step 1.2 applied on $H_{A} \otimes H_{B}$ . Taking the maximum over $A$ in step 1.2 on $H_{A}$ yields $∥ Y ∥_{1} \leq ∥ X ∥_{1}$ .

3.1F1F3step 2.1algebra∎

Apply the trace-distance definition [F3] to $X = ρ - σ$ and $Y = {Tr}_{H_{B}} ρ - {Tr}_{H_{B}} σ = {Tr}_{H_{B}} X$ . Step 2.1 gives $2 D ({Tr}_{H_{B}} ρ, {Tr}_{H_{B}} σ) = ∥ Y ∥_{1} \leq ∥ X ∥_{1} = 2 D (ρ, σ)$ ; division by $2$ proves the assertion.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite adiabatic path model

Definition

Let $V$ be a nonzero finite-dimensional complex inner-product space with inner product linear in its first argument. A finite adiabatic path is a family $H (s) : V \to V$ of linear endomorphisms (Linear map between vector spaces over the same field) indexed by $s \in [0, 1]$ , whose matrix entries are twice continuously differentiable in $s$ and such that $H (s) = H (s)^{*}$ for every $s \in [0, 1]$ . A coherently followed spectral band is a norm-continuous family of orthogonal projections $P (s) : V \to V$ indexed by $s \in [0, 1]$ , of one fixed rank $m \geq 1$ , commuting with $H (s)$ , whose range is a sum of full eigenspaces and which locally continues the same isolated cluster. For a finite union of positively oriented circles $Γ$ , define $\oint_{Γ} F (z) d z$ as the sum of the parameterized integrals $\int_{0}^{2 π} F (c + r e^{i t}) i r e^{i t} d t$ over its circle components. Local continuation means that on each neighborhood there is such a contour enclosing exactly the selected cluster and $P (s) = - \frac{1}{2 π i} \oint_{Γ} (H (s) - z I)^{- 1} d z .$ With $Q (s) = I - P (s)$ , define the full gap $g (s) = \min {∣ λ - μ ∣ : λ \in σ (H (s) ∣_{ran P (s)}), μ \in σ (H (s) ∣_{ran Q (s)})} .$ If $Q (s) = 0$ , the full gap is $+ \infty$ . Admissible gapped paths have a uniform full gap $\inf_{s \in [0, 1]} g (s) > 0$ . Distinct eigenvalues inside the band may cross; its total rank remains $m$ .

For a real parameter $T \in R$ , the slow-time propagator $U_{T}$ is the unique solution of $i \frac{d}{d s} U_{T} (s) = T H (s) U_{T} (s), U_{T} (0) = I .$ Identifying complex coordinates with real and imaginary parts reduces this to a real finite matrix ODE (Linear matrix ODEs have unique global solutions on a fixed interval); differentiating $U_{T} (s)^{*} U_{T} (s)$ shows it stays unitary.

An instance also supplies an explicit preparation isometry $A_{0} : C^{m} \to V$ with image $ran P (0)$ and its declared preparation cost. For a rank-one band this means a specified unit vector $ψ_{0} \in ran P (0)$ and a circuit preparing it; for a rank- $m$ band it is an orthonormal frame, not just the matrix $H (0)$ or the projector $P (0)$ . Given an input density operator $ρ_{i n}$ on $C^{m}$ , the evolved output is $ρ_{T} = U_{T} (1) A_{0} ρ_{i n} A_{0}^{*} U_{T} (1)^{*}$ . This is a density operator: for $W = U_{T} (1) A_{0}$ , $W^{*} W = A_{0}^{*} U_{T} (1)^{*} U_{T} (1) A_{0} = I$ by isometry and unitarity; hence $W ρ_{i n} W^{*}$ is nonnegative by its quadratic form, and $tr (W ρ_{i n} W^{*}) = tr (ρ_{i n} W^{*} W) = 1$ by trace cyclicity (Non-negative and positive operators, The basis-independent trace of an endomorphism of a finite-dimensional vector space, For $A \in M_{m \times n} (F)$ and $B \in M_{n \times m} (F)$ , $tr (A B) = tr (B A)$ ). A rank-one input is the pure-state projector (Pure state and ray, Density operator). A supplied target density operator $σ$ on $V$ is compared with $ρ_{T}$ by trace distance $D (ρ_{T}, σ)$ (Trace Distance). A finite output POVM on $V$ and an accepting outcome set may be supplied; its success probability is the sum of the corresponding POVM probabilities (Finite POVMs and their outcome law, POVM outcome weights are probabilities). A finite projective measurement on $V$ may also be supplied, with success probability given by its projective outcome law (Finite projective measurements, Projective measurement outcome weights are probabilities); this is a special case of the POVM interface. The model is mathematical and includes no physical postulate.

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

Finite gapped spectral projection regularity

Statement

For a $C^{2}$ finite-dimensional Hermitian path with a coherently followed spectral cluster separated from the complementary spectrum by a positive gap, the spectral projection $P (s)$ is $C^{2}$ on $[0, 1]$ .

Facts & Assumptions

Given: The finite adiabatic path and the fixed-rank, locally Riesz spectral band from Finite adiabatic path model.

[F1]

A finite Hermitian matrix has a real spectrum and an orthogonal eigenspace decomposition (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

[F2]

For a normal matrix $H = \sum_{j} λ_{j} P_{j}$ , functions of $H$ are the finite sums $f (H) = \sum_{j} f (λ_{j}) P_{j}$ (The spectral functional calculus f(T) for a normal endomorphism).

[F3]

The operator norm is submultiplicative (The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2).

Proof

1.1givenF1F3algebrachoose

Fix $s_{0} \in [0, 1]$ . By [F1], the selected finite set of eigenvalues at $s_{0}$ is separated from its complement by the positive gap. Choose finitely many positively oriented closed contours whose interiors contain exactly this cluster and whose boundaries avoid the spectrum; for a sufficiently small neighborhood of $s_{0}$ , the resolvent on these contours remains defined. Indeed, if $R_{0} (z) = (H (s_{0}) - z I)^{- 1}$ and $∥ H (s) - H (s_{0}) ∥ ∥ R_{0} (z) ∥ < 1$ uniformly on the compact contour, then submultiplicativity [F3] makes the Neumann series for $I + (H (s) - H (s_{0})) R_{0} (z)$ convergent and gives the inverse.

2.1givenF1F2step 1.1algebra

On this neighborhood, [F2] and the scalar residue formula give the same Riesz projection as the definition: $P (s) = - \frac{1}{2 π i} \oint_{Γ} (H (s) - z I)^{- 1} d z .$ To see this, diagonalize $H (s)$ ; the integral of $(λ - z)^{- 1}$ is $- 2 π i$ when $λ$ is inside the contour and zero when it is outside, so the sum is exactly the projection onto the selected eigenspaces.

3.1step 2.1algebra

Put $R_{z} (s) = (H (s) - z I)^{- 1}$ . Differentiating $(H - z I) R_{z} = I$ gives ${\dot{R}}_{z} = - R_{z} H^{'} R_{z}$ and differentiating again gives ${\ddot{R}}_{z} = 2 R_{z} H^{'} R_{z} H^{'} R_{z} - R_{z} H^{''} R_{z}$ . The contour is compact and stays uniformly in the resolvent set on this neighborhood, so these integrands and their first two derivatives are continuous uniformly in $z$ . Differentiation under the finite contour integral is therefore valid, and step 2.1 makes $P$ twice continuously differentiable near $s_{0}$ .

4.1givenF1F2step 3.1∎

On the overlap of two such neighborhoods, each contour formula projects onto the same coherently followed eigenspaces by [F1]–[F2]; hence the local projections agree. Their first two derivatives consequently agree on overlaps, so the local $C^{2}$ representations patch to a global $C^{2}$ map on $[0, 1]$ , with one-sided derivatives at the endpoints.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Adiabatic path access and resource model

Definition

An adiabatic path access instance consists of a finite path model (Finite adiabatic path model), its exact initial preparation circuit $A_{0}$ and cost $C_{i n i t}$ , a finite term count $r$ , and a uniform description $H (s) = \sum_{j = 1}^{r} c_{j} (s) H_{j},$ where the $H_{j}$ are stated finite-dimensional self-adjoint operators and the real coefficient functions $c_{j}$ have explicit rational binary inputs, uniform evaluation procedures, certified value errors and certified first-derivative bound $M_{1} \geq \sup_{s} ∥ H^{'} (s) ∥$ . The access declaration provides, for every allowed time code $u$ , either the exact term operation $e^{- i u H_{j}}$ as a named oracle with its query charge, or a full-list uniform circuit family $V_{j} (u)$ with a certified bound $∥ V_{j} (u) - e^{- i u H_{j}} ∥ \leq η_{j} (u)$ . Each inverse or controlled call is available only when separately declared. This is the finite term-list access interface of Hamiltonian simulation error and resources and Term-list Hamiltonian access.

The resource record lists separately: $C_{i n i t}$ ; the term count $r$ ; all term-oracle queries; controlled and inverse calls; gate, clean-ancilla and dirty-ancilla counts; coefficient-precision bits; full circuit-description bits; uniform generator time; and the continuous evolution time $T$ . If a physical energy-normalized action is used, it also records $T \sup_{s} ∥ H (s) ∥$ . A missing coordinate is unavailable, not zero. No arbitrary matrix description or spectral projector supplies an initial preparation, term exponential, controlled call, inverse, coefficient evaluator, or circuit generator for free.

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

Finite spectral-band derivative estimates for adiabatic paths

Statement

Let $H (s)$ be a $C^{2}$ finite-dimensional Hermitian path and $P (s)$ a $C^{2}$ spectral projection of fixed rank $m \geq 1$ separated from its complement by gap $g (s) > 0$ . Put $Q = I - P$ . For any operator $X$ define its reduced-resolvent transform at $s$ by $\tilde{X} = - \sum_{λ \in Λ_{P}} (P_{λ} X {\hat{R}}_{λ} + {\hat{R}}_{λ} X P_{λ}), {\hat{R}}_{λ} = Q (H ∣_{ran Q} - λ I)^{- 1} Q,$ where $Λ_{P}$ is the set of distinct eigenvalues in $ran P$ and $P_{λ}$ is the corresponding eigenspace projection. Then $\dot{P} = \tilde{\dot{H}}, ∥ \tilde{X} ∥ \leq \frac{\sqrt{m} ∥ X ∥}{g}, ∥ Q \tilde{X} P ∥ \leq \frac{\sqrt{m} ∥ Q X P ∥}{g}, ∥ P \tilde{X} Q ∥ \leq \frac{\sqrt{m} ∥ P X Q ∥}{g},$ $∥ \dot{P} ∥ \leq \frac{\sqrt{m} ∥ \dot{H} ∥}{g}, ∥ Q \ddot{P} P ∥ \leq \frac{\sqrt{m} ∥ \ddot{H} ∥}{g} + \frac{4 m ∥ \dot{H} ∥^{2}}{g^{2}},$ and $∥ Q \dot{\tilde{\dot{P}}} P ∥ \leq \frac{\sqrt{m} ∥ Q \ddot{P} P ∥}{g} + \frac{2 m ∥ \dot{H} ∥ ∥ \dot{P} ∥}{g^{2}} .$ The rank $m$ may count multiplicity; the argument only uses that the number of distinct band eigenvalues is at most $m$ .

Facts & Assumptions

Given: The finite path, the coherent gapped projection, and the gap convention from Finite adiabatic path model.

[F1]

The band projection is $C^{2}$ (Finite gapped spectral projection regularity).

[F2]

At each parameter value, $H$ has an orthogonal eigenspace decomposition (Self-adjoint and normal endomorphisms of a finite-dimensional real or complex inner product space, Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

[F3]

On a nonzero domain the operator norm is defined by its maximum on unit vectors; on the zero domain it is zero. It is submultiplicative (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).

[F4]

Cauchy–Schwarz holds in the finite-dimensional inner-product spaces (Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs).

[F5]

For a finite-dimensional map $A$ , $∥ A ∥ = ∥ A^{*} ∥$ : Cauchy–Schwarz gives $∥ A ∥ = \max_{∥ x ∥ = ∥ y ∥ = 1} ∣ ⟨ A x, y ⟩ ∣$ when both spaces are nonzero (choose $y = A x / ∥ A x ∥$ when $A x \neq 0$ ), and the adjoint identity exchanges $x, y$ ; if a space is zero both map norms are zero (The adjoint $T^{*} : W \to V$ is characterised by $⟨ T v, w ⟩_{W} = ⟨ v, T^{*} w ⟩_{V}$ , The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||, Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs).

[F6]

Reduced resolvents on the complement obey $∥ {\hat{R}}_{λ} ∥ \leq 1 / g$ because every complementary eigenvalue is at distance at least $g$ from every band eigenvalue; this follows by diagonalizing the self-adjoint restriction and applying the operator-norm definition.

Proof

1.1givenF2F3algebra

Fix $s$ and write $P = \sum_{λ \in Λ_{P}} P_{λ}$ . The displayed definition makes $\tilde{X}$ off-diagonal: $P \tilde{X} P = Q \tilde{X} Q = 0$ . On each band-to-complement block, $[H, \tilde{X}]$ multiplies $- P_{λ} X {\hat{R}}_{λ}$ by $λ - H ∣_{Q}$ , giving $P_{λ} X Q$ ; on the reverse block it gives $- Q X P_{λ}$ . Summing yields $[H, \tilde{X}] = P X - X P$ .

2.1F2F3F4F5F6step 1.1algebra

Choose an orthonormal basis $e_{1}, \dots, e_{m}$ of $ran P$ adapted to the mutually orthogonal $P_{λ}$ . For each basis vector $e_{j}$ in $ran P_{λ}$ , $Q \tilde{X} e_{j} = - {\hat{R}}_{λ} Q X e_{j}$ , so [F6] gives $\sum_{j} ∥ Q \tilde{X} e_{j} ∥^{2} \leq g^{- 2} \sum_{j} ∥ Q X e_{j} ∥^{2} \leq m ∥ Q X P ∥^{2} / g^{2}$ . For a unit vector $u = \sum_{j} u_{j} e_{j}$ , Cauchy–Schwarz [F4] yields $∥ Q \tilde{X} P u ∥ \leq \sum_{j} ∣ u_{j} ∣ ∥ Q \tilde{X} e_{j} ∥ \leq (\sum_{j} ∣ u_{j} ∣^{2})^{1 / 2} (\sum_{j} ∥ Q \tilde{X} e_{j} ∥^{2})^{1 / 2}$ , proving $∥ Q \tilde{X} P ∥ \leq \sqrt{m} ∥ Q X P ∥ / g$ . Since each ${\hat{R}}_{λ}$ and $P_{λ}$ is self-adjoint, taking adjoints in the defining sum gives $\tilde{X^{*}} = {\tilde{X}}^{*}$ . Applying the column estimate to $X^{*}$ and using [F5] gives $∥ P \tilde{X} Q ∥ \leq \sqrt{m} ∥ P X Q ∥ / g$ . Since $\tilde{X}$ is off-diagonal, for $u = p + q$ one has $∥ \tilde{X} u ∥^{2} = ∥ P \tilde{X} Q q ∥^{2} + ∥ Q \tilde{X} P p ∥^{2}$ ; hence its full norm is the maximum of the two block norms. This proves $∥ \tilde{X} ∥ \leq \sqrt{m} ∥ X ∥ / g$ .

2.2F1F2step 1.1algebra

On a local fixed Riesz contour put $R_{z} = (H - z I)^{- 1}$ and ${\hat{R}}_{z} = Q (H ∣_{Q} - z I)^{- 1} Q$ . Then $\tilde{X} = (2 π i)^{- 1} \oint R_{z} X R_{z} d z$ . For $G (A, B) = (2 π i)^{- 1} \oint R_{z} A R_{z} B R_{z} d z$ , using $[H - z, R_{z}] = 0$ gives $[H, G (A, B)] = \frac{1}{2 π i} \oint (A R_{z} B R_{z} - R_{z} A R_{z} B) d z = A \tilde{B} - \tilde{A} B .$ Indeed, $R_{z} [H - z, A] R_{z} = A R_{z} - R_{z} A$ and $R_{z} [H - z, B] R_{z} = B R_{z} - R_{z} B$ ; adding the two commutator contributions cancels the middle terms. Write $C = A \tilde{B} - \tilde{A} B$ . On each band eigenspace $P_{λ}$ , the Sylvester equations from this commutator give $P G Q = P \tilde{C} Q, Q G P = - Q \tilde{C} P,$ because $P_{λ} \tilde{C} Q = - P_{λ} C {\hat{R}}_{λ}$ and $Q \tilde{C} P_{λ} = - {\hat{R}}_{λ} C P_{λ}$ .

3.1F1F2F3step 1.1step 2.1algebra

Differentiate $H P = P H$ and multiply on the left by $Q$ and on the right by each $P_{λ}$ . The resulting Sylvester equation is $(H ∣_{Q} - λ I) Q \dot{P} P_{λ} = - Q \dot{H} P_{λ}$ , so $Q \dot{P} P_{λ} = - {\hat{R}}_{λ} \dot{H} P_{λ}$ . Differentiating $P^{2} = P$ gives $P \dot{P} P = Q \dot{P} Q = 0$ ; self-adjointness gives the other off-diagonal block by adjoint. These identities equal the reduced-resolvent formula for $\tilde{\dot{H}}$ , proving $\dot{P} = \tilde{\dot{H}}$ . Step 2.1 then gives $∥ \dot{P} ∥ \leq \sqrt{m} ∥ \dot{H} ∥ / g$ .

3.2F1F2step 2.2algebra

The diagonal blocks follow by expanding $R_{z} = \sum_{λ \in Λ_{P}} P_{λ} / (λ - z) + {\hat{R}}_{z}$ . In $Q G Q$ , the only non-holomorphic terms have the middle resolvent in $P_{λ}$ , and their integrals are $- {\hat{R}}_{λ} A P_{λ} B {\hat{R}}_{λ}$ ; terms with all three resolvents in $Q$ are holomorphic inside the contour. Hence $Q G Q = - Q \tilde{A} \tilde{B} Q$ . In $P G P$ , terms with three band resolvents have zero integral because their rational integrands decay as $z^{- 3}$ and all their poles lie inside the contour. The remaining terms have two band poles $λ, μ$ and one $Q$ resolvent. Their scalar contour coefficient equals ${\hat{R}}_{λ}^{2}$ if $λ = μ$ by Cauchy's derivative formula, and equals $({\hat{R}}_{λ} - {\hat{R}}_{μ}) / (λ - μ) = {\hat{R}}_{λ} {\hat{R}}_{μ}$ if $λ \neq μ$ by the resolvent identity. Thus $P G P = P \tilde{A} \tilde{B} P$ . Together with step 2.2, these blocks prove $G (A, B) = (P - Q) (\tilde{A} \tilde{B} + \tilde{A \tilde{B}} - \tilde{\tilde{A} B}) .$ All contours enclose the whole band; coincident band eigenvalues are grouped into one $P_{λ}$ , and the complementary resolvent is holomorphic throughout the enclosed region.

4.1F1F2step 3.1step 3.2algebra

Differentiating the contour formula and using ${\dot{R}}_{z} = - R_{z} \dot{H} R_{z}$ gives $\dot{\tilde{X}} = \tilde{\dot{X}} - G (\dot{H}, X) - G (X, \dot{H}) .$ Apply step 3.2 to both $G$ terms and use $\dot{P} = \tilde{\dot{H}}$ from step 3.1. Their sum is $(P - Q) (\dot{P} \tilde{X} + \tilde{X} \dot{P} + \tilde{[\dot{H}, \tilde{X}]} - \tilde{[\dot{P}, X]}),$ because the remaining terms are $\tilde{\dot{H} \tilde{X} + X \dot{P} - \dot{P} X - \tilde{X} \dot{H}} = \tilde{[\dot{H}, \tilde{X}]} - \tilde{[\dot{P}, X]}$ . Negating this sum in the derivative formula yields $\dot{\tilde{X}} = \tilde{\dot{X}} + (Q - P) (\dot{P} \tilde{X} + \tilde{X} \dot{P} + \tilde{[\dot{H}, \tilde{X}]} - \tilde{[\dot{P}, X]}) .$ The contour formula is local, so it remains valid at internal band eigenvalue coincidences; no selected eigenvalue is crossed by the contour.

5.1F2F3step 2.1step 3.1step 4.1algebra

Apply step 4.1 to $X = \dot{H}$ . Since $\tilde{\dot{H}} = \dot{P}$ is off-diagonal, ${\dot{P}}^{2}$ is block diagonal and has zero $Q P$ block. Also $[\dot{P}, \dot{H}] = - [\dot{H}, \dot{P}]$ . Therefore $Q \ddot{P} P = Q \tilde{\ddot{H}} P + 2 Q \tilde{[\dot{H}, \dot{P}]} P .$ The block estimate in step 2.1 bounds the first term by $\sqrt{m} ∥ \ddot{H} ∥ / g$ and the second by $2 (\sqrt{m} / g) ∥ [\dot{H}, \dot{P}] ∥ \leq 4 \sqrt{m} ∥ \dot{H} ∥ ∥ \dot{P} ∥ / g \leq 4 m ∥ \dot{H} ∥^{2} / g^{2}$ using submultiplicativity [F3] and step 3.1. This is the claimed bound.

6.1F2F3step 2.1step 3.1step 4.1algebra∎

Apply step 4.1 to $X = \dot{P}$ . The products $\dot{P} \tilde{\dot{P}}$ and $\tilde{\dot{P}} \dot{P}$ are block diagonal, and $[\dot{P}, \dot{P}] = 0$ . Hence $Q \dot{\tilde{\dot{P}}} P = Q \tilde{\ddot{P}} P + Q \tilde{[\dot{H}, \tilde{\dot{P}}]} P .$ The block bound from step 2.1 makes the first term at most $\sqrt{m} ∥ Q \ddot{P} P ∥ / g$ . The second is at most $(\sqrt{m} / g) ∥ [\dot{H}, \tilde{\dot{P}}] ∥ \leq (2 \sqrt{m} / g) ∥ \dot{H} ∥ ∥ \tilde{\dot{P}} ∥ \leq 2 m ∥ \dot{H} ∥ ∥ \dot{P} ∥ / g^{2}$ , using submultiplicativity [F3] and steps 2.1 and 3.1.

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

Finite JRS adiabatic projector bound

Statement

Let $H : [0, 1] \to L (V)$ be a $C^{2}$ finite-dimensional Hermitian path, and let $P (s)$ be a coherently followed spectral projection of constant rank $m \geq 1$ , separated from its complement by full gap $g (s) > 0$ . Let $U_{T}$ solve $i U_{T}^{'} (s) = T H (s) U_{T} (s)$ with $U_{T} (0) = I$ , where $T > 0$ . Define $A_{m} (s) = \frac{1}{T} [\frac{m ∥ H^{'} (0) ∥}{g (0)^{2}} + \frac{m ∥ H^{'} (s) ∥}{g (s)^{2}} + \int_{0}^{s} (\frac{m ∥ H^{''} (r) ∥}{g (r)^{2}} + \frac{7 m \sqrt{m} ∥ H^{'} (r) ∥^{2}}{g (r)^{3}}) d r] .$ Then $∥ U_{T} (s) P (0) U_{T} (s)^{*} - P (s) ∥ \leq A_{m} (s) .$ For every unit $ψ \in ran P (0)$ , its transition probability out of the band at time $s$ is at most $A_{m} (s)^{2}$ . The rank $m$ may be larger than the number of distinct eigenvalues in the band; using rank in the constants is a valid upper bound.

Facts & Assumptions

Given: The finite path, its gapped band, the slow-time propagator, and $T > 0$ from Finite adiabatic path model.

[F1]

The band projection is $C^{2}$ (Finite gapped spectral projection regularity).

[F2]

The twiddle transform satisfies $\dot{P} = \tilde{H^{'}}$ , $∥ \tilde{X} ∥ \leq \sqrt{m} ∥ X ∥ / g$ , the block bounds $∥ Q \tilde{X} P ∥ \leq \sqrt{m} ∥ Q X P ∥ / g$ and $∥ P \tilde{X} Q ∥ \leq \sqrt{m} ∥ P X Q ∥ / g$ , $∥ Q \ddot{P} P ∥ \leq \sqrt{m} ∥ H^{''} ∥ / g + 4 m ∥ H^{'} ∥^{2} / g^{2}$ , and $∥ Q \dot{\tilde{\dot{P}}} P ∥ \leq \sqrt{m} ∥ Q \ddot{P} P ∥ / g + 2 m ∥ H^{'} ∥ ∥ \dot{P} ∥ / g^{2}$ (Finite spectral-band derivative estimates for adiabatic paths).

[F3]

The operator norm is submultiplicative and invariant under multiplication by a unitary (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).

[F4]

A continuous finite matrix coefficient has a unique propagator on $[0, 1]$ (Linear matrix ODEs have unique global solutions on a fixed interval), after realifying its complex coordinates.

Proof

1.1F1F4givenalgebra

Put $D (s) = [P^{'} (s), P (s)]$ . Since $P, P^{'}$ are self-adjoint, $D^{*} = - D$ , so $K_{A} (s) = T H (s) + i D (s)$ is self-adjoint. Let $U_{A}$ solve $i U_{A}^{'} = K_{A} U_{A}$ , $U_{A} (0) = I$ ; [F4] gives existence and uniqueness, and differentiating $U_{A}^{*} U_{A}$ gives unitarity. Differentiating $P^{2} = P$ yields $P P^{'} P = 0$ and $P^{'} P + P P^{'} = P^{'}$ , hence $[D, P] = P^{'}$ . Therefore $P$ solves $i P^{'} = [K_{A}, P]$ , and so does $F (s) = U_{A} (s) P (0) U_{A} (s)^{*}$ . Both have initial value $P (0)$ ; uniqueness for this finite linear matrix ODE gives $F (s) = P (s)$ , or equivalently $U_{A} (s) P (0) U_{A} (s)^{*} = P (s)$ .

2.1step 1.1F3algebra

Define the unitary wave operator $Ω (s) = U_{A} (s)^{*} U_{T} (s)$ . Differentiating with the two evolution equations gives $Ω^{'} (s) = - U_{A} (s)^{*} D (s) U_{T} (s)$ and therefore $Ω (s) = I - \int_{0}^{s} U_{A} (r)^{*} D (r) U_{A} (r) Ω (r) d r$ . The intertwining identity in step 1.1 implies that the conjugated kernel is off-diagonal relative to $P (0), Q (0)$ and that $Q (0) Ω (s) P (0) = - \int_{0}^{s} Q (0) P^{'} (r) [r] P (0) Ω (r) P (0) d r,$ where $X [r] = U_{A} (r)^{*} X (r) U_{A} (r)$ .

3.1F2F3step 1.1step 2.1algebra

For any differentiable $X$ , the commutator identity from Finite spectral-band derivative estimates for adiabatic paths and step 1.1 gives $\frac{d}{d r} (Q (0) \tilde{X} [r] P (0)) = - i T Q (0) X [r] P (0) + Q (0) \dot{\tilde{X}} [r] P (0) .$ Indeed, $Q [H, \tilde{X}] P = - Q X P$ , and the extra commutator with $i D / T$ has zero $Q P$ block because $P [D, \tilde{X}] Q = Q [D, \tilde{X}] P = 0$ when $D$ and $\tilde{X}$ are off-diagonal. Integrating this identity by parts in step 2.1 with $X = P^{'}$ and $Y (r) = P (0) Ω (r) P (0)$ yields $Q (0) Ω (s) P (0) = - \frac{i}{T} [Q (0) \tilde{P^{'}} [r] P (0) Y (r) ∣_{0}^{s} - \int_{0}^{s} Q (0) \dot{\tilde{P^{'}}} [r] P (0) Y (r) d r - \int_{0}^{s} Q (0) \tilde{P^{'}} [r] P (0) P (0) Ω^{'} (r) P (0) d r] .$ Here $∥ Y (r) ∥ \leq 1$ and $P (0) Ω^{'} (r) P (0) = P (0) P^{'} [r] Q (0) Ω (r) P (0)$ , because the $P Q$ block of $[P^{'}, P]$ is $- P P^{'} Q$ . The last integrand is therefore bounded by $∥ Q \tilde{P^{'}} P ∥ ∥ P^{'} ∥ ∥ Q (0) Ω P (0) ∥$ . Repeating the same calculation with $P (0)$ and $Q (0)$ interchanged bounds $∥ P (0) Ω Q (0) ∥$ by the same expression.

4.1F2F3step 3.1algebra

Use [F2] on the endpoint and derivative terms of step 3.1, and $∥ Q \tilde{P^{'}} P ∥ \leq \sqrt{m} ∥ P^{'} ∥ / g$ on its product term. Since $∥ Q (0) Ω P (0) ∥ \leq 1$ , this gives $∥ Q (0) Ω P (0) ∥ \leq \frac{1}{T} [\frac{\sqrt{m} ∥ P^{'} (0) ∥}{g (0)} + \frac{\sqrt{m} ∥ P^{'} (s) ∥}{g (s)} + \int_{0}^{s} (\frac{\sqrt{m} ∥ Q P^{''} P ∥}{g} + \frac{\sqrt{m} ∥ P^{'} ∥^{2}}{g} + \frac{2 m ∥ H^{'} ∥ ∥ P^{'} ∥}{g^{2}}) d r] .$ Now $∥ P^{'} ∥ \leq \sqrt{m} ∥ H^{'} ∥ / g$ . The first two integral terms are respectively at most $m ∥ H^{''} ∥ / g^{2} + 4 m \sqrt{m} ∥ H^{'} ∥^{2} / g^{3}$ and $m \sqrt{m} ∥ H^{'} ∥^{2} / g^{3}$ ; the last is at most $2 m \sqrt{m} ∥ H^{'} ∥^{2} / g^{3}$ . Their sum gives exactly the integrand in $A_{m} (s)$ , and the endpoint terms give its two endpoint summands. The same bound holds for $∥ P (0) Ω Q (0) ∥$ .

5.1step 1.1step 4.1algebra∎

Unitary conjugation by $U_{A}$ and step 1.1 give $∥ U_{T} P (0) U_{T}^{*} - P (s) ∥ = ∥ Ω P (0) Ω^{*} - P (0) ∥ = ∥ Q (0) Ω P (0) - P (0) Ω Q (0) ∥ .$ The last operator is off-diagonal with the two blocks bounded in step 4.1; its norm is the maximum of their norms, so it is at most $A_{m} (s)$ . For a unit $ψ \in ran P (0)$ , $Q (s) U_{T} (s) ψ = U_{A} (s) Q (0) Ω (s) P (0) ψ$ by step 1.1. Its squared norm is the transition probability and is at most $∥ Q (0) Ω (s) P (0) ∥^{2} \leq A_{m} (s)^{2}$ .

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Discretized adiabatic path simulation schedule

Definition

Input: An adiabatic path access instance from Adiabatic path access and resource model, a nonnegative finite exact time code $T$ from Term-list Hamiltonian access, a rational tolerance $0 < ε \leq 1$ , and finite rational certificates $M_{1} \geq \sup_{s \in [0, 1]} ∥ H^{'} (s) ∥$ and $B \geq 0$ . The time code supports exact comparisons and arithmetic needed to compute $q$ and the derived supported call times. Write $M \geq 1$ for the term count. The coefficient functions are real and have the uniform evaluation procedures and error certificates in the access instance. Each requested coefficient approximation is a finitely encoded real rational. The certificate $B$ bounds, for every sampled grid point and its supplied approximations, the commutator sum of the frozen self-adjoint summands. The access record provides supported term-time calls for every product-formula call below, with the requested certified operator errors. If any required coefficient, call, or certificate is unavailable, the algorithm returns no circuit.

Output: A finite access schedule that composes the supplied preparation, the segment calls and the declared output procedure, with the requested error budget and separately recorded supplied and generated resources. Each term call uses its declared provider: a supplied circuit-family call or a named-oracle call with its query charge. If all required operations are circuit families, the schedule expands into their composed circuit; otherwise it records each call using its declared provider, including every named-oracle query.

If $T = 0$ , apply the supplied initial preparation $A_{0}$ and perform the declared output procedure.
If $T > 0$ , set $q = \max {1, ⌈ \frac{3 T M_{1}}{ε} ⌉}, τ = T / q .$ These are computable finite integers and a supported time code. For each $j = 0, \dots, q - 1$ , let $s_{j} = j / q$ and request rational coefficient approximations ${\tilde{c}}_{j k}$ defining ${\tilde{H}}_{j} = \sum_{k = 1}^{M} {\tilde{c}}_{j k} H_{k}$ with certificate $∥ {\tilde{H}}_{j} - H (s_{j}) ∥ \leq ε / (3 T)$ .
Using the input certificate $B$ , and supported time codes for all calls below, set $r_{P F} = \max {1, ⌈ \frac{3 q τ^{2} B}{ε} ⌉} .$ For each $j = 0, \dots, q - 1$ in increasing order, and each product-formula substep $a = 1, \dots, r_{P F}$ , execute term calls for $k = M, M - 1, \dots, 1$ at time code $(τ / r_{P F}) {\tilde{c}}_{j k}$ . This chronological order realizes the algebraic product $S_{1} (τ / r_{P F}) = e^{- i (τ / r_{P F}) {\tilde{c}}_{j 1} H_{1}} \dots e^{- i (τ / r_{P F}) {\tilde{c}}_{j M} H_{M}}$ because circuit products act right to left; $S_{1}$ is the formula in First-order Lie product formula. Each of the $q M r_{P F}$ calls is supplied with operator error at most $ε / (6 q M r_{P F})$ .
Execute the $q$ segment call sequences in increasing $j$ after $A_{0}$ , then perform the declared output procedure. Record initial preparation, term queries, gates, ancillary wires, coefficient bits, circuit-description bits, generator time and $T$ separately. If any required coefficient evaluation, time code or term-exponential access is unavailable, this algorithm has no output schedule under the declared model.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Five-local history-state adiabatic path

Definition

Input: A full-list uniform circuit on $n \geq 1$ qubits with $L \geq 1$ listed gates $U_{1}, \dots, U_{L}$ , each acting on at most two data qubits, and a rational tolerance $0 < ε \leq 1$ . Circuit products act right to left (Full-list uniform quantum circuit family). The computation is applied to the explicitly supplied all-zero input preparation $A_{0}$ ; its wire and preparation cost $C_{i n i t}$ is recorded by Circuit-family and computation cost model and Adiabatic path access and resource model. The path-access input also supplies uniform term-time providers for the constructed term list, exact coefficient evaluation, supported time codes and certified call errors required by Discretized adiabatic path simulation schedule.

Output: The explicit finite term list and linearly interpolated Hamiltonian path $H (s)$ , together with the supplied initial preparation and resource coordinates, plus the evolution access schedule and data-register output produced by steps 5–7 when the required access providers are available. The schedule uses the declared circuit-family or named-oracle provider for each term call and records its corresponding resource charge.

Set $K = ⌈ 2 L / ε ⌉$ and $N = L + K$ . Append $K$ identity gates, writing $U_{ℓ} = I$ for $L < ℓ \leq N$ . Use data space $(C^{2})^{\otimes n}$ and an ordered $N$ -qubit clock register (Finite registers and their ordered computational bases, Ordered tensor registers, their inner product, and wire permutations). Its legal unary clock basis is $∣ c_{ℓ} ⟩ = ∣ 1^{ℓ} 0^{N - ℓ} ⟩, 0 \leq ℓ \leq N .$
Let $H_{c l o c k} = \sum_{j = 1}^{N - 1} ∣ 01 ⟩ ⟨ 01 ∣_{{c l o c k}_{j}, {c l o c k}_{j + 1}}$ and $H_{i n p u t} = \sum_{i = 1}^{n} ∣ 1 ⟩ ⟨ 1 ∣_{{d a t a}_{i}} \otimes ∣ 0 ⟩ ⟨ 0 ∣_{{c l o c k}_{1}}, H_{c l o c k 0} = \sum_{j = 1}^{N} ∣ 1 ⟩ ⟨ 1 ∣_{{c l o c k}_{j}} .$ The first tensor factor is the data register. The zero-summand convention applies when an index range is empty.
For each transition $ℓ - 1 \to ℓ$ , specify two local clock patterns $a_{ℓ}, b_{ℓ}$ : if $1 < ℓ < N$ , use $a_{ℓ} = 100, b_{ℓ} = 110$ on clock bits $(ℓ - 1, ℓ, ℓ + 1)$ ; for $ℓ = 1$ , use $a_{1} = 00, b_{1} = 10$ on bits $(1, 2)$ ; for $ℓ = N$ , use $a_{N} = 10, b_{N} = 11$ on bits $(N - 1, N)$ . For a clock pattern $a$ , let $∣ a ⟩ ⟨ a ∣$ act on those listed clock bits and as identity on all other clock bits. Define the five-local propagation term $h_{ℓ} = \frac{1}{2} [I_{d a t a} \otimes (∣ a_{ℓ} ⟩ ⟨ a_{ℓ} ∣ + ∣ b_{ℓ} ⟩ ⟨ b_{ℓ} ∣) - U_{ℓ} \otimes ∣ b_{ℓ} ⟩ ⟨ a_{ℓ} ∣ - U_{ℓ}^{*} \otimes ∣ a_{ℓ} ⟩ ⟨ b_{ℓ} ∣], H_{p r o p} = \sum_{ℓ = 1}^{N} h_{ℓ} .$
Put $K_{0} = n + 3 N$ and $Δ_{0} = 1 / (216 (N + 1)^{3})$ , and choose the positive integer $J = 2 K_{0} + 4 K_{0}^{2} / Δ_{0} + 1.$ Output the linearly interpolated Hamiltonian $H (s) = (1 - s) H_{i n i t} + s H_{f i n a l}, H_{i n i t} = H_{i n p u t} + H_{c l o c k 0} + J H_{c l o c k}, H_{f i n a l} = H_{i n p u t} + H_{p r o p} + J H_{c l o c k} .$ The term list, integer coefficient $J$ , initial preparation, term-access queries, coefficient bits, gate costs, and generator time are explicit coordinates of the path access model (Adiabatic path access and resource model); no spectral projector supplies $A_{0}$ . With $M = n + 3 N - 1$ terms, record the rational certificates $M_{1} = 3 N$ for the derivative and $B = M^{2} J^{2}$ for every sampled commutator sum; the coefficient functions are the exact constants $1, J$ and affine functions $s, 1 - s$ .
Set $Δ_{0} = 1 / [216 (N + 1)^{3}]$ , $γ = 3 Δ_{0} / 4$ , $B_{T} = 6 N / γ^{2} + 63 N^{2} / γ^{3}$ , and $T = ⌈ 4 B_{T} / ε ⌉$ . Set the finite-precision simulation tolerance to $ε_{s i m} = ε / 4$ . These are finite rational computations.
Invoke Discretized adiabatic path simulation schedule on the constructed path-access instance with evolution time $T$ and tolerance $ε_{s i m}$ . Its output schedule applies the supplied $A_{0}$ before the path evolution, using each term's declared circuit-family or named-oracle provider. If any required term provider, coefficient evaluation or supported call is unavailable, return no schedule.
Declare the data register as the output and the clock register as discarded by the output procedure passed to step 6 (the resulting state is the partial trace over the clock, Partial trace over a finite tensor factor). Record $T$ , preparation, simulation calls, coefficient precision, circuit-description and generator costs separately.

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

History state and padded output

Statement

Let the five-local path in Five-local history-state adiabatic path have $N = L + K$ gates, including its $K$ identity gates, and let $V_{0} = I$ and $V_{ℓ} = U_{ℓ} \dots U_{1}$ . On the legal unary-clock space, the propagation Hamiltonian has kernel ${\frac{1}{\sqrt{N + 1}} \sum_{ℓ = 0}^{N} V_{ℓ} ξ \otimes ∣ c_{ℓ} ⟩ : ξ \in (C^{2})^{\otimes n}} .$ After adding $H_{i n p u t}$ , this kernel is one-dimensional and its unit vector is $∣ η ⟩ = \frac{1}{\sqrt{N + 1}} \sum_{ℓ = 0}^{N} V_{ℓ} ∣ 0^{n} ⟩ \otimes ∣ c_{ℓ} ⟩ .$ The full $H_{f i n a l}$ also has this unique ground state. Its data-register marginal is at trace distance at most $L / (N + 1) \leq ε / 2$ from the specified circuit output state.

Facts & Assumptions

Given: The gate list, local propagation terms, legal unary clock, input penalty, and padding parameters from Five-local history-state adiabatic path.

[F1]

The partial trace over the clock sums diagonal clock blocks in an orthonormal product basis (Partial trace over a finite tensor factor).

[F2]

A unit vector $ψ$ represents the density operator $∣ ψ ⟩ ⟨ ψ ∣$ (Density operator, Dirac Notation Conversion).

[F3]

Any two density operators have trace distance at most $1$ (Trace Distance Range And Equality).

Proof

1.1givenalgebra

Fix an assignment to all clock bits outside the local support of $h_{ℓ}$ . The subspace with that fixed spectator assignment and local clock state in ${a_{ℓ}, b_{ℓ}}$ is invariant; in the order $(a_{ℓ}, b_{ℓ})$ the block is $\frac{1}{2} (\begin{array}{cc} I & - U_{ℓ}^{*} \\ - U_{ℓ} & I \end{array}) .$ The term is zero on every local pattern outside this pair. These mutually orthogonal blocks, together with the subspaces for those other local patterns, decompose the full register, so it suffices to inspect each displayed block and the zero action on the rest. For any data vectors $x, y$ , its quadratic form is $\frac{1}{2} ∥ y - U_{ℓ} x ∥^{2} \geq 0$ , and its kernel consists exactly of paired amplitudes $(x, U_{ℓ} x)$ . Hence $h_{ℓ}$ is positive semidefinite on the full clock register.

2.1givenstep 1.1constructalgebra

On legal unary clocks, $a_{ℓ}$ occurs only at $c_{ℓ - 1}$ and $b_{ℓ}$ only at $c_{ℓ}$ . Define the unitary $W = \sum_{j = 0}^{N} V_{j} \otimes ∣ c_{j} ⟩ ⟨ c_{j} ∣$ on that space. Since $V_{ℓ} = U_{ℓ} V_{ℓ - 1}$ , conjugating the block from step 1.1 by $W$ makes every adjacent block $\frac{1}{2} (\begin{array}{cc} I & - I \\ - I & I \end{array})$ . Summing over edges gives $W^{*} H_{p r o p} W = I_{d a t a} \otimes L_{N} / 2$ .

3.1step 2.1algebra

The quadratic form of $L_{N}$ is $⟨ z, L_{N} z ⟩ = \sum_{j = 0}^{N - 1} ∣ z_{j} - z_{j + 1} ∣^{2}$ , so its kernel is the constant clock vectors. Step 2.1 therefore gives exactly the displayed propagation kernel, with arbitrary data vector $ξ$ .

4.1givenstep 3.1algebra

On a legal clock, $H_{i n p u t}$ vanishes except at $c_{0}$ , where it is the data Hamming-weight operator $N_{1} = \sum_{i} ∣ 1 ⟩ ⟨ 1 ∣_{i}$ . Since $V_{0} = I$ , conjugation by $W$ leaves this block unchanged. For a kernel vector with data vector $ξ$ , its input energy is $⟨ ξ, N_{1} ξ ⟩ / (N + 1)$ , which is zero exactly when $ξ$ lies in the one-dimensional span of $∣ 0^{n} ⟩$ . Thus $H_{p r o p} + H_{i n p u t}$ has the unique normalized kernel vector $∣ η ⟩$ .

5.1givenstep 1.1step 4.1algebra

The clock penalty $H_{c l o c k}$ is positive semidefinite and has kernel exactly the legal unary strings: a binary string has no adjacent pattern $01$ exactly when all its $1$ bits precede all its $0$ bits. Each term of $H_{f i n a l}$ is positive semidefinite by step 1.1 and the definitions of $H_{i n p u t}, H_{c l o c k}$ . A zero-energy vector must therefore lie in the clock-penalty kernel and in the kernel identified in step 4.1. This proves uniqueness for the full final Hamiltonian.

5.2F1F2step 4.1algebra

Tracing the clock out of $∣ η ⟩ ⟨ η ∣$ and using [F1] removes all cross terms between distinct $c_{ℓ}$ , giving $ρ_{d a t a} = \frac{1}{N + 1} \sum_{ℓ = 0}^{N} ∣ V_{ℓ} 0^{n} ⟩ ⟨ V_{ℓ} 0^{n} ∣ .$ For each $ℓ \geq L$ , the appended gates are identities, so $V_{ℓ} ∣ 0^{n} ⟩ = ∣ ψ_{o u t} ⟩ : = U_{L} \dots U_{1} ∣ 0^{n} ⟩$ . There are $K + 1$ such indices, and the other $L$ terms form a density operator $σ$ after normalization. Hence $ρ_{d a t a} = \frac{L}{N + 1} σ + \frac{K + 1}{N + 1} ∣ ψ_{o u t} ⟩ ⟨ ψ_{o u t} ∣$ .

6.1F2F3step 5.2algebra∎

By homogeneity of the trace norm in the definition of trace distance, the distance from $∣ ψ_{o u t} ⟩ ⟨ ψ_{o u t} ∣$ is $\frac{L}{N + 1} D (σ, ∣ ψ_{o u t} ⟩ ⟨ ψ_{o u t} ∣) \leq L / (N + 1)$ by [F3]. Since $K = ⌈ 2 L / ε ⌉$ and $N = L + K$ , we have $L / (N + 1) \leq L / K \leq ε / 2$ .

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

Nonnegative monotone ground vector of the history path

Statement

Let $N \geq 1$ , $s \in [0, 1]$ , $a = 1 - s$ , $t = s / 2$ , and let $L_{N}$ be the graph Laplacian of the path with vertices $0, 1, \dots, N$ . Define the clock matrix $H_{0} (s) = a diag (0, 1, \dots, N) + t L_{N} .$ For each $s \in [0, 1]$ , its smallest eigenvalue is simple and has a normalized nonnegative eigenvector $v (s) = (v_{0}, \dots, v_{N})$ satisfying $v_{0} \geq v_{1} \geq \dots \geq v_{N} \geq 0.$ For $s > 0$ the vector is strictly positive; at $s = 0$ it is $e_{0}$ and its tail coordinates are zero. At $s = 1$ it is the uniform vector.

For a path produced by Five-local history-state adiabatic path, set $W_{0} = I$ , $W_{ℓ} = U_{ℓ} \dots U_{1}$ and $η_{ℓ} = W_{ℓ} ∣ 0^{n} ⟩ \otimes ∣ c_{ℓ} ⟩$ . The all-zero-input history sector $S_{0} = span {η_{0}, \dots, η_{N}}$ is invariant under $H (s)$ , and its restriction has matrix $H_{0} (s)$ in this orthonormal history basis.

Facts & Assumptions

Given: The unary clock and linear interpolation from Five-local history-state adiabatic path.

[F1]

A finite-dimensional self-adjoint operator has an orthonormal eigenbasis with real eigenvalues (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

Proof

1.1givenF1algebra

For the constructed path, the vectors $η_{ℓ}$ are orthonormal because the prefixes $W_{ℓ}$ are unitary and the clock states are orthonormal. The clock penalty vanishes on them. The input penalty annihilates $η_{0}$ because its data input is $∣ 0^{n} ⟩$ , and annihilates $η_{ℓ}$ for $ℓ > 0$ because the first clock bit is $1$ . Also $H_{c l o c k 0} η_{ℓ} = ℓ η_{ℓ}$ . Each propagation term $h_{ℓ}$ sends $η_{ℓ - 1}$ to $(η_{ℓ - 1} - η_{ℓ}) / 2$ and $η_{ℓ}$ to $(η_{ℓ} - η_{ℓ - 1}) / 2$ , and annihilates the other history basis vectors, since $W_{ℓ} = U_{ℓ} W_{ℓ - 1}$ . Thus $S_{0}$ is invariant and the restricted matrix is $a diag (0, 1, \dots, N) + t L_{N}$ . For every $N \geq 1$ , the quadratic form of this abstract matrix at $x$ is $a \sum_{i = 0}^{N} i ∣ x_{i} ∣^{2} + t \sum_{i = 0}^{N - 1} ∣ x_{i} - x_{i + 1} ∣^{2}$ , so both summands are positive semidefinite.

2.1step 1.1algebra

If $s = 0$ , then $H_{0} (0) = diag (0, 1, \dots, N)$ and its unique normalized nonnegative ground vector is $e_{0}$ . If $s = 1$ , then $H_{0} (1) = L_{N} / 2$ ; its quadratic form is one half the sum of squared adjacent differences, so its kernel consists exactly of constant vectors, giving the stated uniform ground vector.

2.2F1step 1.1algebra

Suppose $0 < s < 1$ , so $a, t > 0$ . The matrix is real symmetric with neighboring off-diagonal entries $- t$ . By [F1], a complex eigenvector for the smallest eigenvalue exists; its real or imaginary part is a nonzero real eigenvector because the matrix and eigenvalue are real. Normalize that real eigenvector. Expanding any vector in the eigenbasis from [F1] shows its Rayleigh quotient is a weighted average of the eigenvalues, so this real eigenvector minimizes the quotient. Replacing its coordinates by their absolute values does not increase the Rayleigh quotient, since each edge contribution is $t (x_{i} - x_{i + 1})^{2}$ and $(∣ x_{i} ∣ - ∣ x_{i + 1} ∣)^{2} \leq (x_{i} - x_{i + 1})^{2}$ ; therefore a nonnegative ground vector $v$ exists. Its eigenvalue equation at any zero coordinate forces every adjacent coordinate to be zero, and connectedness of the path would then force $v = 0$ . Hence $v_{i} > 0$ for every $i$ .

3.1step 2.2algebra

The endpoint equation at vertex $0$ determines $v_{1}$ uniquely from $v_{0}$ , and each interior equation determines $v_{i + 1}$ from $v_{i}, v_{i - 1}$ . If $v_{0} = 0$ , the endpoint equation gives $v_{1} = 0$ and recurrence gives $v = 0$ , impossible. Thus every eigenvector at a fixed eigenvalue is determined by its first coordinate, so the ground eigenspace is one-dimensional.

3.2step 1.1step 2.2F1algebra

Write $E$ for the ground eigenvalue and $d_{i} = v_{i} - v_{i + 1}$ for $0 \leq i < N$ . The endpoint and interior eigenvalue equations give $d_{0} = \frac{E}{t} v_{0}, d_{i} - d_{i - 1} = \frac{E - a i}{t} v_{i} (1 \leq i < N), d_{N - 1} = \frac{a N - E}{t} v_{N} .$ The ground energy satisfies $E \geq 0$ because both terms in $H_{0} (s)$ are positive semidefinite. Testing the normalized constant vector gives $E \leq a N / 2$ , because its Laplacian energy is zero and the average of $0, 1, \dots, N$ is $N / 2$ . Therefore $d_{0} \geq 0$ and $d_{N - 1} \geq 0$ .

4.1step 3.2algebra∎

Since $a > 0$ and each $v_{i} > 0$ , the increments $d_{i} - d_{i - 1}$ in step 3.2 are nonnegative while $a i \leq E$ and nonpositive after $a i \geq E$ . Thus the sequence $(d_{i})$ first does not decrease and then does not increase; every one of its entries is at least the smaller of its two endpoint entries. Step 3.2 makes both endpoints nonnegative, so every $d_{i} \geq 0$ . This proves $v_{i} \geq v_{i + 1}$ and completes the remaining case.

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

Restricted history-path gap

Statement

Let $N \geq 1$ be the number of propagation steps. On the legal-clock block with the zero data input, remove the input penalty and conjugate by the prefix unitaries as in History state and padded output. The resulting clock matrix is $H_{0} (s) = (1 - s) diag (0, 1, \dots, N) + \frac{s}{2} L_{N},$ where $L_{N}$ is the path Laplacian. Its ground eigenvalue is simple and its spectral gap is at least $1 / (48 N^{2})$ for every $s \in [0, 1]$ . In particular, the restricted clock gap is $Ω (N^{- 2})$ uniformly along the path.

Facts & Assumptions

Given: The five-local path and its legal-clock restriction from Five-local history-state adiabatic path.

[F1]

For every $s > 0$ , the normalized ground vector $v$ of $H_{0} (s)$ is strictly positive and nonincreasing in its clock index (Nonnegative monotone ground vector of the history path).

[F2]

For a finite irreducible reversible row-stochastic chain with stationary distribution $π$ , conductance $ϕ$ gives the algebraic spectral-gap estimate $1 - λ_{2} \geq ϕ^{2} / 2$ (Finite reversible Cheeger inequality).

[F3]

The finite-dimensional spectral theorem gives an orthonormal eigenbasis for $H_{0} (s)$ (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

Proof

1.1givenF3algebra

On legal clock $c_{i}$ , $H_{c l o c k 0}$ has eigenvalue $i$ ; the propagation terms have diagonal entries $1 / 2$ at the endpoints, $1$ internally, and adjacent entries $- 1 / 2$ . Therefore the clock matrix is the displayed $H_{0} (s) = a D + t L_{N}$ , where $a = 1 - s$ , $t = s / 2$ , and $D = diag (0, 1, \dots, N)$ .

2.1F3step 1.1algebra

If $0 \leq s \leq 1 / 6$ , the Rayleigh quotient at $e_{0}$ gives the ground eigenvalue $E_{0} \leq t$ . On the codimension-one subspace $e_{0}^{⊥}$ , $D \geq I$ and $L_{N} \geq 0$ , so every Rayleigh quotient there is at least $a$ . If the second eigenvalue $E_{1}$ were below $a$ , the span of eigenvectors for the two lowest eigenvalues would have dimension at least two and would contain a nonzero vector orthogonal to $e_{0}$ ; its quotient, as an eigenbasis expansion supported on eigenvalues at most $E_{1}$ , would be at most $E_{1} < a$ , a contradiction. Hence $E_{1} \geq a$ , and $E_{1} - E_{0} \geq a - t = 1 - 3 s / 2 \geq 3 / 4$ .

2.2F1F3step 1.1algebra

Now suppose $s \geq 1 / 6$ , so $t \geq 1 / 12$ , and let $v$ be the normalized positive ground vector from [F1], with eigenvalue $E_{0}$ . Set $π_{i} = v_{i}^{2}$ , so $\sum_{i} π_{i} = 1$ and $π_{0} \geq π_{1} \geq \dots \geq π_{N} > 0$ . For a vector $f = (f_{i})$ with $\sum_{i} π_{i} f_{i} = 0$ , set $x_{i} = v_{i} f_{i}$ ; then $x ⊥ v$ and $∥ x ∥^{2} = \sum_{i} π_{i} ∣ f_{i} ∣^{2}$ . The eigenvalue equation $H_{0} v = E_{0} v$ , expanded edge by edge, gives the ground-state identity $⟨ x, (H_{0} - E_{0} I) x ⟩ = t \sum_{i = 0}^{N - 1} v_{i} v_{i + 1} ∣ f_{i} - f_{i + 1} ∣^{2} .$ Indeed, the diagonal coefficient at vertex $i$ after subtracting $E_{0}$ is $t$ times the sum of neighboring ratios $v_{j} / v_{i}$ ; multiplying by $v_{i}^{2} ∣ f_{i} ∣^{2}$ assigns $t v_{i} v_{j} ∣ f_{i} ∣^{2}$ to each incident edge, and the off-diagonal term supplies $- 2 t v_{i} v_{j} Re ({\overline{f}}_{i} f_{j})$ .

3.1F1step 2.2constructalgebra

Since $v_{i} \geq v_{i + 1}$ , each edge weight satisfies $v_{i} v_{i + 1} \geq π_{i + 1}$ . Define a continuous-time reversible path chain with stationary masses $π_{i}$ and symmetric edge conductances $c_{i} = π_{i + 1}$ : its rate from $i$ to $i + 1$ is $c_{i} / π_{i} = π_{i + 1} / π_{i} \leq 1$ , and its reverse rate is $c_{i} / π_{i + 1} = 1$ . Each total exit rate is at most $2$ . Let $Q$ be its generator and $P = I + Q / 2$ . Then $P$ is row-stochastic, reversible with stationary law $π$ , and irreducible, and its Dirichlet form is $⟨ f, (I - P) f ⟩_{π} = \frac{1}{2} \sum_{i} c_{i} ∣ f_{i} - f_{i + 1} ∣^{2}$ .

4.1F1step 3.1choosealgebra

For any set $S$ with $0 < π (S) \leq 1 / 2$ , if $0 \in S$ , choose the largest $k$ for which ${0, \dots, k} \subseteq S$ . Then $k < N$ , edge $(k, k + 1)$ crosses the cut, and the tail mass is at least $1 / 2$ . Monotonicity gives $\sum_{j = k + 1}^{N} π_{j} \leq N π_{k + 1}$ , so $π_{k + 1} \geq 1 / (2 N)$ . The chain flow across the edge is $c_{k} / 2 = π_{k + 1} / 2$ , hence $Q_{P} (S, S^{c}) / π (S) \geq 1 / (2 N)$ . If $0 \notin S$ , put $k = \min S - 1$ ; then $S \subseteq {k + 1, \dots, N}$ and $π (S) \leq N π_{k + 1}$ , while the crossing flow is again $π_{k + 1} / 2$ , giving the same ratio bound. Thus $ϕ (P) \geq 1 / (2 N)$ .

5.1F2F3step 2.1step 2.2step 3.1step 4.1algebra∎

By [F2], $1 - λ_{2} (P) \geq 1 / (8 N^{2})$ . The generator gap is twice this number because $P = I + Q / 2$ , so its Dirichlet-form Poincaré constant is at least $1 / (4 N^{2})$ . For any $x ⊥ v$ , set $f_{i} = x_{i} / v_{i}$ ; then $\sum_{i} π_{i} f_{i} = 0$ . The ground-state identity in step 2.2 and $v_{i} v_{i + 1} \geq c_{i}$ give $⟨ x, (H_{0} - E_{0} I) x ⟩ \geq t / (4 N^{2}) ∥ x ∥^{2}$ . By [F3], expand $x$ in an orthonormal eigenbasis of $H_{0}$ with $v$ as its simple ground vector; choose $x$ to be a unit eigenvector for $E_{1}$ , orthogonal to $v$ . Its quotient is exactly $E_{1} - E_{0}$ , so the established lower bound applies to this $x$ . Thus $E_{1} - E_{0} \geq t / (4 N^{2}) \geq 1 / (48 N^{2})$ for $s \geq 1 / 6$ . Together with step 2.1, this proves the uniform bound.

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

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.

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

Full-space history-path gap

Statement

For the path in Five-local history-state adiabatic path, put $N = L + K$ , $K_{0} = n + 3 N$ , and $Δ_{0} = \frac{1}{216 (N + 1)^{3}}, J = 2 K_{0} + \frac{4 K_{0}^{2}}{Δ_{0}} + 1.$ For every $s \in [0, 1]$ , the full Hamiltonian has a unique ground state and its gap is greater than $3 Δ_{0} / 4$ . Consequently the minimum gap is $Ω (N^{- 3})$ .

Facts & Assumptions

Given: The five-local path, its input/propagation/clock terms, and the chosen $J$ from Five-local history-state adiabatic path.

[F1]

The zero-input legal clock block has gap at least $1 / (48 N^{2})$ (Restricted history-path gap).

[F2]

Its normalized ground vector $v$ is nonnegative and nonincreasing, and its ground state is unique (Nonnegative monotone ground vector of the history path).

[F3]

The ideal final history state is the unique kernel vector of $H_{i n p u t} + H_{p r o p} + J H_{c l o c k}$ (History state and padded output).

[F4]

The large clock-penalty lemma bounds the first two full eigenvalues by those of the legal compression with additive error $K^{2} / (J - 2 K)$ (Large clock-penalty perturbation).

[F5]

Finite self-adjoint matrices have an orthonormal eigenbasis (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

Proof

1.1givenF3constructalgebra

Let $S$ be the subspace of legal unary clocks. The prefix conjugation from History state and padded output preserves each clock basis state and makes $H_{p r o p}$ equal to $L_{N} / 2$ on the clock. Since the input penalty acts only at $c_{0}$ and the prefix at $c_{0}$ is the identity, the compression of $H_{1} (s) : = H (s) - J H_{c l o c k}$ to $S$ decomposes, in the computational basis $x \in {0, 1}^{n}$ , as $H_{x} (s) = H_{0} (s) + ∣ x ∣ ∣ c_{0} ⟩ ⟨ c_{0} ∣,$ where $H_{0} (s)$ is the zero-input clock block and $∣ x ∣$ is Hamming weight.

2.1F1F2F5step 1.1algebra

The $x = 0$ block has simple ground energy $E_{0}$ and gap $Δ \geq 1 / (48 N^{2})$ by [F1]–[F2]. Write $p = ∣ v_{0} ∣^{2}$ . Since $0 \leq v_{i} \leq v_{0}$ and $\sum_{i} ∣ v_{i} ∣^{2} = 1$ , $p \geq 1 / (N + 1) > 0$ . Also $Δ \leq 2$ : the compression of $H_{0} (s)$ to $S = span {e_{0}, e_{1}}$ is positive and has trace at most $2$ (for $N = 1$ its trace is $a + 2 t = 1$ , and for $N \geq 2$ it is $a + 3 t = 1 + s / 2 \leq 3 / 2$ ). If $u_{0}$ is a normalized ground vector, the two-dimensional space $S$ contains a nonzero vector $z ⊥ u_{0}$ . Its Rayleigh quotient is at least $E_{1}$ by expansion in an orthonormal eigenbasis, while the quotient is at most the largest eigenvalue of the compression to $S$ , hence at most its trace $2$ . Thus $E_{1} \leq 2$ and, since $E_{0} \geq 0$ , $Δ = E_{1} - E_{0} \leq 2$ .

3.1F1F2F5step 2.1algebra

For any $x \neq 0$ , put $r = ∣ x ∣ \geq 1$ and $R = ∣ c_{0} ⟩ ⟨ c_{0} ∣$ . The spectral gap of the zero-input block gives $H_{0} - E_{0} I \geq Δ (I - ∣ v ⟩ ⟨ v ∣)$ , and $r R \geq R$ . Thus $H_{x} - E_{0} I \geq B : = Δ (I - ∣ v ⟩ ⟨ v ∣) + R .$ If $p < 1$ , set $w = (c_{0} - \sqrt{p} v) / \sqrt{1 - p}$ . On the two-dimensional span of $v$ and $c_{0}$ , the matrix of $B$ in the orthonormal basis $v, w$ has trace $1 + Δ$ and determinant $p Δ$ . Its smaller eigenvalue is at least its determinant divided by its trace, hence at least $p Δ / (1 + Δ)$ . On the orthogonal complement, $B = Δ I$ , so this bound applies to the whole space. If $p = 1$ , then $c_{0} = v$ and $B$ has eigenvalues $1$ on $v$ and $Δ$ on $v^{⊥}$ , so $B \geq \min {1, Δ} I \geq Δ / (1 + Δ) I$ . Thus in either case $B \geq p Δ / (1 + Δ) I$ . By $Δ \leq 2$ , every nonzero-input block has ground energy at least $E_{0} + Δ p / 3 \geq E_{0} + 1 / [144 N^{2} (N + 1)]$ .

4.1step 2.1step 3.1algebra

The legal compression therefore has unique ground in the $x = 0$ block and gap at least $\min {\frac{1}{48 N^{2}}, \frac{1}{144 N^{2} (N + 1)}} = \frac{1}{144 N^{2} (N + 1)} \geq Δ_{0} .$ The last inequality is equivalent to $3 (N + 1)^{2} \geq 2 N^{2}$ , which holds for every $N \geq 1$ .

5.1givenF4F5step 4.1algebra

On the full register, $H_{2} = H_{c l o c k}$ is positive, vanishes exactly on $S$ , and is at least $I$ on $S^{⊥}$ : every illegal binary clock string contains at least one adjacent $01$ pair. To bound $H_{p r o p}$ , fix an assignment of all clock bits outside the local support of a term $h_{ℓ}$ . On the two local pattern states $a_{ℓ}, b_{ℓ}$ , the block is $\frac{1}{2} (\begin{array}{cc} I & - U_{ℓ}^{*} \\ - U_{ℓ} & I \end{array})$ ; it has eigenvalues $0$ and $1$ because $U_{ℓ}$ is unitary, and $h_{ℓ}$ is zero on the other local patterns. Thus $0 \leq h_{ℓ} \leq I$ , $∥ h_{ℓ} ∥ \leq 1$ , and $0 \leq H_{p r o p} \leq N I$ . Also $∥ H_{i n p u t} ∥ \leq n$ and $∥ H_{c l o c k 0} ∥ \leq N$ , by their sums of $n$ and $N$ projections. Hence $H_{1} (s) = H_{i n p u t} + (1 - s) H_{c l o c k 0} + s H_{p r o p}$ is self-adjoint and $∥ H_{1} (s) ∥ \leq n + (1 - s) N + s N = n + N \leq K_{0}$ . The legal dimension is $2^{n} (N + 1) \geq 2$ , so [F4] applies to its first two eigenvalues with $K = K_{0}$ .

6.1F4step 4.1step 5.1algebra∎

For this $J$ , $J > 2 K_{0}$ and $ϵ_{J} = \frac{K_{0}^{2}}{J - 2 K_{0}} < \frac{Δ_{0}}{4} .$ The perturbation bounds in [F4] give $λ_{1} (H (s)) \leq μ_{1}$ and $λ_{2} (H (s)) \geq μ_{2} - ϵ_{J}$ , where $μ_{2} - μ_{1} \geq Δ_{0}$ by step 4.1. Thus the full gap is at least $Δ_{0} - ϵ_{J} > 3 Δ_{0} / 4$ for every $s$ . Its positivity makes the ground state unique, and $Δ_{0} = Θ (N^{- 3})$ gives the stated asymptotic gap.

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

Circuit-to-adiabatic simulation

Statement

Let a uniform circuit have $n \geq 1$ data qubits and $L \geq 1$ gates, each on at most two data qubits. For rational $0 < ε \leq 1$ , set $K = ⌈ 2 L / ε ⌉$ and $N = L + K$ . The construction in Five-local history-state adiabatic path is a five-local finite Hermitian path with a product initial ground state, a unique ground state along the path, gap greater than $3 / [864 (N + 1)^{3}]$ , derivative bound $∥ H^{'} ∥ \leq 3 N$ , and $H^{''} = 0$ . If its term-time providers supply every call required by Discretized adiabatic path simulation schedule with the requested certified error at polynomial cost, and coefficient evaluations and output operations also have polynomial cost, the initial ground state can be evolved and the clock discarded to produce a data state at trace distance at most $ε$ from the circuit output, using $T = O (N^{11} / ε) = O (L^{11} ε^{- 12})$ continuous evolution time and polynomially many charged term calls, gates, coefficient bits and generator steps. The initial preparation cost, local term access costs, precision costs and output costs are recorded separately by Adiabatic path access and resource model.

Facts & Assumptions

Given: The uniformly described circuit, its explicitly supplied all-zero preparation, rational $ε$ , and declared polynomial-cost term and coefficient providers for the path.

[F1]

The five-local path is defined in Five-local history-state adiabatic path, with explicit initial preparation and term access coordinates in Adiabatic path access and resource model.

[F2]

Its final history state has data marginal within $L / (N + 1) \leq ε / 2$ of the circuit output (History state and padded output).

[F3]

The full path has a unique ground state and gap greater than $3 Δ_{0} / 4$ , with $Δ_{0} = 1 / [216 (N + 1)^{3}]$ (Full-space history-path gap).

[F4]

The finite-rank JRS bound controls the projector error by $A_{1} (1)$ (Finite JRS adiabatic projector bound).

[F5]

Partial trace contracts trace distance (Partial trace contracts trace distance); for pure states trace distance equals the square root of one minus squared overlap (Pure state trace distance).

[F6]

The proved path simulator supplies an access schedule with the requested operator error and charges the declared access and preparation costs; circuit-family providers compile to a circuit family under the stated polynomial-generation condition, while named-oracle calls retain their query charges (Finite adiabatic path simulation from term access).

[F7]

Trace norm satisfies the triangle inequality, so trace distance satisfies it on density operators (Trace Norm Duality And Norm Properties, Trace Distance).

Proof

1.1F1F3algebra

Write $H (s) = (1 - s) H_{i n i t} + s H_{f i n a l}$ . The common $H_{i n p u t}$ and $J H_{c l o c k}$ terms cancel in $H^{'}$ , leaving $H^{'} = H_{p r o p} - H_{c l o c k 0}$ , so $∥ H^{'} ∥ \leq 3 N$ from the term bounds, and $H^{''} = 0$ . By [F3], the full ground gap is at least $γ : = 3 Δ_{0} / 4 = 1 / [288 (N + 1)^{3}]$ throughout the path. Each term of $H_{i n i t} = H_{i n p u t} + H_{c l o c k 0} + J H_{c l o c k}$ is positive semidefinite. A binary string has no adjacent $01$ pair exactly when all of its $1$ bits precede all of its $0$ bits, so $H_{c l o c k}$ vanishes exactly on the legal unary clocks. On those clocks $H_{c l o c k 0}$ vanishes only at $c_{0}$ ; at $c_{0}$ , the input penalty vanishes exactly on $∣ 0^{n} ⟩$ . Thus the unique initial ground vector is $∣ 0^{n} ⟩ ∣ c_{0} ⟩$ , whose supplied preparation is included in [F1].

2.1F3F4step 1.1algebra

In the rank-one JRS expression from [F4], each endpoint term is at most $3 N / γ^{2}$ , and the integral term is at most $7 (3 N)^{2} / γ^{3}$ because $H^{''} = 0$ . Put $B_{T} = \frac{6 N}{γ^{2}} + \frac{63 N^{2}}{γ^{3}}, T = ⌈ \frac{4 B_{T}}{ε} ⌉ .$ Then $A_{1} (1) \leq B_{T} / T \leq ε / 4$ . Since $γ^{- 1} = 288 (N + 1)^{3}$ , we have $B_{T} = O (N^{11})$ and $T = O (N^{11} / ε)$ . Also $K = Θ (L / ε)$ and $N = Θ (L / ε)$ for $L \geq 1$ , $ε \leq 1$ , giving the stated $O (L^{11} ε^{- 12})$ bound.

3.1F4F5step 2.1algebra

Let $ψ_{T}$ be the ideal evolved unit vector and $η$ the final ground vector. The JRS projector estimate gives $∥ ∣ ψ_{T} ⟩ ⟨ ψ_{T} ∣ - ∣ η ⟩ ⟨ η ∣ ∥ \leq ε / 4$ . For rank-one projections the operator norm of their difference equals their trace distance: on the span of the two vectors the difference has eigenvalues $\pm \sqrt{1 - ∣ ⟨ ψ_{T}, η ⟩ ∣^{2}}$ , and it vanishes on the orthogonal complement. Thus their full-register trace distance is at most $ε / 4$ .

4.1F5F6step 3.1algebra

Run the proved simulator [F6] with tolerance $ε / 4$ and execute its schedule on the supplied initial vector. If ${\tilde{ψ}}_{T}$ is the resulting unit vector, operator-norm error gives $∥ {\tilde{ψ}}_{T} - ψ_{T} ∥ \leq ε / 4$ . Put $c = ⟨ ψ_{T}, {\tilde{ψ}}_{T} ⟩$ . By [F5], the pure-state trace distance squared is $(1 - ∣ c ∣) (1 + ∣ c ∣) \leq 2 (1 - ∣ c ∣) \leq 2 - 2 Re c = ∥ {\tilde{ψ}}_{T} - ψ_{T} ∥^{2}$ , so it is at most $ε / 4$ . By partial-trace contractivity, tracing out the clock does not increase either this error or the adiabatic error in step 3.1.

5.1F2F5F7step 3.1step 4.1algebra

The data marginal of $∣ η ⟩$ is within $ε / 2$ of the target circuit output by [F2]. By [F7], the triangle inequality for trace distance, steps 3.1–4.1, and the padding estimate give total output distance at most $ε / 4 + ε / 4 + ε / 2 = ε$ .

6.1F1F6step 2.1algebra∎

The term list has $M = n + N + N + (N - 1) = n + 3 N - 1 \leq n + 3 N$ terms: $n$ input projectors, $N$ clock-potential projectors, $N$ propagation terms, and $N - 1$ clock-penalty projectors. Each has norm at most $1$ by the local block calculation in the proof of the full-gap lemma and the projection form of the other terms. Set the certified derivative bound to $M_{1} = 3 N$ . The coefficient functions are the constants $1$ , $J$ , and the affine functions $s$ and $1 - s$ ; at rational grid points they are exactly computable rationals, so take zero coefficient error. For every sample, each coefficient has magnitude at most $J$ and each term norm is at most $1$ , whence $\sum_{p < q} ∥ [A_{p}, A_{q}] ∥ \leq 2 (\binom{M}{2}) J^{2} \leq M^{2} J^{2}$ ; use the finite rational certificate $B = M^{2} J^{2}$ . The value of $J = 2 K_{0} + 864 K_{0}^{2} (N + 1)^{3} + 1$ is polynomial in $n, N$ , so $M_{1}, B$ and all coefficient encodings have polynomial bit length. With $T = ⌈ 4 B_{T} / ε ⌉ = O (N^{11} / ε)$ and $M_{1} = 3 N$ , the grid count $q = O (T N / ε)$ is polynomial. Since $τ = T / q \leq ε / (9 N)$ , the product-formula count $r_{P F} \leq 1 + 3 q τ^{2} B / ε = 1 + 3 T τ B / ε$ is polynomial as well. Thus [F6] executes finitely many, polynomially many term calls, and by hypothesis their requested-error providers, coefficient procedures and output operation have polynomial charged cost. Preparation cost, queries, gates, ancillas, coefficient precision, circuit-description bits and generator time are all separately recorded; no spectral projector is used to prepare the initial state.

5 · Examples, counterexamples and false statements

None yet.

Adiabatic Computation and Circuit Equivalence

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Finite reversible Cheeger inequality

Statement

Facts & Assumptions

Proof

Large clock-penalty perturbation

Statement

Facts & Assumptions

Proof

Partial trace contracts trace distance

Statement

Facts & Assumptions

Proof

Finite adiabatic path model

Definition

Finite gapped spectral projection regularity

Statement

Facts & Assumptions

Proof

Adiabatic path access and resource model

Definition

Finite spectral-band derivative estimates for adiabatic paths

Statement

Facts & Assumptions

Proof

Finite JRS adiabatic projector bound

Statement

Facts & Assumptions

Proof

Discretized adiabatic path simulation schedule

Definition

Five-local history-state adiabatic path

Definition

History state and padded output

Statement

Facts & Assumptions

Proof

Nonnegative monotone ground vector of the history path

Statement

Facts & Assumptions

Proof

Restricted history-path gap

Statement

Facts & Assumptions

Proof

Finite adiabatic path simulation from term access

Statement

Facts & Assumptions

Proof

Full-space history-path gap

Statement

Facts & Assumptions

Proof

Circuit-to-adiabatic simulation

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources