= Solution
Each summand of $J_X$ acts on one <qubit>, while each summand $Z_iZ_j$ of $J_Z$ acts on two. Therefore $J=J_X+J_Z$ is a <k-local Hamiltonian>[2-local Hamiltonian]. We have
$$
\|J_X\|=O(n),
\qquad
\|J_Z\|\leq\binom n2=O(n^2).
$$
Split $t$ into $r$ steps of length $\delta=t/r$ and use the <second-order product formula>
$$
S_2(\delta)=
e^{-i\delta J_X/2}e^{-i\delta J_Z}e^{-i\delta J_X/2}.
$$
For one step, $\Lambda=O(\delta n^2)$ in the stated estimate, so the <spectral norm>[spectral-norm error] is $O(\delta^3n^6)$. The error bound for a product of <unitary operators> makes the total error
$$
O(r\delta^3n^6)=O\left(\frac{n^6t^3}{r^2}\right).
$$
It is therefore enough to choose
$$
r=O\left(\frac{n^3t^{3/2}}{\sqrt\epsilon}\right),
$$
with $r$ also large enough that the small-step estimate applies.
All $Z_iZ_j$ terms <commuting operators>[commute]. A factor $e^{-i\delta Z_iZ_j}$ uses a constant-size circuit of two <controlled-NOT gates> and one <phase gate>, up to a <global phase>, so one product-formula step costs $O(n^2)$ gates. The complete <Hamiltonian simulation> consequently has size
$$
\boxed{O\left(\frac{n^5t^{3/2}}{\sqrt\epsilon}\right)}.
$$
Back to article page
