What is Quantum Hamiltonian Complexity?

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:

  1. 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.
  2. 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 x \in \mathcal{X}, 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 E: \mathcal{X} \to \mathbb{R}. For example, in the classic Ising model of ferromagnetism, \mathcal{X} = \{\pm 1\}^n. Each coordinate x_i represents the spin of atom i, and atoms i and j interact with each other whenever (i,j) is an edge in a graph G, which is usually a low-dimensional lattice. Energy for this system is defined as E(x) = \sum_{(i,j) \in G}-x_i x_j.

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 T. Then the probability the system is in state x is given by Boltzmann’s distribution: \Pr[x] = \frac{e^{-\beta E(x)}}{Z}, where \beta \propto 1/T and Z is the partition function required to normalize the probabilities. As the temperature tends to infinity, this distribution will approach the uniform distribution over \mathcal{X}, 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 G is connected. These are the states (+1,+1,\ldots,+1) and (-1,-1,\ldots,-1) in which all atoms have the same spin. The ground state energy is -|\{i,j:(i,j) \in G\}|.

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 n-qubit state \left|\psi\right\rangle, 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 H \in (\mathbb{C}^2)^{\otimes n} \times (\mathbb{C}^2)^{\otimes n}, is the quantum Hamiltonian, and just as the energy function characterizes a classical system, the Hamiltonian characterizes a quantum system. For a given eigenvector |\lambda_i\rangle of H with eigenvalue \lambda_i, when we measure the energy of |\psi\rangle we obtain the result \lambda_i with probability \langle\psi|\lambda_i\rangle, and the system collapses to the state |\lambda_i\rangle (assuming the eigenvalue \lambda_i has multiplicity 1). Thus, the ground state and ground state energy of a quantum system with eigenvalue H are the minimum eigenvalue \lambda_0 of H and the corresponding eigenvector |\lambda_0\rangle.

The Boltzmann distribution also has a quantum analogue. A quantum system at thermal equilibrium will be in the following mixed state: \rho_{\text{eq}} = \frac{e^{-\beta H}}{Z}. As the temperature approaches absolute zero, \rho_{\text{eq}} 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 -i \hbar \frac{d|\psi\rangle}{dt} = H|\psi\rangle, where \hbar is Planck’s constant and t is time. Thus, if a closed system is in the state |\psi\rangle_0 at time 0, its state at time t will be |\psi\rangle_t = e^{-itH/\hbar}|\psi\rangle_0. Since H is Hermitian, e^{-itH/\hbar} 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 H \in (\mathbb{C}^2)^{\otimes n} \times (\mathbb{C}^2)^{\otimes n} and non-negative reals a, b with b \geq a+1,

  • If \lambda_0(H) \leq a, output YES
  • If \lambda_0(H) \geq b, output NO


One issue with this definition is that the input includes an enormous 2^n \times 2^n 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.

circle_diagram0
Hamiltonians are too big to work with. What if we restrict our focus to local Hamiltonians?

A k-local Hamiltonian is a Hamiltonian that is decomposed into a sum of terms, each of which represents a Hamiltonian acting on a k-unit subset of the n qubits in the system. In other words, H = \sum_i (H_i)_{S_i} \otimes I_{[n]\backslash S_i}, where each S_i is a subset of [n] of size k. For brevity’s sake, we abuse notation and write H as \sum_i H_i. We can think of the H_i’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:


k-Local Hamiltonian Problem

Given a Hamiltonian H \in (\mathbb{C}^2)^{\otimes n} \times (\mathbb{C}^2)^{\otimes n} specified as a collection of r local interactions \{H_i\}, and non-negative reals a, b with b \geq a+1,

  • If \lambda_0(H) \leq a, output YES
  • If \lambda_0(H) \geq b, output NO

Presuming the matrices \{H_i\} and the reals a, b are specified to polynomial precision, then the input size is polynomial in n, since k is a constant and each of the matrices H_i has 2^k \cdot 2^k 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 k-local Hamiltonian problem (henceforth denoted k-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, k-CSP is a special case of k-LH.

Suppose we have a k-CSP instance \varphi, and we want to turn it into a k-LH instance. A clause C with constituent variables x_1, \ldots, x_k becomes a 2^k \times 2^k diagonal \{0,1\} matrix H_C acting on the qubits |x_1\rangle,\ldots,|x_k\rangle. Note that the rows and columns of this matrix are indexed by the assignment vectors x \in \{0,1\}^k. Formally, H_C encodes the truth table of C in the following manner: (H_C)_{x,x} = 1 - C(x). Another way of stating this is H_C = \sum_{x \in \{0,1\}^k\text{ s.t. }C(x)=0}|x\rangle\langle{x}|.

Informally, H_C takes the clauses of \varphi and turns them into local quantum interactions. We’ve constructed H_C so that it has two eigenvalues: 0 and 1. The eigenspace corresponding to 0 is spanned by the set of computational basis vectors |x\rangle that satisfy C, and the eigenspace corresponding to 1 is spanned by the computational basis vectors that don’t satisfy C. In effect, when we consider H_C as a term of H, we are giving an energy penalty to any variable assignment that doesn’t satisfy C. H = \sum_{C}H_C 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 x_1,\ldots,x_n that satisfies all of the clauses (in other words, iff \varphi is satisfiable). Otherwise, the ground state energy of H will be at least 1, so determining whether \varphi is satisfiable is equivalent to solving k-LH with inputs a = 0, and b = 1. (In fact, k-LH generalizes MAX-k-CSP, since the ground state energy of H is exactly the number of clauses minus the maximum number of satisfiable clauses.)

Continue reading “What is Quantum Hamiltonian Complexity?”