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.)
Let’s work through an example. Consider the following 2SAT formula:
The truth table for the first clause is:
0  0  0 
0  1  1 
1  0  1 
1  1  1 
So is the following matrix:
We also have
Then,
has diagonal entries that are zero, so it has 0 as an eigenvalue. We can therefore conclude that is satisfiable. (In this example it was easy to write out and see that it has zeros on the diagonal, but when is large, becomes exponentially big, so we can’t just compute it explicitly and look through its diagonal entries.)
Quantum CookLevin Theorem
We’ve seen that any CSP problem can be thought of as a LH problem (with a diagonal Hamiltonian matrix). And the analogy can be drawn even further. One reason CSP is so useful is that it (and in particular 3SAT) is NPcomplete, according to the CookLevin Theorem. 3SAT captures the difficulty of classical efficiently verifiable computation. It may not come as a surprise, then, that LH captures the difficulty of quantum efficiently verifiable computation. This result is the “quantum CookLevin theorem”, but before we see it we need to define the complexity class QMA, the quantum analogue of NP.
Because quantum computation is probabilistic, QMA is more precisely the quantum analogue of MA (Merlin Arthur), which allows the verifier to have a chance of error:
MA
iff there exists a probabilistic polytime verifier and a polynomial such that

,
For QMA, the verifier is a quantum computer and the witness is a quantum state. Moreover, we’re interested in the complexity of promise problems:
QMA
A promise problem iff there exists a quantum polytime verifier and a polynomial such that

,
A problem is QMAcomplete if it is in QMA and if any problem in QMA can be reduced to it in polynomial time. In 2002, Kitaev proved that LH is QMAcomplete for all . This was the first time a natural problem was shown to be QMAcomplete. In 2003 Kempe and Regev proved that 3LH is QMAcomplete, and finally in 2006 Kempe, Kitaev and Regev proved that 2LH is QMA complete, achieving the best possible result unless P = QMA. (3SAT is NPcomplete but 2SAT is in P, so it may seem curious that 2LH is QMAcomplete. But in fact, this isn’t too surprising, because as we mentioned earlier, LH corresponds to MAXSAT, and MAX2SAT is NPcomplete.)
“Quantum CookLevin Theorem”
The 2local Hamiltonian problem is QMAcomplete.
A very sketchy proof sketch. This theorem is called the quantum CookLevin theorem not just because of the result, but also because the proof is along the same lines as the proof of the CookLevin theorem.
Recall that in the proof of the CookLevin theorem, we start with a verifier Turing machine that takes as input and, in time accepts iff is a valid witness for being in the language. We then devise (for each ) a 3SAT formula such that any satisfying solution to the instance must be an encoding of a valid history of the Turing machine from start to finish on the input . The constraints must guarantee that (a) the input indeed starts with , (b) at every time step the state of the machine correctly follows from its state at time , and that (c) the final state of the machine indicates acceptance. The constraints for (a) and (c) are trivial, and the reason we can do (b) is because Turing machines compute locally.
For our quantum CookLevin proof, we follow the same template. Given a quantum circuit, we construct a local Hamiltonian that has ground energy below some constant only if there is a quantum encoding of the circuit that includes the proper (a) initial state, (b) intermediate computation, and (c) final state. As before, (a) and (c) are easy, because the parts of the initial and final states we need to ‘inspect’ (with the local terms of the Hamiltonian) are essentially classical. But when we try to compute local constraints for (b), we run into a big problem: entanglement.
Consider some step of the computation. This will consist of applying a quantum gate to a state to obtain . Even assuming we’ve already written down constraints to verify that is correct, it is nontrivial to write down constraints to verify that because may differ from in a highly nonlocal way if there is entanglement between farflung qubits. For example, suppose for the sake of illustration that and . And suppose we want to check that with 1local constraints. Unfortunately, there is no way to distinguish from by looking at one qubit at a time: the reduced density matrix of either state for either qubit is the same: /2. There are examples like this that apply for local constraints for any , so we can’t even verify the ‘trivial’ gate , let alone gates that actually change the state. It would seem that we are stuck.
Luckily, although quantum superposition makes this problem more difficult, we can actually use superposition in a clever manner in order to surmount the difficulty. Instead of encoding the states and separately, we can put them in superposition in a way that will allow us to verify that . Suppose again that , so we want to check that . Let . Then, just by looking at the last qubit of , we can tell how close is to : the reduced density matrix of the last qubit contains information about the angle between and :
The challenge is to describe a local Hamiltonian that has a state with energy below some parameter whenever is a valid witness for , and otherwise has no state with energy below . We won’t cover the details here, but the crucial idea is that when is a valid witness for , the following ‘witness state’ (which is a superposition of the states of the quantum computer over all the time steps) will have low energy for a carefullydevised :
where is the initial state of the computation, and is called the “clock register”. Note that because the size of the clock register is logarithmic in , we actually need to use local constraints. For 5local constraints to suffice, the witness state will need to be a little more complicated (the proof for 2local constraints is even more difficult). Even for the case of LH, the complete proof must demonstrate that no state besides the witness state has low energy.
□
Roadmap
The upshot is that 2LH is the canonical QMAcomplete problem. This is a beautiful result from a quantum complexity theory perspective, but from a physics perspective it is very bad news. The QMAcompleteness of the local Hamiltonian problem means that (presuming BQP QMA) we can’t solve 2LH, and we couldn’t even solve it with a quantum computer. Because of the central importance of finding the ground energy, this in turn means that almost anything a physicist would like to compute about a system is intractable.
So is all hope lost? No! Just as we started out wanting to understand Hamiltonians in general and restricted our focus to local Hamiltonians, the approach the physics community has taken is to focus on even more restricted classes of Hamiltonians that still capture interesting physical systems. One route is to restrict the topology of the system encoded by the Hamiltonian: for example, in many physics models, the particles form a lowdimensional lattice and the only interactions between them are 2local interactions along edges. Even this isn’t enough, though: the problem remains QMAhard on many simple topologies like lattices (for example, 2LH on the 2D lattice is QMAcomplete, and 2LH on even the 1D lattice is QMAcomplete when instead of qubits we are dealing with 8dimensional qudits). So we add a further restriction, which is to focus on gapped Hamiltonians: these are Hamiltonians for which there is a constant gap between the ground energy and the secondlowest energy.
Thus, in the notes to follow, we will focus our energies on trying to solve the gapped local Hamiltonian problem for 1D and 2D lattices. The reason there is hope in these settings is that entanglement is (or is conjectured to be) limited by ‘area laws’. In the next post, Fred Zhang will describe a diagrammatic language (‘tensor networks’) for thinking about lowentanglement quantum states, and he’ll show how physicists solve the local Hamiltonian problem for gapped 1D systems.
3 thoughts on “What is Quantum Hamiltonian Complexity?”
Comments are closed.