⚛️ quantum physics

On The Complexity of Redundancy-Free Quantum Hamiltonians

This paper investigates the computational complexity of redundancy-free quantum Hamiltonians, establishing that approximating their partition functions and preparing thermofield double states becomes tractable at lower temperatures compared to general Hamiltonians, while proving that estimating their ground state energy remains QMA-complete.

Original authors: Matthew B. Hastings, Alexander Schmidhuber

Published 2026-10-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthew B. Hastings, Alexander Schmidhuber

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of quantum physics, researchers often grapple with systems where the rules of the classical world break down. Imagine a collection of tiny magnets, each capable of pointing in multiple directions at once, interacting with their neighbors in ways that create a complex web of influence. When these magnets are heated or cooled, they settle into specific patterns of behavior, a state known as thermal equilibrium. Predicting how these systems behave, especially when they are large and the interactions are complicated, is one of the most difficult challenges in modern science. The difficulty often stems from "frustration," a condition where the system cannot satisfy all its internal desires simultaneously, leading to a chaotic jumble of possibilities. For decades, scientists have struggled to find efficient ways to simulate these states on computers, as the complexity tends to explode as the system grows.

A new study by Matthew B. Hastings and Alexander Schmidhuber explores a specific, simplified class of these quantum systems to understand where the line between solvable and unsolvable lies. They focus on a type of quantum system where the components interact in a very particular way: they are "redundancy-free." In these systems, the mathematical rules governing the interactions are so strict that no combination of parts can accidentally cancel each other out to create a trivial result. This lack of hidden shortcuts makes the system a pure testbed for studying the raw difficulty of quantum interactions. The researchers were motivated by a new computational technique called Hamiltonian Decoded Quantum Interferometry, which attempts to prepare these complex states by first creating a simplified version of the system and then decoding the results. The central question was whether this simplified version was inherently easier to handle, or if it retained the same impossible complexity as the original.

The authors discovered that the answer depends entirely on the temperature of the system and how many neighbors each part has. They found that for these redundancy-free systems, the problem becomes manageable at temperatures that are significantly higher than what is possible for general quantum systems. Specifically, while a typical complex system becomes too hard to simulate once the temperature drops below a certain threshold related to the number of connections, these special systems remain easy to simulate even when the temperature is much lower. The researchers proved that if the system is warm enough, a classical computer can efficiently calculate the properties of the system, such as its total energy distribution. However, they also showed that if the temperature drops too low, the problem suddenly becomes as hard as the most difficult puzzles in computer science, specifically becoming NP-hard for approximating the partition function and QMA-complete for estimating the ground state energy.

To understand why this happens, the team introduced a concept they call an "anticommutation glass." In a standard glass, like window glass, the atoms are frozen in a disordered state, creating a material that is rigid but lacks a repeating crystal structure. In this quantum version, the disorder does not come from random impurities or messy arrangements, but purely from the way the quantum parts refuse to cooperate with one another. When two parts try to interact, they sometimes push against each other in a way that prevents them from settling down easily. The researchers used numerical simulations to show that these systems exhibit a phenomenon called hysteresis, where the system gets stuck in a temporary state and refuses to find its true lowest energy state, much like a magnet that stays magnetized even after the external field is removed. This behavior confirms that the difficulty arises from the fundamental structure of the interactions, not from external noise.

The study also addressed the broader question of whether these simplified systems are truly representative of the hardest problems in quantum physics. The researchers proved that even with these strict rules removing all redundancies, the task of finding the lowest energy state remains as difficult as the most complex problems known to computer science. This means that the simplification does not strip away the essential hardness of the problem; it merely shifts the temperature at which that hardness becomes apparent. This finding is crucial for the development of quantum algorithms, as it suggests that while these systems are easier to handle at higher temperatures, they still retain the full power of quantum complexity at lower temperatures.

Furthermore, the paper provides a roadmap for how to prepare these states on a quantum computer. The authors demonstrated that for the range of temperatures where the problem is solvable, there is an efficient method to generate the desired quantum state. They showed that the correlations between distant parts of the system decay very quickly, allowing a computer to build the state piece by piece without needing to know the entire system at once. This is a significant improvement over methods for general systems, which require much higher temperatures to achieve the same level of efficiency. The researchers also proposed a potential path toward even faster algorithms using a specific mathematical construction, though they noted that proving this works for all cases remains an open challenge.

Ultimately, this work clarifies the boundary between what is computationally possible and what is not in the quantum realm. By isolating a class of systems where the only source of difficulty is the way parts refuse to commute, or swap places, the researchers have shown that the complexity of quantum states is not an accident of messy details but a fundamental feature of how these systems interact. The results suggest that while we can make progress on simulating these systems at higher temperatures, the deep, low-temperature regime remains a formidable frontier, requiring the full power of quantum mechanics to navigate. This insight helps scientists understand where to focus their efforts, knowing that the hardest problems are not just a matter of scale, but of the intrinsic nature of the quantum connections themselves.

Technical Summary: On The Complexity of Redundancy-Free Quantum Hamiltonians

Problem Definition
The paper investigates the computational complexity of a specific class of quantum Hamiltonians termed "redundancy-free." A Hamiltonian $H = \sum_i J_i O_i$ is defined as redundancy-free if the trace vanishes for any product of terms in which at least one term appears an odd number of times. This class includes Hamiltonians composed of sums of products of Pauli operators where no nontrivial product of the terms equals the identity (Pauli redundancy-free).

The primary motivation for studying these Hamiltonians arises from Hamiltonian Decoded Quantum Interferometry (HDQI). In HDQI, preparing the Gibbs state of a general Hamiltonian is reduced to two steps: (1) preparing a "pilot state" equivalent to the thermofield double (TFD) of a redundancy-free relaxation of the Hamiltonian, and (2) solving a classical decoding problem to remove redundancies. While the decoding step is well-understood, the complexity of preparing the pilot state (the TFD of the redundancy-free Hamiltonian) remained an open question. This work characterizes the hardness of this state preparation and the associated partition function approximation.

Methodology and Framework
The authors analyze the complexity as a function of the inverse temperature $\beta$ and the degree $d$ of the anticommutation graph $G$ . In this graph, vertices represent Hamiltonian terms $O_i$ , and edges exist between vertices $i$ and $j$ if $\{O_i, O_j\} = 0$ . The central parameter governing the complexity is $\kappa = \beta^2 d$ .

The paper employs several distinct methodologies:

Polymer Expansion: For small $\kappa$ , the authors utilize a polymer expansion of the free energy. They define polymers as connected subgraphs of the anticommutation graph and derive convergence conditions for the series expansion of the partition function.
Anticommutation Glass Construction: To establish hardness at large $\kappa$ , the authors construct a system called an "anticommutation glass." This system consists of two sets of operators (X-type and Z-type) with an invertible anticommutation matrix, creating frustration purely from anticommutation relations without classical redundancies.
Feiguin-Klich Hamiltonian: For state preparation, the authors explore the Feiguin-Klich Hamiltonian ( $H_{FK}$ ), a non-Hermitian operator whose ground state is the desired TFD. They analyze its spectral gap and the convergence of its power series expansion.
QMA-Hardness Reduction: To prove ground state energy hardness, the authors reduce the local Hamiltonian problem for antiferromagnetic XY models on triangular lattices to redundancy-free Hamiltonians. They employ a three-qubit encoding scheme to remove relations while preserving the ground state energy structure.

Key Results

1. Complexity of Partition Function Approximation

Small $\kappa$ (Easy Regime): The authors prove that for $\kappa$ sufficiently small (specifically $\beta \lesssim 1/\sqrt{d}$ ), the polymer expansion for the free energy converges. This yields an efficient classical algorithm to approximate the partition function with time complexity polynomial in the system size $n$ and error $\epsilon$ . This represents a quadratic improvement over general Hamiltonians, which are only tractable for $\beta \lesssim 1/d$ .
Large $\kappa$ (Hard Regime): Conversely, for sufficiently large $\kappa$ , approximating the partition function is shown to be NP-hard. The authors demonstrate that redundancy-free Hamiltonians can effectively encode arbitrary classical Ising models (with both ferromagnetic and antiferromagnetic interactions) into their partition functions. This is achieved by constructing an effective Ising model using the "basins" of the anticommutation glass.
Ground State Energy: Estimating the ground state energy of redundancy-free Hamiltonians is proven to be QMA-complete, even with bounded locality (at most 5) and bounded anticommutation degree (at most 26).

2. Quantum State Preparation

Subexponential Algorithm: For small $\kappa$ , the authors present a subexponential time quantum algorithm to prepare the thermofield double state. This relies on the decay of correlations, which is shown to be governed by $\kappa = \beta^2 d$ rather than $\beta d$ .
Polynomial Time for General Hamiltonians: While a polynomial-time algorithm for redundancy-free Hamiltonians at $\beta \lesssim 1/\sqrt{d}$ remains unproven, the authors provide a polynomial-time algorithm for preparing TFDs of general Hamiltonians on interaction graphs of degree $d$ for $\beta \lesssim 1/d$ . This algorithm utilizes the Feiguin-Klich Hamiltonian and relies on proving a spectral gap for sufficiently small $\beta d$ .

3. Physical Properties: Correlations and Entanglement

Correlation Decay: The paper establishes that correlations in redundancy-free Hamiltonians decay exponentially with distance, controlled by $\kappa = \beta^2 d$ . This decay is quadratically stronger in its dependence on $\beta$ compared to general Hamiltonians.
Entanglement: Despite being algorithmically tractable at $\beta \sim 1/\sqrt{d}$ , these Hamiltonians exhibit genuine quantum entanglement at much lower temperatures, specifically $\beta = O(1/d)$ . The authors construct explicit examples (including a canonical realization of a complete bipartite anticommutation graph) where the thermal state is entangled (NPT) at $\beta \sim 1/d$ , demonstrating that tractability does not imply separability.
Mutual Information: A strengthened bound on thermal mutual information is derived, showing a $\beta^2$ scaling for redundancy-free Hamiltonians compared to the linear $\beta$ scaling for general Hamiltonians.

Significance and Claims
The paper claims that redundancy-free Hamiltonians serve as a critical testbed for understanding the sources of hardness in quantum state preparation. The results suggest that Hamiltonian Decoded Quantum Interferometry (HDQI) may simplify the preparation of thermal states for certain Hamiltonians by shifting the computational burden to a redundancy-free relaxation that is "easy" at temperatures where the decoding step is efficient.

Specifically, the work provides evidence that:

The hardness of preparing TFDs is not solely due to classical redundancies but can arise purely from anticommutation relations (frustration).
There is a distinct "easy" regime for redundancy-free Hamiltonians ( $\beta \lesssim 1/\sqrt{d}$ ) that is quadratically larger than the easy regime for general Hamiltonians ( $\beta \lesssim 1/d$ ).
The "anticommutation glass" model captures the essential difficulty of general quantum Hamiltonians, as their ground state energy estimation remains QMA-complete.

The authors remain modest regarding the polynomial-time preparation of TFDs for redundancy-free Hamiltonians at $\beta \lesssim 1/\sqrt{d}$ , noting that while they provide a subexponential algorithm and a route toward polynomial time via the Feiguin-Klich Hamiltonian, a rigorous proof of the spectral gap in this regime for redundancy-free cases is left as future work. They explicitly state that their polynomial-time result for general Hamiltonians at $\beta \lesssim 1/d$ improves upon previous work by removing assumptions on lattice dimension.

More like this