Theory Trotter_Product_Formula

theory Trotter_Product_Formula
  imports Hermitian_Functional_Calculus
begin

section ‹The Lie--Trotter product formula›

text ‹For Hermitian $H_1,\dots,H_m$ with $\norm{H_jv}\le L\norm v$, $r$ rounds of
$e^{itH_1/r}\cdots e^{itH_m/r}$ are within $2(mLt)^2/r$ of $e^{it(H_1+\dots+H_m)}$ (‹trotter›).
Each factor is $I+i\delta H_j$ up to $(\delta L)^2$, from $|e^{ix}-1-ix|\le x^2$ and the functional
calculus; the errors add along products and powers of unitaries.›

subsection ‹Scalar bounds›

text ‹Taylor remainders of first order:
\[ |\sin x-x|\le\tfrac{x^2}{2},\qquad|\cos x-1|\le\tfrac{x^2}{2},\qquad|e^{ix}-1-ix|\le x^2,\qquad|e^{ix}-1|\le|x|. \]›

lemma sin_minus_x_bound: "¦sin (x::real) - x¦ ≤ x2 / 2"
proof (cases "¦x¦ ≤ 3")
  case True
  have m: "¦sin x - (∑m<3. sin_coeff m * x ^ m)¦ ≤ inverse (fact 3) * ¦x¦ ^ 3"
    by (rule Maclaurin_sin_bound)
  have s: "(∑m<3. sin_coeff m * x ^ m) = x"
    by (simp add: sin_coeff_def eval_nat_numeral)
  have f: "inverse (fact 3) * ¦x¦ ^ 3 = ¦x¦ ^ 3 / (6::real)" by (simp add: fact_numeral)
  have "¦sin x - x¦ ≤ ¦x¦ ^ 3 / 6" using m unfolding s f .
  also have "… = ¦x¦ * x2 / 6" by (simp add: power2_eq_square power3_eq_cube)
  also have "… ≤ 3 * x2 / 6" by (rule divide_right_mono, rule mult_right_mono) (use True in simp_all)
  finally show ?thesis by simp
next
  case False
  have "¦sin x - x¦ ≤ 1 + ¦x¦" using abs_sin_le_one[of x] by linarith
  also have "… ≤ x2 / 2"
  proof -
    have "3 * ¦x¦ ≤ ¦x¦ * ¦x¦" using False by (intro mult_right_mono) simp_all
    thus ?thesis using False by (simp add: power2_eq_square)
  qed
  finally show ?thesis .
qed

lemma cos_minus_one_bound: "¦cos (x::real) - 1¦ ≤ x2 / 2"
proof -
  have "cos x = 1 - 2 * sin (x / 2) ^ 2" using cos_double_sin[of "x / 2"] by simp
  hence "¦cos x - 1¦ = 2 * sin (x / 2) ^ 2" by simp
  also have "… ≤ 2 * (x / 2) ^ 2"
    using abs_le_square_iff[THEN iffD1, OF abs_sin_x_le_abs_x[of "x / 2"]] by simp
  also have "… = x2 / 2" by (simp add: power2_eq_square)
  finally show ?thesis .
qed

lemma cis_remainder: "cmod (cis (x::real) - 1 - 𝗂 * complex_of_real x) ≤ x2"
proof -
  have "cmod (cis x - 1 - 𝗂 * complex_of_real x) ≤ ¦Re (cis x - 1 - 𝗂 * complex_of_real x)¦ + ¦Im (cis x - 1 - 𝗂 * complex_of_real x)¦"
    by (rule cmod_le)
  also have "… = ¦cos x - 1¦ + ¦sin x - x¦" by simp
  also have "… ≤ x2 / 2 + x2 / 2" by (rule add_mono[OF cos_minus_one_bound sin_minus_x_bound])
  finally show ?thesis by simp
qed

lemma cis_minus_one: "cmod (cis (x::real) - 1) ≤ ¦x¦"
proof -
  have "(cmod (cis x - 1))2 = (cos x - 1)2 + (sin x)2" by (simp add: cmod_def)
  also have "… = 2 - 2 * cos x" using sin_cos_squared_add[of x] by (simp add: power2_eq_square algebra_simps)
  also have "… = 4 * (sin (x / 2))2" using cos_double_sin[of "x / 2"] by simp
  also have "… ≤ 4 * (x / 2)2"
    using abs_le_square_iff[THEN iffD1, OF abs_sin_x_le_abs_x[of "x / 2"]] by simp
  also have "… = ¦x¦2" by (simp add: power2_eq_square)
  finally show ?thesis by (simp add: abs_le_square_iff[symmetric])
qed

subsection ‹Bounds from the spectrum›

lemma vnorm_minus_le:
  assumes "dim_vec a = dim_vec b"
  shows "∥a - b∥ ≤ ∥a∥ + ∥b∥"
proof -
  have "a - b = a + (-1) ⋅v b" using assms by (intro eq_vecI) simp_all
  thus ?thesis using vnorm_add_le[of a "(-1) ⋅v b"] assms cpx_vec_length_smult[of "-1" b] by simp
qed

text ‹If $\norm{Av}\le L\norm v$ for all $v$, every eigenvalue satisfies $|\lambda|\le L$; and if $|g|\le c$ on
the spectrum, $\norm{g(A)v}\le c\norm v$.›

lemma herm_spectrum_bound:
  assumes A: "A ∈ carrier_mat n n" and b: "⋀v. dim_vec v = n ⟹ ∥A *v v∥ ≤ L * ∥v∥"
      and l: "l ∈ herm_spectrum A"
  shows "¦l¦ ≤ L"
proof -
  obtain v where v: "dim_vec v = n" "v ≠ 0v n" "A *v v = complex_of_real l ⋅v v"
    using l A unfolding herm_spectrum_iff by auto
  have "¦l¦ * ∥v∥ = ∥A *v v∥" using v(3) by (simp add: cpx_vec_length_smult)
  also have "… ≤ L * ∥v∥" by (rule b[OF v(1)])
  finally show ?thesis using mult_right_le_imp_le vnorm_pos[OF v(1,2)] by blast
qed

lemma mat_fun_bound:
  assumes A: "A ∈ carrier_mat n n" "hermitian A" and c: "0 ≤ c"
      and g: "⋀l. l ∈ herm_spectrum A ⟹ cmod (g l) ≤ c" and v: "dim_vec v = n"
  shows "∥mat_fun g A *v v∥ ≤ c * ∥v∥"
proof -
  obtain U Dl where sd: "spectral_decomp A U Dl" using spectral_decomp_exists[OF A] by blast
  note d = spectral_decompD[OF A(1) sd]
  have Ud: "U† ∈ carrier_mat n n" by (rule dagger_carrier[OF d(1)])
  have gD: "diag_matrix (map g Dl) ∈ carrier_mat n n" using diag_matrix_carrier[of "map g Dl"] d(3) by simp
  define w where "w = U† *v v"
  have w: "dim_vec w = n" using carrier_matD[OF d(1)] by (simp add: w_def)
  have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF v])
  have wc: "w ∈ carrier_vec n" by (rule carrier_vecI[OF w])
  have "mat_fun g A *v v = (U * diag_matrix (map g Dl)) *v w"
    unfolding mat_fun_decomp[OF A sd] w_def by (rule assoc_mult_mat_vec[OF mult_carrier_mat[OF d(1) gD] Ud vc])
  also have "… = U *v (diag_matrix (map g Dl) *v w)" by (rule assoc_mult_mat_vec[OF d(1) gD wc])
  finally have "∥mat_fun g A *v v∥ = ∥diag_matrix (map g Dl) *v w∥"
    using unitary_vnorm[OF d(1,2), of "diag_matrix (map g Dl) *v w"] gD d(3) by simp
  also have "… ≤ c * ∥w∥"
  proof -
    have dv: "diag_matrix (map g Dl) *v w = Matrix.vec n (λi. g (Dl ! i) * w $ i)"
      using diag_matrix_mult_vec[of w "map g Dl"] w d(3) by (auto intro!: eq_vecI)
    have "∥diag_matrix (map g Dl) *v w∥2 = (∑i<n. (cmod (g (Dl ! i) * w $ i))2)"
      unfolding dv vnorm_sq by simp
    also have "… ≤ (∑i<n. c2 * (cmod (w $ i))2)"
    proof (rule sum_mono)
      fix i assume "i ∈ {..<n}"
      hence "cmod (g (Dl ! i)) ≤ c" using g spectral_decomp_eig_in_spectrum[OF A(1) sd] by simp
      hence "(cmod (g (Dl ! i)))2 ≤ c2" by (rule power_mono) simp
      thus "(cmod (g (Dl ! i) * w $ i))2 ≤ c2 * (cmod (w $ i))2"
        by (simp add: norm_mult power_mult_distrib mult_right_mono)
    qed
    also have "… = (c * ∥w∥)2" by (simp add: vnorm_sq w power_mult_distrib sum_distrib_left)
    finally show ?thesis by (rule power2_le_imp_le) (simp add: c vnorm_ge0)
  qed
  also have "∥w∥ = ∥v∥" unfolding w_def by (rule unitary_vnorm[OF Ud unitary_dagger[OF d(2)] v])
  finally show ?thesis .
qed

text ‹The functions $e^{idx}-1-idx$ and $e^{idx}-1$ applied to $A$ give $e^{idA}-I-idA$ and $e^{idA}-I$.›

lemma mat_fun_evolution_rem:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun (λx. cis (d * x) - 1 - 𝗂 * complex_of_real (d * x)) A =
    evolution A d - 1m n - (𝗂 * complex_of_real d) ⋅m A" (is "_ = ?B")
proof (rule mat_fun_eqI[OF A])
  show "?B ∈ carrier_mat n n" by (intro minus_carrier_mat smult_carrier_mat) (rule A(1))
  show "?B acts_as (λx. cis (d * x) - 1 - 𝗂 * complex_of_real (d * x)) on_eigenvectors_of A" unfolding acts_on_eigenvectors_def
  proof (intro allI impI)
    fix v l assume v: "dim_vec v = dim_row A" and ev: "A *v v = complex_of_real l ⋅v v"
    have vn: "dim_vec v = n" using v A(1) by simp
    have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF vn])
    have e: "evolution A d *v v = cis (d * l) ⋅v v" by (rule evolution_eigen[OF A vn ev])
    have E1: "evolution A d - 1m n ∈ carrier_mat n n" by (rule minus_carrier_mat) simp
    have m1: "(evolution A d - 1m n) *v v = evolution A d *v v - 1m n *v v"
      by (rule minus_mult_distrib_mat_vec[OF evolution_carrier[OF A] one_carrier_mat vc])
    have "?B *v v = (evolution A d - 1m n) *v v - ((𝗂 * complex_of_real d) ⋅m A) *v v"
      by (rule minus_mult_distrib_mat_vec[OF E1 smult_carrier_mat[OF A(1)] vc])
    also have "… = evolution A d *v v - 1m n *v v - ((𝗂 * complex_of_real d) ⋅m A) *v v"
      by (simp only: m1)
    also have "… = cis (d * l) ⋅v v - v - (𝗂 * complex_of_real d) ⋅v (complex_of_real l ⋅v v)"
      using e ev smult_mat_mult_mat_vec_assoc[OF A(1) carrier_vecI[OF vn]] vc by simp
    also have "… = (cis (d * l) - 1 - 𝗂 * complex_of_real (d * l)) ⋅v v"
      by (intro eq_vecI) (simp_all add: algebra_simps)
    finally show "?B *v v = (cis (d * l) - 1 - 𝗂 * complex_of_real (d * l)) ⋅v v" .
  qed
qed

lemma mat_fun_evolution_one:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun (λx. cis (d * x) - 1) A = evolution A d - 1m n" (is "_ = ?B")
proof (rule mat_fun_eqI[OF A])
  show "?B ∈ carrier_mat n n" by (rule minus_carrier_mat) simp
  show "?B acts_as (λx. cis (d * x) - 1) on_eigenvectors_of A" unfolding acts_on_eigenvectors_def
  proof (intro allI impI)
    fix v l assume v: "dim_vec v = dim_row A" and ev: "A *v v = complex_of_real l ⋅v v"
    have vn: "dim_vec v = n" using v A(1) by simp
    have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF vn])
    have e: "evolution A d *v v = cis (d * l) ⋅v v" by (rule evolution_eigen[OF A vn ev])
    have "?B *v v = evolution A d *v v - 1m n *v v"
      by (rule minus_mult_distrib_mat_vec[OF evolution_carrier[OF A] one_carrier_mat vc])
    also have "… = (cis (d * l) - 1) ⋅v v" using e vc by (intro eq_vecI, simp_all add: algebra_simps)
    finally show "?B *v v = (cis (d * l) - 1) ⋅v v" .
  qed
qed

subsection ‹Closeness of operators›

text ‹$U$ and $V$ are $\eta$-close, written ‹U ≈η V›, if $\norm{Uv-Vv}\le\eta\norm v$ for every $v$:
the operator norm of $U-V$ is at most $\eta$.›

definition op_close :: "complex Matrix.mat ⇒ real ⇒ complex Matrix.mat ⇒ bool"
    ("(_ ≈⇘_⇙/ _)" [51, 0, 51] 50) where
  "U ≈⇘η⇙ V ⟷ (∀v. dim_vec v = dim_col U ⟶ ∥U *v v - V *v v∥ ≤ η * ∥v∥)"

text ‹For $U\in M_{m,n}$ closeness is a bound on the vectors of length $n$.›

lemma op_close_iff:
  assumes "U ∈ carrier_mat m n"
  shows "U ≈⇘η⇙ V ⟷ (∀v. dim_vec v = n ⟶ ∥U *v v - V *v v∥ ≤ η * ∥v∥)"
  using assms by (simp add: op_close_def)

lemma op_closeI:
  assumes "U ∈ carrier_mat m n" and "⋀v. dim_vec v = n ⟹ ∥U *v v - V *v v∥ ≤ η * ∥v∥"
  shows "U ≈⇘η⇙ V"
  using assms by (simp add: op_close_def)

lemma op_closeD:
  "U ≈⇘η⇙ V ⟹ U ∈ carrier_mat m n ⟹ dim_vec v = n ⟹ ∥U *v v - V *v v∥ ≤ η * ∥v∥"
  by (simp add: op_close_def)

text ‹Closeness is reflexive and symmetric, and passes to adjoints of unitaries, since
$U^*-V^*=U^*(V-U)V^*$ and unitaries preserve norms.›

lemma op_close_refl:
  assumes e: "0 ≤ η" and U: "U ∈ carrier_mat n n"
  shows "U ≈⇘η⇙ U"
proof -
  have z: "U *v v - U *v v = 0v n" if "dim_vec v = n" for v :: "complex Matrix.vec"
    using that U by (intro eq_vecI) simp_all
  show ?thesis
  proof (rule op_closeI[OF U])
    fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
    have "∥U *v v - U *v v∥ = 0" unfolding z[OF v] by (simp add: cpx_vec_length_def)
    thus "∥U *v v - U *v v∥ ≤ η * ∥v∥" using e vnorm_ge0[of v] by simp
  qed
qed

lemma op_close_sym:
  assumes "U ≈⇘η⇙ V" "U ∈ carrier_mat n n" "V ∈ carrier_mat n n"
  shows "V ≈⇘η⇙ U"
proof (rule op_closeI[OF assms(3)])
  fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
  have "∥V *v v - U *v v∥ = ∥U *v v - V *v v∥" by (rule vnorm_minus_commute) (use assms in simp)
  thus "∥V *v v - U *v v∥ ≤ η * ∥v∥" using op_closeD[OF assms(1,2) v] by simp
qed

lemma op_close_dagger:
  assumes U: "U ∈ carrier_mat n n" "unitary U" and V: "V ∈ carrier_mat n n" "unitary V"
      and c: "U ≈⇘η⇙ V"
  shows "U† ≈⇘η⇙ V†"
proof (rule op_closeI[OF dagger_carrier[OF U(1)]])
  fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
  have vc: "v ∈ carrier_vec n" using v by (rule carrier_vecI)
  have Ud: "U† ∈ carrier_mat n n" and Vd: "V† ∈ carrier_mat n n" using U V by (simp_all add: dagger_carrier)
  have UU: "U * (U†) = 1m n" and VV: "V * (V†) = 1m n" using U V unfolding unitary_def by auto
  let ?w = "V† *v v"
  have w: "dim_vec ?w = n" using V(1) by simp
  have dd: "dim_vec (U† *v v - ?w) = n" using U(1) V(1) by simp
  have uv: "U *v (U† *v v) = v" using assoc_mult_mat_vec[OF U(1) Ud vc, symmetric] UU vc by simp
  have vw: "V *v ?w = v" using assoc_mult_mat_vec[OF V(1) Vd vc, symmetric] VV vc by simp
  have e: "U *v (U† *v v - ?w) = V *v ?w - U *v ?w"
  proof -
    have "U *v (U† *v v - ?w) = U *v (U† *v v) - U *v ?w"
      by (rule mult_minus_distrib_mat_vec[OF U(1)]) (use Ud Vd vc in simp_all)
    thus ?thesis unfolding uv vw .
  qed
  have "∥U† *v v - ?w∥ = ∥U *v (U† *v v - ?w)∥" by (rule unitary_vnorm[OF U dd, symmetric])
  also have "… = ∥U *v ?w - V *v ?w∥" unfolding e by (rule vnorm_minus_commute) (use U V in simp)
  also have "… ≤ η * ∥?w∥" by (rule op_closeD[OF c U(1) w])
  also have "∥?w∥ = ∥v∥" by (rule unitary_vnorm[OF Vd unitary_dagger[OF V(2)] v])
  finally show "∥U† *v v - V† *v v∥ ≤ η * ∥v∥" .
qed

subsection ‹First-order bounds›

context
  fixes A :: "complex Matrix.mat" and n :: nat and L :: real
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
      and Ab: "⋀v. dim_vec v = n ⟹ ∥A *v v∥ ≤ L * ∥v∥"
begin

text ‹For $\norm{Av}\le L\norm v$, the bounds above applied on the spectrum give
\[ \norm{e^{idA}v-v-id\,Av}\le(dL)^2\norm v,\qquad \norm{e^{idA}v-v}\le|d|L\norm v. \]›

lemma evolution_first_order:
  assumes v: "dim_vec v = n"
  shows "∥evolution A d *v v - v - (𝗂 * complex_of_real d) ⋅v (A *v v)∥ ≤ (d * L)2 * ∥v∥"
proof -
  have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF v])
  have E1: "evolution A d - 1m n ∈ carrier_mat n n" by (rule minus_carrier_mat) simp
  have m1: "(evolution A d - 1m n) *v v = evolution A d *v v - 1m n *v v"
    by (rule minus_mult_distrib_mat_vec[OF evolution_carrier[OF A] one_carrier_mat vc])
  have "mat_fun (λx. cis (d * x) - 1 - 𝗂 * complex_of_real (d * x)) A *v v =
      (evolution A d - 1m n - (𝗂 * complex_of_real d) ⋅m A) *v v"
    by (simp only: mat_fun_evolution_rem[OF A])
  also have "… = (evolution A d - 1m n) *v v - ((𝗂 * complex_of_real d) ⋅m A) *v v"
    by (rule minus_mult_distrib_mat_vec[OF E1 smult_carrier_mat[OF A(1)] vc])
  also have "… = evolution A d *v v - v - (𝗂 * complex_of_real d) ⋅v (A *v v)"
    using m1 smult_mat_mult_mat_vec_assoc[OF A(1) carrier_vecI[OF v]] vc by simp
  finally have e: "mat_fun (λx. cis (d * x) - 1 - 𝗂 * complex_of_real (d * x)) A *v v =
      evolution A d *v v - v - (𝗂 * complex_of_real d) ⋅v (A *v v)" .
  have "∥mat_fun (λx. cis (d * x) - 1 - 𝗂 * complex_of_real (d * x)) A *v v∥ ≤ (d * L)2 * ∥v∥"
  proof (rule mat_fun_bound[OF A _ _ v])
    fix l assume l0: "l ∈ herm_spectrum A"
    have l: "¦l¦ ≤ L" by (rule herm_spectrum_bound[OF A(1) _ l0]) (rule Ab)
    have "l2 ≤ L2" using power_mono[OF l, of 2] by simp
    hence "d2 * l2 ≤ d2 * L2" by (rule mult_left_mono) simp
    hence "(d * l)2 ≤ (d * L)2" by (simp add: power_mult_distrib)
    thus "cmod (cis (d * l) - 1 - 𝗂 * complex_of_real (d * l)) ≤ (d * L)2"
      using cis_remainder[of "d * l"] by linarith
  qed simp
  thus ?thesis unfolding e .
qed

lemma evolution_step:
  assumes v: "dim_vec v = n"
  shows "∥evolution A d *v v - v∥ ≤ ¦d¦ * L * ∥v∥"
proof -
  have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF v])
  have "mat_fun (λx. cis (d * x) - 1) A *v v = (evolution A d - 1m n) *v v"
    by (simp only: mat_fun_evolution_one[OF A])
  also have "… = evolution A d *v v - v"
    using minus_mult_distrib_mat_vec[OF evolution_carrier[OF A] one_carrier_mat vc] vc by simp
  finally have e: "mat_fun (λx. cis (d * x) - 1) A *v v = evolution A d *v v - v" .
  have L0: "0 ≤ L" if "0 < n"
  proof -
    have "∥A *v unit_vec n 0∥ ≤ L * ∥unit_vec n 0∥" by (rule Ab) simp
    thus ?thesis using that vnorm_ge0[of "A *v unit_vec n 0"] by simp
  qed
  show ?thesis
  proof (cases "n = 0")
    case True
    hence "evolution A d *v v - v = 0v 0" using v evolution_carrier[OF A, of d] by (intro eq_vecI) simp_all
    thus ?thesis using vnorm_ge0[of v] True v by (simp add: cpx_vec_length_def)
  next
    case False
    have "∥mat_fun (λx. cis (d * x) - 1) A *v v∥ ≤ (¦d¦ * L) * ∥v∥"
    proof (rule mat_fun_bound[OF A _ _ v])
      show "0 ≤ ¦d¦ * L" using L0 False by simp
      fix l assume l0: "l ∈ herm_spectrum A"
      have l: "¦l¦ ≤ L" by (rule herm_spectrum_bound[OF A(1) _ l0]) (rule Ab)
      have "¦d¦ * ¦l¦ ≤ ¦d¦ * L" by (rule mult_left_mono[OF l]) simp
      thus "cmod (cis (d * l) - 1) ≤ ¦d¦ * L" using cis_minus_one[of "d * l"] by (simp add: abs_mult)
    qed
    thus ?thesis unfolding e by simp
  qed
qed

end

subsection ‹Products of evolutions›

text ‹‹evolution_product n d Hs› is $e^{idH_1}\cdots e^{idH_m}$ and ‹hamiltonian_sum n Hs› is $H_1+\dots+H_m$.›

fun evolution_product :: "nat ⇒ real ⇒ complex Matrix.mat list ⇒ complex Matrix.mat" where
  "evolution_product n d [] = 1m n"
| "evolution_product n d (H # Hs) = evolution H d * evolution_product n d Hs"

fun hamiltonian_sum :: "nat ⇒ complex Matrix.mat list ⇒ complex Matrix.mat" where
  "hamiltonian_sum n [] = 0m n n"
| "hamiltonian_sum n (H # Hs) = H + hamiltonian_sum n Hs"

text ‹‹herm_bounded n L H›: $H$ is a Hermitian $n\times n$ matrix with $\norm{Hv}\le L\norm v$.›

definition herm_bounded :: "nat ⇒ real ⇒ complex Matrix.mat ⇒ bool" where
  "herm_bounded n L H ⟷ H ∈ carrier_mat n n ∧ hermitian H ∧
     (∀v. dim_vec v = n ⟶ ∥H *v v∥ ≤ L * ∥v∥)"

lemma herm_boundedD:
  assumes "herm_bounded n L H"
  shows "H ∈ carrier_mat n n" "hermitian H" "⋀v. dim_vec v = n ⟹ ∥H *v v∥ ≤ L * ∥v∥"
  using assms unfolding herm_bounded_def by auto

lemma herm_bounded_herm: "herm_bounded n L H ⟹ H ∈ carrier_mat n n ∧ hermitian H"
  by (simp add: herm_bounded_def)

lemma evolution_product_carrier:
  "(⋀H. H ∈ set Hs ⟹ H ∈ carrier_mat n n ∧ hermitian H) ⟹ evolution_product n d Hs ∈ carrier_mat n n"
proof (induction Hs)
  case (Cons H Hs)
  have h: "H ∈ carrier_mat n n" "hermitian H" using Cons.prems by auto
  show ?case using mult_carrier_mat[OF evolution_carrier[OF h] Cons.IH] Cons.prems by simp
qed simp

lemma hamiltonian_sum_carrier: "(⋀H. H ∈ set Hs ⟹ H ∈ carrier_mat n n) ⟹ hamiltonian_sum n Hs ∈ carrier_mat n n"
  by (induction Hs) auto

context
  fixes n :: nat and L :: real
begin

text ‹For Hamiltonians bounded by $L$: the product of their evolutions is unitary, their sum is Hermitian
with $\norm{\sum_jH_jv}\le mL\norm v$, and
\[ \norm{e^{idH_1}\cdots e^{idH_m}v-v}\le m\,|d|L\,\norm v. \]›

lemma evolution_product_unitary:
  "(⋀H. H ∈ set Hs ⟹ herm_bounded n L H) ⟹ unitary (evolution_product n d Hs)"
proof (induction Hs)
  case Nil
  show ?case by (simp add: id_is_unitary)
next
  case (Cons H Hs)
  note h = herm_boundedD[OF Cons.prems[of H, OF list.set_intros(1)]]
  have "unitary (evolution H d * evolution_product n d Hs)"
    by (rule unitary_mult[OF evolution_unitary[OF h(1,2)] Cons.IH evolution_carrier[OF h(1,2)] evolution_product_carrier])
      (use Cons.prems in ‹simp_all add: herm_bounded_def›)
  thus ?case by simp
qed

lemma hamiltonian_sum_hermitian:
  "(⋀H. H ∈ set Hs ⟹ herm_bounded n L H) ⟹ hermitian (hamiltonian_sum n Hs)"
proof (induction Hs)
  case Nil
  show ?case unfolding hermitian_def by (rule eq_matI) (simp_all add: adjoint_eval)
next
  case (Cons H Hs)
  note h = herm_boundedD[OF Cons.prems[of H, OF list.set_intros(1)]]
  have c: "hamiltonian_sum n Hs ∈ carrier_mat n n" by (rule hamiltonian_sum_carrier) (use Cons.prems in ‹simp add: herm_bounded_def›)
  have ih: "hermitian (hamiltonian_sum n Hs)" by (rule Cons.IH) (use Cons.prems in simp)
  have "hermitian (H + hamiltonian_sum n Hs)" using adjoint_add[OF h(1) c] h(2) ih unfolding hermitian_def by simp
  thus ?case by simp
qed

lemma hamiltonian_sum_bound:
  "(⋀H. H ∈ set Hs ⟹ herm_bounded n L H) ⟹ dim_vec v = n ⟹
   ∥hamiltonian_sum n Hs *v v∥ ≤ real (length Hs) * L * ∥v∥"
proof (induction Hs)
  case Nil
  have "hamiltonian_sum n [] *v v = 0v n" using carrier_vecI[OF Nil.prems(2)] Nil.prems(2) by (intro eq_vecI) simp_all
  thus ?case by (simp add: cpx_vec_length_def)
next
  case (Cons H Hs)
  note h = herm_boundedD[OF Cons.prems(1)[of H, OF list.set_intros(1)]]
  have S: "hamiltonian_sum n Hs ∈ carrier_mat n n" by (rule hamiltonian_sum_carrier) (use Cons.prems in ‹simp add: herm_bounded_def›)
  have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF Cons.prems(2)])
  have "hamiltonian_sum n (H # Hs) *v v = H *v v + hamiltonian_sum n Hs *v v"
    using add_mult_distrib_mat_vec[OF h(1) S vc] by simp
  hence "∥hamiltonian_sum n (H # Hs) *v v∥ ≤ ∥H *v v∥ + ∥hamiltonian_sum n Hs *v v∥"
    using vnorm_add_le[of "H *v v" "hamiltonian_sum n Hs *v v"] h(1) S by simp
  also have "… ≤ L * ∥v∥ + real (length Hs) * L * ∥v∥"
    using h(3)[OF Cons.prems(2)] Cons.IH Cons.prems by (intro add_mono) simp_all
  finally show ?case by (simp add: algebra_simps)
qed

lemma evolution_product_norm:
  "(⋀H. H ∈ set Hs ⟹ herm_bounded n L H) ⟹ dim_vec v = n ⟹ ∥evolution_product n d Hs *v v∥ = ∥v∥"
  by (rule unitary_vnorm[OF evolution_product_carrier[OF herm_bounded_herm] evolution_product_unitary])

lemma evolution_product_step:
  "(⋀H. H ∈ set Hs ⟹ herm_bounded n L H) ⟹ dim_vec v = n ⟹
   ∥evolution_product n d Hs *v v - v∥ ≤ real (length Hs) * (¦d¦ * L) * ∥v∥"
proof (induction Hs arbitrary: v)
  case Nil
  have "evolution_product n d [] *v v - v = 0v n" using carrier_vecI[OF Nil.prems(2)] Nil.prems(2) by (intro eq_vecI) simp_all
  thus ?case by (simp add: cpx_vec_length_def)
next
  case (Cons H Hs v)
  note h = herm_boundedD[OF Cons.prems(1)[of H, OF list.set_intros(1)]]
  have hs: "⋀G. G ∈ set Hs ⟹ herm_bounded n L G" using Cons.prems(1) by simp
  have P: "evolution_product n d Hs ∈ carrier_mat n n" by (rule evolution_product_carrier[OF herm_bounded_herm[OF hs]])
  have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF Cons.prems(2)])
  let ?w = "evolution_product n d Hs *v v"
  have w: "dim_vec ?w = n" using P by simp
  have e: "evolution_product n d (H # Hs) *v v = evolution H d *v ?w"
    using assoc_mult_mat_vec[OF evolution_carrier[OF h(1,2)] P vc] by simp
  have "∥evolution H d *v ?w - v∥ ≤ ∥evolution H d *v ?w - ?w∥ + ∥?w - v∥"
    by (rule vnorm_diff_le[where n = n]) (use w Cons.prems(2) evolution_carrier[OF h(1,2), of d] in simp_all)
  also have "… ≤ ¦d¦ * L * ∥?w∥ + real (length Hs) * (¦d¦ * L) * ∥v∥"
    by (rule add_mono[OF evolution_step[OF h(1,2) h(3) w] Cons.IH[OF hs Cons.prems(2)]])
  also have "∥?w∥ = ∥v∥" by (rule evolution_product_norm[OF hs Cons.prems(2)])
  finally show ?case unfolding e by (simp add: algebra_simps)
qed

end

text ‹To first order the product of the evolutions is the evolution of the sum:
\[ \Bigl\|e^{idH_1}\cdots e^{idH_m}v-v-id\sum_jH_jv\Bigr\|\le m^2(dL)^2\norm v. \]›

lemma evolution_product_first_order:
  fixes n :: nat and L :: real
  shows "(⋀H. H ∈ set Hs ⟹ herm_bounded n L H) ⟹ dim_vec v = n ⟹
   ∥evolution_product n d Hs *v v - v - (𝗂 * complex_of_real d) ⋅v (hamiltonian_sum n Hs *v v)∥
     ≤ (d * L)2 * (real (length Hs))2 * ∥v∥"
proof (induction Hs arbitrary: v)
  case Nil
  have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF Nil.prems(2)])
  have "evolution_product n d [] *v v - v - (𝗂 * complex_of_real d) ⋅v (hamiltonian_sum n [] *v v) = 0v n"
    using vc Nil.prems(2) by (intro eq_vecI) simp_all
  thus ?case by (simp add: cpx_vec_length_def)
next
  case (Cons H Hs v)
  note h = herm_boundedD[OF Cons.prems(1)[of H, OF list.set_intros(1)]]
  have hs: "⋀G. G ∈ set Hs ⟹ herm_bounded n L G" using Cons.prems(1) by simp
  have v: "dim_vec v = n" by (rule Cons.prems(2))
  have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF v])
  have P: "evolution_product n d Hs ∈ carrier_mat n n" by (rule evolution_product_carrier[OF herm_bounded_herm[OF hs]])
  have S: "hamiltonian_sum n Hs ∈ carrier_mat n n" by (rule hamiltonian_sum_carrier[OF herm_boundedD(1)[OF hs]])
  have E: "evolution H d ∈ carrier_mat n n" by (rule evolution_carrier[OF h(1,2)])
  define c where "c = 𝗂 * complex_of_real d"
  define k where "k = real (length Hs)"
  let ?w = "evolution_product n d Hs *v v"
  have w: "dim_vec ?w = n" using P by simp
  have wc: "?w ∈ carrier_vec n" by (rule carrier_vecI[OF w])
  have e1: "evolution_product n d (H # Hs) *v v = evolution H d *v ?w"
    using assoc_mult_mat_vec[OF E P vc] by simp
  have e2: "hamiltonian_sum n (H # Hs) *v v = H *v v + hamiltonian_sum n Hs *v v"
    using add_mult_distrib_mat_vec[OF h(1) S vc] by simp
  have e3: "H *v (?w - v) = H *v ?w - H *v v" by (rule mult_minus_distrib_mat_vec[OF h(1) wc vc])
  have split: "evolution H d *v ?w - v - c ⋅v (H *v v + hamiltonian_sum n Hs *v v) =
      (evolution H d *v ?w - ?w - c ⋅v (H *v ?w)) + ((?w - v - c ⋅v (hamiltonian_sum n Hs *v v)) + c ⋅v (H *v (?w - v)))"
    unfolding e3 using E h(1) S w v by (intro eq_vecI) (simp_all add: algebra_simps)
  have b1: "∥evolution H d *v ?w - ?w - c ⋅v (H *v ?w)∥ ≤ (d * L)2 * ∥v∥"
    using evolution_first_order[OF h(1,2) h(3) w, of d] evolution_product_norm[OF hs v] unfolding c_def by simp
  have b2: "∥?w - v - c ⋅v (hamiltonian_sum n Hs *v v)∥ ≤ (d * L)2 * k2 * ∥v∥"
    using Cons.IH[OF hs v] unfolding c_def k_def .
  have b3: "∥c ⋅v (H *v (?w - v))∥ ≤ (d * L)2 * k * ∥v∥"
  proof -
    have "∥c ⋅v (H *v (?w - v))∥ = ¦d¦ * ∥H *v (?w - v)∥" by (simp add: cpx_vec_length_smult c_def norm_mult)
    also have "… ≤ ¦d¦ * (L * ∥?w - v∥)" by (rule mult_left_mono[OF h(3)]) (use w v in simp_all)
    also have "… ≤ ¦d¦ * (L * (k * (¦d¦ * L) * ∥v∥))"
    proof (cases "n = 0")
      case True
      hence "∥?w - v∥ = 0" "∥v∥ = 0" using w v by (simp_all add: cpx_vec_length_def)
      thus ?thesis by simp
    next
      case False
      have L0: "0 ≤ L"
      proof -
        have "∥H *v unit_vec n 0∥ ≤ L * ∥unit_vec n 0∥" by (rule h(3)) simp
        thus ?thesis using False vnorm_ge0[of "H *v unit_vec n 0"] by simp
      qed
      show ?thesis
        using evolution_product_step[where d = d, OF hs v] L0 unfolding k_def by (intro mult_left_mono) simp_all
    qed
    also have "… = (d * L)2 * k * ∥v∥" by (simp add: power2_eq_square)
    finally show ?thesis .
  qed
  have nn: "0 ≤ (d * L)2 * ∥v∥" using vnorm_ge0[of v] by simp
  have "∥evolution H d *v ?w - v - c ⋅v (H *v v + hamiltonian_sum n Hs *v v)∥
      ≤ ∥evolution H d *v ?w - ?w - c ⋅v (H *v ?w)∥ + (∥?w - v - c ⋅v (hamiltonian_sum n Hs *v v)∥ + ∥c ⋅v (H *v (?w - v))∥)"
  proof -
    let ?X = "evolution H d *v ?w - ?w - c ⋅v (H *v ?w)"
    let ?Y = "?w - v - c ⋅v (hamiltonian_sum n Hs *v v)" and ?Z = "c ⋅v (H *v (?w - v))"
    have dX: "dim_vec ?X = n" and dY: "dim_vec ?Y = n" and dZ: "dim_vec ?Z = n"
      using E h(1) S w v by simp_all
    have "∥?X + (?Y + ?Z)∥ ≤ ∥?X∥ + ∥?Y + ?Z∥" by (rule vnorm_add_le) (use dX dY in simp)
    also have "∥?Y + ?Z∥ ≤ ∥?Y∥ + ∥?Z∥" by (rule vnorm_add_le) (use dY dZ in simp)
    finally show ?thesis unfolding split by simp
  qed
  also have "… ≤ (d * L)2 * ∥v∥ + ((d * L)2 * k2 * ∥v∥ + (d * L)2 * k * ∥v∥)"
    using b1 b2 b3 by linarith
  also have "… = (d * L)2 * ∥v∥ * (1 + k2 + k)" by (simp add: algebra_simps)
  also have "… ≤ (d * L)2 * ∥v∥ * (k + 1)2"
    by (rule mult_left_mono[OF _ nn]) (simp add: power2_eq_square algebra_simps k_def)
  finally show ?case unfolding e1 e2 c_def k_def by (simp add: algebra_simps)
qed

text ‹One Trotter step: $\norm{e^{idH_1}\cdots e^{idH_m}-e^{id(H_1+\dots+H_m)}}\le 2m^2(dL)^2$.›

lemma trotter_step:
  assumes Hs: "⋀H. H ∈ set Hs ⟹ herm_bounded n L H"
  shows "evolution_product n d Hs ≈⇘2 * (d * L)2 * (real (length Hs))2⇙ evolution (hamiltonian_sum n Hs) d"
proof (rule op_closeI[OF evolution_product_carrier[OF herm_bounded_herm[OF Hs]]])
  fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
  have P: "evolution_product n d Hs ∈ carrier_mat n n" by (rule evolution_product_carrier[OF herm_bounded_herm[OF Hs]])
  have S: "hamiltonian_sum n Hs ∈ carrier_mat n n" "hermitian (hamiltonian_sum n Hs)"
    using hamiltonian_sum_carrier[OF herm_boundedD(1)[OF Hs]] hamiltonian_sum_hermitian[OF Hs] by simp_all
  have E: "evolution (hamiltonian_sum n Hs) d ∈ carrier_mat n n" by (rule evolution_carrier[OF S])
  let ?c = "𝗂 * complex_of_real d" and ?m = "real (length Hs)"
  let ?a = "evolution_product n d Hs *v v - v - ?c ⋅v (hamiltonian_sum n Hs *v v)"
  let ?b = "evolution (hamiltonian_sum n Hs) d *v v - v - ?c ⋅v (hamiltonian_sum n Hs *v v)"
  have a: "∥?a∥ ≤ (d * L)2 * ?m2 * ∥v∥" by (rule evolution_product_first_order[OF Hs v])
  have b: "∥?b∥ ≤ (d * (?m * L))2 * ∥v∥"
    by (rule evolution_first_order[OF S _ v]) (rule hamiltonian_sum_bound[OF Hs])
  have "evolution_product n d Hs *v v - evolution (hamiltonian_sum n Hs) d *v v = ?a - ?b"
    using P E S(1) v by (intro eq_vecI) simp_all
  hence "∥evolution_product n d Hs *v v - evolution (hamiltonian_sum n Hs) d *v v∥ ≤ ∥?a∥ + ∥?b∥"
    using vnorm_minus_le[of ?a ?b] P E S(1) v by simp
  also have "… ≤ (d * L)2 * ?m2 * ∥v∥ + (d * (?m * L))2 * ∥v∥" using a b by linarith
  also have "… = 2 * (d * L)2 * ?m2 * ∥v∥" by (simp add: power_mult_distrib algebra_simps)
  finally show "∥evolution_product n d Hs *v v - evolution (hamiltonian_sum n Hs) d *v v∥ ≤ 2 * (d * L)2 * ?m2 * ∥v∥" .
qed

text ‹Errors of unitaries add up along powers.›

lemma op_close_pow:
  assumes U: "U ∈ carrier_mat n n" "unitary U" and V: "V ∈ carrier_mat n n" "unitary V"
      and c: "U ≈⇘η⇙ V"
  shows "U ^m k ≈⇘real k * η⇙ V ^m k"
proof (induction k)
  case 0
  show ?case
  proof (rule op_closeI[OF pow_carrier_mat[OF U(1)]])
    fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
    have "U ^m 0 *v v - V ^m 0 *v v = 0v n" using v carrier_matD[OF U(1)] carrier_matD[OF V(1)] carrier_vecI[OF v] by (intro eq_vecI) simp_all
    thus "∥U ^m 0 *v v - V ^m 0 *v v∥ ≤ real 0 * η * ∥v∥" by (simp add: vnorm_zero_vec)
  qed
next
  case (Suc k)
  show ?case
  proof (rule op_closeI[OF pow_carrier_mat[OF U(1)]])
    fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
    have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF v])
    have Uk: "U ^m k ∈ carrier_mat n n" and Vk: "V ^m k ∈ carrier_mat n n"
      using pow_carrier_mat U(1) V(1) by blast+
    have uVk: "unitary (V ^m k)" by (rule unitary_pow[OF V])
    let ?x = "U *v v" and ?y = "V *v v"
    have x: "dim_vec ?x = n" and y: "dim_vec ?y = n" using U(1) V(1) by simp_all
    have e1: "U ^m Suc k *v v = U ^m k *v ?x" using assoc_mult_mat_vec[OF Uk U(1) vc] by simp
    have e2: "V ^m Suc k *v v = V ^m k *v ?y" using assoc_mult_mat_vec[OF Vk V(1) vc] by simp
    have "∥U ^m k *v ?x - V ^m k *v ?y∥ ≤ ∥U ^m k *v ?x - V ^m k *v ?x∥ + ∥V ^m k *v ?x - V ^m k *v ?y∥"
      by (rule vnorm_diff_le[where n = n]) (use Uk Vk carrier_matD[OF U(1)] carrier_matD[OF V(1)] in simp_all)
    also have "V ^m k *v ?x - V ^m k *v ?y = V ^m k *v (?x - ?y)"
      by (rule mult_minus_distrib_mat_vec[OF Vk, symmetric]) (use x y in ‹simp_all add: carrier_vecI›)
    also have "∥V ^m k *v (?x - ?y)∥ = ∥?x - ?y∥" by (rule unitary_vnorm[OF Vk uVk]) (use y in simp)
    also have "∥U ^m k *v ?x - V ^m k *v ?x∥ ≤ real k * η * ∥?x∥" by (rule op_closeD[OF Suc pow_carrier_mat[OF U(1)] x])
    also have "∥?x∥ = ∥v∥" by (rule unitary_vnorm[OF U v])
    also have "∥?x - ?y∥ ≤ η * ∥v∥" by (rule op_closeD[OF c U(1) v])
    finally show "∥U ^m Suc k *v v - V ^m Suc k *v v∥ ≤ real (Suc k) * η * ∥v∥"
      unfolding e1 e2 by (simp add: algebra_simps)
  qed
qed

text ‹The Lie--Trotter product formula with explicit error:
$\norm{(e^{itH_1/r}\cdots e^{itH_m/r})^r-e^{it(H_1+\dots+H_m)}}\le 2(mLt)^2/r$.›

theorem trotter:
  assumes Hs: "⋀H. H ∈ set Hs ⟹ herm_bounded n L H" and r: "0 < r"
  shows "evolution_product n (t / real r) Hs ^m r ≈⇘2 * (real (length Hs) * L * t)2 / real r⇙ evolution (hamiltonian_sum n Hs) t"
proof -
  have S: "hamiltonian_sum n Hs ∈ carrier_mat n n" "hermitian (hamiltonian_sum n Hs)"
    using hamiltonian_sum_carrier[OF herm_boundedD(1)[OF Hs]] hamiltonian_sum_hermitian[OF Hs] by simp_all
  have c: "evolution_product n (t / real r) Hs ^m r ≈⇘real r * (2 * (t / real r * L)2 * (real (length Hs))2)⇙ evolution (hamiltonian_sum n Hs) (t / real r) ^m r"
    by (rule op_close_pow[OF evolution_product_carrier[OF herm_bounded_herm[OF Hs]] evolution_product_unitary[OF Hs] evolution_carrier[OF S]
          evolution_unitary[OF S] trotter_step[OF Hs]])
  have p: "evolution (hamiltonian_sum n Hs) (t / real r) ^m r = evolution (hamiltonian_sum n Hs) t"
    using evolution_pow[OF S, of "t / real r" r] r by simp
  have a: "real r * (2 * (t / real r * L)2 * (real (length Hs))2) = 2 * (real (length Hs) * L * t)2 / real r"
    using r by (simp add: power2_eq_square field_simps)
  show ?thesis using c unfolding p a .
qed

end