CHAPTER 14

Hamiltonian simulation and modern algorithmic tools

Learning goals. Connect unitary evolution to Hamiltonians, derive a product formula, and understand the access and output assumptions behind block encoding and linear-system algorithms.

14.1 Why simulate quantum systems?

A Hamiltonian H is a Hermitian operator specifying a system’s energy and dynamics. In units with $\hbar=1$,

$$i\frac{d}{dt}|\psi(t)\rangle=H|\psi(t)\rangle,\qquad |\psi(t)\rangle=e^{-iHt}|\psi(0)\rangle$$

for time-independent H. Simulating such evolution is a natural quantum-computing task because the target itself has quantum structure. But “simulate a molecule” still needs a precise model: orbitals, truncation, initial state, desired observable, accuracy, and classical benchmark.

For n qubits, a Hamiltonian can be expanded in Pauli strings: $H=\sum_\ell h_\ell P_\ell$, with real coefficients for Hermitian H. A Pauli string is a tensor product of I,X,Y,Z. Since $P_\ell^2=I$,

$$e^{-ih_\ell P_\ell t} =I\cos(h_\ell t)-iP_\ell\sin(h_\ell t).$$

Basis rotations and parity-computing circuits can implement these individual terms. For a Z-string, CNOTs compute parity into a target, an $R_z$ applies the phase, and reversed CNOTs uncompute the parity.

14.2 Product formulas and their error

If A and B commute, $e^{-i(A+B)t}=e^{-iAt}e^{-iBt}$. Otherwise the equality generally fails. Expand each side for a small step δ:

$$e^{-i(A+B)\delta} =I-i(A+B)\delta-\tfrac12(A^2+AB+BA+B^2)\delta^2+\cdots,$$ $$e^{-iA\delta}e^{-iB\delta} =I-i(A+B)\delta-\left(\tfrac12A^2+AB+\tfrac12B^2\right)\delta^2+\cdots.$$

The difference is proportional to $[A,B]\delta^2/2$. Repeating r steps of size t/r gives a first-order product-formula error with typical bound scaling $O(t^2\|[A,B]\|/r)$ for bounded operators. A symmetric step $e^{-iA\delta/2}e^{-iB\delta}e^{-iA\delta/2}$ cancels leading asymmetry and improves the order under appropriate assumptions [21, 22].

Worked two-term model. Let $H=X+Z$. Because XZ+ZX=0,

$$H^2=X^2+XZ+ZX+Z^2=2I.$$

Therefore

$$e^{-iHt}=\cos(\sqrt2t)I- i\frac{\sin(\sqrt2t)}{\sqrt2}(X+Z).$$

Acting on $|0\rangle$ gives amplitudes $\cos(\sqrt2t)-i\sin(\sqrt2t)/\sqrt2$ and $-i\sin(\sqrt2t)/\sqrt2$. This exact solution is a useful check on an approximate simulator.

14.3 Energies through phase estimation

For an energy eigenstate $H|E\rangle=E|E\rangle$, $e^{-iHt}|E\rangle=e^{-iEt}|E\rangle$. Phase estimation can infer E after accounting for sign, time, and periodic ambiguity. Preparing a state with sufficient overlap on the desired eigenstate can be as important as simulating evolution. A precise phase estimate of the wrong eigenstate is not a successful ground-state calculation.

The full resource budget combines model error, state-preparation error, Hamiltonian-simulation error, phase-estimation error, and sampling or confidence requirements. Giving every component the entire error tolerance is invalid; the errors must be combined or budgeted with a justified bound.

14.4 Block encoding: matrices inside unitaries

An arbitrary matrix A is not usually unitary, so it cannot simply be applied as a deterministic closed-system gate. A block encoding embeds $A/\alpha$ into a larger unitary U:

$$(\langle0^a|\otimes I)\,U\,(|0^a\rangle\otimes I)=A/\alpha.$$

Here α≥‖A‖ is a normalization and a is the ancilla count. Other blocks make the complete matrix unitary. Postselecting the ancillas on zero applies the desired block with a state-dependent probability; that probability and the cost of constructing U must be counted.

For a sum $A=\sum_\ell a_\ell U_\ell$ of unitaries, one can prepare an index superposition weighted by $\sqrt{|a_\ell|/\alpha}$, apply a selected $U_\ell$ with its sign or phase, and unprepare the index. This illustrates how a matrix’s representation determines its access cost.

Quantum signal processing and quantum singular value transformation use structured sequences of such unitaries, reflections, and phase rotations to transform eigenvalues or singular values by controlled polynomials. The required polynomial must satisfy boundedness and parity constraints, and its degree controls query cost. These methods unify important simulation, search, and linear-algebra algorithms; they do not provide arbitrary matrix functions for free [23, 24].

14.5 Linear systems and input-output restrictions

For $A|x\rangle\propto|b\rangle$, a quantum linear-system algorithm aims to prepare a state proportional to $A^{-1}|b\rangle$. In A’s eigenbasis, inversion multiplies coefficient $b_j$ by $1/\lambda_j$. Small eigenvalues cause large amplification, making the condition number κ an essential parameter [25].

The output is a quantum state, not a printed list of every component of a classical solution vector. Extracting all N entries generally removes the advertised logarithmic dependence on N. Promising use cases specify efficient access to A and b, suitable conditioning, and an output observable obtainable with limited measurements.

A classical comparison must receive comparable data access. Sampling access, sparse-entry oracles, low-rank structure, and preprocessed data can also enable powerful classical algorithms. A quantum linear-algebra primitive is a starting point for an application analysis, not a completed speedup claim.

14.6 Amplitude estimation and learning

Amplitude estimation combines amplification with phase information to estimate a success probability. Ideal coherent-query algorithms can improve the scaling with additive precision from the ordinary sampling $O(1/\epsilon^2)$ to $O(1/\epsilon)$ under appropriate access and success guarantees [16]. The improvement trades repeated shallow sampling for coherent operations, inverses, or more elaborate schedules. Noisy hardware can change that trade.

Quantum machine learning includes learning quantum data, quantum feature maps, and variational models. Loading classical data, generalization, training stability, and classical baselines are separate questions. An exponentially large Hilbert space alone proves no learning advantage. Strong results are task-specific; broad superiority on ordinary classical datasets remains an open question in this introductory scope [26].

14.7 Exercises