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¦ ≤ x⇧2 / 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¦ * x⇧2 / 6" by (simp add: power2_eq_square power3_eq_cube)
also have "… ≤ 3 * x⇧2 / 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 "… ≤ x⇧2 / 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¦ ≤ x⇧2 / 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 "… = x⇧2 / 2" by (simp add: power2_eq_square)
finally show ?thesis .
qed
lemma cis_remainder: "cmod (cis (x::real) - 1 - 𝗂 * complex_of_real x) ≤ x⇧2"
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 "… ≤ x⇧2 / 2 + x⇧2 / 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 ≠ 0⇩v 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. c⇧2 * (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 ≤ c⇧2" by (rule power_mono) simp
thus "(cmod (g (Dl ! i) * w $ i))⇧2 ≤ c⇧2 * (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 - 1⇩m 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 - 1⇩m n ∈ carrier_mat n n" by (rule minus_carrier_mat) simp
have m1: "(evolution A d - 1⇩m n) *⇩v v = evolution A d *⇩v v - 1⇩m 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 - 1⇩m 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 - 1⇩m 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 - 1⇩m 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 - 1⇩m 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 = 0⇩v 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⇧†) = 1⇩m n" and VV: "V * (V⇧†) = 1⇩m 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 - 1⇩m n ∈ carrier_mat n n" by (rule minus_carrier_mat) simp
have m1: "(evolution A d - 1⇩m n) *⇩v v = evolution A d *⇩v v - 1⇩m 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 - 1⇩m n - (𝗂 * complex_of_real d) ⋅⇩m A) *⇩v v"
by (simp only: mat_fun_evolution_rem[OF A])
also have "… = (evolution A d - 1⇩m 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 "l⇧2 ≤ L⇧2" using power_mono[OF l, of 2] by simp
hence "d⇧2 * l⇧2 ≤ d⇧2 * L⇧2" 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 - 1⇩m 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 = 0⇩v 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 [] = 1⇩m 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 [] = 0⇩m 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 = 0⇩v 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 = 0⇩v 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) = 0⇩v 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 * k⇧2 * ∥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 * k⇧2 * ∥v∥ + (d * L)⇧2 * k * ∥v∥)"
using b1 b2 b3 by linarith
also have "… = (d * L)⇧2 * ∥v∥ * (1 + k⇧2 + 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 * ?m⇧2 * ∥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 * ?m⇧2 * ∥v∥ + (d * (?m * L))⇧2 * ∥v∥" using a b by linarith
also have "… = 2 * (d * L)⇧2 * ?m⇧2 * ∥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 * ?m⇧2 * ∥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 = 0⇩v 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