Commuting Local Hamiltonian Problem on 2D beyond qubits

Despite two decades of study, the complexity of CLHP still remains open, with a few special cases known to be in NP ([BV03, AE13, AE11b, Sch11, AKV18, Has12a]). Bravyi and Vyalyi initiated this line of work, showing that qudit $2$-local CLHP is in NP  [BV03]. Their proof uses a decomposition lemma based on the theory of finite-dimensional $C^{*}$-algebra representations. All subsequent work on the CLHP has made use of this framework.

Aharonov and Eldar [AE11b] extended the results to the $3$-local case for qubits and qutrits. Specifically, they proved that 3-local qubit-CLHP is in NP. They also proved that 3-local qutrit CLHP is in NP on the Nearly Euclidean interaction graphs. All the above results are proved by showing that there is a trivial ground state, i.e. the ground state can be prepared by a constant depth quantum circuit. This constant depth circuit is the NP witness and the energy of this trivial ground state can be checked in classical polynomial time by a light-cone argument. However, for 4-local CLHP, even if the interaction graph is a 2D square lattice, there are systems like the Toric code which has no trivial ground states.

In this work, we mainly focus on 4-local CLHP on a 2D square lattice with qudits (abbreviated as qudit-CLHP-2D). Specifically, consider a 2D square lattice as in Fig. 1(a) with a qudit $q$ on each vertex and on each plaquette $p$, there is a Hermitian term acting on the qudits on its four vertices. With some abuse of notations, we also use $p$ to denote the Hermitian term on the plaquette $p$. The qudit-CLHP-2D is given an $n$-qudit Hamiltonian $H=\sum_{p}p$ where $\{p\}_{p}$ are commuting, two parameters $a,b$ where $b-a\geq 1/poly(n)$, decide whether the minimum eigenvalue of $H$ is smaller than $a$ or greater than $b$. There is an alternate 2D setting in which qudits are placed on the edges and there are Hermitian terms on “plaquettes” and “stars”. The two settings, i.e. qudits on vertices or qudits on edges, are equivalent when the underlying graph is a 2D square lattice. ( See Appendix C.)

Along this line, Schuch [Sch11] first proved that the qubit-CLHP-2D is in NP. Schuch’s proof provides a witness showing that a low-energy state exists without giving an explicit description of the state. Indeed his proof leaves open the question of whether an explicit description of the state even exists. Aharonov, Kenneth, and Vigdorovich [AKV18] later gave a constructive proof, showing that after some transformation, the qubit-CLHP-2D is equivalent to the Toric code permitting boundaries. We say a proof is constructive if The NP prover shows that the ground energy is below $a$ by providing a circuit for preparing the ground state. A boundary roughly means a qubit $q$ where one of the four terms involving this qubit, i.e. $p_{1},p_{2},p_{1}^{\prime},p_{2}^{\prime}$ in Fig. 1(b), acts trivially on $q$. A Hamiltonian is equivalent to the Toric code permitting boundaries if after choosing an appropriate basis for each qubit, terms $\{p\}_{p}$ in the Hamiltonian act similarly as $X$ or $Z$ on the non-boundary qubits. Both proofs  [Sch11, AKV18] for the qubit-CLHP-2D heavily depend on the restrictions to the qubits, since the induced algebra of a term $p$ on a qubit $q$ can only have a very limited structure. The limited structure for the qubits case does not hold for higher dimensional particles, not even for qutrits.

Hastings [Has12a] proved a subclass of the qudit-CLHP-2D is in NP with some restrictive assumptions. Roughly speaking, he grouped all qudits on the same vertical line as a supersite, then viewed the 2D lattice as a 1D line, which reduced the qudit-CLHP-2D back to the “qudit” 2-local case [BV03]. However, the main problem is that those supersites are not really qudit of constant dimension. In fact, the dimension of the supersite is sub-exponential in the number of qudits. Thus Hastings further assumes that several technical conditions hold, like certain operators in the proof can be efficiently represented by matrix product operators of bounded dimension.

Besides the qudit-CLHP-2D, Bravyi and Vyalyi [BV03] also addressed the special case of the commuting Hamiltonian problem where all the terms are factorized (CHP-factorized). That is $H=\sum_{i}h_{i}$, and each term $h_{i}$ is a tensor product of single-qudit Hermitian operators. For example, the Toric code is an instance of CHP-factorized, since each term is $X^{\otimes 4}$ or $Z^{\otimes 4}$. In general, in CHP-factorized each $h_{i}$ is not necessarily local, and there are no constraints on the underlying interaction graph. Bravyi and Vyalyi give a non-constructive proof to show that the qubit-CHP-factorized is in NP. It is an open question whether their proof can be generalized to higher dimensional particles (qudit-CHP-factorized) or whether their proof for qubits can be made constructive.

All of the above results prove that subclasses of CLHP are in NP. On the other hand, Gosset, Mehta, and Vidick [GMV17] give a result that indicates CLHP might be harder than NP, or even as hard as the general LHP. They show that the ground space connectivity problem of commuting local Hamiltonian is QCMA-complete, which is as hard as the ground space connectivity problem for the general local Hamiltonian.

The manuscript is structured as follows. In Sec. 2 we give notations and definitions which are used throughout this manuscript. In Sec. 3 we review the necessary definitions and techniques of $C^{*}$-algebra and the Structure Lemma required for proving that the qutrit-CLHP-2D is in NP. In Sec. 4 and Sec. 5, we give proofs for the qutrit-CLHP-2D and the qudit-CLHP-2D-factorized respectively.

The manuscript is written in a way that several proofs can be read separately. In summary, for readers interested in Lemma 23 (The Decrease Dimension and Rounding Lemma), the suggested order is Sec. 2 and Sec. 4.1. For readers interested in the qutrit-CLHP-2D, the suggested order is Sec 2, Sec. 3, Sec. 4. For readers interested in the qudit-CLHP-2D-factorized, the suggested order is Sec 2, Sec. 5, and then Sec. 3 if necessary.

In this manuscript, we give two new results of the qudit-CLHP-2D. First, we proved that qutrit-CLHP-2D is in NP, by introducing a non-constructive way of self-reduction for the qudit-CLHP, when there are semi-separable qudits. This self-reduction (proven in Lemma 23) works for qudit and might be of independent interest. Second, we prove that qudit-CLHP-2D-factorized is in NP, by showing that the Hamiltonian is equivalent to a direct sum of qubit stabilizer Hamiltonian.

One direct question is whether our proof for qutrit-CLHP-2D can be made to be constructive. That is whether one can prepare the ground state by polynomial-size quantum circuits. Aharonov, Kenneth and Vigdorovich [AKV18] proved that the qubit-CLHP-2D is equivalent to the Toric code permitting boundary. It is natural to ask whether qutrit-CLHP-2D, or general qudit-CLHP-2D, can have different ground space properties from the stabilizer Hamiltonians. Another question is whether our constructive proof for the qudit-CLHP-2D-factorized can be modified to prepare the ground states of the qubit-CHP (without 2D geometry). Recall that the qubit-CHP is in NP by a non-constructive method [BV03].

A further question is to extend the frontier of the complexity of CLHP. In particular, we conjecture that Lemma 23 can be used in more general settings. Recall that Lemma 23 works for qudit rather than only for qutrits, and it implies w.l.o.g we can assume that there are no semi-separable qudits. It is interesting to see whether one can prove that the qudit-CLHP-2D$\in\mbox{\bf NP}$ by combining Lemma 23 and other methods like [AKV18]. Another promising setting is considering 3-local qutrit-CLHP, without any geometry constraints. Recall that [AE11b] proved for 3-local qubit-CLHP is in NP, by showing that after removing all separable qubits, the resulting Hamiltonian can be viewed as a 2-local qudit-CLHP. It is possible that for 3-local qutrit-CLHP, if we remove all semi-separable qutrits, the Hamiltonian is again of a 2-local structure, which will imply 3-local qutrit-CLHP is in NP.

Most known results are trying to show that CLHP is in NP. On the other side, it will be very interesting to provide any evidence that CLHP might be harder than NP.

Given a Hermitian operator $H$, we use $\lambda(H)$ to denote its ground energy, i.e. minimum eigenvalue. For two operators, $h$ and $h^{\prime}$, we use $[h,h^{\prime}]$ to denote its commutator $hh^{\prime}-h^{\prime}h$. In particular, $[h,h^{\prime}]=0$ means $h,h^{\prime}$ are commuting. Two sets of operators, $S$ and $\hat{S}$, commute if $[h,\hat{h}]=0,\forall h\in S,\hat{h}\in\hat{S}.$ For a set of Hermitian operators $\{h_{i}\}_{i}$, we use $\ker\{h_{i}\}_{i}$ to denote its common $0$-eigenspace, i.e. $\ker\{h_{i}\}_{i}:=\{\left|\psi\right\rangle\,|\,h_{i}\left|\psi\right\rangle=0,\forall i\}$. We say $\ker\{h_{i}\}_{i}$ is non-trivial iff $\ker\{h_{i}\}_{i}\neq\{0\}.$¹¹1This $0$ means the zero vector. With some abuse of notations, we use $0$ both for real number zero, and zero vector. For ease of illustration, we also denote a Hermitian $H=\sum_{i}h_{i}$ as a set $\{h_{i}\}_{i}$. We say a Hermitian operator $\Pi$ is a projection if $\Pi^{2}=\Pi$. When $\{h_{i}\}_{i}$ are commuting projections, we have $\lambda(H)=0$ iff $\ker{\{h_{i}\}_{i}}$ is non-trivial.

Let $\mathcal{H}$ be a finite-dimensional Hilbert space. We use $\mathcal{L}(\mathcal{H})$ to denote the set of linear operators on $\mathcal{H}$. For Hermitian $h$, we use $h\succeq 0$ to denote $h$ is positive semidefinite, that is all of its eigenvalues are non-negative. We use $I$ to denote the identity matrix. Let $h$ be a Hermitian operator on Hilbert space $\mathcal{X}=\mathcal{H}\otimes\mathcal{Z}$, we say $h$ keeps the decomposition $\mathcal{H}=\bigoplus_{i}\mathcal{H}_{i}$ invariant if $h$ keeps the subspace $\mathcal{H}_{i}\otimes\mathcal{Z}$ invariant, $\forall i$. We say the decomposition $\mathcal{H}=\bigoplus_{i=1}^{m}\mathcal{H}_{i}$ is non-trivial if $m\geq 2$.

In the following, we use $q$ to denote a qudit, and $\mathcal{H}^{q}$ to denote the Hilbert space of the qudit $q$. Consider an operator $h$ acting on $n$ qudits. We say that $h$ acts trivially on a qudit $q$ if $h$ acts as identity on $\mathcal{H}^{q}$. When $h$ acts non-trivially on only $k$ of the $n$ qudits, we will interchangeably view $h$ as an operator on $k$ qudits or a global operator on $n$ qudits. The meaning will be clear in the context. We use $tr_{S}()$ for tracing out the qudits in $S$, and use $tr()$ for tracing out all the qudits. We use $S^{c}$ to denote the set of qudits outside $S$.

We further say a commuting (4-local) Hamiltonian on 2D is factorized, if each $p$ is factorized on its vertices, that is $p=p^{q_{1}}\otimes p^{q_{2}}\otimes p^{q_{3}}\otimes p^{q_{4}}$ for Hermitian terms $p^{q_{i}}$ acting on qudit $q_{i}$, as shown in Fig. 1(a). We call $p^{q_{i}}$ factors. For the Toric code, $p\in\{X^{\otimes 4},Z^{\otimes 4}\}$.

We define a special case of the qudit-CLHP called qudit-CLHP-projection where each term $h_{i}$ is a projection, $b=1$, and $a=0$. Note that since $\{h_{i}\}_{i}$ are commuting projections, we know $\lambda(H)$ must be a non-negative integer. Thus in the No instance we use $\lambda(H)\geq 1$ rather than $\lambda(H)\geq 1/poly(n)$. We define qudit-CLHP-2D-projection similarly.

Consider a commuting $k$-local Hamiltonian $H=\sum_{i}h_{i}$ on $n$ qudits with Hermitian terms $\{h_{i}\}_{i}$. Although $h_{i}$ acts non-trivially only on $k$ qudits, in this section we view it as an operator on $n$ qudits. We will name the $n$ qudits as $q_{1},q_{2},...,q_{n}$. When we refer to an arbitrary qudit, we name it as $q$.

The definition of separable is first introduced by [AE11b]. Roughly speaking, it says all the Hermitian terms $\{h_{i}\}_{i}$ are block-diagonalized in the same way. We introduce the notion of semi-separable qudit, which will play a key role in the proof of the qutrit-CLHP-2D.

Semi-separable qudit is a relaxation of separable qudits, in the sense that we allow one term to be not block-diagonalized w.r.t the decomposition $\mathcal{H}^{q}=\bigoplus_{j=1}^{m}\mathcal{H}^{q}_{j}$. Note that by the definition of semi-separable, $h_{i}$ is Hermitian and we have $[h_{i},\Pi_{j}]=0,\forall i\neq 0,\forall j$. We will repeatedly use this fact. It is also important to keep in mind that $[h_{0},\Pi_{j}]$ might not be equal to $0$, since we allow $h_{0}$ not keeping $\mathcal{H}^{q}_{j}$ invariant.

Then we introduce the induced algebra, which connects a Hermitian operator and a $C^{*}$-algebra.

The induced algebra is independent of the chosen decomposition for Hermitian $h$.

By Lemma 10 we know the induced algebra of $h$ on $\mathcal{H}$, i.e. $\mathcal{A}^{\mathcal{H}}_{h}$ in Definition 9, is independent of the decomposition we choose, thus $\mathcal{A}^{\mathcal{H}}_{h}$ is well-defined. Note that if there is a decomposition $\mathcal{H}=\bigoplus_{i}\mathcal{H}_{i}$ such that $\mathcal{A}_{h}^{\mathcal{H}}$ keeps $\mathcal{H}_{i}$ invariant, $\forall i$, then it follows that $h$ keeps $\mathcal{H}_{i}$ invariant, $\forall i$.

The Structure Lemma [T⁺03] says that every finite-dimensional $C^{*}$-algebra is a direct sum of algebras of all operators on a Hilbert space. See Sec. 7.3 of  [GHL⁺15] for an accessible proof of the Structure Lemma. The following statement is taken from [AKV18].

Given a $C^{*}$-algebra $\mathcal{A}$, we denote the decomposition $\mathcal{H}=\bigoplus_{i}\mathcal{H}_{i}$ in Lemma 11 as the decomposition induced by $\mathcal{A}$. Note that here we do not argue whether the decomposition in Lemma 11 is unique or not. However, for clarity when we mention the decomposition induced by $\mathcal{A}$, we always refer to the same canonical decomposition. For example, we can set the canonical decomposition to be the one obtained by the proof in Sec. 7.3 of  [GHL⁺15]. In the following we give some definitions of decompositions, and a further remark on Lemma 11.

Lemma 11 implies all operators in $\mathcal{A}$ keep the decomposition $\mathcal{H}=\bigoplus_{i}\mathcal{H}_{i}$ invariant. It is worth noting that the decomposition induced by $\mathcal{A}$ might not be the best decomposition that $\mathcal{A}$ keeps invariant. In particular, consider the $C^{*}$-algebra $\mathcal{A}$ generated by $I$, i.e. $\{cI\}_{c\in\mathbb{C}}$. The decomposition of $\mathcal{H}$ induced by $\mathcal{A}$ is trivial, i.e. $\mathcal{H}=\mathcal{H}_{1}$, but $\mathcal{A}$ keeps any decomposition of $\mathcal{H}$ invariant. Using Lemma 11, we can analyze how two induced algebras can commute with each other.

In the following, we give a sufficient condition that implies the decomposition of space induced by the $C^{*}$-algebra is non-trivial.

The following definitions will be used throughout Sec. 5.

Note that by Corollary 13, $h,h^{\prime}$ have a tensor-product structure on $\mathcal{H}_{i}$. Since the dimension of any Hilbert space must be an integer, two terms on a qutrit $q$ of dimension $3$ can only commute in the following ways.

Similar arguments for qubits are widely used in the proof of the qubit-CLHP-2D is in NP [Sch11][AKV18]. We summarize it as below:

Note that Lemma 16 and Lemma 17 only involve 2 commuting terms $h,h^{\prime}$, and their overlapping space is only $\mathcal{H}$. Those techniques do not directly apply to 2D Hamiltonians, where some of the terms overlap on 2 qudits.

Lemmas in this section work for qudit-CLHP-projection³³3W.l.o.g we can assume that all terms are projections by Lemma 48., that is we do not assume that each particle is a qutrit, or the Hamiltonian is on 2D. Recall that qudit-CLHP-projection is: Consider a qudit-CLHP $H=\sum_{i}h_{i}$ where $\{h_{i}\}_{i}$ are $k$-local projections for some constant $k$, $[h_{i},h_{j}]=0$ for $i\neq j$. The question is to determine whether $\lambda(H)=0$ or $\lambda(H)\geq 1$. Note that $\lambda(H)=0$ iff all the commuting projections $\{h_{i}\}_{i}$ have a common $0$-eigenvector, i.e. $ker\{h_{i}\}_{i}$ is non-trivial. When $\lambda(H)=0$, the common $0$-eigenvectors of $\{h_{i}\}_{i}$ are the ground states of $H$. We also denote the Hamiltonian $H$ as $\{h_{i}\}_{i}$.

The key lemma in this section, Lemma 23, is to prove that when there is a semi-separable qudit, the prover can perform a non-constructive self-reduction for the qudit-CLHP-projection. Here self-reduction means reducing the qudit-CLHP-projection to another qudit-CLHP-projection, where the Hilbert space of the qudit has a smaller dimension. Before going into the formal proofs, in the following, we intuitively explain how Lemma 23 works. Specifically, temporarily assume that $\lambda(H)=0$ thus we are in the Yes instance and try to prove $\lambda(H)=0$. We begin with the example when there is a separable qudit, then generalize this idea to the case of semi-separable qudit, and after that we give the formal proofs.

When there is a separable qudit $q$, the prover can easily perform a constructive self-reduction. Suppose $q$ is a separable qudit, by definition, there exists a non-trivial decomposition $\mathcal{H}^{q}=\bigoplus_{j}\mathcal{H}_{j}^{q}$ such that all the terms $\{h_{i}\}_{i}$ keep the decomposition invariant. Then there must be a subspace $\mathcal{H}_{j_{0}}$ which contains a common $0$-eigenstate of $\{h_{i}\}_{i}$. Denote the projector onto $\mathcal{H}_{j_{0}}^{q}$ as $\Pi_{j_{0}}$. The prover can give the decomposition $\mathcal{H}^{q}=\bigoplus_{j}\mathcal{H}_{j}^{q}$ and the index $j_{0}$. The verifier checks that $q$ is a separable qudit, then restricts the space of $q$ from $\mathcal{H}^{q}$ to $\mathcal{H}_{j_{0}}^{q}$, and restricts all terms $\{h_{i}\}_{i}$ to $\{h_{i}^{<j_{0}>}:=\Pi_{j_{0}}h_{i}\Pi_{j_{0}}\}_{i}$, and ask the prover to prove that $\{h_{i}^{<j_{0}>}\}_{i}$ has a common $0$-eigenstate. By definition of separable, the decomposition is non-trivial, thus the new instance $\{h_{i}^{<j_{0}>}\}_{i}$ is strictly simpler in the sense that we strictly decrease the dimension of the qudit $q$. Note that this method is constructive — the common $0$-eigenstate of the new instance $\{h_{i}^{<j_{0}>}\}_{i}$ is also the common $0$-eigenstate of the original instance $\{h_{i}\}_{i}$.

Our key observation is, for qudit-CLHP-projection, even for semi-separable qudit, the NP prover is able to perform a similar self-reduction, via a non-constructive way. If we follow the intuition of the separable qudit case, one might try restricting $\mathcal{H}^{q}\rightarrow\mathcal{H}^{q}_{j}$, and transform every term to be $\Pi_{j}h_{i}\Pi_{j}$. The problem is that since $h_{0}$ does not keep $\mathcal{H}^{q}_{j}$ invariant, and does not commute with $\Pi_{j}$, the $\Pi_{j}h_{0}\Pi_{j}$ is no longer a projection. One may also doubt whether the resulting Hamiltonian is commuting. A more serious problem is that, unlike the case for separable qudit, since $h_{0}$ does not keep $\mathcal{H}^{q}_{j}$ invariant, it is not clear how to connect the ground states of the original Hamiltonian to the ground states of the new Hamiltonian. We circumvent the problems by slightly changing the construction — rounding $\Pi_{j}h_{0}\Pi_{j}$ to its $1$-eigenspace.

Note that the construction of reduced Hamiltonian is consistent with our previous intuition for the separable qudit — If $q$ is separable and $h_{0}$ also keeps $\mathcal{H}^{q}_{j}$ invariant, then $\Pi_{j}h_{0}\Pi_{j}$ is a projection thus $h_{0}^{(j)}=\Pi_{j}h_{0}\Pi_{j}$. It is worth noting that the reduced Hamiltonian keeps the “geometry” of the original Hamiltonian: