Local Hamiltonians

The last chapter returned to Feynman's 1982 proposal and sorted the modern version into three concrete tasks: time evolution, ground-state energy, thermal sampling. Each requires a Hamiltonian H as input. Which H? That depends on the physics — the electrons of a molecule, the spins of a magnet, the electrons hopping on a lattice. And here lies the crucial structural point: every physically relevant Hamiltonian has a very specific algebraic shape. It is a sum of small pieces, each acting on only a handful of particles. That shape has a name — locality — and it is the single feature that makes the whole Part 15 algorithmic programme possible.

This chapter introduces locality carefully, writes down the five or six Hamiltonians you will meet for the rest of the track, and shows why locality is also the source of the QMA-hardness ceiling you met in chapter 98. By the end, you should be able to look at any physics Hamiltonian, say "this is k-local" for the right k, and predict whether the corresponding simulation task is easy-for-quantum or hard-even-for-quantum.

The definition, with pictures

Start with the sharpest version, before any physics.

The notation A_S \otimes I_{\bar S} is worth decoding if you are not fluent with it. Suppose you have 10 qubits and a two-local term that acts on qubits 3 and 7. You write it as the tensor product I_1 \otimes I_2 \otimes A_{3,7} \otimes I_4 \otimes \ldots, where A_{3,7} is a 4 \times 4 matrix on those two qubits and every other qubit gets the 2 \times 2 identity. Formally it is a 2^{10} \times 2^{10} matrix; structurally it is a small matrix padded with identity. That padding is what the word "local" captures.

Why the word "local" does not mean "small" or "nearby by default": in the most general definition, a 2-local term can act on any two of the n qubits, however far apart they sit in space. Electron-electron Coulomb repulsion, for instance, is 2-local in the Jordan-Wigner encoding, but the two electrons can be on opposite sides of the molecule. Geometric locality — an additional restriction that the qubits must be nearest neighbours — is a strictly stronger condition.

Two sanity checks on the definition:

• Every single-qubit term is 1-local. A magnetic field term -h Z_i acts on one qubit.
• No Hamiltonian is "0-local" in a useful sense — a 0-local term is a scalar multiple of the identity, which just shifts all eigenvalues uniformly and is physically trivial.

Why k-locality is physically universal

The genuinely surprising fact — and the one you should carry out of this chapter — is that essentially every Hamiltonian that arises in physics is k-local for k \leq 4, and most are 2-local. That is not a coincidence. It traces to the structure of the interactions nature uses.

Two-body forces. The overwhelming majority of fundamental interactions in physics are pairwise. The Coulomb force between two electrons is a two-body force. The exchange interaction between two spins is two-body. Gravity (classically) is two-body. A three-body force would require three particles to interact in a way that cannot be decomposed into pair interactions — such forces exist in nuclear physics, but they are small corrections, not the dominant term.

Short range. Most condensed-matter Hamiltonians have interactions that fall off with distance, so "next-to-nearest" terms are weaker than "nearest-neighbour" terms, which in turn are weaker than on-site terms. Dropping all terms beyond some range gives a geometrically local Hamiltonian with a controlled approximation error.

Encoding preserves locality. When you encode a molecular Hamiltonian or a lattice Hamiltonian onto qubits via Jordan-Wigner or Bravyi-Kitaev, the encoding preserves bounded locality — fermionic two-body terms become qubit 4-local (Jordan-Wigner) or O(\log n)-local (Bravyi-Kitaev), still a bounded polynomial.

Taken together: low k is what nature gives you, and what algorithm designers exploit. Feynman's Claim 3 from the last chapter — "build a quantum simulator" — becomes an efficient algorithm precisely because the Hamiltonians that matter are sums of a polynomial number of k-local terms with bounded k.

The zoo — five Hamiltonians you need to know

Here are the canonical Hamiltonians of quantum simulation, in order of increasing intricacy. For each, see what acts on what and count the locality.

1. Transverse-field Ising model (2-local)

The simplest non-trivial quantum many-body Hamiltonian:

Here \langle i,j \rangle means "over neighbouring pairs on some lattice." The first sum is the classical Ising interaction — a coupling that energetically rewards aligned spins (Z_i Z_j = +1 when the two spins agree, -1 otherwise). The second sum is the transverse field — a magnetic field in the x-direction that tries to flip each spin, adding quantum fluctuation.

Locality: 2-local (the ZZ terms) and 1-local (the X terms). Number of terms: M = O(n) — one X per site, one ZZ per bond. Physics: undergoes a quantum phase transition at h/J = 1 between a ferromagnetic phase (large J) and a paramagnetic phase (large h). A benchmark problem for quantum simulation; widely used as a VQE target.

2. Heisenberg model (2-local)

Spin interactions isotropic in all three directions:

Locality: 2-local. Physics: describes quantum magnets. The 1D antiferromagnetic Heisenberg chain (solved by Bethe in 1931) is a textbook integrable system; the 2D version on a triangular or kagome lattice is a hotbed of research on quantum spin liquids. Variants: XXZ (two couplings), XY (drop the Z term), all still 2-local.

3. Hubbard model (fermionic, 4-local in qubits)

Electrons on a lattice, hopping and interacting:

The first sum (kinetic) lets an electron hop from site j to site i if both sites have room; "h.c." is Hermitian conjugate (the reverse hop). The second sum (on-site repulsion) penalises having two electrons of opposite spin on the same site; n_{i\sigma} = c_{i\sigma}^\dagger c_{i\sigma} is the number operator.

Locality in fermionic form: 2-local — every term involves at most two sites. Locality in qubits (via Jordan-Wigner): the kinetic term becomes c_i^\dagger c_j = \frac{1}{2}(X_i X_j + Y_i Y_j) \prod_{k\text{ between }i,j} Z_k. The Z string is the Jordan-Wigner tail; for nearest neighbours it reduces to k=2 with the right labelling, but for non-nearest pairs it spans the qubits between. For practical locality on a 2D lattice: 4-local after encoding. Physics: at half-filling, undergoes a Mott metal-to-insulator transition. The 2D Hubbard model near half-filling is the minimal model for high-T_c superconductivity — and classically unsolved.

4. Molecular electronic Hamiltonian (4-local in qubits)

The Hamiltonian of electrons in a molecule, which is what quantum chemistry is about:

t_{pq} are one-electron integrals (kinetic energy plus nuclear attraction; computed classically from the chosen orbital basis), and V_{pqrs} are two-electron integrals (Coulomb repulsion between orbitals).

Locality in qubits (Jordan-Wigner): 4-local (the two-electron terms involve four fermionic operators). Number of terms: O(n^4) where n is the number of spin-orbitals. Physics: the whole of quantum chemistry. Binding energies, reaction barriers, drug-target affinities.

5. Lattice gauge theories (k-local for small k)

High-energy physics' non-perturbative tool. A gauge theory on a lattice discretises spacetime and places fields on links and matter on sites. For \mathrm{U}(1) and \mathrm{SU}(N) gauge groups, the Kogut-Susskind Hamiltonian splits into plaquette terms (4 links around a square), link terms, and matter terms — all k-local with k \leq 4. Simulating lattice QCD at non-zero chemical potential is the long-term target, unreachable by classical Monte Carlo because of the sign problem.

Everything from here on in Part 15 is about running algorithms on Hamiltonians from this zoo — or small generalisations of them.

Why locality makes simulation efficient

The single-most important fact about a k-local Hamiltonian, operationally, is that each individual term e^{-i h_i t} can be implemented as a constant-size quantum circuit. Each h_i acts on at most k qubits, so e^{-ih_i t} is a 2^k \times 2^k unitary — a matrix of size at most 16 (for k=4). Any 2^k \times 2^k unitary can be decomposed into O(4^k) one- and two-qubit elementary gates by the Solovay-Kitaev theorem. For bounded k, this is a constant gate count per term.

Then Lloyd 1996 [2] tells you how to stitch the pieces together. For a time-t evolution under H = \sum_{i=1}^M h_i:

for large enough r (the number of Trotter steps). This is the first-order Trotter-Suzuki approximation. Each Trotter step costs M bounded-size unitaries. The total gate count is O(M \cdot r), with r = O(M \cdot t^2 / \epsilon) chosen to keep the error bounded by \epsilon. Plugging in:

Why this is polynomial: M is polynomial in n (each term acts on k of n qubits, and there are at most \binom{n}{k} = O(n^k) such terms; for physical Hamiltonians often M = O(n) or O(n^2)). t and 1/\epsilon are inputs. So the total gate count is polynomial in n, t, and 1/\epsilon — efficient in every parameter. A classical simulation would need to store and update 2^n amplitudes — exponential in n. This is the Feynman-Lloyd efficient-simulation theorem.

Higher-order Trotter schemes (Suzuki 1991) and later algorithms (LCU, QSP, qubitisation — chapter 132) improve the scaling further, but the basic insight comes from locality: if you can simulate each h_i in constant time, you can simulate the sum in polynomial time. Strip locality and everything breaks — an arbitrary 2^n \times 2^n unitary has 4^n free parameters, and no finite circuit can realise it in general.

Why locality still makes ground-state finding hard

Now the negative side. Deciding the ground-state energy of a general k-local Hamiltonian is QMA-complete (chapter 98). Kitaev's 1999 theorem, plus later tightenings:

This is a deep result, and it shapes the whole algorithmic landscape. The consequence, in one sentence: no efficient quantum algorithm can solve the ground-state problem in full generality, unless QMA collapses into BQP — an unlikely-but-open complexity assumption.

What can a quantum algorithm do? Approximate, heuristically, or under extra structural assumptions:

Phase estimation. Works if you can prepare a state with non-negligible overlap with the true ground state. The overlap preparation is the hard part.

Variational Quantum Eigensolver (VQE). Gives an upper bound on E_0 by minimising \langle \psi(\vec\theta)|H|\psi(\vec\theta)\rangle over parameters \vec\theta in a chosen circuit ansatz. The bound is tight only if the ansatz is expressive enough — which, for strongly correlated systems, is an open problem.

Adiabatic preparation. Start with a trivial ground state (say, all |+\rangle), slowly turn on the full Hamiltonian. If you evolve slowly enough, the system stays in its ground state. "Slowly enough" means a time inversely proportional to the smallest spectral gap encountered along the way. For Hamiltonians with gapless points, this is expensive.

Imaginary-time evolution. Apply e^{-\tau H} for large \tau to any state with ground-state overlap, and what comes out is proportional to the ground state. Implementing e^{-\tau H} directly is non-unitary and tricky, but it can be approximated.

The practical art of quantum chemistry on quantum computers is choosing which of these routes to combine, which structure to exploit, and which hardware constraints to respect. Locality is the feature that makes this field exist; QMA-completeness is the feature that prevents it from being easy.

Examples — write these down

Common confusions

• "k-local means k total qubits." No — the k refers to how many qubits any single term touches. A 2-local Hamiltonian on 100 qubits has many terms, but each term touches at most 2 of the 100. The total system size is unrelated to k.

• "Locality of the Hamiltonian equals physical locality." Not quite. A Hamiltonian is k-local if each term acts on at most k qubits, anywhere in the system. It is geometrically local if additionally the qubits touched by each term are spatially near each other on some lattice or graph. Molecular electronic Hamiltonians are 4-local (algebraically) but not geometrically local — two electrons at opposite ends of a molecule still interact via Coulomb repulsion. Hubbard models are geometrically 2-local (after fermion encoding) because the kinetic term couples nearest neighbours only.

• "Ground-state finding is easy because the Hamiltonian is local." Exactly backwards. Locality makes dynamics easy (Trotter works). Ground-state finding is QMA-complete even for 2-local Hamiltonians — locality is not what you need to find a ground state efficiently; you'd need much stronger structure (a gap, a spectral signature, a good starting state).

• "If H is k-local, then H^2 is k-local too." No. Squaring generates cross-terms that touch more qubits. For a 2-local H, H^2 is 4-local in general. This matters when you want to compute variance \langle H^2\rangle - \langle H\rangle^2 on a quantum computer: you need to decompose H^2 into k-local pieces, and k grows.

• "The Hubbard model is 2-local, so it's easy." Qualified yes and no. In fermionic language the Hubbard model is 2-local. After Jordan-Wigner encoding on a 2D lattice, it becomes up to 4-local (because of the Z-string tails). Simulation is efficient by Lloyd's theorem — but the 2D Hubbard ground state remains classically intractable, and its phase diagram near half-filling is the most-studied open problem in condensed-matter physics.

• "Locality is purely mathematical and has nothing to do with physics." In fact the opposite — locality is because of physics. The fundamental interactions of nature are short-range and pairwise, so Hamiltonians derived from them are k-local with small k. If nature had many-body long-range interactions at every scale, classical and quantum simulation would both be much harder.

Going deeper

Kitaev's proof of QMA-completeness

Kitaev's 1999 proof that local Hamiltonian is QMA-complete is one of the beautiful theorems of quantum complexity. The construction — called the history-state construction — takes any quantum verification circuit V with T gates and builds a 5-local Hamiltonian H_V on roughly O(T + n) qubits whose ground state encodes the full history of the circuit's computation:

The clock register tracks the time step; the data register holds the state after applying the first t gates. The Hamiltonian H_V has pieces that penalise the state's deviation from this history form, with an extra piece that penalises "end-of-computation state is a rejecting state." The ground-state energy is low iff there is a witness |\psi\rangle that V accepts — exactly the QMA acceptance condition. Thus k-local Hamiltonian is QMA-hard for k=5. Kempe-Kitaev-Regev 2006 tightened to k=2 via "perturbation gadgets." Oliveira-Terhal 2008 showed even geometrically 2-local on a 2D lattice is QMA-complete.

This is the quantum Cook-Levin theorem. See chapter 98 for the full treatment.

Fermion encodings in detail

The Jordan-Wigner encoding represents n fermionic modes with n qubits. The mapping:

The \prod Z string — the Jordan-Wigner string — enforces fermionic anti-commutation. Every two-body fermionic term c_i^\dagger c_j picks up a string of Pauli-Z operators on the qubits between i and j. For neighbouring modes on a 1D lattice, this is a string of length 1 (trivial), and the two-body term becomes genuinely 2-local. For non-neighbouring modes — or for 2D and 3D lattices where the linear qubit ordering does not match the physical geometry — the string can be long, making the qubit term O(n)-local in the worst case.

Bravyi-Kitaev encoding addresses this by ordering qubits on a binary tree and redefining the creation/annihilation operators. Each fermionic operator becomes a product of O(\log n) Paulis instead of O(n). The cost is algebraic intricacy; the payoff is lower-depth circuits for large molecules. Modern chemistry-quantum-computing packages (OpenFermion, Qiskit Nature) support both.

Trotter-Suzuki hierarchy

The first-order Trotter formula e^{-iHt} \approx \prod_i e^{-ih_i t/r} has error O(t^2/r) per step, so error \epsilon requires r = O(t^2/\epsilon). Suzuki 1991 introduced higher-order formulas: a fourth-order Suzuki formula has error O(t^5/r^4) per step, so error \epsilon requires r = O(t^{5/4} / \epsilon^{1/4}) — much better scaling in \epsilon, at the cost of more gates per step (5 fractional time-steps per Trotter step at fourth order). For precision targets like chemical accuracy (\epsilon \sim 10^{-3} Hartree), higher-order Trotter is almost always faster.

Post-Trotter methods — linear combinations of unitaries (Berry et al. 2015), qubitisation (Low-Chuang 2017) — achieve optimal scaling O(t + \log(1/\epsilon)) using different tricks. Chapter 132 treats these.

DFT and local potentials

Density Functional Theory, the classical chemistry workhorse, famously sidesteps the k-local Hamiltonian problem by reformulating ground-state finding as a variational problem over the electron density rather than the wavefunction. Hohenberg-Kohn 1964 proved that the ground-state energy is a functional of the density alone. Kohn-Sham 1965 recast this as a self-consistent single-particle problem — the "Kohn-Sham equations" — with a local exchange-correlation potential v_{xc}(\vec r). DFT is efficient because the Kohn-Sham problem is effectively a system of non-interacting electrons in a local potential; but it is only as accurate as the approximation used for v_{xc}.

DFT's locality is different from the k-locality of the Hamiltonian. The Hamiltonian H has interaction terms that are 4-local in qubits; Kohn-Sham replaces them with a 1-local effective Hamiltonian where the electron-electron interaction has been folded into a local potential. The approximation is excellent for many systems, poor for systems with strong correlation. Quantum algorithms for chemistry come back to the original k-local form and solve it without the Kohn-Sham approximation.

Indian research on k-local Hamiltonian models

TIFR's condensed-matter theory group (led historically by T. V. Ramakrishnan and currently by several researchers including G. Baskaran) has worked for decades on Hubbard-like models, including the resonating-valence-bond scenario for high-T_c superconductivity — directly relevant to the quantum simulation goals of Part 15. IISc Bangalore's quantum chemistry group (Mukhopadhyay et al.) has published on VQE benchmarks for small molecules. HRI Allahabad and Raman Research Institute host theoretical quantum-information groups with papers on QMA-completeness variants. The zoo of k-local Hamiltonians is central to Indian theoretical physics, not peripheral.

Where this leads next

• Feynman Revisited — chapter 129, the motivation for simulating Hamiltonians in the first place.
• Trotter-Suzuki Decomposition — chapter 131, the first algorithm for e^{-iHt} given a k-local H.
• Variational Quantum Eigensolver — chapter 133, the near-term route to ground-state energies.
• QMA and the Quantum Cook-Levin Theorem — chapter 98, the proof that local Hamiltonian is QMA-complete.
• Quantum Chemistry Introduction — Part 15.3, the molecular-Hamiltonian workflow.

References

1. Kitaev, Shen, Vyalyi, Classical and Quantum Computation — American Mathematical Society.
2. Seth Lloyd, Universal Quantum Simulators, Science (1996) — DOI:10.1126/science.273.5278.1073.
3. Wikipedia, Local Hamiltonian problem.
4. John Preskill, Lecture Notes on Quantum Computation, Chapter 5 — theory.caltech.edu/~preskill/ph229.
5. McClean, Romero, Babbush, Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms (2016) — arXiv:1509.04279.
6. Nielsen and Chuang, Quantum Computation and Quantum Information, §4.7 — Cambridge University Press.