= Solution
For <first-order two-local Hamiltonian simulation>, regard each term $H_k$ as a <Hermitian operator>, as is standard for a local-Hamiltonian decomposition. The <Lie-Trotter product formula> for bounded operators states
$$
e^{\sum_k A_k}=\lim_{r\to\infty}\left(e^{A_M/r}\cdots e^{A_1/r}\right)^r
$$
in <operator norm>; the reversed factor ordering is just as valid as the displayed one. Take $A_k=-iH_k$ and use the circuit
$$
V_r=\left(e^{-iH_M/r}\cdots e^{-iH_1/r}\right)^r.
$$
Each factor is a <unitary operator> on at most two <qubits> and hence is one allowed two-<qubit> gate, with a spectator identity for a one-<qubit> term. The factors in the rightmost part of each written product act first. Merely quoting the limit would not establish the requested rate, so we give a quantitative error bound.
For two <Hermitian operators> $A,B$ and $t\geq0$, differentiating
$$
F(s)=e^{-i(t-s)(A+B)}e^{-isA}e^{-isB},\qquad0\leq s\leq t,
$$
gives $F'(s)=i e^{-i(t-s)(A+B)}[B,e^{-isA}]e^{-isB}$. The <commutator> identity obtained by differentiating $e^{iuA}Be^{-iuA}$ implies $\|[B,e^{-isA}]\|\leq s\|[A,B]\|$. Since the surrounding factors are unitary, integration yields the <first-order unitary product-formula error bound>
$$
\|e^{-it(A+B)}-e^{-itA}e^{-itB}\|\leq\frac{t^2}{2}\|[A,B]\|.
$$
Splitting the terms successively and using the triangle inequality therefore gives the one-step estimate
$$
\left\|e^{-iH/r}-e^{-iH_M/r}\cdots e^{-iH_1/r}\right\|
\leq\frac1{2r^2}\sum_{k<\ell}\|[H_k,H_\ell]\|
<\frac{M(M-1)}{2r^2},
$$
for $M>1$. Here <submultiplicativity of the operator norm> gives $\|[H_k,H_\ell]\|\leq2\|H_k\|\|H_\ell\|<2$. The ordering chosen for the products changes the sign of local commutators, not this norm bound. Applying part (i) to the $r$ steps gives
$$
\boxed{\|e^{-iH}-V_r\|\leq\frac1{2r}\sum_{k<\ell}\|[H_k,H_\ell]\|
<\frac{M(M-1)}{2r}.}
$$
Choose $r=\max(1,\lceil M(M-1)/(2\epsilon)\rceil)$. For $M>1$ the error is strictly below $\epsilon$; $M=1$ is exact already with $r=1$. The <quantum circuit> contains $Mr$ two-<qubit> gates. \b[A sufficient gate count is]
$$
\boxed{Mr=O\!\left(M+\frac{M^3}{\epsilon}\right)
=O\!\left(\frac{n^6}{\epsilon}\right),\qquad0<\epsilon\leq1.}
$$
Thus the worst-case polynomial degree in this first-order bound is six. Terms with disjoint supports commute and may improve the count in particular decompositions, but the stated assumptions alone suffice for this bound, without a further sparsity or bounded-degree condition. The requested gate model allows arbitrary two-<qubit> unitaries, so no additional compilation error is incurred here.
Back to article page
