Adiabatic theorem for the linear interpolation (1 − s)H_I + sH_F
ProvedQAlgorithms.Nannicini.adiabatic_theorem_linInterpThere is an absolute constant with the following property.
Let be Hermitian matrices on a finite-dimensional space and let
be their linear interpolation (Eq. (9.6)). Let be continuous and let be a unit eigenvector of with eigenvalue . Let be a spectral gap around : for every , is a simple eigenvalue of and every other eigenvalue lies at distance at least from it. Let and
If solves on with , then
This is the form of the adiabatic theorem used for adiabatic optimization by linear interpolation: the running time is governed by and the minimum gap along the path.
Formalization Note is the operator norm. Since and , no derivative data are supplied. The source's is replaced by any lower bound on the gaps, which is equivalent because the bound on decreases in . The constant is quantified before all data.
import Definitions.Def_QAlgorithms_Defs_Adiabatic set_option autoImplicit false
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement form. There exists a single real constant , with no sign condition, chosen before everything else, such that the following holds.
Notation. For Hermitian , set
is the spectral norm. "Gap around " means: Hermitian, occurs exactly once in the increasingly sorted eigenvalue list counted with multiplicity, and all other listed eigenvalues lie at distance at least from .
Hypotheses. For every finite index type (fixed universe, decidable equality), assume the following.
- are both Hermitian.
- is continuous on .
- satisfies and for all .
- , and has a gap around for every .
- , and is a real number with
- satisfies for all , with the derivative taken within .
- .
Conclusion. There is a real with
Edge cases.
- No positivity of is asserted. If , the constraint on is satisfied by every a non-positive number.
- If , the bound on reads .
- An empty makes the hypotheses unsatisfiable.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.