Hamiltonian simulation

Hamiltonian simulation constructs a quantum circuit approximating the time-evolution operator $e^{-itH}$ generated by a Hamiltonian operator $H$, with cost controlled by the evolution time, requested precision, and structure of $H$.

If $H={\sum }_j{h}_j$ and all local terms commute, thenexactly. Approximating each fixed-size factor to error at most $\epsilon /m$ and applying the telescoping bound for products of operators gives total operator norm error at most $\epsilon$.

A local Hamiltonian is a sum of terms, each acting nontrivially on only a bounded number of subsystems.

The operator support is the set of subsystems on which an operator may act nontrivially; it acts as the identity outside that set. Unitary time evolution can enlarge the support, while a Lieb-Robinson bound controls the error of replacing the evolved operator by one with smaller support. The support diameter and the number of sites in the support are different quantities.

A stoquastic Hamiltonian is a real Hermitian Hamiltonian operator with nonpositive off-diagonal entries in a specified basis, usually the computational basis. The property depends on that basis. Permutation matrices in a quantum circuit's propagation terms and $|-⟩⟨-|$ input penalties give a useful family of such operators.

A real nonnegative normalized filter $w$ defines $g_Z=\int w(t)e^{itH}{h}_Z{e}^{-itH}dt$. In an energy eigenbasis, it multiplies each matrix element by $\hat{w}(E_i-E_j)$. A Fourier cutoff at the spectral gap removes couplings between a unique ground state and excitations. The filtered terms still sum to $H$, because the total Hamiltonian is unchanged by its own unitary time evolution. Each term commutes with the ground projector, but need not be minimized there.

In a telescoping local-shell decomposition, split the spectral filter integral at a time proportional to the shell distance. A Lieb-Robinson bound controls short times, while the two-sided almost-exponential spectral filter tail controls long times. Polynomial shell-weight growth then gives the displayed decay. The estimate is asymptotic at large distance; small shells retain the elementary operator-norm bound. The evenization of a nonnegative bandlimited filter can supply the two-sided tail from a one-sided existence statement.

If each local term is already minimized by the global ground state, subtract its minimum $a_Z$ to obtain a positive operator. Nonnegative normalized spectral filtering of Hamiltonian terms preserves positivity and leaves the ground eigenvalue $a_Z$ unchanged. Thus the same state minimizes every filtered term. This preserves frustration freeness but does not create it for an initially frustrated decomposition.

The condition $[g_Z,P_0]=0$ makes a unique global ground state an eigenvector of every filtered term, but its termwise eigenvalues can exceed the corresponding minima. For example $h_{12}=|1⟩⟨1{|}_1+|0⟩⟨0{|}_2$ and $h_{23}=|1⟩⟨1{|}_3+2|1⟩⟨1{|}_2$ commute with their sum. Their sum is uniquely minimized by $|000⟩$, yet $h_{12}$ is lower on $|010⟩$. Filtering leaves these commuting terms unchanged, so it cannot force frustration freeness.

Filter a fixed local term using a nested sequence of neighbourhood Hamiltonians $H_s$, and call the results $G_s$. The differences $G_s-G_{s-1}$ give a shell decomposition. When $H_0=h_Z$ and $H_D=H$, normalization gives $G_0=h_Z$ and telescoping gives $g_Z=h_Z+{\sum }_{s=1}^D(G_s-G_{s-1})$. Individual shell terms need not commute with the full ground projector.

Given a polynomial list of fixed-locality Hermitian terms and thresholds $a<b$ separated by at least an inverse polynomial, distinguish whether the minimum eigenvalue of their sum is at most $a$ or at least $b$. Terms may be normalized to $0\le h_j\le I$ with polynomial rescaling. This promise problem is in QMA by local-energy measurement verification.

Uniformly sample one positive local term and measure the effect $h_j$. The averaged energy-flag effect on a witness is $H/M$, where $M$ is the number of terms. Repetition with a threshold halfway between the promised flag probabilities uses $O(M^2/(b-a{)}^2)$ witness registers for constant error. A spectral tensor-product analysis, as in QMA parallel repetition with entangled witnesses, proves soundness against entangled witnesses. Constant-locality positive operator-valued measures are efficiently implementable using one ancilla qubit.

A diagonal Hamiltonian is diagonal in a specified product basis, usually the computational basis. Every basis state is therefore an energy eigenstate, and optimization of its diagonal entries becomes minimization of the corresponding classical cost function.

A quantum Hamiltonian $H={\sum }_j{h}_j$ with positive-semidefinite local terms is frustration free when one state minimizes every $h_j$ simultaneously. After shifting each local minimum to zero, that state lies in every kernel $\ker h_j$ and has zero total energy.

In a nearest-neighbour frustration-free Hamiltonian chain, multiply the bond orthogonal projections in two disjoint alternating layers. The resulting product $K$ fixes the common ground state space but contracts its orthogonal complement by a factor bounded away from one in terms of the spectral gap. A bound $\Vert K{|}_{\mathrm{supp}H}\Vert \le (1+\Delta /2{)}^{-1/3}$ implies exponentially convergent powers. The product is generally neither Hermitian nor normal.

To evaluate a layered product on $A_x|{\psi }_0⟩$, scan the bond orthogonal projections from right to left. A projection disjoint from the current support commutes through the accumulated operator and disappears against the common ground state. Retained projections expand the support by at most one site per layer. Their product $L$ gives a local operator $L{A}_x$ with both $K^r{A}_x|{\psi }_0⟩=L{A}_x|{\psi }_0⟩$ and $⟨{\psi }_0|L{A}_x=⟨{\psi }_0|A_x$.

Combine a local projector cone in a frustration-free chain with the contraction bound from the detectability lemma. If the localized operator misses a second observable's support, their commutation and the exact ground-state bra identity convert the connected correlation function into an approximation error. The two-projection power estimate yields spatial decay rate $\alpha =\frac{1}{3}\ln (1+\Delta /2)$ for the stated detectability contraction.

A decomposition $H={\sum }_Z{h}_Z$ has frustration freeness when a global ground state minimizes every term simultaneously. For finite-dimensional Hermitian terms this implies $E_0(H)={\sum }_Z{E}_0(h_Z)$. Shifting each term by its minimum produces positive operators with a common null vector. The property depends on the decomposition, not only the total operator.

A $k$-local Hamiltonian is a sum of terms that each act nontrivially on at most $k$ subsystems. The integer $k$ remains fixed as the system size grows.

Product-formula Hamiltonian simulation approximates $e^{-it(A+B)}$ by alternating exponentials of $A$ and $B$, which are assumed easier to implement separately.

For a sum of $M$ Hermitian two-local terms of norm below one, repeat a first-order Lie-Trotter product formula step $r$ times. The first-order unitary product-formula error bound gives total error at most $t^2{\sum }_{j<k}\Vert [H_j,H_k]\Vert /(2r)<M(M-1)t^2/(2r)$ for $M>1$. Taking $r=\max (1,\lceil M(M-1)t^2/(2ϵ)\rceil )$ uses $Mr$ arbitrary two-qubit gates. At unit time and $M=O(n^2)$ this is a sufficient $O(n^6/ϵ)$ bound; additional commutation structure can improve it.

The symmetric second-order formula, also called Strang splitting, isfor bounded operators, with the constant controlled by nested commutators.

Let $A|x⟩=a(x)|x⟩$, where a reversible circuit $C$ computes $a(x)$ into a clean register. Then applying $e^{-ita(x)}$ as a phase on that register and performing uncomputation implements $e^{-itA}$ on the data register. For $a(x)=(-1{)}^{f(x)}$, a Boolean output qubit suffices: $C^{†}(I\otimes e^{-itZ})C$ acts as $e^{-itA}$ when that qubit starts in $|0⟩$. This exact construction avoids a Lie-Trotter product formula because the eigenvalue is computed directly.

The Pauli Z gates give eigenvalue $(-1{)}^{{\sum }_j{x}_j}$ on $|x⟩$. Use parity computation by CNOT gates to put the parity bit in a zero ancilla, apply $e^{itZ}$ to it, and uncompute. The data acquire exactly $e^{it(-1{)}^{{\sum }_j{x}_j}}$, and the ancillary line returns to zero. This compute-phase-uncompute construction needs $2n+1$ one- and two-qubit gates. Accumulating parity into the last data line instead uses $2n-1$ gates without an extra ancilla. Neither implementation drops the global phase.