Commuting Local Hamiltonians Beyond 2D

Our guided reductions will be constructed using the building block of “rounding schemes” (Definition 11) in which a Hamiltonian $H$ over a set of registers $𝖱={𝖱}_1\otimes \mathrm{\cdots }\otimes {𝖱}_n$ is “rounded” to a Hamiltonian $\tilde{H}$ over a possibly smaller space, as in Figure 1. In particular, $\tilde{H}$ is defined over registers $\widetilde{𝖱}={\widetilde{𝖱}}_{i_1}\otimes \mathrm{\cdots }\otimes {\widetilde{𝖱}}_{i_{\mathrm{\ell }}}$, with $\widetilde{𝖱}$ is a subspace of $𝖱$. As long as we can ensure $\tilde{H}$ remains commuting and has a zero-energy ground state if and only if $H$ does, this step will allow us to iteratively simplify the Hamiltonian. This idea of rounding projectors is not new (prior works such as [7, 15] can be viewed as implementing a rounding scheme). Our contribution, however, is to formalize this notion and introduce more general rounding schemes.

In [15], the authors devised a rounding scheme in the case where all but a single Hamiltonian term commutes with a set of projectors. In our work, we construct a rounding scheme which works even when there are two non-commuting terms, increasing the generality of this approach.

Our main insight behind this theorem is that in the case when only two local projectors survive, we can recover a commuting local Hamiltonian by projecting onto the non-zero blocks arising from the Jordan decomposition of the product of the two projectors. We can view this as an extension of the rounding scheme from [15] to pairs of projectors, where we look at blocks of size $2$ instead of size $1$. The use of Jordan’s Lemma requires a much more careful and detailed analysis of the commutative properties of Jordan blocks.

Our second technical result is a characterization of rank $1$ commuting Hamiltonians. The Structure Lemma can be viewed as providing a general scaffolding for how two operators can commute. When both operators are restricted to be rank $1$, we can strengthen the Structure Lemma to show that commutation occurs in one of two specific ways.

This result allows us to employ a strategy of “puncturing and repairing” paths through local Hamiltonians. In particular, we can partition the local terms adjacent to a qudit into two sets such that terms in each set interact only on the qudit. Within each set, if we find that the local terms commute in a singular way, we can show that the qudit is a so-called classical qudit and can be removed. In the case when the local terms commute in a reducing way, the prover can provide a pair of projector that removes all but two of the terms. The prover’s projectors essentially cuts a small patch into the local Hamiltonian, but leaves terms that no longer commute. We patch these holes using the rounding technique described previously, and by repeating this protocol we can cut long strings into geometrically local commuting Hamiltonians.

Our final contribution is a more detailed application of the triangulation technique of [3]. In particular, we use a technique we call “cubulation”, where we super-impose a 3D cubic lattice on top of a general polyhedral lattice. We subsequently use our cutting and repairing technique to remove Hamiltonian terms intersecting both the vertices and edges of the super-imposed cubic lattice, allowing us to reduce a 3D commuting local Hamiltonian problem to a 2-local problem, which is known to be in $\mathrm{𝖭𝖯}$.

We note that applying the cubulation technique to a general polyhedral lattice requires dealing with many different cases related to how the Hamiltonian terms intersect with the edges of the super-imposed lattice.

In Appendix A of the full version of the paper, we provide a simple model of verifiers that captures the complexity of commuting local Hamiltonians. As we discuss in the next subsection, we believe that demonstrating hardness for commuting local Hamiltonian problems is one of the most interesting directions of research related to commuting Hamiltonians. We admit that the model we provide does not make any progress towards this goal, but we hope that providing a tangible “complexity class” associated with commuting local Hamiltonians, we will at least provide a language that can be used to describe this problem.

In the 2-local setting of [7], every pair of terms $h,h^{\prime }$ either do not interact, or interact only on a single-qudit register $𝖱$. This means that for each register, a single decomposition $𝖱={\oplus }_i{𝖱}_i$ can be constructed so that every operators acts invariantly on the corresponding projectors ${\pi }_i\triangleq {({\pi }_i)}_{{𝖱}_i}$. Concretely, each term $h$ is block diagonal with respect to the subspaces ${𝖱}_i$. This decomposition naturally lends itself to a rounding scheme, where the projector is chosen to be one of the ${\pi }_i$’s. The resulting Hamiltonian is

Certainly ${\lambda }_0({\tilde{H}}_i)=0⟹{\lambda }_0(H)=0$. For the other direction, we use that for any CLH instance, ${\lambda }_0(H)=0\iff \mathrm{Tr}[{\prod }_j(𝕀-h_j)]={\sum }_i\mathrm{Tr}[{\prod }_h{\pi }_i(𝕀-h){\pi }_i]=0$. Moreover, since all $h$ commute with ${\pi }_i$, each trace in the sum is non-negative. Thus we get the following equivalent condition to the existence of a ground state:

The expression on the right is equivalent to existence of a zero-energy eigenstate for the Hamiltonian ${\tilde{H}}_i={\sum }_h{\pi }_{i}h{\pi }_i$, defined over registers $({𝖱}_1,\mathrm{\dots },{\pi }_i{𝖱}_i{\pi }_i,\mathrm{\dots },{𝖱}_n)$, where ${\pi }_i{𝖱}_i{\pi }_i\le {𝖱}_i$ is the sub-space generated by projecting vectors of ${𝖱}_i$ onto ${\pi }_i$. Thus, mapping $H\to {\tilde{H}}_i$ yields our desired rounding scheme. Crucially, the resulting Hamiltonian is also simpler than the original; the Structure Lemma tells us that ${𝖱}_i={\otimes }_h{𝖱}_i^{(h)}$ where each ${\pi }_{i}h{\pi }_i$ acts on non-trivially only on ${𝖱}_i^{(h)}$. This effectively decouples all terms on $𝖱$, as depicted in Figure 2.

For higher localities, the situation becomes more complicated. In general, if one has a 2D CLH instance with a $k$-wise interaction on a register $𝖱$, then commutation between adjacent terms is not entirely determined by the terms’ structure on $𝖱$. For instance, imagine $h=|1⟩⟨1|\otimes {\tilde{h}}_{𝖱}$ and $h^{\prime }=|0⟩⟨0|\otimes {\tilde{h}}_{𝖱}^{\prime }$; these terms commute regardless of our choice of $\tilde{h}$ and ${\tilde{h}}^{\prime }$! However, a variation of the above argument can be made to work.

Consider when $k=4$, as in Figure 3. Then the pairs $h_2$ and $h_4$ induce some decomposition $𝖱={\oplus }_i{𝖱}_i$, and pairs $h_1$ and $h_3$ induce a decomposition $𝖱={\oplus }_i{\widetilde{𝖱}}_i$. In general these decompositions are not the same. Let the projectors for these subspaces be ${\{{\pi }_i\}}_i$ and ${\{{\tilde{\pi }}_i\}}_i$. Then, rather than Equation 4, we get

As in the $2$-local case, this equivalence only holds when the traces on the RHS are non-negative. Fortunately, the two matrices

are both PSD, and $\mathrm{Tr}[AB]\ge 0$. Note that this is sensitive to ordering and the same may not hold if we order the terms as $h_1,h_2,h_3,h_4$. As this equivalence will be heavily used going forward, we formalize it in the following lemma.

Equation 5 is recovered by taking $S=\{1,2\}$ and $T=\{3,4\}$. This lemma therefore yields a statement equivalent to Equation 4. However, even with this equivalence it is not clear how to convert the right-hand-side into a CLH instance. Not only do the terms ${\tilde{\pi }}_j{h}_1{\tilde{\pi }}_j$ and ${\pi }_i{h}_2{\pi }_i$ not commute, we do not have a consistent subspace onto which can restrict $𝖱$.

Previous works dealt with this in a couple different ways. In [21], any non-trivial decomposition (i.e. $|{\{{𝖱}_i\}}_i|>1$) on qubits (so dimension 2 registers $𝖱$) requires $dim({𝖱}_i)=1$. Therefore,

For $h_2$ and $h_4$ we perform the same restriction as before:

After this step, ${\tilde{h}}_1$ and ${\tilde{h}}_3$ may no longer commute. However, notice that every term acts as $|\phi ⟩⟨\phi |$ on $𝖱$ and thus this register (which [21] calls a removable qudit) can traced out from the system. [21] shows that “puncturing” out all removeable qudits yields a 1-dimensional Hamiltonian. Thus, the author obtains a guided reduction (where the prover has provided ${\tilde{\pi }}_j$ and ${\pi }_i$) from 2-local qubit CLHs on the 2D lattice to 1-dimensional (non-commuting) local Hamiltonians. Such Hamiltonians can be easily seen to be contained in $\mathrm{𝖭𝖯}$.

It is not clear how to extend this argument beyond qudit dimension $d=2$, as the subspaces from the Structure Lemma are no longer 1 dimensional and thus the Hamiltonian terms may act non-trivially within each subspace. Still, [15] show that in the case of qutrits, Schuch’s techniques can be extended. One of their key insights is identifying semi-separable qutrits, which means that there is a non-trivial decomposition on which all but one term acts invariantly. In this case, [15] demonstrate a rounding technique which reduces the original Hamiltonian $H$ into another CLH instance $H^{\prime }$ with all semi-separable qutrits removed (the authors call this a “self-reduction”). Following this step, the Structure Lemma is applied and a careful casework of possible resulting decompositions of $H^{\prime }$ allow the authors to recover a 1D structure.

The key insight from [3] is that assuming enough terms are removed from a 2D CLH, the remaining system can be viewed as two local. For now, consider a 2D grid (where terms are on the faces and qubits are on edges), as all the key ideas can be seen from this restricted case. First, a triangulation is constructed over the 2D lattice (Figure 4(b)). This step does not depend on the underlying Hamiltonian, although the centers of the triangles should be selected as to reside within some Hamiltonian term. Then, paths are drawn from the center, through each edge of the triangle, and connecting an adjacent center. By construction, besides the center of the triangle, all terms are $2$-local. [3] deal with the $3$-local center terms by showing that arbitrary 2D qubit Hamiltonians are equivalent to a (generalization of) the Toric code. Using properties of the Toric code, [3] argue that the Hamiltonian contains enough “correctable” terms so that the triangle centers can be chosen to coincide with these correctable terms. These terms are removed, then corrected after preparing the ground state of the $2$-local Hamiltonian.

In the reduction to $2$-local Hamiltonians of [3], all that is really needed is a way create holes within each triangle. They accomplish this primarily through the removal of correctable terms. At a high level, we use our rounding scheme to puncture holes in the Hamiltonian in more varied ways, allowing us to apply the techniques from [3] in more general settings than qubit 2D CLH instances.

We accomplish this through analyzing the possible local algebras of rank-1 commuting operators via the Structure Lemma. In the simplest case, imagine there are only two operators acting non-trivially on a register $𝖱$. This is essentially the 2-local setting of [7]. There a simple consequence of the Structure Lemma is the following lemma.

As long as this subspace has non-zero overlap with the ground space, restricting our Hamiltonian to ${𝖱}_i$ punctures a “hole” in the geometric structure of the Hamiltonian, as in Figure 2. But like in the discussion in Section 2.1, this argument does not directly apply when interactions are more than $2$-local. To generalize this argument, we show that the local algebra of rank-1 commuting operators can be classified as reducing or singular where intuitively,

• $\mathrm{■}$

  If two operators commute in a reducing way, then in ${𝖱}_i$ at least one operator becomes the $0$-operator.

• $\mathrm{■}$

  If two operators commute in a singular way, then $dim{𝖱}_i=1$ and both act as a scalar.

For each combination of reducing and singular cases, we show that our rounding scheme yields a Hamiltonian where a hole has been punctured near $𝖱$ and thus a corner of the co-triangulation can be placed in this hole. A crucial part of this argument is that rounding schemes yield another CLH instance. This fact will be crucial in the 3D setting, where after an initial application of our rounding scheme, there are still “obstructions” in the 3D surface. However, these obstructions turn out to be $2$-local and, since our intermediate Hamiltonian is commuting, we may apply the Structure Lemma via Lemma 10 to remove the obstructions.

In comparison to previous techniques,

1. 1.

   The semi-separable self-reduction of [15] also retains commutativity. However, our reduction is more general and (assuming the rank-$1$ constraint) can be applied generically to single qudit register in the Hamiltonian.

2. 2.

   [21] reduction is also quite general, however, the final Hamiltonian generated is no longer commuting. This makes it hard to imagine how one would generalize their techniques to more complex structures, where one might want to perform the reduction recursively.

3. 3.

   The result of [3] is in some sense closest to ours; for any triangulation and center, they can find a term (or adjacent term) which is removable. However, their ideas rely on the exact characterization of 2D qubit Hamiltonians as related to the defected Toric code.¹¹1The defected Toric code is a generalization of the Toric code where real coefficients are permitted in front of each term.

The remainder of the paper is laid out as follows.

• $\mathrm{■}$

  In Section 4, we give the key technical tools we will need in this paper. In Section 4.1, we describe our rounding scheme, which allows us to reduce from a CLH instance to a “simpler” CLH instance. To apply this rounding scheme to rank-1 CLH instances, we will need our characterization of local algebras of rank-1 CLHs as singular and reducing. This is done in Section 5.

• $\mathrm{■}$

  Sections 6–7 apply the rounding scheme to various geometrically local instances of the commuting local Hamiltonian problem.

  • –

    In Section 6, we prove that 2D*-${\text{CLH}}^{(1)}$ is in $\mathrm{𝖭𝖯}$ (Theorem 24)

  • –

    In Section 7, we prove that 3D*-${\text{CLH}}^{(1)}$ is in $\mathrm{𝖭𝖯}$ (Theorem 26).

See full version for details. $◀$