Theory Suzuki_Error
theory Suzuki_Error
imports Suzuki_Order
begin
section ‹Higher-order product formulas›
text ‹Suzuki's formula of order $2k+2$ over $r$ steps is within
$r(2|F|+1)(\Lambda|t|/r)^{2k+3}e^{\Lambda|t|/r}/(2k+3)!$ of $e^{itH}$ (‹suzuki_error›), so
$r\sim|t|^{1+1/(2k+2)}$ steps suffice. The proof compares both sides with their Taylor
polynomials of degree $2k+2$, which agree by ‹suzuki_order›.›
text ‹Two facts about factorials and the exponential series: $i!\,k!\le(i+k)!$, and
\[ \Bigl|e^z-\sum_{q\le P}\frac{z^q}{q!}\Bigr|\le\frac{|z|^{P+1}e^{|z|}}{(P+1)!}. \]›
lemma fact_mult_le_fact_add: "fact i * fact k ≤ (fact (i + k) :: real)"
proof (induction k)
case (Suc k)
have "fact i * fact (Suc k) = (fact i * fact k) * real (Suc k)" by (simp add: algebra_simps)
also have "… ≤ fact (i + k) * real (Suc (i + k))" by (rule mult_mono) (use Suc.IH in auto)
also have "… = fact (i + Suc k)" by (simp add: algebra_simps)
finally show ?case .
qed simp
lemma exp_tail:
fixes z :: complex
shows "cmod (exp z - (∑q≤P. z ^ q / fact q)) ≤ cmod z ^ Suc P * exp (cmod z) / fact (Suc P)"
proof -
let ?f = "λn. z ^ n /⇩R fact n" and ?x = "cmod z"
have s: "?f sums exp z" by (rule exp_converges)
have t: "(λi. ?f (i + Suc P)) sums (exp z - (∑i<Suc P. ?f i))" by (rule sums_split_initial_segment[OF s])
have e: "exp z - (∑q≤P. z ^ q / fact q) = (∑i. ?f (i + Suc P))"
using sums_unique[OF t] by (simp add: lessThan_Suc_atMost scaleR_conv_of_real field_simps)
have sn: "summable (λi. norm (?f (i + Suc P)))"
by (rule summable_ignore_initial_segment[OF summable_norm_exp])
have sx: "summable (λi. ?x ^ i / fact i)" using summable_exp[of ?x] by (simp add: field_simps)
have "cmod (∑i. ?f (i + Suc P)) ≤ (∑i. norm (?f (i + Suc P)))" by (rule summable_norm[OF sn])
also have "… ≤ (∑i. ?x ^ Suc P / fact (Suc P) * (?x ^ i / fact i))"
proof (intro suminf_le sn summable_mult[OF sx])
fix i
have "norm (?f (i + Suc P)) = ?x ^ (i + Suc P) / fact (i + Suc P)" by (simp add: norm_power norm_mult field_simps del: fact_Suc power_Suc add_Suc_right)
also have "… ≤ ?x ^ (i + Suc P) / (fact i * fact (Suc P))"
by (rule divide_left_mono) (use fact_mult_le_fact_add[of i "Suc P"] in ‹simp_all del: fact_Suc add_Suc_right›)
also have "… = ?x ^ Suc P / fact (Suc P) * (?x ^ i / fact i)" by (simp add: power_add field_simps)
finally show "norm (?f (i + Suc P)) ≤ ?x ^ Suc P / fact (Suc P) * (?x ^ i / fact i)" .
qed
also have "… = ?x ^ Suc P / fact (Suc P) * exp ?x"
proof -
have ex: "(∑i. ?x ^ i / fact i) = exp ?x"
using sums_unique[OF exp_converges[of ?x]] by (simp add: field_simps)
show ?thesis using suminf_mult[OF sx, of "?x ^ Suc P / fact (Suc P)"] ex by simp
qed
finally show ?thesis using e by (simp add: field_simps)
qed
text ‹A sum of matrices that act on $v$ by scalars acts by the sum of the scalars.›
lemma matrix_sum_eigen:
fixes F :: "nat ⇒ complex Matrix.mat"
assumes F: "⋀q. q < m ⟹ F q ∈ carrier_mat n n" and v: "dim_vec v = n"
and ev: "⋀q. q < m ⟹ F q *⇩v v = c q ⋅⇩v v"
shows "matrix_sum n F m *⇩v v = (∑q<m. c q) ⋅⇩v v"
using F ev
proof (induction m)
case 0
show ?case using v by (auto intro!: eq_vecI)
next
case (Suc m)
have S: "matrix_sum n F m ∈ carrier_mat n n" by (rule matrix_sum_dim) (use Suc.prems in auto)
have "matrix_sum n F (Suc m) *⇩v v = F m *⇩v v + matrix_sum n F m *⇩v v"
using add_mult_distrib_mat_vec[OF Suc.prems(1)[of m] S carrier_vecI[OF v]] by simp
also have "… = c m ⋅⇩v v + (∑q<m. c q) ⋅⇩v v" using Suc by simp
also have "… = (∑q<Suc m. c q) ⋅⇩v v" by (auto intro!: eq_vecI simp: algebra_simps)
finally show ?case .
qed
text ‹The Taylor polynomial $\sum_{q\le P}(isH)^q/q!$ of $e^{isH}$. On an eigenvector it is the Taylor
polynomial of $e^{is\lambda}$, so it is within $(|s|L)^{P+1}e^{|s|L}/(P+1)!$ of $e^{isH}$ when
$\norm{Hv}\le L\norm v$ (‹evolution_taylor›).›
definition exp_taylor :: "nat ⇒ complex Matrix.mat ⇒ real ⇒ nat ⇒ complex Matrix.mat" where
"exp_taylor n H s P = matrix_sum n (λq. exp_coeff ((𝗂 * complex_of_real s) ⋅⇩m H) q) (Suc P)"
lemma exp_taylor_carrier: "H ∈ carrier_mat n n ⟹ exp_taylor n H s P ∈ carrier_mat n n"
unfolding exp_taylor_def by (rule matrix_sum_dim) (simp add: exp_coeff_def)
lemma exp_taylor_eigen:
assumes H: "H ∈ carrier_mat n n" and v: "dim_vec v = n" and ev: "H *⇩v v = complex_of_real l ⋅⇩v v"
shows "exp_taylor n H s P *⇩v v = (∑q≤P. (𝗂 * complex_of_real (s * l)) ^ q / fact q) ⋅⇩v v"
proof -
have "exp_coeff ((𝗂 * complex_of_real s) ⋅⇩m H) q *⇩v v = ((𝗂 * complex_of_real (s * l)) ^ q / fact q) ⋅⇩v v" for q
proof -
let ?c = "complex_of_real (1 / fact q) * (𝗂 * complex_of_real s) ^ q"
have t: "exp_coeff ((𝗂 * complex_of_real s) ⋅⇩m H) q = ?c ⋅⇩m H ^⇩m q"
using H by (simp add: exp_coeff_def smult_pow_mat) (rule eq_matI, auto)
have Hq: "H ^⇩m q ∈ carrier_mat n n" using H by simp
have "exp_coeff ((𝗂 * complex_of_real s) ⋅⇩m H) q *⇩v v = ?c ⋅⇩v ((H ^⇩m q) *⇩v v)"
unfolding t by (rule smult_mat_mult_mat_vec_assoc[OF Hq carrier_vecI[OF v]])
also have "… = ?c ⋅⇩v ((complex_of_real l ^ q) ⋅⇩v v)" unfolding pow_eigen[OF H v ev] ..
also have "… = ((𝗂 * complex_of_real (s * l)) ^ q / fact q) ⋅⇩v v"
by (simp add: smult_smult_assoc power_mult_distrib field_simps)
finally show ?thesis .
qed
thus ?thesis unfolding exp_taylor_def lessThan_Suc_atMost[symmetric]
by (intro matrix_sum_eigen[OF _ v]) (use H in ‹simp_all add: exp_coeff_def›)
qed
lemma evolution_taylor:
assumes H: "herm_bounded n L H" and L: "0 ≤ L"
shows "evolution H s ≈⇘(¦s¦ * L) ^ Suc P * exp (¦s¦ * L) / fact (Suc P)⇙ exp_taylor n H s P"
proof -
have Hc: "H ∈ carrier_mat n n" "hermitian H" using herm_boundedD[OF H] by simp_all
let ?g = "λx. cis (s * x) - (∑q≤P. (𝗂 * complex_of_real (s * x)) ^ q / fact q)"
let ?B = "evolution H s - exp_taylor n H s P"
have mf: "mat_fun ?g H = ?B"
proof (rule mat_fun_eqI[OF Hc])
show "?B ∈ carrier_mat n n" by (rule minus_carrier_mat[OF exp_taylor_carrier[OF Hc(1)]])
show "?B acts_as ?g on_eigenvectors_of H" unfolding acts_on_eigenvectors_def
proof (intro allI impI)
fix v l assume v: "dim_vec v = dim_row H" and ev: "H *⇩v v = complex_of_real l ⋅⇩v v"
have vn: "dim_vec v = n" using v Hc(1) by simp
have "?B *⇩v v = evolution H s *⇩v v - exp_taylor n H s P *⇩v v"
by (rule minus_mult_distrib_mat_vec[OF evolution_carrier[OF Hc] exp_taylor_carrier[OF Hc(1)] carrier_vecI[OF vn]])
also have "… = ?g l ⋅⇩v v"
using evolution_eigen[OF Hc vn ev] exp_taylor_eigen[OF Hc(1) vn ev] by (auto intro!: eq_vecI simp: algebra_simps)
finally show "?B *⇩v v = ?g l ⋅⇩v v" .
qed
qed
have c0: "0 ≤ (¦s¦ * L) ^ Suc P * exp (¦s¦ * L) / fact (Suc P)" using L by simp
show ?thesis
proof (rule op_closeI[OF evolution_carrier[OF Hc]])
fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
have "evolution H s *⇩v v - exp_taylor n H s P *⇩v v = ?B *⇩v v"
by (rule minus_mult_distrib_mat_vec[OF evolution_carrier[OF Hc] exp_taylor_carrier[OF Hc(1)] carrier_vecI[OF v], symmetric])
also have "… = mat_fun ?g H *⇩v v" unfolding mf ..
finally have e: "evolution H s *⇩v v - exp_taylor n H s P *⇩v v = mat_fun ?g H *⇩v v" .
have "∥mat_fun ?g H *⇩v v∥ ≤ (¦s¦ * L) ^ Suc P * exp (¦s¦ * L) / fact (Suc P) * ∥v∥"
proof (rule mat_fun_bound[OF Hc c0 _ v])
fix l assume l: "l ∈ herm_spectrum H"
have lL: "¦l¦ ≤ L" by (rule herm_spectrum_bound[OF Hc(1) herm_boundedD(3)[OF H] l])
have "cmod (?g l) = cmod (exp (𝗂 * complex_of_real (s * l)) - (∑q≤P. (𝗂 * complex_of_real (s * l)) ^ q / fact q))"
by (simp add: cis_conv_exp)
also have "… ≤ ¦s * l¦ ^ Suc P * exp ¦s * l¦ / fact (Suc P)"
proof -
have z: "cmod (𝗂 * complex_of_real (s * l)) = ¦s * l¦" by (simp add: norm_mult abs_mult)
show ?thesis using exp_tail[of "𝗂 * complex_of_real (s * l)" P] unfolding z .
qed
also have "… ≤ (¦s¦ * L) ^ Suc P * exp (¦s¦ * L) / fact (Suc P)"
proof -
have sl: "¦s * l¦ ≤ ¦s¦ * L" using lL by (simp add: abs_mult mult_left_mono)
show ?thesis by (intro divide_right_mono mult_mono power_mono sl) (simp_all add: sl L)
qed
finally show "cmod (?g l) ≤ (¦s¦ * L) ^ Suc P * exp (¦s¦ * L) / fact (Suc P)" .
qed
thus "∥evolution H s *⇩v v - exp_taylor n H s P *⇩v v∥ ≤ (¦s¦ * L) ^ Suc P * exp (¦s¦ * L) / fact (Suc P) * ∥v∥"
unfolding e .
qed
qed
lemma square_reindex:
fixes G :: "nat ⇒ nat ⇒ 'a::comm_monoid_add"
shows "(∑q≤P. ∑r≤Q. G q r) = (∑p≤P + Q. ∑q≤p. if q ≤ P ∧ p - q ≤ Q then G q (p - q) else 0)"
proof -
have "(∑q≤P. ∑r≤Q. G q r) = (∑(q, r)∈{..P} × {..Q}. G q r)" by (simp add: sum.cartesian_product)
also have "… = (∑(p, q)∈{(p, q). p ≤ P + Q ∧ q ≤ p ∧ q ≤ P ∧ p - q ≤ Q}. G q (p - q))"
by (rule sum.reindex_bij_witness[where i = "λ(p, q). (q, p - q)" and j = "λ(q, r). (q + r, q)"]) auto
also have "… = (∑(p, q)∈Sigma {..P + Q} (λp. {..p}). if q ≤ P ∧ p - q ≤ Q then G q (p - q) else 0)"
by (rule sum.mono_neutral_cong_left) (auto split: if_splits)
also have "… = (∑p≤P + Q. ∑q≤p. if q ≤ P ∧ p - q ≤ Q then G q (p - q) else 0)"
by (rule sum.Sigma[symmetric]) auto
finally show ?thesis .
qed
text ‹Evaluating a series up to degree $P$, $\sum_{p\le P}t^pf_p$, and truncating it at degree $P$. Evaluation
turns Cauchy products of truncations into products of matrices:
\[ \Bigl(\sum_{p\le P}t^pf_p\Bigr)\Bigl(\sum_{q\le Q}t^qg_q\Bigr)=\sum_{p\le P+Q}t^p\,(f^{\le P}\ast g^{\le Q})_p. \]›
definition poly_eval :: "nat ⇒ (nat ⇒ complex Matrix.mat) ⇒ nat ⇒ real ⇒ complex Matrix.mat" where
"poly_eval n f P t = matrix_sum n (λp. (complex_of_real t ^ p) ⋅⇩m f p) (Suc P)"
definition truncate_seq :: "nat ⇒ nat ⇒ (nat ⇒ complex Matrix.mat) ⇒ nat ⇒ complex Matrix.mat" where
"truncate_seq n P f p = (if p ≤ P then f p else 0⇩m n n)"
lemma truncate_seq_carrier [simp]: "seq_carrier n f ⟹ seq_carrier n (truncate_seq n P f)"
by (simp add: seq_carrier_def truncate_seq_def)
lemma poly_eval_carrier: "seq_carrier n f ⟹ poly_eval n f P t ∈ carrier_mat n n"
unfolding poly_eval_def by (rule matrix_sum_dim) simp
lemma poly_eval_index:
assumes "seq_carrier n f" "i < n" "j < n"
shows "poly_eval n f P t $$ (i, j) = (∑p≤P. complex_of_real t ^ p * f p $$ (i, j))"
unfolding poly_eval_def lessThan_Suc_atMost[symmetric] using assms by (subst matrix_sum_index) simp_all
lemma poly_eval_mult:
assumes f: "seq_carrier n f" and g: "seq_carrier n g"
shows "poly_eval n f P t * poly_eval n g Q t = poly_eval n (cauchy_prod n (truncate_seq n P f) (truncate_seq n Q g)) (P + Q) t"
proof (rule eq_matI)
let ?t = "complex_of_real t"
have c: "seq_carrier n (cauchy_prod n (truncate_seq n P f) (truncate_seq n Q g))" using f g by (simp add: cauchy_prod_carrier)
fix i j assume i: "i < dim_row (poly_eval n (cauchy_prod n (truncate_seq n P f) (truncate_seq n Q g)) (P + Q) t)"
and j: "j < dim_col (poly_eval n (cauchy_prod n (truncate_seq n P f) (truncate_seq n Q g)) (P + Q) t)"
have ij: "i < n" "j < n" using i j carrier_matD[OF poly_eval_carrier[OF c]] by auto
have sw: "(∑k<n. ∑q≤P. ∑r≤Q. T k q r) = (∑q≤P. ∑r≤Q. ∑k<n. T k q r)" for T :: "nat ⇒ nat ⇒ nat ⇒ complex"
by (subst sum.swap) (rule sum.cong[OF refl], rule sum.swap)
have "(poly_eval n f P t * poly_eval n g Q t) $$ (i, j) = (∑k<n. poly_eval n f P t $$ (i, k) * poly_eval n g Q t $$ (k, j))"
using ij carrier_matD[OF poly_eval_carrier[OF f, where P = P and t = t]] carrier_matD[OF poly_eval_carrier[OF g, where P = Q and t = t]]
by (simp add: scalar_prod_def atLeast0LessThan)
also have "… = (∑k<n. (∑q≤P. ?t ^ q * f q $$ (i, k)) * (∑r≤Q. ?t ^ r * g r $$ (k, j)))"
by (intro sum.cong refl) (simp add: poly_eval_index[OF f ij(1)] poly_eval_index[OF g _ ij(2)])
also have "… = (∑q≤P. ∑r≤Q. ∑k<n. ?t ^ (q + r) * (f q $$ (i, k) * g r $$ (k, j)))"
by (simp only: sum_product sw) (simp add: power_add mult_ac)
also have "… = (∑p≤P + Q. ∑q≤p. if q ≤ P ∧ p - q ≤ Q
then ∑k<n. ?t ^ (q + (p - q)) * (f q $$ (i, k) * g (p - q) $$ (k, j)) else 0)"
by (rule square_reindex)
also have "… = (∑p≤P + Q. ?t ^ p * (∑q≤p. ∑k<n. truncate_seq n P f q $$ (i, k) * truncate_seq n Q g (p - q) $$ (k, j)))"
unfolding sum_distrib_left
by (intro sum.cong refl) (use ij in ‹auto simp: truncate_seq_def sum_distrib_left mult_ac›)
also have "… = poly_eval n (cauchy_prod n (truncate_seq n P f) (truncate_seq n Q g)) (P + Q) t $$ (i, j)"
using poly_eval_index[OF c ij] cauchy_prod_index[OF truncate_seq_carrier[OF f] truncate_seq_carrier[OF g] ij] by simp
finally show "(poly_eval n f P t * poly_eval n g Q t) $$ (i, j) = poly_eval n (cauchy_prod n (truncate_seq n P f) (truncate_seq n Q g)) (P + Q) t $$ (i, j)" .
qed (use carrier_matD[OF poly_eval_carrier[OF f, where P = P and t = t]] carrier_matD[OF poly_eval_carrier[OF g, where P = Q and t = t]]
carrier_matD[OF poly_eval_carrier[OF cauchy_prod_carrier[OF truncate_seq_carrier[OF f] truncate_seq_carrier[OF g]], where P = "P + Q" and t = t]] in simp_all)
text ‹‹op_bound n c M›: $\norm{Mv}\le c\norm v$ for all $v$. Bounds multiply over products, scale, add over
sums, and give $\norm{X^p/p!}\le a^p/p!$ and $\norm{(f\ast g)_p}\le\sum_{q\le p}c_q\,c'_{p-q}$.›
definition op_bound :: "nat ⇒ real ⇒ complex Matrix.mat ⇒ bool" where
"op_bound n c M ⟷ (∀v. dim_vec v = n ⟶ ∥M *⇩v v∥ ≤ c * ∥v∥)"
lemma op_boundD: "op_bound n c M ⟹ dim_vec v = n ⟹ ∥M *⇩v v∥ ≤ c * ∥v∥"
by (simp add: op_bound_def)
lemma op_bound_zero: "op_bound n 0 (0⇩m n n)"
proof -
have "0⇩m n n *⇩v v = 0⇩v n" if "dim_vec v = n" for v :: "complex Matrix.vec"
using that by (intro eq_vecI) (auto simp: scalar_prod_def)
thus ?thesis by (simp add: op_bound_def vnorm_zero_vec)
qed
lemma op_bound_mult:
assumes A: "A ∈ carrier_mat n n" "op_bound n a A" and B: "B ∈ carrier_mat n n" "op_bound n b B" and a: "0 ≤ a"
shows "op_bound n (a * b) (A * B)"
unfolding op_bound_def
proof (intro allI impI)
fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
have "∥(A * B) *⇩v v∥ = ∥A *⇩v (B *⇩v v)∥" using assoc_mult_mat_vec[OF A(1) B(1) carrier_vecI[OF v]] by simp
also have "… ≤ a * ∥B *⇩v v∥" by (rule op_boundD[OF A(2)]) (use B(1) in simp)
also have "… ≤ a * (b * ∥v∥)" by (rule mult_left_mono[OF op_boundD[OF B(2) v] a])
finally show "∥(A * B) *⇩v v∥ ≤ a * b * ∥v∥" by (simp add: mult_ac)
qed
lemma op_bound_smult: "A ∈ carrier_mat n n ⟹ op_bound n a A ⟹ op_bound n (cmod c * a) (c ⋅⇩m A)"
unfolding op_bound_def
proof (intro allI impI)
fix v :: "complex Matrix.vec" assume A: "A ∈ carrier_mat n n" and b: "∀v. dim_vec v = n ⟶ ∥A *⇩v v∥ ≤ a * ∥v∥"
and v: "dim_vec v = n"
have "∥(c ⋅⇩m A) *⇩v v∥ = cmod c * ∥A *⇩v v∥"
using smult_mat_mult_mat_vec_assoc[OF A carrier_vecI[OF v]] by (simp add: cpx_vec_length_smult)
also have "… ≤ cmod c * (a * ∥v∥)" using b v by (simp add: mult_left_mono)
finally show "∥(c ⋅⇩m A) *⇩v v∥ ≤ cmod c * a * ∥v∥" by (simp add: mult_ac)
qed
lemma op_bound_matrix_sum:
assumes "⋀q. q < m ⟹ F q ∈ carrier_mat n n" "⋀q. q < m ⟹ op_bound n (c q) (F q)"
shows "op_bound n (∑q<m. c q) (matrix_sum n F m)"
using assms
proof (induction m)
case 0
show ?case using op_bound_zero by simp
next
case (Suc m)
have S: "matrix_sum n F m ∈ carrier_mat n n" by (rule matrix_sum_dim) (use Suc.prems in auto)
have IH: "op_bound n (∑q<m. c q) (matrix_sum n F m)" by (rule Suc.IH) (use Suc.prems in auto)
show ?case unfolding op_bound_def
proof (intro allI impI)
fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
have "matrix_sum n F (Suc m) *⇩v v = F m *⇩v v + matrix_sum n F m *⇩v v"
using add_mult_distrib_mat_vec[OF Suc.prems(1)[of m] S carrier_vecI[OF v]] by simp
hence "∥matrix_sum n F (Suc m) *⇩v v∥ ≤ ∥F m *⇩v v∥ + ∥matrix_sum n F m *⇩v v∥"
using vnorm_add_le[of "F m *⇩v v" "matrix_sum n F m *⇩v v"] Suc.prems(1)[of m] S by simp
also have "… ≤ c m * ∥v∥ + (∑q<m. c q) * ∥v∥"
using op_boundD[OF Suc.prems(2)[of m] v] op_boundD[OF IH v] by simp
finally show "∥matrix_sum n F (Suc m) *⇩v v∥ ≤ (∑q<Suc m. c q) * ∥v∥" by (simp add: algebra_simps)
qed
qed
lemma op_bound_pow:
assumes A: "A ∈ carrier_mat n n" "op_bound n a A" and a: "0 ≤ a"
shows "op_bound n (a ^ q) (A ^⇩m q)"
proof (induction q)
case 0
show ?case using A(1) by (simp add: op_bound_def one_mult_mat_vec[OF carrier_vecI])
next
case (Suc q)
have "op_bound n (a ^ q * a) (A ^⇩m q * A)" by (rule op_bound_mult[OF _ Suc A]) (use A a in simp_all)
thus ?case by (simp add: mult.commute)
qed
lemma exp_coeff_op_bound:
assumes Y: "Y ∈ carrier_mat n n" "op_bound n a Y" and a: "0 ≤ a"
shows "op_bound n (a ^ q / fact q) (exp_coeff Y q)"
proof -
have "cmod (complex_of_real (1 / fact q)) * a ^ q = a ^ q / fact q" by (simp only: norm_of_real) simp
thus ?thesis using op_bound_smult[OF pow_carrier_mat[OF Y(1)] op_bound_pow[OF Y a], of "complex_of_real (1 / fact q)" q]
unfolding exp_coeff_def by simp
qed
text ‹\[ \sum_{q\le p}\frac{a^q\,b^{p-q}}{q!\,(p-q)!}=\frac{(a+b)^p}{p!}. \]›
lemma binomial_exp_coef:
fixes a b :: "'a::field_char_0"
shows "(∑q≤p. a ^ q * b ^ (p - q) / (fact q * fact (p - q))) = (a + b) ^ p / fact p"
proof -
have "(a + b) ^ p = (∑q≤p. of_nat (p choose q) * a ^ q * b ^ (p - q))" by (rule binomial_ring)
also have "… = fact p * (∑q≤p. a ^ q * b ^ (p - q) / (fact q * fact (p - q)))"
unfolding sum_distrib_left by (intro sum.cong refl) (simp add: binomial_fact field_simps)
finally show ?thesis by (simp add: field_simps)
qed
lemma op_bound_mono: "op_bound n c M ⟹ c ≤ c' ⟹ op_bound n c' M"
unfolding op_bound_def
proof (intro allI impI)
fix v :: "complex Matrix.vec" assume b: "∀v. dim_vec v = n ⟶ ∥M *⇩v v∥ ≤ c * ∥v∥" and cc: "c ≤ c'" and v: "dim_vec v = n"
have "∥M *⇩v v∥ ≤ c * ∥v∥" using b v by simp
also have "… ≤ c' * ∥v∥" by (rule mult_right_mono[OF cc vnorm_ge0])
finally show "∥M *⇩v v∥ ≤ c' * ∥v∥" .
qed
lemma cauchy_prod_op_bound:
assumes f: "seq_carrier n f" and g: "seq_carrier n g" and bf: "⋀q. op_bound n (cf q) (f q)" and bg: "⋀q. op_bound n (cg q) (g q)"
and cf: "⋀q. 0 ≤ cf q"
shows "op_bound n (∑q≤p. cf q * cg (p - q)) (cauchy_prod n f g p)"
unfolding cauchy_prod_def lessThan_Suc_atMost[symmetric]
by (rule op_bound_matrix_sum) (use f g in ‹simp_all add: op_bound_mult[OF seq_carrier_in[OF f] bf seq_carrier_in[OF g] bg cf]›)
text ‹The total weight $\Lambda=L\sum_{(a,H)\in F}|a|$ of a formula. The $p$-th coefficient of the formula is
bounded by $\Lambda^p/p!$ (‹prod_coeff_op_bound›).›
definition total_weight :: "real ⇒ (real × complex Matrix.mat) list ⇒ real" where
"total_weight L F = (∑x←F. ¦fst x¦) * L"
lemma total_weight_nonneg: "0 ≤ L ⟹ 0 ≤ total_weight L F"
unfolding total_weight_def by (intro mult_nonneg_nonneg sum_list_nonneg) auto
lemma factor_gen_carrier: "herm_bounded n L (snd x) ⟹ factor_gen x ∈ carrier_mat n n"
using herm_boundedD(1) by (simp add: factor_gen_def)
lemma factor_gen_op_bound:
assumes "herm_bounded n L (snd x)"
shows "op_bound n (¦fst x¦ * L) (factor_gen x)"
proof -
have "op_bound n L (snd x)" using herm_boundedD(3)[OF assms] by (simp add: op_bound_def)
from op_bound_smult[OF herm_boundedD(1)[OF assms] this, of "𝗂 * complex_of_real (fst x)"]
show ?thesis by (simp add: factor_gen_def norm_mult)
qed
lemma prod_coeff_op_bound:
assumes F: "∀x ∈ set F. herm_bounded n L (snd x)" and L: "0 ≤ L"
shows "op_bound n (total_weight L F ^ p / fact p) (prod_coeff n (map factor_gen F) p)"
using F
proof (induction F arbitrary: p)
case Nil
show ?case using op_bound_zero by (cases p) (simp_all add: total_weight_def seq_one_def op_bound_def one_mult_mat_vec[OF carrier_vecI])
next
case (Cons x G)
have Y: "factor_gen x ∈ carrier_mat n n" "op_bound n (¦fst x¦ * L) (factor_gen x)"
using Cons.prems factor_gen_carrier[of n L x] factor_gen_op_bound[of n L x] by auto
have G: "∀Z ∈ set (map factor_gen G). Z ∈ carrier_mat n n" using Cons.prems factor_gen_carrier by auto
have a0: "0 ≤ ¦fst x¦ * L" using L by simp
have "op_bound n (∑q≤p. (¦fst x¦ * L) ^ q / fact q * (total_weight L G ^ (p - q) / fact (p - q))) (cauchy_prod n (exp_coeff (factor_gen x)) (prod_coeff n (map factor_gen G)) p)"
by (rule cauchy_prod_op_bound[OF exp_coeff_carrier[OF Y(1)] prod_coeff_carrier[OF G] exp_coeff_op_bound[OF Y a0] Cons.IH]) (use Cons.prems a0 in simp_all)
moreover have "(∑q≤p. (¦fst x¦ * L) ^ q / fact q * (total_weight L G ^ (p - q) / fact (p - q))) = total_weight L (x # G) ^ p / fact p"
using binomial_exp_coef[where a = "¦fst x¦ * L" and b = "total_weight L G" and p = p] by (simp add: total_weight_def algebra_simps)
ultimately show ?case by simp
qed
text ‹The operator of a formula, $\prod_{(a,H)\in F}e^{iatH}$; it is unitary.›
fun formula_product :: "nat ⇒ real ⇒ (real × complex Matrix.mat) list ⇒ complex Matrix.mat" where
"formula_product n t [] = 1⇩m n"
| "formula_product n t (x # F) = evolution (snd x) (fst x * t) * formula_product n t F"
lemma formula_product_carrier_unitary:
assumes "∀x ∈ set F. herm_bounded n L (snd x)"
shows "formula_product n t F ∈ carrier_mat n n ∧ Quantum.unitary (formula_product n t F)"
using assms
proof (induction F)
case Nil
show ?case by (simp add: id_is_unitary)
next
case (Cons x F)
note h = herm_boundedD[of n L "snd x"]
have hx: "snd x ∈ carrier_mat n n" "hermitian (snd x)" using Cons.prems h by auto
have IH: "formula_product n t F ∈ carrier_mat n n" "Quantum.unitary (formula_product n t F)" using Cons by auto
have "Quantum.unitary (evolution (snd x) (fst x * t) * formula_product n t F)"
by (rule unitary_mult[OF evolution_unitary[OF hx] IH(2) evolution_carrier[OF hx] IH(1)])
thus ?case using mult_carrier_mat[OF evolution_carrier[OF hx] IH(1)] by simp
qed
lemma exp_taylor_poly_eval:
assumes H: "H ∈ carrier_mat n n"
shows "exp_taylor n H (a * t) P = poly_eval n (exp_coeff (factor_gen (a, H))) P t"
unfolding exp_taylor_def poly_eval_def factor_gen_def fst_conv snd_conv
proof (rule matrix_sum_cong)
fix q assume "q < Suc P"
have "(𝗂 * complex_of_real (a * t)) ⋅⇩m H = complex_of_real t ⋅⇩m ((𝗂 * complex_of_real a) ⋅⇩m H)"
by (rule eq_matI) auto
thus "exp_coeff ((𝗂 * complex_of_real (a * t)) ⋅⇩m H) q = complex_of_real t ^ q ⋅⇩m exp_coeff ((𝗂 * complex_of_real a) ⋅⇩m H) q"
using exp_coeff_smult[of "(𝗂 * complex_of_real a) ⋅⇩m H" n "complex_of_real t" q] H by (simp add: seq_scale_def)
qed
lemma poly_eval_cong: "(⋀p. p ≤ P ⟹ f p = g p) ⟹ poly_eval n f P t = poly_eval n g P t"
unfolding poly_eval_def by (rule matrix_sum_cong) simp
text ‹Splitting a polynomial at degree $P$, and the tail bound
$\sum_{p<Q}z^{K+p}/(K+p)!\le z^Ke^z/K!$ for $z\ge0$.›
lemma poly_eval_split:
assumes f: "seq_carrier n f"
shows "poly_eval n f (P + Q) t = poly_eval n f P t + matrix_sum n (λp. (complex_of_real t ^ (Suc P + p)) ⋅⇩m f (Suc P + p)) Q"
proof (induction Q)
case 0
show ?case using poly_eval_carrier[OF f, where P = P and t = t] by simp
next
case (Suc Q)
let ?h = "matrix_sum n (λp. (complex_of_real t ^ (Suc P + p)) ⋅⇩m f (Suc P + p)) Q"
have c: "(complex_of_real t ^ (Suc P + Q)) ⋅⇩m f (Suc P + Q) ∈ carrier_mat n n" "poly_eval n f P t ∈ carrier_mat n n"
"?h ∈ carrier_mat n n" using f poly_eval_carrier[OF f] by (auto intro!: matrix_sum_dim)
have "poly_eval n f (P + Suc Q) t = (complex_of_real t ^ (Suc P + Q)) ⋅⇩m f (Suc P + Q) + poly_eval n f (P + Q) t"
by (simp add: poly_eval_def)
also have "… = (complex_of_real t ^ (Suc P + Q)) ⋅⇩m f (Suc P + Q) + (poly_eval n f P t + ?h)" unfolding Suc ..
also have "… = ((complex_of_real t ^ (Suc P + Q)) ⋅⇩m f (Suc P + Q) + poly_eval n f P t) + ?h"
by (rule assoc_add_mat[OF c, symmetric])
also have "(complex_of_real t ^ (Suc P + Q)) ⋅⇩m f (Suc P + Q) + poly_eval n f P t
= poly_eval n f P t + (complex_of_real t ^ (Suc P + Q)) ⋅⇩m f (Suc P + Q)"
by (rule comm_add_mat[OF c(1,2)])
also have "(poly_eval n f P t + (complex_of_real t ^ (Suc P + Q)) ⋅⇩m f (Suc P + Q)) + ?h
= poly_eval n f P t + ((complex_of_real t ^ (Suc P + Q)) ⋅⇩m f (Suc P + Q) + ?h)"
by (rule assoc_add_mat[OF c(2) c(1) c(3)])
finally show ?case by simp
qed
lemma partial_tail:
fixes z :: real
assumes z: "0 ≤ z"
shows "(∑p<Q. z ^ (K + p) / fact (K + p)) ≤ z ^ K * exp z / fact K"
proof -
have "(∑p<Q. z ^ (K + p) / fact (K + p)) ≤ (∑p<Q. z ^ K / fact K * (z ^ p / fact p))"
proof (rule sum_mono)
fix p
have "z ^ (K + p) / fact (K + p) ≤ z ^ (K + p) / (fact K * fact p)"
by (rule divide_left_mono) (use z fact_mult_le_fact_add[of K p] in simp_all)
thus "z ^ (K + p) / fact (K + p) ≤ z ^ K / fact K * (z ^ p / fact p)" by (simp add: power_add field_simps)
qed
also have "… = z ^ K / fact K * (∑p<Q. z ^ p / fact p)" by (simp add: sum_distrib_left)
also have "(∑p<Q. z ^ p / fact p) ≤ exp z"
proof -
have s: "summable (λp. z ^ p / fact p)" using summable_exp[of z] by (simp add: field_simps)
have "(∑p<Q. z ^ p / fact p) ≤ (∑p. z ^ p / fact p)" by (rule sum_le_suminf[OF s]) (use z in simp_all)
also have "… = exp z" using sums_unique[OF exp_converges[of z]] by (simp add: field_simps)
finally show ?thesis .
qed
hence "z ^ K / fact K * (∑p<Q. z ^ p / fact p) ≤ z ^ K / fact K * exp z" by (rule mult_left_mono) (use z in simp)
finally show ?thesis by simp
qed
lemma poly_eval_op_bound:
assumes f: "seq_carrier n f" and b: "⋀p. op_bound n (c p) (f p)"
shows "op_bound n (∑p≤P. ¦t¦ ^ p * c p) (poly_eval n f P t)"
unfolding poly_eval_def lessThan_Suc_atMost[symmetric]
proof (rule op_bound_matrix_sum)
fix p
show "(complex_of_real t ^ p) ⋅⇩m f p ∈ carrier_mat n n" using f by simp
have "cmod (complex_of_real t ^ p) = ¦t¦ ^ p" by (simp add: norm_power)
thus "op_bound n (¦t¦ ^ p * c p) ((complex_of_real t ^ p) ⋅⇩m f p)"
using op_bound_smult[OF seq_carrier_in[OF f] b, of "complex_of_real t ^ p" p] by simp
qed
lemma poly_eval_seq_one: "poly_eval n (seq_one n) P t = 1⇩m n"
proof -
have "poly_eval n (seq_one n) P t = (complex_of_real t ^ 0) ⋅⇩m seq_one n 0"
unfolding poly_eval_def by (rule matrix_sum_single) (auto simp: seq_one_def)
thus ?thesis by (simp add: seq_one_def one_smult_mat)
qed
text ‹A formula is close to its own Taylor polynomial: with $|F|$ factors and weight $\Lambda$,
\[ \Bigl\|\prod_{(a,H)\in F}e^{iatH}-\sum_{p\le P}t^p\,\mathrm{coeff}_p\Bigr\|\le
2|F|\,\frac{(\Lambda|t|)^{P+1}e^{\Lambda|t|}}{(P+1)!}. \]›
theorem formula_product_approx:
assumes F: "∀x ∈ set F. herm_bounded n L (snd x)" and L: "0 ≤ L"
shows "formula_product n t F ≈⇘2 * real (length F) * (total_weight L F * ¦t¦) ^ Suc P * exp (total_weight L F * ¦t¦) / fact (Suc P)⇙ poly_eval n (prod_coeff n (map factor_gen F)) P t"
using F
proof (induction F)
case Nil
show ?case
proof (rule op_closeI[where m = n and n = n])
show "formula_product n t [] ∈ carrier_mat n n" by simp
next
fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
have "formula_product n t [] *⇩v v - poly_eval n (prod_coeff n (map factor_gen [])) P t *⇩v v = 0⇩v n"
using v by (intro eq_vecI) (simp_all add: poly_eval_seq_one)
thus "∥formula_product n t [] *⇩v v - poly_eval n (prod_coeff n (map factor_gen [])) P t *⇩v v∥
≤ 2 * real (length []) * (total_weight L [] * ¦t¦) ^ Suc P * exp (total_weight L [] * ¦t¦) / fact (Suc P) * ∥v∥"
by (simp add: vnorm_zero_vec)
qed
next
case (Cons x G)
let ?a = "fst x" and ?H = "snd x" and ?Y = "factor_gen x" and ?fG = "prod_coeff n (map factor_gen G)"
let ?x0 = "¦fst x¦ * L" and ?y0 = "total_weight L G" and ?P' = "Suc P"
let ?z = "(?x0 + ?y0) * ¦t¦"
have hx: "herm_bounded n L ?H" and hG: "∀y ∈ set G. herm_bounded n L (snd y)" using Cons.prems by auto
have Hc: "?H ∈ carrier_mat n n" "hermitian ?H" using herm_boundedD[OF hx] by simp_all
have G: "∀Z ∈ set (map factor_gen G). Z ∈ carrier_mat n n" using hG factor_gen_carrier by auto
have Yc: "?Y ∈ carrier_mat n n" and Yb: "op_bound n ?x0 ?Y" using factor_gen_carrier[OF hx] factor_gen_op_bound[OF hx] by simp_all
have x0: "0 ≤ ?x0" and y0: "0 ≤ ?y0" using L total_weight_nonneg by simp_all
have fGc: "seq_carrier n ?fG" by (rule prod_coeff_carrier[OF G])
have tYc: "seq_carrier n (exp_coeff ?Y)" by (rule exp_coeff_carrier[OF Yc])
define E where "E = evolution ?H (?a * t)"
define T where "T = poly_eval n (exp_coeff ?Y) P t"
define SG where "SG = poly_eval n ?fG P t"
define W where "W = formula_product n t G"
define C where "C = cauchy_prod n (truncate_seq n P (exp_coeff ?Y)) (truncate_seq n P ?fG)"
define hi where "hi = matrix_sum n (λp. (complex_of_real t ^ (Suc P + p)) ⋅⇩m C (Suc P + p)) P"
have Cc: "seq_carrier n C" unfolding C_def by (simp add: cauchy_prod_carrier tYc fGc)
have Ec: "E ∈ carrier_mat n n" unfolding E_def by (rule evolution_carrier[OF Hc])
have Tc: "T ∈ carrier_mat n n" unfolding T_def by (rule poly_eval_carrier[OF tYc])
have SGc: "SG ∈ carrier_mat n n" unfolding SG_def by (rule poly_eval_carrier[OF fGc])
have Wcu: "W ∈ carrier_mat n n" "Quantum.unitary W" using formula_product_carrier_unitary[OF hG] by (simp_all add: W_def)
have hic: "hi ∈ carrier_mat n n" unfolding hi_def by (rule matrix_sum_dim) (simp add: Cc)
have fx: "prod_coeff n (map factor_gen (x # G)) = cauchy_prod n (exp_coeff ?Y) ?fG" by simp
have lamx: "total_weight L (x # G) * ¦t¦ = ?z" by (simp add: total_weight_def algebra_simps)
have TE: "T = exp_taylor n ?H (?a * t) P" unfolding T_def using exp_taylor_poly_eval[OF Hc(1), of ?a t P] by (simp add: factor_gen_def)
have TSG: "T * SG = poly_eval n (cauchy_prod n (exp_coeff ?Y) ?fG) P t + hi"
proof -
have "T * SG = poly_eval n C (P + P) t" unfolding T_def SG_def C_def by (rule poly_eval_mult[OF tYc fGc])
also have "… = poly_eval n C P t + hi" unfolding hi_def by (rule poly_eval_split[OF Cc])
also have "poly_eval n C P t = poly_eval n (cauchy_prod n (exp_coeff ?Y) ?fG) P t"
unfolding C_def by (rule poly_eval_cong, rule cauchy_prod_congr) (auto simp: truncate_seq_def)
finally show ?thesis .
qed
have rY: "E ≈⇘(?x0 * ¦t¦) ^ ?P' * exp (?x0 * ¦t¦) / fact ?P'⇙ T"
proof -
have e: "¦?a * t¦ * L = ?x0 * ¦t¦" by (simp add: abs_mult mult_ac)
show ?thesis using evolution_taylor[OF hx L, of "?a * t" P] unfolding E_def TE e .
qed
have cT: "op_bound n (exp (?x0 * ¦t¦)) T"
proof -
have "op_bound n (∑p≤P. ¦t¦ ^ p * (?x0 ^ p / fact p)) T"
unfolding T_def by (rule poly_eval_op_bound[OF tYc exp_coeff_op_bound[OF Yc Yb x0]])
moreover have "(∑p≤P. ¦t¦ ^ p * (?x0 ^ p / fact p)) ≤ exp (?x0 * ¦t¦)"
using partial_tail[where z = "?x0 * ¦t¦" and Q = "Suc P" and K = 0, OF mult_nonneg_nonneg[OF x0 abs_ge_zero]]
by (simp add: lessThan_Suc_atMost power_mult_distrib mult_ac)
ultimately show ?thesis by (rule op_bound_mono)
qed
have Cb: "op_bound n ((?x0 + ?y0) ^ p / fact p) (C p)" for p
proof -
have tb: "op_bound n (?x0 ^ q / fact q) (truncate_seq n P (exp_coeff ?Y) q)" for q
using exp_coeff_op_bound[OF Yc Yb x0, of q] op_bound_mono[OF op_bound_zero, of "?x0 ^ q / fact q" n] x0
by (simp add: truncate_seq_def)
have gb: "op_bound n (?y0 ^ q / fact q) (truncate_seq n P ?fG q)" for q
using prod_coeff_op_bound[OF hG L, of q] op_bound_mono[OF op_bound_zero, of "?y0 ^ q / fact q" n] y0
by (simp add: truncate_seq_def)
have "op_bound n (∑q≤p. ?x0 ^ q / fact q * (?y0 ^ (p - q) / fact (p - q))) (C p)"
unfolding C_def by (rule cauchy_prod_op_bound[OF truncate_seq_carrier[OF tYc] truncate_seq_carrier[OF fGc] tb gb]) (use x0 in simp)
moreover have "(∑q≤p. ?x0 ^ q / fact q * (?y0 ^ (p - q) / fact (p - q))) = (?x0 + ?y0) ^ p / fact p"
using binomial_exp_coef[where a = ?x0 and b = ?y0 and p = p] by simp
ultimately show ?thesis by simp
qed
have hb: "op_bound n (?z ^ ?P' * exp ?z / fact ?P') hi"
proof -
have "op_bound n (∑p<P. ¦t¦ ^ (Suc P + p) * ((?x0 + ?y0) ^ (Suc P + p) / fact (Suc P + p))) hi"
proof (unfold hi_def, rule op_bound_matrix_sum)
fix p
show "(complex_of_real t ^ (Suc P + p)) ⋅⇩m C (Suc P + p) ∈ carrier_mat n n" using Cc by simp
have "cmod (complex_of_real t ^ (Suc P + p)) = ¦t¦ ^ (Suc P + p)" by (simp only: norm_power norm_of_real)
thus "op_bound n (¦t¦ ^ (Suc P + p) * ((?x0 + ?y0) ^ (Suc P + p) / fact (Suc P + p)))
((complex_of_real t ^ (Suc P + p)) ⋅⇩m C (Suc P + p))"
using op_bound_smult[OF seq_carrier_in[OF Cc] Cb, of "complex_of_real t ^ (Suc P + p)" "Suc P + p"] by simp
qed
moreover have "(∑p<P. ¦t¦ ^ (Suc P + p) * ((?x0 + ?y0) ^ (Suc P + p) / fact (Suc P + p)))
≤ ?z ^ ?P' * exp ?z / fact ?P'"
using partial_tail[where z = ?z and Q = P and K = "Suc P", OF mult_nonneg_nonneg[OF add_nonneg_nonneg[OF x0 y0] abs_ge_zero]]
by (simp add: power_mult_distrib mult_ac)
ultimately show ?thesis by (rule op_bound_mono)
qed
let ?rG = "2 * real (length G) * (?y0 * ¦t¦) ^ ?P' * exp (?y0 * ¦t¦) / fact ?P'"
have IH: "W ≈⇘?rG⇙ SG" using Cons.IH[OF hG] by (simp add: W_def SG_def)
show ?case unfolding lamx
proof (rule op_closeI[where m = n and n = n])
show "formula_product n t (x # G) ∈ carrier_mat n n"
using formula_product_carrier_unitary[OF Cons.prems] by simp
next
fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
define w where "w = W *⇩v v"
have wn: "dim_vec w = n" and nw: "∥w∥ = ∥v∥" using Wcu v unitary_vnorm[OF Wcu v] by (simp_all add: w_def)
have sp: "formula_product n t (x # G) *⇩v v = E *⇩v w"
unfolding w_def E_def W_def using assoc_mult_mat_vec[OF evolution_carrier[OF Hc] _ carrier_vecI[OF v]] Wcu(1)
by (simp add: W_def)
have pf: "poly_eval n (prod_coeff n (map factor_gen (x # G))) P t *⇩v v = poly_eval n (cauchy_prod n (exp_coeff ?Y) ?fG) P t *⇩v v" by simp
let ?pf = "poly_eval n (cauchy_prod n (exp_coeff ?Y) ?fG) P t"
have pfc: "?pf ∈ carrier_mat n n" by (rule poly_eval_carrier) (simp add: cauchy_prod_carrier tYc fGc)
have e3: "T *⇩v (SG *⇩v v) - ?pf *⇩v v = hi *⇩v v"
proof -
have "T *⇩v (SG *⇩v v) = (?pf + hi) *⇩v v" using assoc_mult_mat_vec[OF Tc SGc carrier_vecI[OF v]] TSG by simp
also have "… = ?pf *⇩v v + hi *⇩v v" by (rule add_mult_distrib_mat_vec[OF pfc hic carrier_vecI[OF v]])
finally have tsg: "T *⇩v (SG *⇩v v) = ?pf *⇩v v + hi *⇩v v" .
have g: "dim_vec a = n ⟹ dim_vec b = n ⟹ (a + b) - a = b" for a b :: "complex Matrix.vec"
by (intro eq_vecI) auto
show ?thesis unfolding tsg by (rule g) (use pfc hic v in simp_all)
qed
have e2: "T *⇩v w - T *⇩v (SG *⇩v v) = T *⇩v (w - SG *⇩v v)"
proof -
have "SG *⇩v v ∈ carrier_vec n" by (rule carrier_vecI) (use SGc in simp)
thus ?thesis by (rule mult_minus_distrib_mat_vec[OF Tc carrier_vecI[OF wn], symmetric])
qed
have b1: "∥E *⇩v w - T *⇩v w∥ ≤ (?x0 * ¦t¦) ^ ?P' * exp (?x0 * ¦t¦) / fact ?P' * ∥v∥"
using op_closeD[OF rY Ec wn] nw by simp
have b2: "∥T *⇩v (w - SG *⇩v v)∥ ≤ exp (?x0 * ¦t¦) * (?rG * ∥v∥)"
proof -
have "∥T *⇩v (w - SG *⇩v v)∥ ≤ exp (?x0 * ¦t¦) * ∥w - SG *⇩v v∥"
by (rule op_boundD[OF cT]) (use wn SGc in simp)
also have "∥w - SG *⇩v v∥ ≤ ?rG * ∥v∥" using op_closeD[OF IH Wcu(1) v] by (simp add: w_def)
finally show ?thesis by simp
qed
have b3: "∥hi *⇩v v∥ ≤ ?z ^ ?P' * exp ?z / fact ?P' * ∥v∥" by (rule op_boundD[OF hb v])
have "∥E *⇩v w - ?pf *⇩v v∥ ≤ ∥E *⇩v w - T *⇩v w∥ + ∥T *⇩v w - ?pf *⇩v v∥"
by (rule vnorm_diff_le[where n = n]) (use Ec Tc pfc wn v in simp_all)
also have "∥T *⇩v w - ?pf *⇩v v∥ ≤ ∥T *⇩v w - T *⇩v (SG *⇩v v)∥ + ∥T *⇩v (SG *⇩v v) - ?pf *⇩v v∥"
by (rule vnorm_diff_le[where n = n]) (use Tc SGc pfc wn v in simp_all)
finally have tri: "∥E *⇩v w - ?pf *⇩v v∥ ≤ (?x0 * ¦t¦) ^ ?P' * exp (?x0 * ¦t¦) / fact ?P' * ∥v∥
+ exp (?x0 * ¦t¦) * (?rG * ∥v∥) + ?z ^ ?P' * exp ?z / fact ?P' * ∥v∥"
using b1 b2 b3 unfolding e2 e3 by linarith
have z0: "0 ≤ ?z" "?x0 * ¦t¦ ≤ ?z" "?y0 * ¦t¦ ≤ ?z" using x0 y0 by (simp_all add: distrib_right)
have k1: "(?x0 * ¦t¦) ^ ?P' * exp (?x0 * ¦t¦) ≤ ?z ^ ?P' * exp ?z"
by (intro mult_mono power_mono) (use z0 x0 y0 in simp_all)
have k2: "exp (?x0 * ¦t¦) * ((?y0 * ¦t¦) ^ ?P' * exp (?y0 * ¦t¦)) ≤ ?z ^ ?P' * exp ?z"
proof -
have "exp (?x0 * ¦t¦) * exp (?y0 * ¦t¦) = exp ?z" by (simp add: exp_add[symmetric] distrib_right)
moreover have "(?y0 * ¦t¦) ^ ?P' ≤ ?z ^ ?P'" by (rule power_mono) (use z0 y0 in simp_all)
ultimately show ?thesis by (metis mult.left_commute mult_right_mono exp_ge_zero)
qed
have "(?x0 * ¦t¦) ^ ?P' * exp (?x0 * ¦t¦) / fact ?P' * ∥v∥
+ exp (?x0 * ¦t¦) * (?rG * ∥v∥) + ?z ^ ?P' * exp ?z / fact ?P' * ∥v∥
≤ 2 * real (length (x # G)) * ?z ^ ?P' * exp ?z / fact ?P' * ∥v∥"
proof -
have "(?x0 * ¦t¦) ^ ?P' * exp (?x0 * ¦t¦) + exp (?x0 * ¦t¦) * (2 * real (length G) * (?y0 * ¦t¦) ^ ?P' * exp (?y0 * ¦t¦))
+ ?z ^ ?P' * exp ?z ≤ 2 * real (length (x # G)) * (?z ^ ?P' * exp ?z)"
using k1 mult_left_mono[OF k2, of "2 * real (length G)"] by (simp add: algebra_simps)
hence "((?x0 * ¦t¦) ^ ?P' * exp (?x0 * ¦t¦) + exp (?x0 * ¦t¦) * (2 * real (length G) * (?y0 * ¦t¦) ^ ?P' * exp (?y0 * ¦t¦))
+ ?z ^ ?P' * exp ?z) / fact ?P' * ∥v∥ ≤ 2 * real (length (x # G)) * (?z ^ ?P' * exp ?z) / fact ?P' * ∥v∥"
by (intro mult_right_mono divide_right_mono) (simp_all add: vnorm_ge0)
thus ?thesis by (simp add: algebra_simps add_divide_distrib)
qed
with tri show "∥formula_product n t (x # G) *⇩v v - poly_eval n (prod_coeff n (map factor_gen (x # G))) P t *⇩v v∥
≤ 2 * real (length (x # G)) * ?z ^ ?P' * exp ?z / fact ?P' * ∥v∥"
unfolding sp pf by linarith
qed
qed
text ‹Closeness is transitive, the errors adding up, and monotone in the error.›
lemma op_close_trans:
assumes "U ≈⇘a⇙ V" "V ≈⇘b⇙ W" "U ∈ carrier_mat n n" "V ∈ carrier_mat n n" "W ∈ carrier_mat n n"
shows "U ≈⇘a + b⇙ W"
proof (rule op_closeI[OF assms(3)])
fix v :: "complex Matrix.vec" assume v: "dim_vec v = n"
have "∥U *⇩v v - W *⇩v v∥ ≤ ∥U *⇩v v - V *⇩v v∥ + ∥V *⇩v v - W *⇩v v∥"
by (rule vnorm_diff_le[where n = n]) (use assms in simp_all)
also have "… ≤ a * ∥v∥ + b * ∥v∥" using op_closeD[OF assms(1,3) v] op_closeD[OF assms(2,4) v] by simp
finally show "∥U *⇩v v - W *⇩v v∥ ≤ (a + b) * ∥v∥" by (simp add: algebra_simps)
qed
lemma op_close_mono:
assumes "U ≈⇘a⇙ V" "a ≤ b"
shows "U ≈⇘b⇙ V"
unfolding op_close_def
proof (intro allI impI)
fix v :: "complex Matrix.vec" assume "dim_vec v = dim_col U"
thus "∥U *⇩v v - V *⇩v v∥ ≤ b * ∥v∥"
using assms(1)[unfolded op_close_def] mult_right_mono[OF assms(2) vnorm_ge0[of v]] order_trans by blast
qed
text ‹For Suzuki's formula: the sum of $m$ Hamiltonians bounded by $L$ is bounded by $mL$, the formula has
$2\cdot5^km$ factors, its weights add up to $m$, and $\Lambda\ge mL$.›
lemma hamiltonian_sum_herm_bounded:
"∀H ∈ set Hs. herm_bounded n L H ⟹ herm_bounded n (real (length Hs) * L) (hamiltonian_sum n Hs)"
unfolding herm_bounded_def[of n "real (length Hs) * L"]
using hamiltonian_sum_carrier[of Hs n] hamiltonian_sum_hermitian[of Hs n L] hamiltonian_sum_bound[of Hs n L] herm_boundedD(1) by blast
lemma length_suzuki: "length (suzuki k Hs) = 2 * 5 ^ k * length Hs"
by (induction k) (simp_all add: strang_def suzuki_weights_def Let_def length_concat comp_def)
lemma sum_suzuki: "(∑x←suzuki k Hs. fst x) = real (length Hs)"
proof (induction k)
case 0
show ?case by (simp add: strang_def comp_def sum_list_triv rev_map)
next
case (Suc k)
thus ?case by (simp add: suzuki_weights_def Let_def comp_def sum_list_const_mult) (simp add: algebra_simps)
qed
lemma total_weight_suzuki: "0 ≤ L ⟹ real (length Hs) * L ≤ total_weight L (suzuki k Hs)"
unfolding total_weight_def sum_suzuki[of k Hs, symmetric]
by (intro mult_right_mono sum_list_mono) simp_all
text ‹One Suzuki step: $\norm{S_{2k+2}(\delta)-e^{i\delta H}}\le(2|F|+1)(\Lambda|\delta|)^{2k+3}e^{\Lambda|\delta|}/(2k+3)!$.›
lemma suzuki_step:
fixes k :: nat and d :: real
assumes Hs: "∀H ∈ set Hs. herm_bounded n L H" and L: "0 ≤ L"
defines "F ≡ suzuki k Hs" and "q ≡ 2 * k + 3"
shows "formula_product n d F ≈⇘(2 * real (length F) + 1) * (total_weight L F * ¦d¦) ^ q * exp (total_weight L F * ¦d¦) / fact q⇙ evolution (hamiltonian_sum n Hs) d"
proof -
have F: "∀x ∈ set F. herm_bounded n L (snd x)" using Hs suzuki_snd unfolding F_def by blast
have C: "∀H ∈ set Hs. H ∈ carrier_mat n n" using Hs herm_boundedD(1) by blast
have Hb: "herm_bounded n (real (length Hs) * L) (hamiltonian_sum n Hs)" by (rule hamiltonian_sum_herm_bounded[OF Hs])
note Hh = herm_boundedD[OF Hb]
have mL: "0 ≤ real (length Hs) * L" using L by simp
let ?X = "𝗂 ⋅⇩m hamiltonian_sum n Hs" and ?f = "prod_coeff n (map factor_gen F)"
have q: "q = Suc (2 * k + 2)" by (simp add: q_def)
have pe: "poly_eval n ?f (2 * k + 2) d = exp_taylor n (hamiltonian_sum n Hs) d (2 * k + 2)"
proof -
have "poly_eval n ?f (2 * k + 2) d = poly_eval n (exp_coeff (factor_gen (1, hamiltonian_sum n Hs))) (2 * k + 2) d"
by (rule poly_eval_cong) (use suzuki_order[OF C, of k] in ‹simp add: F_def factor_gen_def›)
also have "… = exp_taylor n (hamiltonian_sum n Hs) d (2 * k + 2)" using exp_taylor_poly_eval[OF Hh(1), of 1 d] by simp
finally show ?thesis .
qed
have a: "formula_product n d F ≈⇘2 * real (length F) * (total_weight L F * ¦d¦) ^ q * exp (total_weight L F * ¦d¦) / fact q⇙ exp_taylor n (hamiltonian_sum n Hs) d (2 * k + 2)"
using formula_product_approx[OF F L, of d "2 * k + 2"] unfolding pe q .
have b0: "exp_taylor n (hamiltonian_sum n Hs) d (2 * k + 2) ≈⇘(¦d¦ * (real (length Hs) * L)) ^ q * exp (¦d¦ * (real (length Hs) * L)) / fact q⇙ evolution (hamiltonian_sum n Hs) d"
unfolding q by (rule op_close_sym[OF evolution_taylor[OF Hb mL] evolution_carrier[OF Hh(1,2)] exp_taylor_carrier[OF Hh(1)]])
have le: "¦d¦ * (real (length Hs) * L) ≤ total_weight L F * ¦d¦"
using mult_left_mono[OF total_weight_suzuki[OF L, of Hs k] abs_ge_zero[of d]] unfolding F_def by (simp add: mult_ac)
have b: "exp_taylor n (hamiltonian_sum n Hs) d (2 * k + 2) ≈⇘(total_weight L F * ¦d¦) ^ q * exp (total_weight L F * ¦d¦) / fact q⇙ evolution (hamiltonian_sum n Hs) d"
proof (rule op_close_mono[OF b0])
have x0: "0 ≤ ¦d¦ * (real (length Hs) * L)" using mL by simp
have "(¦d¦ * (real (length Hs) * L)) ^ q * exp (¦d¦ * (real (length Hs) * L))
≤ (total_weight L F * ¦d¦) ^ q * exp (total_weight L F * ¦d¦)"
by (rule mult_mono[OF power_mono[OF le x0]]) (use le order_trans[OF x0 le] in simp_all)
thus "(¦d¦ * (real (length Hs) * L)) ^ q * exp (¦d¦ * (real (length Hs) * L)) / fact q
≤ (total_weight L F * ¦d¦) ^ q * exp (total_weight L F * ¦d¦) / fact q"
by (rule divide_right_mono) simp
qed
show ?thesis
using op_close_trans[OF a b conjunct1[OF formula_product_carrier_unitary[OF F]] exp_taylor_carrier[OF Hh(1)] evolution_carrier[OF Hh(1,2)]]
by (simp add: algebra_simps add_divide_distrib)
qed
text ‹Suzuki's formula of order $2k+2$ over $r$ steps:
$\norm{S_{2k+2}(t/r)^r-e^{itH}}\le r(2|F|+1)(\Lambda|t|/r)^{2k+3}e^{\Lambda|t|/r}/(2k+3)!$,
with $|F|=2\cdot5^k m$ factors and $\Lambda\ge mL$.›
theorem suzuki_error:
fixes k :: nat and t :: real
assumes Hs: "∀H ∈ set Hs. herm_bounded n L H" and L: "0 ≤ L" and r: "0 < r"
defines "F ≡ suzuki k Hs" and "q ≡ 2 * k + 3"
shows "formula_product n (t / real r) F ^⇩m r ≈⇘real r * ((2 * real (length F) + 1) * (total_weight L F * ¦t¦ / real r) ^ q
* exp (total_weight L F * ¦t¦ / real r) / fact q)⇙ evolution (hamiltonian_sum n Hs) t"
proof -
have Fh: "∀x ∈ set F. herm_bounded n L (snd x)" using Hs suzuki_snd unfolding F_def by blast
note Hh = herm_boundedD[OF hamiltonian_sum_herm_bounded[OF Hs]]
note U = formula_product_carrier_unitary[OF Fh, of "t / real r"]
have d: "total_weight L F * ¦t / real r¦ = total_weight L F * ¦t¦ / real r" using r by simp
have c: "formula_product n (t / real r) F ^⇩m r ≈⇘real r * ((2 * real (length F) + 1) * (total_weight L F * ¦t / real r¦) ^ q
* exp (total_weight L F * ¦t / real r¦) / fact q)⇙ evolution (hamiltonian_sum n Hs) (t / real r) ^⇩m r"
by (rule op_close_pow[OF conjunct1[OF U] conjunct2[OF U] evolution_carrier[OF Hh(1,2)]
evolution_unitary[OF Hh(1,2)]]) (use suzuki_step[OF Hs L, where k = k and d = "t / real r"] in ‹simp add: F_def q_def›)
have p: "evolution (hamiltonian_sum n Hs) (t / real r) ^⇩m r = evolution (hamiltonian_sum n Hs) t"
using evolution_pow[OF Hh(1,2), of "t / real r" r] r by simp
show ?thesis using c unfolding p d .
qed
end