I am reading a paper titled : Efficient quantum algorithms for simulating sparse Hamiltonians available here. (I am considering pages 2-3)
Define $S_{2k}(\lambda) = \prod_{j=1}^{m}e^{H_j \lambda /2}\prod_{j'=m}^{1}e^{H_j' \lambda /2}$ for $k=1$ and matrices $H_1, \ldots, H_m$, and for $k>1$,
$S_{2k}(\lambda) = [S_{2k-2}(p_k\lambda)]^2[S_{2k-2}((1-p_k)\lambda)][S_{2k-2}(p_k\lambda)]^2$ where $p_k = (4 - 4^{1/(2k-1)})^{-1}$.
The author states without proof that $S_{2k} (\lambda)$ consists of a product of $2(m-1)5^{k-1}+1$ exponentials. This expression seems mysterious to me.
For instance if $k=1$, then we have a product of $2m$ exponentials, whereas if $k=1$, the stated formula $2(m-1)5^0+1=2m-1$.
Ok, well how about $k=2$, then I think we should have according to the recursive formula $2(2m-1) + (2m-1) + 2(2m-1) = 5(2m-1) = 10m-5$ exponentials, whereas for $k=2$, the stated formula gives $2(m-1)5 + 1 = 10m-9$, clearly not equal.
I must be confusing something here, any insights appreciated.
Edit: Given that a matrix $A$ commutes with itself, it seems the author has taken the liberty of simplifying an expression $e^{A}e^{A} = e^{2A}$, and counted this as $1$ exponential. I'm still not sure how the overall recursive expression is generated and any help would be appreciated.
Some of the exponentials are lost because they get absorbed into other exponentials.
For example, for $k=1$:
$S_2(\lambda)=e^{H_1\frac{\lambda}{2}}...e^{H_m\frac{\lambda}{2}}e^{H_m\frac{\lambda}{2}}...e^{H_1\frac{\lambda}{2}}=e^{H_1\frac{\lambda}{2}}...e^{H_m\lambda}...e^{H_1\frac{\lambda}{2}}$
and thus the final count is indeed $2m-1$ exponentials. Every time two operators are multiplied, if the beginning of the rightmost bears the same hamiltonian as the ending of the first, then you must count one less exponential, because they collapse into one.
For general k, notice that the recursion relation requires that if the operator $S_{2(k-1)}$ contains $N_{k-1}$ exponentials, then the operator $S_{2k}$ contains $5N_{k-1}-4$ exponentials given that in the recursion defining it, there are 4 multiplications of operators that fulfill the aforementioned properties, and thus each "collision" destroys an exponential due to coincidence (and there are 4 operator "collisions"). We obtain the recursion for the number of exponentials contained in the string operator:
$$N_k=5N_{k-1}-4$$
which is solved by
$$N_k=5^{k-1}N_1-4\sum_{i=0}^{k-2}5^i=5^{k-1}(N_1-1)+1$$
which, since we showed already that $N_1=2m-1$, returns the number of exponentials quoted by the authors.