Doubts regarding Local Hamiltonian Problem

Question

I have background in CS but not in Quantum Computing/Quantum Complexity Theory. I am trying to understand the Local Hamiltonian Problem (the formal definition as below):

Local Hamiltonians or Q5SAT: Let $H_j\ (for\ j=1,...r)$ be 5-local Hamiltonians on N qbits (each specified by complex $2^5 \times 2^5$ matrices). Assume that each $H_j$ is scaled so that all eigenvalues $\lambda$ of $H_j$ satisfy $0\leq \lambda \leq1$. Let $H=\Sigma_{j=1}^r H_j$. There is a promise about $H$ that either all eigenvalues of H are $\geq b$ or there is an eigenvalue of $H$ that is $<a$, where $0\leq a < b \leq 1$ and the difference $b-a$ is at least inverse polynomial in $n$ i.e. $b-a \geq 1/poly(n)$. The problem asks whether $H$ has an eigenvalue $\leq a$ ?

The Local Hamiltonian Problem is $QMA-Complete$. P.S. This problem is supposedly similar to 3SAT (and I understand 3SAT).

Here is what I could understand:

1. Let the problem be over $N$ variables (qbits).
2. We are given some (say $r$) '5-Local Hamiltonian Matrices'. Each $k$-local Matrix is a square Hermitian/Hamiltonian Matrix of size $2^5 \times 2^5$.
3. Each entry (number of bits) in each of these matrix is of size/precision $poly(N)$, where $poly(N)$ is some given polynomial on $N$.
4. Each $k$-Local Matrix represents a set of (some) $k$ variables (qbits).
5. Each $k$-Local Matrix when diagonialized results in diagonal matrix with real entries, each entry in it representing one of the potential 'energy levels'(?) or eigenvalues for that particular $k$-Local Matrix.
6. $H$ is a matrix of size $2^N \times 2^N$.
7. What I understand is, for any k-Local Matrix, we choose exactly one from the $2^k$ 'energy levels' (say $i^{th}$) and its corresponding row ($i^{th}$) of the original k-Local Matrix is chosen.

There are several things I am really struggling to understand:

1. How do we combine the local matrices $H_j$ to form the global matrix $H$?

2. How is one $k$-Local Matrix related to another $k$-Local Matrix? How is the choice of one row or energy level in the first matrix related to or constraints the choice of row or energy level in the second matrix (since its similar to 3SAT)? My (unclear) understanding/guess is its somehow related to the index of each row of each $k$-Local Matrix (each index being a k-bit binary string). But it is not exactly mentioned or explained anywhere. So its not very clear how the constraints using these indexes work and relate any two $k$-Local Matrices.

3. Assuming that we are able to form the global matrix $H$ using the local matrix, what is the overall objective of the problem (w.r.t. this matrix)? Do we have to find a row of $H$ such that its eigenvalue or energy is less than $a$?

I am really struggling with understanding the problem since most of the sources assume the background in QC/QM. All the terminology and assumptions about background are too convoluted. Moreover no matter where I look there doesn't seem to be a single step-by-step worked out example for this problem. At each place there is just the above definition and the assumption that the reader understood. Can someone explain this problem (assuming only CS background). Since its a mathematical problem I am hopeful it can be explained without (too much) QC background.

A step by step example would also be very helpful but I couldn't find even one!

Answer 1

To start with a bit of folklore, a qubit is a complex vector with two components that is normalized to have length one. It describes the state of a quantum system that can take values of $0$ or $1$ or complex superpositions thereof: $$ a|0\rangle+b|1\rangle\,. $$ Here, $|0\rangle$ is the basis vector $\begin{bmatrix}1\\0\end{bmatrix}\in\mathbb C^2$ and $|1\rangle$ is the basis vector $\begin{bmatrix}0\\1\end{bmatrix}\in\mathbb C^2\,.$

A measurement outcome will either be $0$ or $1$ where the probabilities of those outcomes are $|a|^2$ (to measure $0$), resp. $|b|^2$ (to measure $1$). The normalization $$ |a|^2+|b|^2=1 $$ ensures that these are classical probabilities.

A system of $N$ qubits (quantum register) is the $N$-fold tensor product (Kronecker product) of $N$ qubits. For example, two qubits $\begin{bmatrix}a\\b\end{bmatrix}$ and $\begin{bmatrix}c\\d\end{bmatrix}$ form the Kronecker product $$ \begin{bmatrix}ac&ad\\bc&bd\end{bmatrix} $$ in bra-ket notation these two qubits are $$ a|0\rangle+b|1\rangle\,,\quad c|0\rangle+d|1\rangle\, $$ and their tensor product is $$\tag{1} ac\,|00\rangle+ad\,|01\rangle+bc\,|10\rangle+bd\,|11\rangle\,. $$ The product states $$\tag{2} |00\rangle=\begin{bmatrix}1&0\\0&0\end{bmatrix}\,,\quad |01\rangle=\begin{bmatrix}0&1\\0&0\end{bmatrix}\,,\quad |10\rangle=\begin{bmatrix}0&0\\1&0\end{bmatrix}\,,\quad |11\rangle=\begin{bmatrix}0&0\\0&1\end{bmatrix}\, $$ are an orthonormal basis of this two-qubit system.

A Hamiltonian is a Hermitian map that acts on vectors of the form (1). When we vectorize the basis vectors (2), i.e., write them as $$\tag{3} |00\rangle=\begin{bmatrix}1\\0\\0\\0\end{bmatrix}\,,\quad |01\rangle=\begin{bmatrix}0\\1\\0\\0\end{bmatrix}\,,\quad |10\rangle=\begin{bmatrix}0\\0\\1\\0\end{bmatrix}\,,\quad |11\rangle=\begin{bmatrix}0\\0\\0\\1\end{bmatrix}\, $$ then we can write the Hamiltonian as a Hermitian $4\times 4$-matrix $$ H=\begin{bmatrix} h_{11}&h_{12}&h_{13}&h_{14}\\ \overline{h_{12}}&h_{22}&h_{23}&h_{24}\\ \overline{h_{13}}&\overline{h_{23}}&h_{33}&h_{34}\\ \overline{h_{14}}&\overline{h_{24}}&\overline{h_{34}}&h_{34}\\ \end{bmatrix}\,. $$ The diagonal elements must be real because $H$ is Hermitian.

When $H$ is the Kronecker product of two Hermitian $2\times 2$-matrices $A$ and $B$ $$ H=A\otimes B=\begin{bmatrix} a_{11}B&a_{12}B\\ \overline{a_{12}}B&a_{22}B\\ \end{bmatrix}= \begin{bmatrix} a_{11}b_{11}&a_{11}b_{12}&a_{12}b_{11}&a_{12}b_{12}\\ a_{11}\overline{b_{12}}&a_{11}b_{22}&a_{12}\overline{b_{12}}&a_{12}b_{22}\\ \overline{a_{12}}b_{11}&\overline{a_{12}}b_{12}&a_{22}b_{11}&a_{22}b_{12}\\ \overline{a_{12}}\overline{b_{12}}&\overline{a_{12}}b_{22}&a_{22}\overline{b_{12}}&a_{22}b_{22}\end{bmatrix} $$ then $A$ is a Hamiltonian for the first qubit and $B$ a Hamiltonian for the second qubit.

To me the definition of a $k$-local Hamiltonian in arXiv:0302079 means that the above $H$ is $1$-local when at least one of $A,B$ is the identity matrix. Assume this is $A$. Then $$ H=I\otimes B=\begin{bmatrix} b_{11}&b_{12}&0&0\\ \overline{b_{12}}&b_{22}&0&0\\ 0&0&b_{11}&b_{12}\\ 0&0&\overline{b_{12}}&b_{22}\end{bmatrix}\,. $$ This $4\times 4$-matrix is essentially a $2\times 2$-matrix.

It does therefore make sense when they say that a $2^N\times 2^N$-matrix $H$ is a "sum" of $k$-local $2^k\times 2^k$-matrices $H_i$.

Answer 2

There are a lot of misconceptions and misunderstandings here. Let's go through your understanding and questions, as I think it's quite instructive.

Your Understanding

Here is what I could understand:

1. Let the problem be over $N$ variables (qbits).

So far so good

2. We are given some (say $r$) '5-Local Hamiltonian Matrices'. Each $k$-local Matrix is a square Hermitian/Hamiltonian Matrix of size $2^5\times 2^5$.

Kind of, this is a bit of laziness in notation that can cause confusion. Every operator in this space is a $2^N\times 2^N$ matrix. Each $k$-local matrix is not a $2^k\times 2^k$ matrix. However, it can be uniquely specify in terms of a $2^k\times 2^k$ matrix and $k$ indices.

Let $O$ be an operator that acts on 1 qubit only, that is it's a $2\times 2$ matrix. We then define $O_j$ be $O$ acting on qubit $j$. This is no longer a $2\times 2$ matrix, despite being $1$-local.

$$ O_j=\overbrace{\underbrace{I\otimes I\otimes\cdots\otimes I}_{\large\text{$j-1$ terms}}\otimes O\otimes I\otimes\cdots\otimes I}^{\large\text{$N$ total terms}}\quad \text{is a $2^N\times 2^N$, $1$-local matrix} $$

However, it should be clear that just given the $2\times 2$ representation of $O$, together with $j$, we can specify the $2^N\times 2^N$ matrix $O_j$, since we just did it above.

A $k$-local Hamiltonian, $H_k$, likewise can be specified by a $2^k\times 2^k$ matrix and a list of which $k$ qubits it acts on. It's a bit messy to write down, but it should be clear that it's possible to do.

I stress though, $H_k$ is still a $2^N\times 2^N$ matrix. When, in the literature, they say a $k$-local Hamiltonian is a $2^k\times 2^k$ matrix they are being lazy and implicitly talking about the non-trivial $k$-qubit subspace of the full $N$-qubit space.

3. Each entry (number of bits) in each of these matrix is of size/precision $poly(N)$, where $poly(N)$ is some given polynomial on $N$.

Yup

4. Each $k$-Local Matrix represents a set of (some) $k$ variables (qbits).

Terminology is a bit off here, but I think you have the idea. Each $k$-local term involves non-trivial transformations on $k$ qubits.

5. Each $k$-Local Matrix when diagonialized results in diagonal matrix with real entries, each entry in it representing one of the potential 'energy levels'(?) or eigenvalues for that particular $k$-Local Matrix.

Right. Since the problem specifies that each $k$-local term is itself a valid Hamiltonian, then each one is Hermitian and so is diagonalizable and has real eigenvalues. In physics the Hamiltonian is the operator corresponding to the observable of energy, so it's common to call eigenvalues of the Hamiltonian "energies", "eigenenergies", "energy levels", ...etc.

6. $H$ is a matrix of size $2^N \times 2^N$.

Correct, as explained above.

7. What I understand is, for any k-Local Matrix, we choose exactly one from the $2^k$ 'energy levels' (say $i^{th}$) and its corresponding row ($i^{th}$) of the original k-Local Matrix is chosen.

I'm not sure I understand what this means or how it relates to the problem. If you're saying that each eigenvalue of the $k$-local Hamiltonian corresponds to a row in its matrix representation, then that's wrong. Firstly, this is basis dependent, so each row/column corresponding to an eigenvalue is only valid if the matrix is written down in the eigenbasis. Even still, picking an energy level doesn't specify the row if that level is degenerate, the best it can do is specify the eigenspace.

Furthermore, because linear algebra is annoying, knowing the eigenvalues of each $H_j$ tells you very little about the eigenvalues of $H=\sum_j H_j$ in general.

Your Questions

There are several things I am really struggling to understand:

1. How do we combine the local matrices $H_j$ to form the global matrix $H$?

Just add them together. I can see why this would be confusing with the misconception that each $k$-local term was a $2^k\times 2^k$ matrix. It should be clear now, I hope?

2. How is one $k$-Local Matrix related to another $k$-Local Matrix?

For $H=\sum_j H_j$, are you talking about $H$ or $H_j$ when you say $k$-local matrix? $H$ and each $H_j$ are all $k$-local by definition.

In general there are no constraints or relationships between different $k$-local $H$s or $H_j$s in a given $H$. This problem considers a very general class of matrix. However, we do have a promise that either

1. All eigenvalues of $H$ are $\geq b$ or
2. There exists an eigenvalue of $H$ which is $<a$.

This narrows the class slightly, discarding any $H$ with an eigenvalue $\lambda$ such that $a\leq\lambda<b$. This may impose some structure on the allowable $H$s and $H_j$s, but it's not immediately obvious what that would be. Indeed this problem couldn't be QMA-complete if there were some simple constraints which defined this class of Hamiltonian.

How is the choice of one row or energy level in the first matrix related to or constraints the choice of row or energy level in the second matrix (since its similar to 3SAT)?

I think you are thinking about this problem backward.

You take as input some set of $k$-local $H_j$s and two values $a$ and $b$ such that $0\leq a<b<\leq 1$. You are expected to output "yes" if there exists an eigenvalue of $H=\sum_j H_j$ less than $a$, and "no" otherwise. The only other things you can assume are

1. $H$'s smallest eigenvalue is either $\geq b$ or it's $<a$.
2. $||H_j||\leq 1$ for all $j$.

You're not making any choices here, about the energy levels in the individual $H_j$s or otherwise.

My (unclear) understanding/guess is its somehow related to the index of each row of each $k$-Local Matrix (each index being a k-bit binary string). But it is not exactly mentioned or explained anywhere. So its not very clear how the constraints using these indexes work and relate any two $k$-Local Matrices.

Again, this is completely missing the point of the problem. See above.

3. Assuming that we are able to form the global matrix $H$ using the local matrix, what is the overall objective of the problem (w.r.t. this matrix)?

The objective is to correctly answer, "Does $H$ have an eigenvalue, $\lambda$, such that $\lambda<a$?"

Do we have to find a row of $H$ such that its eigenvalue or energy is less than $a$?

That's basically the problem, but again row $\leftrightarrow$ eigenvalue iff $H$ is already diagonal, which it's typically not.

I am really struggling with understanding the problem since most of the sources assume the background in QC/QM. All the terminology and assumptions about background are too convoluted.

Fair enough

Moreover no matter where I look there doesn't seem to be a single step-by-step worked out example for this problem.

What do you want "worked out"? An algorithm for solving this problem?

Here's a simple one. Use the QR algorithm to find the eigenvalues of $H$, $\{\lambda_i\}$ to precision $\gg b-a$. Compute $E_0=\min_i \lambda_i$. If $E_0<a$ return TRUE else return FALSE.

This can be run on a quantum computer since quantum computers are Turing complete. This takes exponentially large amounts of space and time, so it's bad, but it's an algorithm solving the problem. It's currently unknown if an efficient algorithm, classical or quantum, can exist. Finding, or disproving the existence of, an efficient classical algorithm would get you \$1,000,000 for solving $P=NP$. Resolving quantum analog would be similarly impactful.

The only other thing to be "worked out" is a proof that all other QMA-complete problems can be solved efficiently given an oracle which solves this problem. You can find such a proof here for $k=2$, from which the QMA-completeness for any $k>2$ is immediately implied.

At each place there is just the above definition and the assumption that the reader understood. Can someone explain this problem (assuming only CS background). Since its a mathematical problem I am hopeful it can be explained without (too much) QC background.

A step by step example would also be very helpful but I couldn't find even one!

I hope the above comments constitute an answer to this. I'll write the problem statement here again in a slightly different way:

1. Input - Set of Hamiltonians $\{H_j\}$, set of indices $\{\ell_j\}$, and two values: $a$ and $b$.

2. Output - TRUE if $\min_\psi \left\langle \psi\left|\sum_j H_j\right|\psi\right\rangle<a$, FALSE otherwise

3. Assumptions

   a. Every $H_j$ is $k$-local for some predetermined $k$ and specified by a $2^k\times 2^k$ matrix

   b. Every $\ell_j$ is a list of $k$ numbers, each between $1$ and $N$ inclusive.

   c. $||H_j||\leq 1$ for all $j$

   d. Each $H_j$ is specified by poly$(N)$ bits of precision only. This is basically to make sure we can read in $H$ without it taking exponential resources. If we need exponential time to read in the input, there's no chance for a polynomial-time algorithm.

   e. $b-a>\frac{1}{\text{poly}(N)}$. Like in (c), this is to ensure there's at least a chance to solve the problem in polynomial time. If we need exponential precision to even check if $a\leq\lambda\leq b$ then there would be no hope for an efficient algorithm.

Example

Input

$$\{H_j\}= \left\{ \left( \begin{array}{cccc} 0 & 0 & 0.0002 & 0 \\ 0 & 0 & 0 & 0.0002 \\ 0.0002 & 0 & 0 & 0 \\ 0 & 0.0002 & 0 & 0 \\ \end{array} \right), \left( \begin{array}{cccc} 0 & 0 & 1.0001 & 0 \\ 0 & 0 & 0 & 1.0001 \\ 1.0001 & 0 & 0 & 0 \\ 0 & 1.0001 & 0 & 0 \\ \end{array} \right) \right\} $$

$$ \{\ell_j\}=\{\{1,2\},\{2,3\}\} $$

$$ \{a,b\}=\{-1,-9/10\} $$

Processing

$\max \{\ell_j\}=3\implies N=3$

Each $H_j$ is $2^2\times 2^2\implies k=2$

Let $\tilde H_j$ be the full $2^3\times 2^3$ defined by $H_j$ and $\ell_j$ together. I chose $\ell$ such that I can easily write down each $\tilde H_j$, in general it's uglier but straightforward.

$$ \tilde H_1 = H_1\otimes I \quad \text{and} \quad \tilde H_2=I\otimes H_2 $$

So we have

$$ H=\sum_j \tilde H_j= \left( \begin{array}{cccccccc} 0 & 0 & 1.0001 & 0 & 0.0002 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1.0001 & 0 & 0.0002 & 0 & 0 \\ 1.0001 & 0 & 0 & 0 & 0 & 0 & 0.0002 & 0 \\ 0 & 1.0001 & 0 & 0 & 0 & 0 & 0 & 0.0002 \\ 0.0002 & 0 & 0 & 0 & 0 & 0 & 1.0001 & 0 \\ 0 & 0.0002 & 0 & 0 & 0 & 0 & 0 & 1.0001 \\ 0 & 0 & 0.0002 & 0 & 1.0001 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.0002 & 0 & 1.0001 & 0 & 0 \\ \end{array} \right) $$

and need to answer the question: is $H$'s smallest eigenvalue, denoted $\lambda_0$, less than $a=-1$? $b$ is only provided so we know how accurate we need to compute $\lambda_0$. If $\lambda_0\nless -1$ then we know $\lambda_0>-9/10$ and so we only need precision on the order of $1/10$.

For this small $(8\times 8)$ Hamiltonian, it's very easy to compute $\lambda_0$. Using an eigensolver, we choose

$$ |\psi\rangle=\frac{1}{2} \left( \begin{array}{c} 0 \\ 1 \\ 0 \\ -1 \\ 0 \\ -1 \\ 0 \\ 1 \\ \end{array} \right) $$

Then

$$ \left\langle \psi\left|H\right|\psi\right\rangle=\lambda_0=-\frac{10003}{10000}<a=-1 $$

Output

TRUE

Note

Finding a good $|\psi\rangle$ was easy for such a small $N$. In general, as $N$ gets large, the difficulty to compute $\lambda_0$ grows exponentially. This is true both on a classical and quantum computer. We can't rule out efficient algorithms for doing this, but none are known.