by Ben Edelman
This is the first installment of a threepart series of posts on quantum Hamiltonian complexity based on lectures given by the authors in Boaz and Tselil’s seminar. The second installment is here, and the third installment is here.
Quantum Hamiltonian complexity is a growing area of study that has important ramifications for both physics and computation. Our hope is that these three posts will provide an accessible (and incomplete) preview of the subject for readers who know the basics of theoretical computer science and quantum information. Much of the material is adapted from an excellent survey by Gharibian et al..
In a nutshell, quantum Hamiltonian complexity is the study of the local Hamiltonian problem. Why is this problem important enough to justify the existence of an entire subfield? To illustrate why, here are two informal characterizations of it:
 To a physicist, the local Hamiltonian problem is a formalization of the difficulty of simulating and understanding manyparticle quantum systems. There are deep connections between the complexity of this problem and the amount of quantum entanglement in a system. In practical terms, physicists would love to be able to solve this problem on a regular basis, and they’ve developed a rich theory of heuristics to that end.
 To a computer scientist, the local Hamiltonian problem is the quantum version of constraint satisfaction problems. Any CSP can be written as a local Hamiltonian problem; and just as constraint satisfaction is the prototypical NPcomplete problem by the CookLevin theorem, the local Hamiltonian problem plays the equivalent role for QMA (a quantum analogue of NP) by the “quantum CookLevin theorem.” The connections to classical complexity go on… there is even a quantum PCP conjecture!
But let’s take a step back and start at the beginning. To make sure we understand what a quantum Hamiltonian is and why it is important, it will be instructive to briefly rehash some of the fundamentals of classical statistical mechanics.
Classical energy and ground states
In the classical world, a physical system can be in any one of various states , each of which is a vector, with different coordinates representing different particles. Every state of the system has an energy, given by an energy function . For example, in the classic Ising model of ferromagnetism, . Each coordinate represents the spin of atom , and atoms and interact with each other whenever is an edge in a graph , which is usually a lowdimensional lattice. Energy for this system is defined as .
Suppose we ignore our system for a long time, letting it interact with its external environment until, in the limit, it reaches thermal equilibrium at temperature . Then the probability the system is in state is given by Boltzmann’s distribution: , where and is the partition function required to normalize the probabilities. As the temperature tends to infinity, this distribution will approach the uniform distribution over , and as the temperature tends to absolute zero, the distribution will approach the uniform distribution over the states with minimum energy. We call these minimum energy states ground states, and we call their energy the ground state energy. If we want to calculate something about a system, then it is often crucial to know the ground states and ground state energy of the system. Going back to our example, the Ising model has two ground states whenever is connected. These are the states and in which all atoms have the same spin. The ground state energy is .
Quantum Hamiltonians
A quantum Hamiltonian is essentially the quantum analogue of the classical energy function. Unlike with classical systems, when a quantum system is in a given qubit state , it doesn’t have a determinate energy. Instead, when we measure the energy, the value we obtain may be probabilistic and will correspond to one of the eigenvalues of the observable matrix for energy. This Hermitian matrix, denoted , is the quantum Hamiltonian, and just as the energy function characterizes a classical system, the Hamiltonian characterizes a quantum system. For a given eigenvector of with eigenvalue , when we measure the energy of we obtain the result with probability , and the system collapses to the state (assuming the eigenvalue has multiplicity 1). Thus, the ground state and ground state energy of a quantum system with eigenvalue are the minimum eigenvalue of and the corresponding eigenvector .
The Boltzmann distribution also has a quantum analogue. A quantum system at thermal equilibrium will be in the following mixed state: . As the temperature approaches absolute zero, will approach a superposition over the ground states.
Not only does the Hamiltonian tell us the energy of a system, it also describes the time evolution of the system (as long as it is closed). Schrödinger’s equation states that , where is Planck’s constant and is time. Thus, if a closed system is in the state at time 0, its state at time will be . Since is Hermitian, is unitary, which is another way of saying that quantum mechanical states are subject to unitary evolution.
The Local Hamiltonian problem
As we have seen, understanding the Hamiltonian of a quantum system is crucial for understanding both the system’s equilibrium behavior and its time evolution. There are a huge variety of questions physicists are interested in asking about systems, all of which boil down to questions about equilibrium behavior, time evolution, or both. There is a single problem that captures the complexity of many of these questions, in the sense that most of the questions can’t be answered without solving it. This is the problem of estimating the ground state energy of the Hamiltonian. Especially in condensed matter physics, this problem is ubiquitous.
Formally, we will study the following promise problem: (note: this will not be our final formulation)
The “Hamiltonian Problem”
Given a Hermitian matrix and nonnegative reals with ,
 If , output YES

If , output NO
One issue with this definition is that the input includes an enormous matrix. For a reasonablesized system, there’d be no use in even trying to solve this problem through classical computation, and how to deal with it in the quantum computing setting is far from obvious. Luckily, physicists have found that in reallife systems, interactions tend to be local, and if we consider the special case of local Hamiltonians, the input for the problem is of reasonable size.
A local Hamiltonian is a Hamiltonian that is decomposed into a sum of terms, each of which represents a Hamiltonian acting on a unit subset of the qubits in the system. In other words, , where each is a subset of of size . For brevity’s sake, we abuse notation and write as . We can think of the ’s as local constraints, and the ground state as the state that simultaneously satisfies the constraints to the maximal possible extent. Here, then, is the newandimproved problem definition:
Local Hamiltonian Problem
Given a Hamiltonian specified as a collection of local interactions , and nonnegative reals with ,
 If , output YES
 If , output NO
Presuming the matrices and the reals are specified to polynomial precision, then the input size is polynomial in , since is a constant and each of the matrices has entries. Thus, not only is our new problem physically realistic, it is also a problem we might hope to attack with classical computation. However, we will later see that in fact this problem is likely hard even for quantum computers. The remaining installments in this series of notes will deal with further restrictions of the class of Hamiltonians for which the local Hamiltonian problem may be tractable.
Computer science motivation
As we mentioned in the intro, the local Hamiltonian problem (henceforth denoted LH) doesn’t just have myriad applications in physics—it is also important from a computer science perspective because it is a quantum generalization of constraint satisfiability (you may have noticed that quantum analogues of classical concepts are a running theme). Specifically, CSP is a special case of LH.
Suppose we have a CSP instance , and we want to turn it into a LH instance. A clause with constituent variables becomes a diagonal matrix acting on the qubits . Note that the rows and columns of this matrix are indexed by the assignment vectors . Formally, encodes the truth table of in the following manner: . Another way of stating this is .
Informally, takes the clauses of and turns them into local quantum interactions. We’ve constructed so that it has two eigenvalues: 0 and 1. The eigenspace corresponding to 0 is spanned by the set of computational basis vectors that satisfy , and the eigenspace corresponding to 1 is spanned by the computational basis vectors that don’t satisfy . In effect, when we consider as a term of , we are giving an energy penalty to any variable assignment that doesn’t satisfy . will have the eigenvalue 0 (in other words, a ground state energy of 0) if and only if there is some assignment of the variables that satisfies all of the clauses (in other words, iff is satisfiable). Otherwise, the ground state energy of will be at least 1, so determining whether is satisfiable is equivalent to solving LH with inputs , and . (In fact, LH generalizes MAXCSP, since the ground state energy of is exactly the number of clauses minus the maximum number of satisfiable clauses.)