Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Adiabatic theorem for the linear interpolation (1 − s)H_I + sH_F

Proved
QAlgorithms.Nannicini.adiabatic_theorem_linInterp

by Goku · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

lecture-notesnanniciniquantum-information

There is an absolute constant ccc with the following property.

Let HI,HFH_I, H_FHI​,HF​ be Hermitian matrices on a finite-dimensional space Cι\mathbb{C}^\iotaCι and let

H(s)=(1−s)HI+sHF,s∈[0,1],H(s) = (1-s) H_I + s H_F, \qquad s \in [0,1],H(s)=(1−s)HI​+sHF​,s∈[0,1],

be their linear interpolation (Eq. (9.6)). Let λ:[0,1]→R\lambda : [0,1] \to \mathbb{R}λ:[0,1]→R be continuous and let ∣φ(s)⟩|\varphi(s)\rangle∣φ(s)⟩ be a unit eigenvector of H(s)H(s)H(s) with eigenvalue λ(s)\lambda(s)λ(s). Let γ>0\gamma > 0γ>0 be a spectral gap around λ\lambdaλ: for every sss, λ(s)\lambda(s)λ(s) is a simple eigenvalue of H(s)H(s)H(s) and every other eigenvalue lies at distance at least γ\gammaγ from it. Let δ>0\delta > 0δ>0 and

T≥cδ(∥HF−HI∥γ2+∥HF−HI∥2γ3).T \ge \frac{c}{\delta}\left(\frac{\|H_F - H_I\|}{\gamma^2} + \frac{\|H_F - H_I\|^2}{\gamma^3}\right).T≥δc​(γ2∥HF​−HI​∥​+γ3∥HF​−HI​∥2​).

If ∣ψ(s)⟩|\psi(s)\rangle∣ψ(s)⟩ solves d∣ψ(s)⟩ds=iT H(s)∣ψ(s)⟩\frac{d|\psi(s)\rangle}{ds} = iT\,H(s)|\psi(s)\rangledsd∣ψ(s)⟩​=iTH(s)∣ψ(s)⟩ on [0,1][0,1][0,1] with ∣ψ(0)⟩=∣φ(0)⟩|\psi(0)\rangle = |\varphi(0)\rangle∣ψ(0)⟩=∣φ(0)⟩, then

∥eiθ∣ψ(1)⟩−∣φ(1)⟩∥≤δfor some θ∈R.\bigl\| e^{i\theta}|\psi(1)\rangle - |\varphi(1)\rangle \bigr\| \le \delta \quad \text{for some } \theta \in \mathbb{R}.​eiθ∣ψ(1)⟩−∣φ(1)⟩​≤δfor some θ∈R.

This is the form of the adiabatic theorem used for adiabatic optimization by linear interpolation: the running time is governed by ∥HF−HI∥\|H_F - H_I\|∥HF​−HI​∥ and the minimum gap γ\gammaγ along the path.

Formalization Note ∥⋅∥\|\cdot\|∥⋅∥ is the operator norm. Since H′=HF−HIH' = H_F - H_IH′=HF​−HI​ and H′′=0H'' = 0H′′=0, no derivative data are supplied. The source's γ=min⁡sγ(s)\gamma = \min_s \gamma(s)γ=mins​γ(s) is replaced by any lower bound γ>0\gamma > 0γ>0 on the gaps, which is equivalent because the bound on TTT decreases in γ\gammaγ. The constant ccc is quantified before all data.

Preamble
import Definitions.Def_QAlgorithms_Defs_Adiabatic
set_option autoImplicit false
Formal statement
universe u

namespace QAlgorithms.Nannicini



/-- Nannicini p.225, Corollary 9.24 (Adiabatic theorem for linear interpolation). There exists
some constant `c` such that, when the Hamiltonian `H(s)` performs linear interpolation between an
initial and a final Hamiltonian, as in Eq. (9.6), the statement of Thm. 9.11 holds if we choose `T`
satisfying `T ≥ (c/δ)(‖H_F − H_I‖/γ² + ‖H_F − H_I‖²/γ³)`.

`H(s) = (1 − s)H_I + sH_F` is the frozen `linInterp HI HF s` (Eq. (9.6)), with `H_I, H_F`
Hermitian; it is smooth, `H′ = H_F − H_I`, `H″ = 0`, so no derivative data are supplied. The
constant `c` precedes everything it is uniform over (trap 8). The gap `γ` of Def. 9.9 enters as
any `γ > 0` with `HasGapAround (H s) (λ s) γ` for all `s`, equivalent by monotonicity; the norm is
the operator norm `specNorm`. The other hypotheses are Theorem 9.11's. -/
theorem adiabatic_theorem_linInterp :
    ∃ c : ℝ, ∀ {ι : Type u} [Fintype ι] [DecidableEq ι] (HI HF : Matrix ι ι ℂ),
      HI.IsHermitian → HF.IsHermitian →
      ∀ (lam : ℝ → ℝ), ContinuousOn lam (Set.Icc 0 1) →
      ∀ (φ : ℝ → EuclideanSpace ℂ ι),
      (∀ s ∈ Set.Icc (0 : ℝ) 1,
        IsState (φ s) ∧ act (linInterp HI HF s) (φ s) = (lam s : ℂ) • φ s) →
      ∀ (γ : ℝ), 0 < γ →
      (∀ s ∈ Set.Icc (0 : ℝ) 1, HasGapAround (linInterp HI HF s) (lam s) γ) →
      ∀ (δ : ℝ), 0 < δ → ∀ (T : ℝ),
      c / δ * (specNorm (HF - HI) / γ ^ 2 + specNorm (HF - HI) ^ 2 / γ ^ 3) ≤ T →
      ∀ (ψ : ℝ → EuclideanSpace ℂ ι), SolvesAdiabaticPlus (linInterp HI HF) T ψ → ψ 0 = φ 0 →
      ∃ θ : ℝ, ‖Complex.exp ((θ : ℂ) * Complex.I) • ψ 1 - φ 1‖ ≤ δ := by
  sorry


end QAlgorithms.Nannicini
Source
Giacomo Nannicini, Quantum algorithms for optimizers, 2025, v5; notes dated 9 July 2025, PDF p. 225, Corollary 9.24. https://arxiv.org/pdf/2408.07086v5
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Statement form. There exists a single real constant ccc, with no sign condition, chosen before everything else, such that the following holds.

Notation. For Hermitian HI,HFH_I, H_FHI​,HF​, set

H(s)=(1−s)HI+sHF.H(s)=(1-s)H_I+sH_F.H(s)=(1−s)HI​+sHF​.

∥⋅∥op\|\cdot\|_{\mathrm{op}}∥⋅∥op​ is the spectral norm. "Gap γ\gammaγ around λ\lambdaλ" means: Hermitian, λ\lambdaλ occurs exactly once in the increasingly sorted eigenvalue list counted with multiplicity, and all other listed eigenvalues lie at distance at least γ\gammaγ from λ\lambdaλ.

Hypotheses. For every finite index type ι\iotaι (fixed universe, decidable equality), assume the following.

  • HI,HF∈Cι×ιH_I,H_F\in\mathbb{C}^{\iota\times\iota}HI​,HF​∈Cι×ι are both Hermitian.
  • λ:R→R\lambda:\mathbb{R}\to\mathbb{R}λ:R→R is continuous on [0,1][0,1][0,1].
  • φ:R→Cι\varphi:\mathbb{R}\to\mathbb{C}^\iotaφ:R→Cι satisfies ∥φ(s)∥=1\|\varphi(s)\|=1∥φ(s)∥=1 and H(s)φ(s)=λ(s)φ(s)H(s)\varphi(s)=\lambda(s)\varphi(s)H(s)φ(s)=λ(s)φ(s) for all s∈[0,1]s\in[0,1]s∈[0,1].
  • γ>0\gamma>0γ>0, and H(s)H(s)H(s) has a gap γ\gammaγ around λ(s)\lambda(s)λ(s) for every s∈[0,1]s\in[0,1]s∈[0,1].
  • δ>0\delta>0δ>0, and TTT is a real number with
cδ(∥HF−HI∥opγ2+∥HF−HI∥op2γ3)≤T.\frac{c}{\delta}\left(\frac{\|H_F-H_I\|_{\mathrm{op}}}{\gamma^2}+\frac{\|H_F-H_I\|_{\mathrm{op}}^2}{\gamma^3}\right)\le T.δc​(γ2∥HF​−HI​∥op​​+γ3∥HF​−HI​∥op2​​)≤T.
  • ψ:R→Cι\psi:\mathbb{R}\to\mathbb{C}^\iotaψ:R→Cι satisfies ψ′(s)=i T ((1−s)HI+sHF)ψ(s)\psi'(s)=i\,T\,\bigl((1-s)H_I+sH_F\bigr)\psi(s)ψ′(s)=iT((1−s)HI​+sHF​)ψ(s) for all s∈[0,1]s\in[0,1]s∈[0,1], with the derivative taken within [0,1][0,1][0,1].
  • ψ(0)=φ(0)\psi(0)=\varphi(0)ψ(0)=φ(0).

Conclusion. There is a real θ\thetaθ with

∥eiθψ(1)−φ(1)∥≤δ.\|e^{i\theta}\psi(1)-\varphi(1)\|\le\delta.∥eiθψ(1)−φ(1)∥≤δ.

Edge cases.

  • No positivity of ccc is asserted. If c≤0c\le0c≤0, the constraint on TTT is satisfied by every T≥T\geT≥ a non-positive number.
  • If HF=HIH_F=H_IHF​=HI​, the bound on TTT reads 0≤T0\le T0≤T.
  • An empty ι\iotaι makes the hypotheses unsatisfiable.
Human review
  • Endorsed by Shuze Chen · Oct 13, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 13, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me