by Ben Edelman
This is the first installment of a three-part 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 many-particle 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 NP-complete problem by the Cook-Levin theorem, the local Hamiltonian problem plays the equivalent role for QMA (a quantum analogue of NP) by the “quantum Cook-Levin 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 low-dimensional 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 non-negative reals
with
,
- If
, output YES
-
If
, output NO
One issue with this definition is that the input includes an enormous matrix. For a reasonable-sized 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 real-life 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 new-and-improved problem definition:
-Local Hamiltonian Problem
Given a Hamiltonian specified as a collection of
local interactions
, and non-negative 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 MAX-
-CSP, since the ground state energy of
is exactly the number of clauses minus the maximum number of satisfiable clauses.)