1 Introduction↩︎

Commuting local Hamiltonians have been studied  [1]–[6] across condensed matter physics, quantum information theory, and computational complexity. From the perspective of constraint satisfaction, commuting local Hamiltonians sit at a boundary between classical and quantum problems. When all local terms commute, the ground-state problem reduces to the simultaneous satisfaction of a family of local constraints [1], analogous to a classical constraint satisfaction problem (CSP). Indeed, many commuting Hamiltonians admit ground states that can be described efficiently in classical terms, such as product states, stabilizer states, or tensor network states of bounded bond dimension [7]. The computational complexity of commuting Hamiltonians is thus significantly more tractable than that of general noncommuting models, with many cases lying in the classical complexity class \(\mathsf{NP}\) [1], [5], [6]. In condensed matter physics, commuting Hamiltonians serve as exactly solvable models that capture the essential structure of entire phases of matter. Prominent examples include stabilizer Hamiltonians for quantum error-correcting codes (e.g., the toric code [8]), commuting-projector models for topological order [9], and fracton models with constrained dynamics [10].

Formally, the \(k\)-local commuting Hamiltonian problem consists of Hamiltonians of the form \[\begin{align} H=\sum_{i=1}^m h_i \quad \text{ such that } \quad [h_i,h_j]=0, \quad\quad \forall i,j=1,\dots,m \, \end{align}\] where all of the terms pair-wise commute⁴ and each term is of unit norm \(\|h_i\|\leq 1\) acting on at most \(k\) qubits. Commuting Hamiltonians retain intrinsically quantum features that sharply distinguish them from classical CSPs: although all of the Hamiltonian terms \(\{h_i\}_{i=1}^m\) can be simultaneously diagonalized, the common eigenbasis may not be a product basis, and the ground states may exhibit long-range entanglement and topological order, such as the toric code [8]. From a complexity-theoretic perspective, this places commuting Hamiltonians in an intermediate regime between classical satisfiability and fully quantum local Hamiltonians, providing a test ground for difficult problems such as the quantum PCP conjecture [2], [11], the NLTS conjecture [12], Gibbs state preparation [13] and fast thermalization [14].

1.0.0.1 Almost commuting Hamiltonians.

Despite their utility, commuting Hamiltonians represent a highly nongeneric limit. Physical systems are rarely exactly commuting, and even infinitesimal noncommuting perturbations can produce dramatic qualitative changes. This motivates the study of almost commuting Hamiltonians, in which local terms fail to commute but only do so weakly; for example, when the Hamiltonian terms pair-wise "\(\varepsilon\)-almost commute" such that \[\begin{align} \|[h_i,h_j]\| \leq \varepsilon, \quad\quad \forall i,j=1,\dots,m. \end{align}\] Such Hamiltonians capture a much richer range of physical phenomena, including entanglement generation, slow dynamics, and emergent conservation laws [15]. Almost commuting Hamiltonians arise naturally in systems exhibiting emergent integrability, prethermalization, or many-body localization. A simple and illustrative example is the transverse-field Ising model in the weak-field regime [15], described by the \(2\)-local qubit Hamiltonian \[\begin{align} \label{eq:ising} H = -\sum_{\langle i,j \rangle} Z_i Z_j - h \sum_i X_i \, , \end{align}\tag{1}\] with \(h \ll 1\). At \(h=0\), the Hamiltonian consists of exactly commuting terms and reduces to a classical Ising model with product-state ground states. Turning on a weak transverse field introduces local noncommuting terms whose pairwise commutator norms \(\|[Z_i Z_j,hX_k]\|\) scale with \(h\) whenever \(i=j\) or \(j=k\), resulting in an almost commuting Hamiltonian. Even mild noncommutativity can cause the underlying physics to change qualitatively: the ground state becomes entangled, quantum fluctuations lift degeneracies, and the system supports nontrivial correlations absent in the commuting limit [16]. This illustrates how almost commuting Hamiltonians interpolate between classical constraint satisfaction and genuinely quantum many-body behavior.

The weak transverse-field Ising model might suggest that any almost commuting Hamiltonian can always be identified as a simple perturbation of an underlying commuting model. However, this intuition can be misleading in general. While the perturbation theory [17] perspective is useful in identifying approximately commuting structure in very special or integrable models, this relies on strong assumptions—such as a known commuting parent Hamiltonian or small, easily identifiable model parameters—which may not be present in generic local Hamiltonians.

From a computational standpoint, almost commuting Hamiltonians occupy a compelling intermediate regime. At first sight, they appear no longer classically reducible; and yet they are far from fully quantum Hamiltonians. Understanding whether their ground states and low-energy properties retain some of the tractability of commuting models—or instead exhibit the full hardness of general quantum constraint satisfaction problems—remains an intriguing open question.

1.0.0.2 Making almost commuting matrices commute.

A naive idea for handling almost commuting systems, in general, is to simply discard Hamiltonian terms until the remainder commute; for example, one could consider the anti-commutation graph whose vertices correspond to Hamiltonian terms and whose edges connect pairs that fail to commute, and then try to find a maximum independent set (or some efficient approximation) [18]. The resulting Hamiltonian, obtained by retaining only the corresponding subset of terms, is exactly commuting by construction. However, this approach does not exploit the magnitude of the noncommutativity: its error is determined solely by how many terms are removed. In the worst case, even when all \(\varepsilon\)-almost commute for a small \(\varepsilon >0\), the procedure may discard a constant fraction of the terms, leading to a vacous approximation error that scales with \(m\) (the number of Hamiltonian terms) with no improvement as \(\varepsilon \to 0\). In contrast, a meaningful rounding procedure for almost commuting Hamiltonians should be \(\varepsilon\)-sensitive, with an error that decreases as the commutators become smaller. This suggests that an \(\varepsilon\)-sensitive rounding procedure must do more than just pruning a noncommuting interaction graph: it must exploit the algebraic structure of the Hamiltonian terms themselves.

A more sophisticated angle of attack for dealing with a set of almost commuting matrices is to explicitly find nearby commuting matrices; for example, given a pair of two matrices \[\begin{align} A,B \in \mathbb{C}^{d \times d}\quad \text{ with } \quad \|[A,B]\| \leq \varepsilon \end{align}\] one might try to "round" to \(\hat{A},\hat{B}\) such that \([\hat{A},\hat{B}]=0\) with \(\|\hat{A}-A\| \leq \delta(\varepsilon)\) and \(\|\hat{B}-B\| \leq \delta(\varepsilon)\), for some \(\delta(\varepsilon)\) such that \(\delta(\varepsilon) \rightarrow 0\) as \(\varepsilon\rightarrow 0\). The mathematical problem of rounding almost commuting matrices has a long and subtle history. For pairs of Hermitian matrices, Lin’s theorem [19] guarantees that rounding is indeed possible, and quantitative bounds on \(\delta(\varepsilon)\) were later given by Hastings [20], [21]. Surprisingly, the same is not possible for triplets of Hermitian matrices, as shown by Davidson [22] and also by Hastings and Loring [23] who gave further topological obstructions towards rounding in terms of the Bott index. These results suggest that large collections of almost commuting Hermitian matrices can, in general, not be rounded to nearby commuting matrices unless further structure is enforced, hindering a direct application to almost commuting Hamiltonians. Nevertheless, many physically relevant non-commuting local Hamiltonians are semi-classical, and may very well be close to a commuting Hamiltionian, as the weak transverse-field Ising model in 1 suggests. This raises the question:

Progress on this question could shed new light on the extent to which weak noncommutativity is essential for the observed physics, versus merely a perturbation of an underlying commuting structure. Moreover, from a complexity perspective, it would allow us to better understand the boundary between classical satisfiability and inherently quantum optimization problems.

1.1 Our contributions↩︎

In this work, we overcome prior limitations on rounding approximately commuting Hermitian matrices which have so far hindered applications to many-body Hamiltonians. We develop a locality-preserving algorithmic rounding technique which allows us to simultaneously round large collections of almost commuting Hermitian matrices—avoiding the regimes where general no-go results apply—by exploiting the special structure of physical many-body Hamiltonians:

• (Locality:) Interactions in physical many-body Hamiltonians tend to be local in the sense that they involve a constant number of particles at a time; consequently, each term in the Hamiltonian is actually a highly non-generic Hermitian operator: it only acts non-trivially on a few sub-systems at a time and is equal to the identity everywhere else.

• (Dimensionality:) Many-body Hamiltonians tend to involve particles whose Hilbert space carries a fixed local dimension. In the case of two-level qubit systems (or "spin systems"), such constrained dimensionality can give rise to very useful properties, such as the fact that commutation between Hermitian single-qubit operators becomes transitive: if \(A,B\) commute and \(B,C\) commute, then \(A\) and \(C\) must also commute, provided that \(B\) is not a multiple of the identity.⁵ In higher dimensions, this property can fail due to degenerate eigenspaces.⁶

Our rounding technique exploits these physical constraints, and allows us to efficiently approximate any almost commuting \(2\)-local Hamiltonian by a nearby commuting one, while preserving locality. This is captured by our main result, which we informally state below.

To the best of our knowledge, this yields the first algorithmic rounding technique for almost commuting \(2\)-local qubit Hamiltonians which produces an explicit, quantitative error bound that vanishes as \(\varepsilon \rightarrow 0\), unlike naive methods that fail to take the magnitude of the noncommutativity into account ⁷. As a direct consequence of our rounding result, we show the following:

This extends the classical \(\mathsf{NP}\) containment result of Bravyi and Vyalyi [1] well beyond the commuting setting. In addition, the above theorem also implies a new no-go result in the context of quantum PCPs [2], [11] akin to [24]. Specifically, it suggests that any qPCP-hard family of \(2\)-local qubit Hamiltonians must exhibit some moderate amount of noncommutativity: assuming \(\mathsf{NP} \neq \mathsf{QMA}\), any family of \(2\)-local qubit Hamiltonians for which the \(\gamma\)-LH problem is \(\QMA\)-hard for constant \(\gamma\) must allow for pairwise commutator norms of \(\omega(\frac{1}{m^6})\).

More broadly, this places almost commuting Hamiltonians in an intermediate regime between classical constraint satisfaction and fully quantum optimization. It shows that, at least for \(2\)-local qubit systems, the onset of \(\mathsf{QMA}\)-hardness requires a quantitatively meaningful departure from the algebraic structure of commuting models, thereby linking a complexity-theoretic transition to a concrete operator-algebraic measure of noncommutativity.

1.2 Applications↩︎

As an application of our rounding technique for almost commuting quantum many-body systems, we present two algorithmic applications; the first one in the context of quantum Gibbs sampling and the second in the context of Hamiltonian simulation.

1.2.0.1 Quantum Gibbs sampling.

The Gibbs ensemble connects microscopic descriptions of physical systems with their macroscopic thermodynamic behavior, allowing one to compute quantities such as free energies, effective partition functions, and equilibrium expectation values [15], [25]–[32]. Given a local Hamiltonian \(H\) and an inverse temperature \(\beta > 0\), the Gibbs state is given by the density operator \[\begin{align} \label{eq:gibbs-ex} \rho_\beta(H) = \frac{e^{-\beta H}}{\mathrm{Tr}\left[e^{-\beta H}\right]}. \end{align}\tag{2}\] A recent line of work [33]–[37] has proposed quantum algorithms for preparing such thermal states. Although these methods can offer theoretical speedups [36], [37], their performance typically hinges on either mixing-related characteristics or temperature-dependent quantities that are challenging to estimate or control in realistic settings.

A prominent category of Gibbs sampling tasks—one which typically admits polynomial-time algorithms with provable guarantees [38], [39]—is the commuting case, where \(H\) is a commuting Hamiltonian. By leveraging the Structure Lemma [1], recent work [38] showed that Gibbs sampling for large classes of commuting Hamiltonians even reduces to Gibbs sampling for certain classical Hamiltonians; these in turn can admit powerful classical methods such as Swendsen-Wang dynamics [40], [41]. While the commuting case has been widely studied, only little is known about the non-commuting case, let alone the almost commuting case.⁹ Currently, all existing quantum Gibbs sampling methods fail to take such almost commuting structure into account; in particular, the techniques for the commuting case are known to break down in the presence of (even mild) non-commuting interactions. This raises the question: is it possible to extend quantum Gibbs sampling techniques for commuting Hamiltonians towards almost-commuting Hamiltonians?

In 6.2, we give an affirmative answer to this question: we use our rounding technique to reduce Gibbs sampling for certain almost commuting \(2\)-local Hamiltonians to Gibbs sampling to a nearby commuting Hamiltonian, thereby allowing one to once again make use of the full toolbox for the commuting case [38], [39]. Moreover, we show that a standard continuity bound on the stability of the Gibbs state suffices to ensure that the reduction is sound, and indeed approximately samples from the target state in 2 .

1.2.0.2 Faster Hamiltonian simulation.

Simulating quantum-mechanical systems is one of the central tasks in quantum algorithms. It is well known that Trotter-based Hamiltonian simulation methods can perform better in the presence of commutativity in the Hamiltonian. In fact, for an exactly commuting Hamiltonian, the runtime of Hamiltonian simulation can be logarithmic in the simulation time \(t\) (as explained in 8), unlike the linear or worse scaling in the general case. This makes commutativity a useful algorithmic resource for real-time dynamics, not only a simplifying structural assumption for ground-state problems. For Hamiltonians that do not exactly commute, prior investigations [42] have shown that commutator bounds can lead to faster Trotter-based simulation algorithms. Our setting is complementary: rather than analyzing the Trotter error directly, we first round the Hamiltonian to a nearby commuting one and then simulate the remaining discrepancy separately.

In 6.3, we observe that our rounding, together with the "interaction picture" method of Low and Wiebe [43], gives us a way to directly leverage the first-order commutators alone to speed up Hamiltonian simulation. In a nutshell, we apply the algorithm of [43] with the fast part of the Hamiltonian being the commuting rounding, and the slow part being the error term incurred in the rounding. Intuitively, the system is evolved mostly under a nearby exactly commuting Hamiltonian, while the genuinely noncommuting remainder is treated as a perturbation in the interaction picture. Importantly, our simulation algorithm scales only with the norm of the latter term, as well as the commutator error, rather than with the total norm of the Hamiltonian. In this way, the simulation cost is governed by how far the Hamiltonian is from the commuting regime, rather than by the full norm of the Hamiltonian itself.

1.3 Related work↩︎

The work of [44] studied projections that pairwise nearly commute and used a predecessor (see Theorem 3.2 [44]) of the pinching technique we extend here. However, their techniques do not preserve the locality of the operators, and hence do not apply in our setting.

The specific question of rounding approximately commuting Hamiltonians to commuting Hamiltonians was first studied by Arad [24]. In this work, it is shown that for two-local Hamiltonians on \(d\)-dimensional qudits, whose terms are projectors, an "asymptotically good" rounding exists: that is, in the limit of the commutator error \(\varepsilon\) going to \(0\), the rounding error also goes to \(0\). However, the rounding is non-constructive and no explicit bound on the rounding error was established. Arad’s techniques also do not easily lend themselves to algorithmic rounding, since they are based on a nonconstructive compactnesss argument inspired by a work of Halmos [45]. The rounding results in [24] are incomparable to ours: they are weaker in that they only apply to Hamiltonians whose terms are projectors; at the same time, they are also more general in that they apply to local dimensions greater than \(2\) as well. We remark that Arad’s proof also makes use of local decompositions of the Hamiltonian terms, similar to the Pauli decompositions that we exploit. Comparing our results to his, we consider our main contribution to be the locality-preserving algorithmic rounding theorem with an explicit polynomial bound on the rounding error given by our analysis—to our knowledge, the first constructive rounding technique with an explicit error bound in terms of \(\epsilon\) that goes to zero as \(\epsilon \rightarrow 0\). In fact, coming up with such a bound was listed by Arad as an open question, with the suggestion that it might follow easily from the techniques of [46]. This latter paper belongs to the rich literature on rounding approximately commuting high-dimensional matrices. We do not believe this literature is directly useful or relevant to our problem because we are interested specifically in roundings that preserve the local structure of the Hamiltonian.

Turning to complexity theory, our work connects to the extensive literature on commuting local Hamiltonians. Beginning with the result of Bravyi and Vyalyi [1] that commuting \(2\)-local qubit Hamiltonians lie in \(\NP\), subsequent works have extended \(\NP\) containment results to broader commuting settings, including higher-locality qubit systems, certain qutrit systems, two-dimensional geometries, and more general interaction complexes [2]–[6]. The central contribution of this work is to extend this viewpoint beyond exact commutativity. We show that sufficiently almost commuting \(2\)-local qubit Hamiltonians can be rounded to nearby commuting Hamiltonians, thus extending the classical containment well beyond the commuting setting.

1.4 Technical Overview↩︎

Let us now proceed with a technical overview of the result in this paper. We assume familiarity with the basic formalism of quantum information, and refer the reader to Section 2 for a refresher.

To illustrate our rounding technique, we consider the simple (although already non-trivial¹⁰) example of an \(\varepsilon\)-almost-commuting \(2\)-local Hamiltonian on a three-qubit triangle, i.e. \[\begin{align} H = h_{1,2} + h_{1,3} + h_{2,3} \, , \end{align}\] where the \(i,j\) terms pair-wise \(\epsilon\)-almost commute such that \[\begin{align} \| [h_{1,2},h_{1,3}]\| \leq \varepsilon\, , \quad \| [h_{1,3},h_{2,3}]\| \leq \varepsilon\quad\,\,\, \text{ and } \quad \| [h_{1,2},h_{2,3}]\| \leq \varepsilon \end{align}\] for some \(\varepsilon\in (0,1)\). The goal is to identify an exactly commuting Hamiltonian \(\hat{H} = \hat{h}_{1,2} + \hat{h}_{13} + \hat{h}_{1,3}\) with \([\hat{h}_{1,2},\hat{h}_{1,3}] = [\hat{h}_{1,3},\hat{h}_{2,3}] = [\hat{h}_{1,2},\hat{h}_{2,3}] = 0\), which inherits the locality of the original Hamiltonian, and which is nearby in the sense that \[\begin{align} \| h_{1,2} - \hat{h}_{1,2}\| \leq \delta(\varepsilon) \, , \quad\| h_{13} - \hat{h}_{1,3}\| \leq \delta(\varepsilon), \quad\,\,\, \text{ and } \quad \| h_{2,3} - \hat{h}_{2,3}\| \leq \delta(\varepsilon) \end{align}\] for some function \(\delta(\varepsilon)\) with the property that \(\delta(\varepsilon) \rightarrow 0\) as \(\varepsilon\rightarrow 0\).

Let us first consider the Hamiltonian terms \(h_{1,2}\) and \(h_{1,3}\). Using a local expansion in terms of the Pauli basis \(\{\sigma^{(i)}\}_{i=0}^3\) given in 6, we can expand the Hamiltonian terms in \(H\) as follows:¹¹ \[\begin{align} h_{1,2} &= \sum_{\alpha=0}^3 A^{(\alpha)}_1 \otimes \sigma_2^{(\alpha)} \tag{3}\\ h_{1,3} &= \sum_{\beta=0}^3 B^{(\beta)}_1 \otimes \sigma_3^{(\beta)} \tag{4} \end{align}\] for some collections of Hermitian matrices \(\{A_1^{(\alpha)}\}_\alpha\) and \(\{B_1^{(\beta)}\}_\beta\) in \(\mathbb{C}^{2 \times 2}\). Since we know that \(\|[h_{1,2},h_{1,3}]\| \leq \varepsilon\), it is tempting to argue that the almost-commuting property must also "propagate" down to the collections of matrices \(\{A^{(\alpha)}\}_\alpha\) and \(\{B^{(\beta)}\}_\beta\). In 6, we show that this is indeed the case, leveraging the fact that \(\{\sigma^{(i)}\}_{i=0}^3\) form an orthogonal basis of the space of \(2\times 2\) complex matrices under the Hilbert-Schmidt inner product. Concretely, we can argue that \[\begin{align} \label{eq:almost-commuting-A-B} \|[A_1^{(\alpha)}, B_1^{(\beta)}]\| \leq \varepsilon, \quad \forall \alpha,\beta=0,1,2,3. \end{align}\tag{5}\] This observation allows us to effectively reduce the task of rounding a \(2\)-qubit operator to that of rounding a collection of single-qubit operators; in other words, the goal now is to find nearby matrices \(\{\hat{A}_1^{(\alpha)}\}_\alpha\) and \(\{\hat{B}_1^{(\beta)}\}_\beta\) which perfectly pairwise commute i.e. \([\hat{A}_1^{(\alpha)}, \hat{B}_1^{(\beta)}]=0\), for all \(\alpha,\beta\).

1.4.0.1 Pinching.

How can we make two almost-commuting \(2 \times 2\) Hermitian matrices commute? Here, we take inspiration from the well-known pinching technique for projectors (e.g. [44]). Suppose that \(A,B \in \mathbb{C}^{2 \times 2}\) are arbitrary Hermitian matrices such that \(\|[A,B]\| \leq \varepsilon\); for example, as in 5 . First, we observe that the spectral theorem allows us to expand the matrix \(A\) as \[\begin{align} A = \lambda_{\min}(A) \, \Pi + \lambda_{\max}(A) \, (I -\Pi), \end{align}\] where \(\lambda_{\min},\lambda_{\max} \in \mathbb{R}\) are eigenvalues and \(\Pi\) and \((I -\Pi)\) are orthogonal projectors onto the eigenspaces. To pinch \(B\) by \(A\) (concretely, by the eigenspace projectors associated with \(A\)), we map \[\begin{align} \label{eq:ex-pinchining} B \quad \mapsto \quad \hat{B} = \Pi \, B \, \Pi + (I-\Pi) B (I-\Pi). \end{align}\tag{6}\] Because \(\hat{B}\) is now diagonal in the eigenbasis of \(A\), we can see that \([\hat{B},A]=0\), and hence the two matrices perfectly commute. Moreover, a simple argument (formally proven in 2) reveals that the distance between \(\hat{B}\) and \(B\) is at most \[\begin{align} \label{eq:pinching-for-B} \|\hat{B} - B\| \, \leq \, \frac{\|[A,B]\|}{\Delta(A)} \, \leq \, \frac{\varepsilon}{\Delta(A)} \, , \end{align}\tag{7}\] where \(\Delta(A) = |\lambda_{\max}(A) - \lambda_{\min}(A)|\) is the spectral gap of \(A\). This immediately presents a problem: if the eigenvalues of \(A\) are extremely close to one another, the spectral gap \(\Delta(A)\) can be vanishingly small, thereby causing the distance between \(\hat{B}\) and \(B\) to blow up. In general, we may not have any control over the spectral properties that arise from the Pauli decompositions in 3 and 4 .

1.4.0.2 Gap or snap?

In order to explain how we get around the spectral gap issue, let us again revisit the example of two Hermitian matrices \(A,B \in \mathbb{C}^{2 \times 2}\) with \(\|[A,B]\| \leq \varepsilon\). We introduce a threshold parameter \(\eta \in (0,1)\) (to be determined later) and distinguish between the following cases:

• (the gapped case) \(\Delta(A) \geq \eta\): in this case, the spectrum of \(A\) is sufficiently gapped, and the pinching bound in 7 translates into a well-behaved upper bound of \(\|\hat{B} - B\| \leq \, \frac{\varepsilon}{\eta}\).

• (the nearly-degenerate case) \(\Delta(A) < \eta\): in this case, the pinching bound in 7 may blow up; fortunately, however, a small gap \(\Delta(A)\) necessarily means that \(A\) must also be close to a multiple of the identity. Instead of pinching \(B\), we can simply snap \(A\) towards \(\hat{A} = \lambda_{\max}(A) I\). Importantly, this makes \(\hat{A}\) trivially commute with not just \(B\) but in fact any other matrix as well—an important fact we will crucially exploit later on. A simple calculation (formally shown in 3) reveals that \(\|\hat{A} - A\|\) is at most \(\Delta(A)\), and thus \(\|\hat{A} - A\| < \eta\).

For example, letting \(\eta = \sqrt{\varepsilon}\), we can always find a nearby commuting matrix within distance \(\sqrt{\varepsilon}\); either by pinching \(B\) to get \(\hat{B}\) such that \([\hat{B},A]=0\) and \(\|\hat{B} - B\| \leq \frac{\varepsilon}{\eta} = \sqrt{\varepsilon}\), or by snapping \(A\) to get \(\hat{A}\) such that \([B,\hat{A}]=0\) and \(\|\hat{A} - A\| < \eta = \sqrt{\varepsilon}\). Note that the \(2 \times 2\) qubit structure in the "gap or snap" approach for \(A,B \in \mathbb{C}^{2 \times 2}\) is crucial; indeed, in the qudit case, it is entirely possible for operators to have no spectral gap at all, and yet at the same time it is also not possible to simply "snap" them towards the identity.

1.4.0.3 Locality-preserving rounding.

Equipped with the "gap or snap" paradigm, we explain a slightly simplified version of our full locality-preserving rounding technique on the \(\varepsilon\)-almost commuting Hamiltonian \(H = h_{1,2} + h_{1,3} + h_{2,3}\) from before. (We will indicate the step that was simplified when we reach it in our explanation.) To this end, we once again use local expansions in terms of the Pauli basis \(\{\sigma^{(i)}\}_{i=0}^3\). While our earlier expansions in 3 and 4 only involved one of the qubit systems, our full rounding technique makes use of Pauli expansions on both of the qubits; that is, for each of the terms \(h_{12}, h_{13}\) and \(h_{23}\), we consider both possible expansions as follows: \[\begin{align} h_{1,2} &= \sum_{\alpha=0}^3 A^{(\alpha)}_1 \otimes \sigma_2^{(\alpha)} = \sum_{\alpha=0}^3 \sigma^{(\alpha)}_1 \otimes A_2^{(\alpha)} \quad\quad\quad \text{ for } \quad \{A_1^{(\alpha)}\}_{\alpha=0}^3\, , \quad \{A_2^{(\alpha)}\}_{\alpha=0}^3\quad\tag{8}\\ h_{1,3} &= \sum_{\beta=0}^3 B^{(\beta)}_1 \otimes \sigma_3^{(\beta)} = \sum_{\beta=0}^3 \sigma^{(\beta)}_1 \otimes B_3^{(\beta)} \quad\quad\quad \,\text{ for } \quad \{B_1^{(\beta)}\}_{\beta=0}^3\, , \quad \{B_3^{(\beta)}\}_{\beta=0}^3\quad\tag{9} \\h_{2,3} &= \sum_{\gamma=0}^3 C^{(\gamma)}_2 \otimes \sigma_3^{(\gamma)} = \sum_{\gamma=0}^3 \sigma^{(\gamma)}_2 \otimes C_3^{(\gamma)} \quad\quad\, \,\,\,\,\,\text{ for } \quad \{C_2^{(\gamma)}\}_{\gamma=0}^3\, , \quad \{C_3^{(\gamma)}\}_{\gamma=0}^3 \quad\tag{10} \end{align}\] For convenience’ sake, we refer to the left decomposition in 8 as the decomposition "about qubit \(1\)", and the right decomposition in the same equation as the decomposition "about qubit \(2\)"—and similarly for the others. Note that each expansion introduces a collection of four Hermitian matrices in \(\mathbb{C}^{2 \times 2}\): in the decomposition "about qubit \(i\)", these four matrices act on qubit \(i\). In a slight abuse of notation, we use the same variable and rely on the subscript to indicate which qubit the matrices act on, as well as which of the two sets of matrices we are referring to. Thanks to our previous insight that the \(\varepsilon\)-almost-commuting property of \(h_{1,2}, h_{1,3}\) and \(h_{2,3}\) "propagates" down to the collections of matrices acting on the same qubit (formally, 6), we get \[\begin{align} \|[A_1^{(\alpha)}, B_1^{(\beta)}]\| &\leq \varepsilon, \quad\quad \forall \alpha,\beta=0,1,2,3 \tag{11}\\ \|[A_2^{(\alpha)}, C_2^{(\gamma)}]\| &\leq \varepsilon, \quad\quad \forall \alpha,\gamma=0,1,2,3 \tag{12}\\ \|[B_3^{(\beta)}, C_3^{(\gamma)}]\| &\leq \varepsilon, \quad \forall \beta,\gamma=0,1,2,3\tag{13} \end{align}\] We may visualize the commutation structure of the triangle Hamiltonian as a graph \(G=(V,E)\); here the vertex set \(V\) consists of the \(24\) matrices in 8 , 9 10 , and \(E\) contains edges between vertex pairs which are \(\varepsilon\)-almost commuting according to 11 , 12 and 13 . We can group vertices belonging to the same Hamiltonian term together, and we can use a top and bottom vertex layer within each cluster to represent the two possible Pauli expansions (e.g., see 2).

Choose \(\eta =\varepsilon^{1/3}\). Then, our locality-preserving rounding technique takes place as follows:

1. (Partitioning:) Split the almost-commuting Hamiltonian \(H\) into a gapped and nearly-degenerate part (depending on \(\eta\)) such that \(H= H_{\mathrm{gap}} + H_{\mathrm{deg}}\), where

   • \(H_{\mathrm{gap}}\) features Hamiltonian terms for which both sets of the two possible Pauli expansions contain a matrix of spectral gap of at least \(\eta\) (these particular matrices will enable us to round to nearby commuting matrices via pinching), and

   • \(H_{\mathrm{deg}}\) features Hamiltonian terms that do not satisfy the gap condition: morally, these terms act "almost trivially" on at least one of the qubits they touch.

2. (Snap:) For each term in \(h_{i,j} \in H_{\mathrm{deg}}\), we use snapping to round it to a term that is exactly trivial on at least on qubit. Concretely, suppose \(h_{1,2}\) is in \(H_{\mathrm{deg}}\) because its decomposition \[h_{1,2} = \sum_{\alpha=0}^{3} A_1^\alpha \otimes \sigma_2^{(\alpha)}\] is not gapped—that is, each matrix \(A_1^\alpha\) has spectral gap smaller than \(\eta\). Then snapping simply consists of replacing each \(A_1^\alpha\) in the decomposition with the appropriate multiple of identity, yielding a new operator \(h'_{1,2}\) that is effectively 1-local, and may in fact be simply a multiple of the identity. As a simplifying assumption, we will suppose that all the post-snapping operators \(h'_{i,j}\) are in fact multiples of identity: the general case including 1-local operators is more cumbersome, requiring an additional round of snapping with a larger gap parameter, but conceptually no more difficult than this special case. Let \(H'\) be \(H\) after snapping has been performed (with all the terms in \(H_{\mathrm{gap}}\) unchanged). This step incurs an error of \(O(\eta)\).

3. (Gap:) We are now in the position that for every Hamiltonian term that acts nontrivially on a qubit, the operators in its Pauli decomposition for that qubit are guaranteed to have a spectral gap. Intuitively, the spectral gap means these operators have a "strong opinion" about the correct basis in which to pinch this qubit, and our algorithm will listen to them. More precisely, for any qubit \(i\) that is nontrivially acted on by at least two terms of \(H'\), pick any gapped operator in the decomposition "about qubit \(i\)" of the terms acting on \(i\), and set it to be the pivot \(R_i\) associated with \(i\). (If a qubit does not have two nontrivial terms, set the pivot to be identity.) Once a pivot has been identified for each qubit, pinch each Hamiltonian term \(h'_{i,j}\) simultaneously by the pivots \(R_i\) and \(R_j\): mathematically, \[h'_{i,j} \mapsto \hat{h}_{i,j} = (\mathcal{P}_i \otimes \mathcal{P}_j)(h'_{i,j}),\] where \(\mathcal{P}_i\) is the pinching superoperator given by \[\begin{align} \label{eq:pinching-superoperator-overview} \mathcal{P}_i(X) = \Pi_i \, X \, \Pi_i + (I-\Pi_i) X (I-\Pi_i)\, \end{align}\tag{14}\] and where \(\Pi_i\) and \(I-\Pi_i\) are the eigenspace projectors of the \(i\)-th pivot element. The Hamiltonian \(\hat{H} = \sum_{(i,j)} \hat{h}_{i,j}\) is the final product of our rounding procedure.

   After the pinching process is complete, it is easy to see that all the terms \(\hat{h}_{i,j}\) are forced to commute with each other by construction. What is harder to see is that this does not incur a large error. This is essentially for two reasons:

   • Propagation: If we imagine pinching \(h'_{i,j}\) by a pivot arising from a different Hamiltonian term \(h'_{i,k}\), then this pivot is guaranteed to almost commute—up to error \(\varepsilon\)—with all terms in the decomposition of \(h'_{i,j}\) by the fact that \(h'_{i,j}\) and \(h'_{i,k}\) approximately commute, together with 6.

   • Transitivity: If we imagine pinching \(h'_{i,j}\) by a pivot arising from the same Hamiltonian term \(h'_{i,j}\), then this pivot can be shown to almost commute with all other terms in the decomposition of \(h'_{i,j}\) by using the transitivity of commutation for gapped matrices, by passing through another term \(h'_{i,k}\). This is illustrated in 2. The transitivity uses the gapped property of \(h'_{i,k}\), and yields a slightly worse commutator error of \(\varepsilon/\eta\).

   Thus, the pivot by with we pinch a given Hamiltonian term commutes with that term up to error at most \(\kappa = \varepsilon/\eta\), and it can be shown that the error induced in pinching is at most \(O(\kappa / \eta) = O(\varepsilon/\eta^2)\). (We refer to 7 for a formal analysis of the pinching operation.) Our choice of \(\eta = \varepsilon^{1/3}\) balances the errors from the gap and snap steps, giving us an overall error of \(O(\varepsilon^{1/3})\). In the more general case, where our simplifying assumption in the snapping step is removed, it turns out a second round of snapping is needed: this introduces a further error, so our final bound in the general case turns out to be \(O(\varepsilon^{1/6})\).

Notice that the Hamiltonian \(\hat{H}\) inherits the same locality from the original Hamiltonian \(H\); this is due to the local nature of our pinching and snapping techniques. In 8, we show that our rounding technique—when applied to the triangle Hamiltonian—yields an exactly commuting Hamiltonian \(\hat{H} = \hat{h}_{1,2} + \hat{h}_{2,3} + \hat{h}_{1,3}\) with \([\hat{h}_{1,2},\hat{h}_{1,3}] = [\hat{h}_{1,3},\hat{h}_{2,3}] = [\hat{h}_{1,2},\hat{h}_{2,3}] = 0\) and \[\| H - \hat{H} \| \, \leq \, O(\varepsilon^{1/6}).\] Our rounding technique thus rests on two important structural facts: (i) approximate commutation of Hamiltonian terms propagates to the single-qubit operators in their Pauli decompositions, and (ii) pinching against gapped local pivots enforces exact commutation while preserving locality. In this sense, our procedure is a consistent local change of basis across the interaction graph, with snapping handling terms which are too close to the identity to select a stable basis.

1.4.0.4 Concrete \(3\)-qubit example.

We now illustrate the rounding procedure on a concrete triangle Hamiltonian on three qubits, shown in 3.

The terms \(h_{1,2}\) and \(h_{2,3}\) commute exactly: both are controlled on the shared qubit, qubit \(2\), in the standard basis. On the other hand, \(h_{1,3}\) acts in the \(X\) basis on qubits \(1\) and \(3\), and therefore commutes only approximately with \(h_{1,2}\) and \(h_{2,3}\); the obstruction comes from the \(Z\)-basis components of \(h_{1,2}\) and \(h_{2,3}\), whose coefficients are suppressed by the factor \(1/100\).

This example is useful because it rules out a naïve sequential approach to rounding. One might try first to round the already commuting pair \(h_{1,2},h_{2,3}\) to an exactly commuting pair \(\hat{h}_{1,2},\hat{h}_{2,3}\), without taking \(h_{1,3}\) into account, and only afterwards try to round \(h_{1,3}\) to some \(\hat{h}_{1,3}\) that commutes with both of them. However, for the particular pair \(h_{1,2},h_{2,3}\) above, there is no operator on qubits \(1\) and \(3\) that acts nontrivially on both qubits and commutes exactly with both \(h_{1,2}\) and \(h_{2,3}\). Thus any successful rounding must modify at least one of \(h_{1,2}\) or \(h_{2,3}\), despite the fact that these two terms commute perfectly with each other. This illustrates why the rounding procedure must be global in nature: the choice of how to round one pair of terms cannot be made independently of the remaining interactions.

Let us now see how the one-shot rounding procedure handles this example. All three terms are gapped in the relevant sense in both of their possible Pauli decompositions, so the partitioning and snapping steps are trivial. The only nontrivial part of the procedure is the gapped rounding step, in which we choose a pivot operator \(A_i\) for each qubit \(i\) and then pinch the Hamiltonian terms with respect to these pivots.

We begin with qubit \(2\). The terms acting on qubit \(2\) are already written in the appropriate form, with the Pauli operators placed on the non-shared qubits \(1\) and \(3\): \[\begin{align} h_{1,{\color{blue}2}} &= {\color{blue}(\ket{0}\!\bra{0})_2} \otimes X_1 + \frac{1}{100} {\color{blue}(\ket{1}\!\bra{1})_2} \otimes Z_1, \\ h_{{\color{blue}2},3} &= {\color{blue}(\ket{0}\!\bra{0})_2} \otimes X_3 + \frac{1}{100} {\color{blue}(\ket{1}\!\bra{1})_2} \otimes Z_3. \end{align}\] Thus we may choose either \(\ket{0}\!\bra{0}\) or \(\ket{1}\!\bra{1}\) as the pivot on qubit \(2\); these choices define the same eigenbasis. We take \[A_2 = (\ket{0}\!\bra{0})_2 .\]

Next consider qubit \(1\). The term \(h_{1,3}\) is already expressed in the desired form, while \(h_{1,2}\) must be rewritten so that the Pauli operators act on the non-shared qubit \(2\): \[\begin{align} h_{{\color{red}1},2} &= \frac{1}{2} {\color{red}\left(X + \frac{1}{100} Z\right)_1} \otimes I_2 + \frac{1}{2} {\color{red}\left(X - \frac{1}{100} Z\right)_1} \otimes Z_2, \\ h_{{\color{red}1},3} &= {\color{red}X_1} \otimes X_3 . \end{align}\] There are several possible gapped choices for the pivot. For simplicity, we take \[A_1 = X_1 .\]

Finally, for qubit \(3\), we proceed in the same way: \[\begin{align} h_{2,\textcolor{DarkGreen}{3}} &= \frac{1}{2} I_2 \otimes \textcolor{DarkGreen}{\left(X + \frac{1}{100} Z\right)_3} + \frac{1}{2} Z_2 \otimes \textcolor{DarkGreen}{\left(X - \frac{1}{100} Z\right)_3}, \\ h_{1,\textcolor{DarkGreen}{3}} &= X_1 \otimes \textcolor{DarkGreen}{X_3}. \end{align}\] Again, we choose the convenient pivot \[A_3 = X_3 .\]

With these choices of pivots, the pinching step is especially transparent: it forces the Hamiltonian to be diagonal in the tensor-product basis defined by the \(X\) basis on qubit \(1\), the standard basis on qubit \(2\), and the \(X\) basis on qubit \(3\). The rounded Hamiltonian \[\hat{H} = \hat{h}_{1,2} + \hat{h}_{1,3} + \hat{h}_{2,3}\] is therefore given by \[\begin{align} \hat{h}_{1,2} &= X_1 \otimes \ket{0}\!\bra{0}_2, \\ \hat{h}_{1,3} &= X_1 \otimes X_3, \\ \hat{h}_{2,3} &= \ket{0}\!\bra{0}_2 \otimes X_3. \end{align}\] These three terms now commute exactly.

1.4.0.5 The role of transitivity.

This simple example also illustrates the role played by transitivity of commutation for \(2 \times 2\) matrices. As discussed above, transitivity is what allows the rounding procedure to control commutation relations among different operators appearing in the Pauli decomposition of a single Hamiltonian term. In the present example, this control is reflected in the fact that the small \(Z\)-components in \(h_{1,2}\) and \(h_{2,3}\) are compatible with the choice of \(X\)-basis pivots on qubits \(1\) and \(3\).

One way to see this is to ask what would happen if the coefficient \(1/100\) in \(h_{1,2}\) were replaced by \(1\). Then \(h_{1,2}\) and \(h_{2,3}\) would still commute exactly, since they would remain diagonal in the same basis on the shared qubit \(2\). However, the commutator between \(h_{1,2}\) and \(h_{1,3}\) would become large. In fact, \(h_{1,2}\) would no longer commute with any operator on qubits \(1\) and \(3\) that acts nontrivially on both qubits. Thus the smallness of the noncommuting component is essential: it is precisely what permits the global choice of pivots to round all three terms simultaneously.

1.4.0.6 Generalizing to \(m\) Hamiltonian terms.

The same mechanism extends from this triangle example to general \(2\)-local qubit Hamiltonians with \(m\) terms. Rather than choosing a rounding separately for each pair of Hamiltonian terms, the algorithm chooses pivots at the level of individual qubits. Each Hamiltonian term is then pinched with respect to the pivots on the qubits it touches. This one-shot choice is what preserves locality while enforcing exact commutation globally: once all of the terms are diagonal in the local bases specified by the pivots, every pair of rounded terms now commutes exactly.

The example above captures the main reason such a global procedure is needed. Even when two terms commute exactly, keeping them fixed may be incompatible with rounding the rest of the Hamiltonian. The rounding algorithm therefore treats the Hamiltonian as a whole, using the approximately commuting structure to identify local bases that are simultaneously compatible across all interactions.

1.5 Discussion and Future Work↩︎

The most natural immediate next questions to investigate are whether our rounding can be extended to systems of higher locality or local dimension. We suspect that going beyond qubits may be challenging, since the transitivity property that is crucial to our proof is no longer true for higher dimensions (even for dimension 3).

Another direction for generalization is to study looser notions of approximate commutation. For instance, what can we say if we only have a bound on the average norm of the commutators? Similar regimes were studied algorithmically in [39].

In the context of complexity theory, one interesting direction is to see what our result implies about the quantum PCP conjecture. Recall that our rounding result already implies that any qPCP-hard family of 2-local qubit Hamiltonians must exhibit some moderate amount of noncommutativity: assuming \(\mathsf{NP} \neq \mathsf{QMA}\), any family of \(2\)-local qubit Hamiltonians for which the \(\gamma\)-LH problem is \(\QMA\)-hard for constant \(\gamma\) must allow for pairwise commutator norms of \(\omega(\frac{1}{m^6})\). It would be interesting to see whether this bound can be improved, for instance by finding a better rounding technique with an improved dependence on \(\epsilon\).

Taking an alternate perspective, the complexity of the general \(k\)-local commuting Hamiltonian problem on qudits is wide open, and it is possible that some version of this problem is even qPCP-hard. Moreover, it is possible that gap-amplifying transformations for commuting Hamiltonians will be easier to design than for general Hamiltonians. Could some rounding scheme along the lines of ours show that gap amplification for commuting Hamiltonians directly implies the quantum PCP conjecture?

1.5.0.1 Acknowledgements.

Special thanks to Thomas Vidick for an inspirational email conversation at the start of this project. We also thank Christopher Laumann, Jiaqing Jiang, and Thomas Vidick for useful conversations on the general status for commuting and almost commuting Hamiltonians. We thank ChatGPT for the support with our literature review and the design of our figures. AN was partially supported by NSF CAREER Award 2339948.

2 Preliminaries↩︎

The \(d\)-dimensional complex vector space is denoted by \(\mathbb{C}^d\). We use \(\mathrm{L}(V,W)\) to denote the set of linear operators mapping between finite-dimensional complex vector spaces \(V\) and \(W\), and we use \(\mathrm{L}(\mathbb{C}^d)\) to denote the set of linear operators over \(\mathbb{C}^d\). The operator norm of a linear operator \(A \in \mathrm{L}(V,W)\), for some finite-dimensional complex vector spaces \(V \neq \{0\}\) and \(W\) is given by \[\begin{align} \|A \| = \sup_{\|x\|_2 =1} \|A x\|_2 \, , \end{align}\] where \(\|x \|_2 = \sqrt{\langle x,x \rangle}\) is the standard Euclidean norm; we occasionally omit the subscript for convenience. The operator norm satisfies the triangle inequality and is sub-multiplicative with \(\|A \cdot B\| \leq \|A\| \cdot \|B\|\), for all \(A,B \in \mathrm{L}(V,W)\). A linear operator \(A \in \mathrm{L}(\mathbb{C}^d)\) is called positive semi-definite (PSD), denoted by \(A \succeq 0\), whenever \(x^\dagger A x \geq 0\), for all \(x \in \mathbb{C}^d\), and where \(\dagger\) is the adjoint. A unitary \(U: \mathrm{L} (\mathbb{C}^d) \to \mathrm{L}(\mathbb{C}^d)\) is a linear operator such that \(U^\dagger U = U U^\dagger = I\), where \(I\) is the identity matrix on \(\mathbb{C}^d\). A linear operator \(H \in \mathrm{L}(\mathbb{C}^d)\) is called Hermitian if \(H^\dagger = H\). We use \(\mathrm{Herm}(C^{d})\) to denote the set of \(d\)-dimensional Hermitian matrices. A Hermitian operator \(\Pi \in \mathrm{Herm}(\mathbb{C}^{d})\) is called a projector if \(\Pi^2=\Pi\). Any \(A \in \mathrm{Herm}(\mathbb{C}^{2})\) admits a spectral decomposition of the form \[\begin{align} A = \lambda_1 \Pi + \lambda_2 (I -\Pi) \end{align}\] where \(\lambda_1,\lambda_2 \in \mathbb{R}\) are the eigenvalues of \(A\), and where \(\Pi\) and \((I-\Pi)\) are the projectors onto the respective eigenspaces of \(A\); we call the eigenvalue difference \[\begin{align} \Delta(A) := |\lambda_1 - \lambda_2| \end{align}\] the spectral gap of \(A\), and we say that \(A\) is \(\eta\)-gapped if \(\Delta(N) \geq \eta\).

2.0.0.1 Commutator.

Let \(A,B \in \mathbb{C}^{d \times d}\). Then, the commutator between \(A\) and \(B\) is defined as \[[A, B] := AB - BA.\] We say that \(A\) commutes with \(B\) (equivalently, \(B\) commutes with \(A\)) if \([A, B] = 0\) or \(AB = BA\). We say that \(A\) and \(B\) \(\varepsilon\)-almost commute if there exists \(\varepsilon>0\) such that \[\|[A,B]\| \leq \varepsilon\, ,\] where \(\|\cdot\|\) is the operator norm. We use the following elementary fact about the commutator.

We use the following well-known fact about commuting Hermitian matrices.

2.0.0.2 Spectral stability.

We use Weyl’s inequality (e.g., see [47]) which states that the eigenvalue spectra of Hermitian matrices remains stable under perturbations.

The following is a direct consequence of Weyl’s inequality in 1.

2.0.0.3 Quantum information.

A finite-dimensional complex Hilbert space is denoted by \(\mathcal{H}\), and we use subscripts to distinguish between different systems (or registers); for example, we let \(\mathcal{H}_{1}\) be the Hilbert space corresponding to the system labeled as \(1\). The tensor product of two Hilbert spaces \(\mathcal{H}_{1}\) and \(\mathcal{H}_{2}\) is another Hilbert space which we denote by \(\mathcal{H}_{1,2} = \mathcal{H}_{1} \otimes \mathcal{H}_{2}\).

A quantum system over the \(2\)-dimensional Hilbert space \(\mathcal{H} \cong \mathbb{C}^2\) is called a qubit; in general, when \(\mathcal{H} \cong \mathbb{C}^d\) for \(d \geq 2\), we call it a qudit. For \(n \in \mathbb{N}\), we refer to quantum registers over the Hilbert space \(\mathcal{H} \cong \big(\mathbb{C}^2\big)^{\otimes n}\) as \(n\)-qubit states. We use the word quantum state to refer to both pure states (unit vectors \(\ket{\psi} \in \mathcal{H}\)), as well as density matrices \(\rho \in \mathrm{D}(\mathcal{H})\) with \[\begin{align} \mathrm{D}(\mathcal{H}) = \{ \rho \in \mathrm{L}(\mathcal{H}) \, : \, \rho \text{ is Hermitian, \rho \geq 0 and } \mathrm{Tr}[\rho] =1\}. \end{align}\] Given a bipartite operator \(\rho_{1,2} \in \mathrm{D}(\mathcal{H}_{1,2})\), we denote the partial trace over a system, say the second system, by \(\mathrm{Tr}_2[\cdot]\), and we call \(\rho_1=\mathrm{Tr}_2[\rho_{1,2}]\) the reduced state. We use the following simple fact:

2.0.0.4 Pauli matrices.

The four \(2\times 2\) Pauli matrices are denoted as \[\begin{align} \sigma^{(0)} &= I = \begin{pmatrix} 1 & 0 \\0 & 1 \end{pmatrix}, \quad\quad\,\,\,\,\sigma^{(1)} = X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\\ \sigma^{(2)} &= Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad\quad \sigma^{(3)} = Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}. \end{align}\] Note that the Pauli matrices are all Hermitian, and therefore referred to as observables.

2.1 Local Hamiltonian Problem↩︎

We begin by recalling the promise-problem formulation of the local Hamiltonian problem. This language is convenient because local Hamiltonian problems naturally come with an energy gap promise: an instance is assumed to be either below a lower threshold or above an upper threshold, with no requirement on what happens in between.

We now specialize this general notion to the \(2\)-local Hamiltonian problem. Throughout the paper, we keep track of both the absolute promise gap and the relative promise gap, since the latter is the natural normalization when the Hamiltonian has \(m\) local terms.

The main objects of this paper are restricted versions of the local Hamiltonian problem in which the local terms commute, or nearly commute, with one another. The exactly commuting case serves as the classical benchmark against which we compare the almost commuting setting.

We also introduce the almost commuting analogue, where exact commutation is relaxed to a uniform operator-norm bound on all pairwise commutators. This is the promise problem to which our rounding theorem will later be applied.

2.2 Complexity Classes↩︎

We next recall the complexity-theoretic notions used to state our containment and hardness consequences. Since the local Hamiltonian problem is naturally a promise problem, we use the corresponding promise-problem formulations of \(\NP\) and \(\QMA\).

In contrast to \(\NP\), the class \(\QMA\) allows the verifier to receive a quantum witness and to perform a quantum verification procedure. This is the natural quantum analogue of \(\NP\) and is the complexity class captured by the general local Hamiltonian problem.

We will also use the standard notion of completeness for promise-problem complexity classes. In our setting, completeness is used to formalize the sense in which the local Hamiltonian problem captures the full difficulty of \(\QMA\).

Finally, we record the standard hardness statement for the \(2\)-local Hamiltonian problem in the relative-gap notation used throughout this paper. This result provides the baseline \(\QMA\)-hardness result against which our \(\NP\) containment for almost commuting Hamiltonians should be compared.

3 Commutativity in the World of Qubit Operators↩︎

In this section, we collect the qubit-specific facts that make the pinching step possible. We first define the pinching and snapping operations for single-qubit operators, and then prove the elementary norm bounds that control the errors they introduce. We also isolate the transitivity phenomenon for commuting qubit operators, which is one of the main algebraic features that fails in higher local dimension and is used crucially in our rounding argument.

3.1 Pinching by a Hermitian Qubit Operator↩︎

Equipped with 8, we now show the following result.

3.2 Snapping Hermitian qubit operators to multiples of the Identity↩︎

In this section, we formally introduce the mathematical background for the "snapping technique".

3.3 Transitivity of (Almost) Commutativity of Qubit Operators↩︎

The exact transitivity statement above is useful only after the relevant operators have been made exactly commuting. In the rounding argument, however, we typically know only that two local components almost commute with a common gapped pivot. The following lemma provides the corresponding robust version: if \(A\) and \(C\) each almost commute with a sufficiently gapped qubit operator \(B\), then \(A\) and \(C\) must almost commute with each other.

4 Local-to-Global Framework for Operators on \(2\) Qubits↩︎

In this section, we develop the local-to-global tools used in the rounding argument. The main point is that approximate commutation of two-qubit Hamiltonian terms can be detected at the level of the single-qubit operators appearing in their local Pauli decompositions. This allows us to translate global commutator bounds into local algebraic constraints, which will later be used to choose pivots, perform snapping, and preserve locality throughout the rounding procedure.

4.1 Local Pauli Decomposition↩︎

The following simple fact gives a decomposition of a two-qubit operator acting on qubits \(s\) and \(r\) into a sum of tensor product operators. Similar decompositions play a deep role in the theory of commuting Hamiltonians, for instance in Equation (1) of [2].

When working with local Pauli decompositions of two-qubit operators, it will be convenient for us to use the following notion of a gapped decomposition.

4.2 Global-to-Local Inheritance of Norms of Commutators↩︎

Let \(h_{s,r}\) and \(h_{s,q}\) be \(2\) Hamiltonian terms on a shared qubit with index \(s\) such that they \(\varepsilon\)-almost commute i.e. \(\|[h_{s,r}, h_{s,q}]\| \leq \varepsilon\). Let their local components on the shared qubit be \(\{A^{(\alpha)}\}\) and \(\{B^{(\beta)}\}\). An important question for our techniques is: what can we say about the commutator of any pair \(\|[A^{(\alpha)}, B^{(\beta)}]\|\)? We will prove in 6 that any pair of local components must also \(\varepsilon\)-almost commute. For that proof, we will use [lem:opnorm-orthog-components].

4.3 Snapping a \(2\)-local Hamiltonian term into \(1\)-local Hamiltonian term↩︎

5 Rounding Almost Commuting \(2\)-Local Qubit Hamiltonians↩︎

In this section, we prove the main result of our paper: any almost commuting \(2\)-local Hamiltonian (on qubits) can be mapped to a nearby exactly commuting (qubit) Hamiltonian of the same locality. The proof of our main result uses a technical helper lemma (7), which we formally state and prove later in this section.

6 Applications to Almost Commuting \(2\)-local Hamiltonians↩︎

In this section, we use our locality-preserving rounding technique (formally, 8 ) to show that the almost commuting \(2\)-local Hamiltonian problem lies in \(\mathsf{NP}\).

6.1 Containment in \(\NP\)↩︎

6.2 Quantum Gibbs sampling↩︎

As an application of our locality-preserving rounding technique for almost commuting quantum many-body Hamiltonians, we now consider the task of quantum Gibbs sampling. For a local Hamiltonian \(H\) and an inverse temperature \(\beta > 0\), the Gibbs state \[\begin{align} \label{eq:Gibbs-state} \rho_\beta(H) = \frac{e^{-\beta H}}{\mathrm{Tr}\left[e^{-\beta H}\right]} \end{align}\tag{22}\] describes the thermal equilibrium properties of a quantum system at finite temperature \(T=1/\beta\). Given a precision parameter \(\delta >0\), the \((H,\beta,\delta)\)-Gibbs state preparation (or sampling) task with respect to the Hamiltonian \(H\) and an inverse temperature \(\beta > 0\) is to output \(\rho\) such that \[\begin{align} \| \rho - \rho_\beta(H) \|_1 \leq \delta. \end{align}\]

6.2.0.1 Almost-commuting Hamiltonians.

Our rounding technique allows to reduce quantum Gibbs sampling for \(\varepsilon\)-almost-commuting \(2\)-local qubit Hamiltonians to the task of Gibbs sampling for a nearby commuting \(2\)-local qubit Hamiltonians, provided that \(\varepsilon\) is sufficiently small.

We use the following result on the continuity of the Gibbs state (with respect to the Hamiltonian) which is implicit in [50].

Equipped with the above technical fact, we can now show the following reduction.

We remark that our Gibbs sampling reduction for almost-commuting Hamiltonians above can be further combined with the reduction of [38], thereby reducing Gibbs sampling for (certain) almost-commuting \(2\)-local qubit Hamiltonians to Gibbs sampling of certain classical Hamiltonians.

6.3 Faster Hamiltonian simulation↩︎

Our result gives a method to speed up Hamiltonian simulation for approximately commuting Hamiltonians. The basic idea is to use the fact that time evolution of commuting Hamiltonians can be simulated very efficiently, since the matrix exponential factors into a product of exponentials of the individual terms. For short times, thus, one could simply round an approximately commuting Hamiltonian \(H\) to a commuting Hamiltonian \(H'\) with our technique, and simulate \(H'\) instead of \(H\). For longer times, the error incurred by this rounding may be prohibitive: for this more general case, we use can use the "interaction picture" formalism of Low and Wiebe [43], in essentially a black-box way, to add corrections from the rounding error.

As a first step, we show the following helper lemma which is essentially folklore.

We will now sketch how to use our rounding to perform Hamiltonian simulation. The main technical obstacle to directly applying a standard algorithm is the following: Hamiltonian simulation algorithms are typically given in the oracle model, where access to \(H\) is given through a unitary oracle \(O_H\) that implements a "block-encoding" of \(H\): \((\bra{0}\otimes I)O_H (\ket{0} \otimes I) \propto H\). However, in our setting, we need to work in a model where the Hamiltonian is given as explicit input (i.e. as a classical string containing descriptions of all the local terms), in order to apply our rounding algorithm. Indeed, implicit in the oracle picture is the assumption that for any realistic Hamiltonian, such an oracle can be implemented efficiently. So we will assume that we have a method to construct such a block encoding and leave its size as a parameter.

Our rounding says that \[H = H' + \Delta,\] where \(H'\) is a commuting Hamiltonian with \(\|H'\| := \alpha_A \leq m\), and \(\Delta\) is a local Hamiltonian with \(\|\Delta\| := \alpha_B \leq 216 m \varepsilon^{1/6}\). Moreover, \(H'\) and \(\Delta\) are efficiently computable from \(H\). To perform Hamiltonian simulation, suppose that once we have written down \(\Delta\), we can find a block encoding of \(\Delta/\alpha_B\) with gate complexity \(T_{block}\). Then we can apply the interaction picture algorithm of Low Wiebe. To calculate the gate complexity of the resulting circuit, we apply Theorem 7 from [43] with \(H'\) as the "fast" part of the Hamiltonian and \(\Delta\) as the slow part. This theorem tells us that the gate complexity is \[O(\alpha_B t(C_B + C_A)\polylog(t(\alpha_A + \alpha_B)/\delta)),\] where the quantities \(C_A, C_B\) are as follows:

• \(C_B\) is the gate complexity of a block encoding of \(\Delta/\alpha_B\). By our assumption, this is \(T_{block}\).

• \(C_A\) is the gate complexity of a simulation of \(e^{-iH'/\alpha_B}\) up to error \(\delta\). By 8, we have that \(C_A = O(m \poly(\log(m/\delta), \log \alpha_B^{-1}))\). (In fact, it is also a requirement of the theorem that the gate complexity of a simulation of \(e^{-iH't}\) to error \(\eta\) should scale as \(O(t \log^{\gamma}(t/\eta))\) for some constant \(\gamma\), and this is also true for us by 8.)

Putting this together and ignoring polylogarithmic factors we get a gate complexity of \[\tilde{O}(m(T_{block} + m) \varepsilon^{1/6} t).\] The important feature of this expression is that it scales in the norm of \(\Delta\) and the commutator error, rather than in the total norm of the Hamiltonian.

References↩︎

---

1. islam@bu.edu↩︎

2. anandn@mit.edu↩︎

3. poremba@bu.edu↩︎

4. The commutator of two operators \(A\) and \(B\) is defined as \([A,B] = AB - BA\).↩︎

5. We prove this statement in 4.↩︎

6. For example, suppose that \(A\) and \(C\) act differently inside the same degenerate subspace of the matrix \(B\). Then, both matrices can commute with \(B\) but they need not commute with each other.↩︎

7. For a comparison with the results of [24], which considers non-constructive rounding, see Section 1.3.↩︎

8. Here we mean the difference in energy thresholds for the YES and NO cases of the local Hamiltonian problem. Note that in the formal satement of 1 we use the relative promise gap \(\gamma\), which is equal to the energy promise gap divided by \(m\).↩︎

9. We remark that Schmidhuber et al. [39] recently studied another form of "almost commuting" Hamiltonians; namely, signed Pauli Hamiltonians with a sparse anti-commutation graph. In their work, they provide evidence that Gibbs sampling and optimization for such almost commuting systems is classically intractible, hinting at potential quantum advantage of the HDQI algorithm. However, their notion of almost commuting Hamiltonians is different from ours, and hence our rounding algorithm does not apply in their setting.↩︎

10. We remark that prior no-go results on rounding general Hermitian matrices already apply to triplets [22].↩︎

11. Here, the subscript indicates the qubit and we omit single-qubit identity operators for ease of notation.↩︎

12. We technically define a promise version of \(\NP\). Historically, containment in \(\NP\) was defined when any binary string was either yes or no. That promise version of \(\NP\) has been recently widely adopted when talking about promise problems.↩︎

13. We have heard it credited to Lijie Chen, but it may be folkore.↩︎

14. Our definition of \(\gamma\)-2-CLH requires \(\gamma \geq 1/\poly(n)\).↩︎

15. Without that condition, we can only conclude that \(A\) and \(B\) can be simultaneously diagonalized and that \(B\) and \(C\) can be simultaneously diagonalized, but not necessarily all three can be simultaneously diagonalized. If \(B\) is a multiple of the identity, then any two non-commuting matrices will be a counterexample.↩︎

16. And polynomial in the bit complexity of each Hamiltonian term.↩︎

17. This convention is without loss of generality, since one can absorb all terms that act on a pair \(i,j\) into a single term at the start of the analysis.↩︎