Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.03697

On The Complexity of Redundancy-Free Quantum Hamiltonians

Matthew B. Hastings, Alexander Schmidhuber

quant-phSubmitted Oct 2, 2026• Announced Oct 5, 2026• 0 citations
arXivHTMLPDF

Abstract

We consider a class of redudancy-free Hamiltonians, which are those where the trace vanishes for any product of Hamiltonian terms in which at least one term appears an odd number of times. This includes Hamiltonians which are sums of products of Paulis with no relations between them. These Hamiltonians arise naturally in Hamiltonian Decoded Quantum Interferometry, which separates the hardness of preparing quantum states into two steps: a classical decoding step, and a step preparing the thermofield double state of such a redundancy-free Hamiltonian. We focus on the hardness of these Hamiltonians, both for intrinsic interest and to understand the complexity of the state preparation step in Hamiltonian DQI. We present several results showing that the problem becomes easy at quadratically lower temperature than for a general Hamiltonian, with the complexity at given inverse temperature $β$ depending on $β^2 d$, where $d$ is the degree of the anticommutation graph. We give an efficient classical algorithm for small $β^2 d$ to approximate the partition function, while for large $β^2 d$ we show that approximating the partition function is NP-hard. To this end, we introduce what we call an anticommutation glass, where frustration arises purely from anticommutation relations. We give a subexponential time quantum algorithm to prepare the thermofield state for small $β^2 d$, and present some results toward a polynomial time algorithm based on the Feiguin-Klich Hamiltonian. As a result of possible independent interest, we show that this Hamiltonian leads to a polynomial time algorithm for preparing thermofield double states of general Hamiltonians on an interaction graph of degree $d$ for $β\lesssim 1/d$. Finally, we show that estimating the ground state energy of redundancy-free Hamiltonians is QMA-complete.

Comments
39 pages, 3 figures

Related papers

Hamiltonian Decoded Quantum Interferometry

Alexander Schmidhuber, Jonathan Z. Lu, Noah Shutty +3 more

We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding. For a signed Pauli Hamiltonian $H$ and any degree-$\ell$ polynomial ${P}$, HDQI prepares a purification of the density matrix $ρ_{P}(H) \propto {P}^2(H)$ by solving a combination of two tasks: decoding $\ell$ errors on a classical code defined by $H$, and preparing a pilot state that encodes the anti-commutation structure of $H$. Choosing $P(x)$ to approximate $\exp(-βx/2)$ yields Gibbs states at inverse temperature $β$; other choices prepare approximate ground states, microcanonical ensembles, and other spectral filters. For local Hamiltonians, the corresponding decoding problem is that of LDPC codes. Preparing the pilot state is always efficient for commuting Hamiltonians, but highly non-trivial for non-commuting Hamiltonians. Nevertheless, we prove that this state admits an efficient matrix product state representation for Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size. We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians -- including the toric code and Haah's cubic code -- but we also develop a matching efficient classical algorithm for this task. For a non-commuting semiclassical spin glass and commuting stabilizer Hamiltonians with quantum defects, HDQI prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical pre-processing. These results position HDQI as a versatile algorithmic primitive and the first extension of Regev's reduction to non-abelian groups.

arXiv:2510.07913•Oct 9, 2025•0 citations

Hamiltonian Decoded Quantum Interferometry for General Pauli Hamiltonians

Kaifeng Bu, Weichen Gu, Xiang Li

In this work, we study the Hamiltonian Decoded Quantum Interferometry (HDQI) for the general Hamiltonians $H=\sum_ic_iP_i$ on an $n$-qubit system, where the coefficients $c_i\in \mathbb{R}$ and $P_i$ are Pauli operators. We show that, given access to an appropriate decoding oracle, there exist efficient quantum algorithms for preparing the state $ρ_{\mathcal P}(H) = \frac{\mathcal P^2(H)}{\text{Tr}[\mathcal P^2(H)]}$, where $\mathcal P(H)$ denotes the matrix function induced by a univariate polynomial $\mathcal P(x)$. Such states can be used to approximate the Gibbs states of $H$ for suitable choices of polynomials. We further demonstrate that the proposed algorithms are robust to imperfections in the decoding procedure. Our results substantially extend the scope of HDQI beyond stabilizer-like Hamiltonians, providing a method for Gibbs-state preparation and Hamiltonian optimization in a broad class of physically and computationally relevant quantum systems.

quant-pharXiv:2601.18773•Jan 27, 2026•0 citations

On Efficiently Solvable Cases of Quantum k-SAT

Marco Aldi, Niel de Beaudrap, Sevag Gharibian +1 more

Abstract Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is $$\hbox {QMA}_1$$ QMA 1 -complete (for $$k\ge 3$$ k ≥ 3 , and where $$\hbox {QMA}_1$$ QMA 1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But whereas k-SAT has been well-studied for special tractable cases, as well as from a “parameterized complexity” perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state. Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or clauses. (2) We give a “parameterized algorithm” for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry.

arXiv:1712.09617•Communications in Mathematical Physics•Dec 24, 2020•5 citations

Quantum Gibbs State Preparation via Relative Decoding: From Fast-Mixing Sources to Broader Target Classes

Zhong-Xia Shang, Yufei Wang, Daniel Stilck França

Provable guarantees for preparing quantum Gibbs states, such as rapid mixing or gapped coherent preparation paths, are known only for restricted Hamiltonian families and usually must be re-derived for each new family. Building on homomorphic polynomial transduction, a generalization of decoded quantum interferometry (DQI) and Hamiltonian DQI (HDQI), we show how relative decoding transfers such a guarantee from a source Hamiltonian $H_A$ to a target $H_B$. Writing each Hamiltonian as a sum of $m$ Pauli terms, the subsets of terms whose product is proportional to the identity, its relations, form a binary linear code, $K_A$ for the source and $K_B$ for the target, with the Pauli-label matrix as parity-check matrix as in DQI. Starting from the canonical thermofield double (TFD) of $H_A$, a Bell transform, a reversible label map, and a coherent decoder for the quotient code $K_B/K_A$ prepare an approximate TFD of $H_B$, and hence its Gibbs state. Because this decoder only resolves target relations absent from the source, the reachable inverse temperature is set by the relative distance $d_{\rm rel}$, the fewest terms in any such relation. It can far exceed the ordinary distance $d_{\rm ord}$, the fewest terms in any target relation, which bounds the uniform exact decoding radius of DQI and HDQI. We show that linear $d_{\rm rel}$ with efficient decoding at linear radius certifies a constant inverse temperature. As an example, starting from a nearest-neighbor spin chain whose TFD is known to be preparable at every finite temperature, a sparse classical parity-check matrix yields bounded-degree, geometrically nonlocal, noncommuting targets with $d_{\rm ord}=3$ and $d_{\rm rel}=Θ(m)$. To our knowledge, this gives a new class of efficiently preparable TFDs.

quant-pharXiv:2610.06667•Oct 6, 2026•0 citations

On the complexity of estimating ground state entanglement and free energy

Sevag Gharibian, Jonas Kamminga

Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).

arXiv:2510.06796•Oct 8, 2025•0 citations

The Complexity of Single-Interaction Hamiltonians

Elad Hecker

We study the complexity of Local Hamiltonian problems under the restriction that every local term is an unweighted occurrence of the same fixed interaction. In the resulting Single-Interaction Hamiltonian (SIH) model, once the interaction is fixed, the Hamiltonian is specified entirely by its ordered interaction hypergraph. Our main technical tool is an exact compiler that converts any fixed finite alphabet of local interactions into a single interaction. On a designated auxiliary subspace, the compiled Hamiltonian reproduces the source Hamiltonian exactly, while the complete spectrum below a chosen separation scale is preserved with multiplicity. Combined with a finite-alphabet normalization, this gives a universal polynomial-time reduction from $k$-Local Hamiltonian to SIH$_{3k+3}$ up to a known global energy scale and inverse-polynomial approximation. Sharper constructions give QMA-completeness of SIH$_3$ and of geometrically local SIH$_8$ with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH$_3$ and QMA-completeness of 1-Pinned Stoq-SIH$_4$. We also establish hardness results for uniformly system-size-dependent interactions and derive single-interaction formulations of the Hamiltonian quantum PCP conjecture, frustration-free, exponentially precise, and guided Local Hamiltonian problems. These results show that independently chosen local matrices and independently tunable coupling strengths are not necessary for a broad range of Hamiltonian-complexity phenomena.

quant-pharXiv:2609.39592•Oct 1, 2026•0 citations
We consider a class of redudancy-free Hamiltonians, which are those where the trace vanishes for any product of Hamiltonian terms in which at least one term appears an odd number of times. This includes Hamiltonians which are sums of products of Paulis with no relations between them. These Hamiltonians arise naturally in Hamiltonian Decoded Quantum Interferometry, which separates the hardness of preparing quantum states into two steps: a classical decoding step, and a step preparing the thermofield double state of such a redundancy-free Hamiltonian.
We focus on the hardness of these Hamiltonians, both for intrinsic interest and to understand the complexity of the state preparation step in Hamiltonian DQI. We present several results showing that the problem becomes easy at quadratically lower temperature than for a general Hamiltonian, with the complexity at given inverse temperature βββ depending on β2dβ^2 dβ2d, where ddd is the degree of the anticommutation graph. We give an efficient classical algorithm for small β2dβ^2 dβ2d to approximate the partition function, while for large β2dβ^2 dβ2d we show that approximating the partition function is NP-hard. To this end, we introduce what we call an anticommutation glass, where frustration arises purely from anticommutation relations. We give a subexponential time quantum algorithm to prepare the thermofield state for small β2dβ^2 dβ2d, and present some results toward a polynomial time algorithm based on the Feiguin-Klich Hamiltonian. As a result of possible independent interest, we show that this Hamiltonian leads to a polynomial time algorithm for preparing thermofield double states of general Hamiltonians on an interaction graph of degree ddd for β≲1/dβ\lesssim 1/dβ≲1/d. Finally, we show that estimating the ground state energy of redundancy-free Hamiltonians is QMA-complete.
We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding. For a signed Pauli Hamiltonian HHH and any degree-ℓ\ellℓ polynomial P{P}P, HDQI prepares a purification of the density matrix ρP(H)∝P2(H)ρ_{P}(H) \propto {P}^2(H)ρP​(H)∝P2(H) by solving a combination of two tasks: decoding ℓ\ellℓ errors on a classical code defined by HHH, and preparing a pilot state that encodes the anti-commutation structure of HHH. Choosing P(x)P(x)P(x) to approximate exp⁡(−βx/2)\exp(-βx/2)exp(−βx/2) yields Gibbs states at inverse temperature βββ; other choices prepare approximate ground states, microcanonical ensembles, and other spectral filters. For local Hamiltonians, the corresponding decoding problem is that of LDPC codes. Preparing the pilot state is always efficient for commuting Hamiltonians, but highly non-trivial for non-commuting Hamiltonians. Nevertheless, we prove that this state admits an efficient matrix product state representation for Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size. We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians -- including the toric code and Haah's cubic code -- but we also develop a matching efficient classical algorithm for this task. For a non-commuting semiclassical spin glass and commuting stabilizer Hamiltonians with quantum defects, HDQI prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical pre-processing. These results position HDQI as a versatile algorithmic primitive and the first extension of Regev's reduction to non-abelian groups.
In this work, we study the Hamiltonian Decoded Quantum Interferometry (HDQI) for the general Hamiltonians H=∑iciPiH=\sum_ic_iP_iH=∑i​ci​Pi​ on an nnn-qubit system, where the coefficients ci∈Rc_i\in \mathbb{R}ci​∈R and PiP_iPi​ are Pauli operators. We show that, given access to an appropriate decoding oracle, there exist efficient quantum algorithms for preparing the state ρP(H)=P2(H)Tr[P2(H)]ρ_{\mathcal P}(H) = \frac{\mathcal P^2(H)}{\text{Tr}[\mathcal P^2(H)]}ρP​(H)=Tr[P2(H)]P2(H)​, where P(H)\mathcal P(H)P(H) denotes the matrix function induced by a univariate polynomial P(x)\mathcal P(x)P(x). Such states can be used to approximate the Gibbs states of HHH for suitable choices of polynomials. We further demonstrate that the proposed algorithms are robust to imperfections in the decoding procedure. Our results substantially extend the scope of HDQI beyond stabilizer-like Hamiltonians, providing a method for Gibbs-state preparation and Hamiltonian optimization in a broad class of physically and computationally relevant quantum systems.
Abstract Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is QMA1\hbox {QMA}_1QMA1​ QMA 1 -complete (for k≥3k\ge 3k≥3 k ≥ 3 , and where QMA1\hbox {QMA}_1QMA1​ QMA 1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But whereas k-SAT has been well-studied for special tractable cases, as well as from a “parameterized complexity” perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state. Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or clauses. (2) We give a “parameterized algorithm” for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry.
Provable guarantees for preparing quantum Gibbs states, such as rapid mixing or gapped coherent preparation paths, are known only for restricted Hamiltonian families and usually must be re-derived for each new family. Building on homomorphic polynomial transduction, a generalization of decoded quantum interferometry (DQI) and Hamiltonian DQI (HDQI), we show how relative decoding transfers such a guarantee from a source Hamiltonian HAH_AHA​ to a target HBH_BHB​. Writing each Hamiltonian as a sum of mmm Pauli terms, the subsets of terms whose product is proportional to the identity, its relations, form a binary linear code, KAK_AKA​ for the source and KBK_BKB​ for the target, with the Pauli-label matrix as parity-check matrix as in DQI. Starting from the canonical thermofield double (TFD) of HAH_AHA​, a Bell transform, a reversible label map, and a coherent decoder for the quotient code KB/KAK_B/K_AKB​/KA​ prepare an approximate TFD of HBH_BHB​, and hence its Gibbs state. Because this decoder only resolves target relations absent from the source, the reachable inverse temperature is set by the relative distance dreld_{\rm rel}drel​, the fewest terms in any such relation. It can far exceed the ordinary distance dordd_{\rm ord}dord​, the fewest terms in any target relation, which bounds the uniform exact decoding radius of DQI and HDQI. We show that linear dreld_{\rm rel}drel​ with efficient decoding at linear radius certifies a constant inverse temperature. As an example, starting from a nearest-neighbor spin chain whose TFD is known to be preparable at every finite temperature, a sparse classical parity-check matrix yields bounded-degree, geometrically nonlocal, noncommuting targets with dord=3d_{\rm ord}=3dord​=3 and drel=Θ(m)d_{\rm rel}=Θ(m)drel​=Θ(m). To our knowledge, this gives a new class of efficiently preparable TFDs.
Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).
We study the complexity of Local Hamiltonian problems under the restriction that every local term is an unweighted occurrence of the same fixed interaction. In the resulting Single-Interaction Hamiltonian (SIH) model, once the interaction is fixed, the Hamiltonian is specified entirely by its ordered interaction hypergraph. Our main technical tool is an exact compiler that converts any fixed finite alphabet of local interactions into a single interaction. On a designated auxiliary subspace, the compiled Hamiltonian reproduces the source Hamiltonian exactly, while the complete spectrum below a chosen separation scale is preserved with multiplicity. Combined with a finite-alphabet normalization, this gives a universal polynomial-time reduction from kkk-Local Hamiltonian to SIH3k+3_{3k+3}3k+3​ up to a known global energy scale and inverse-polynomial approximation. Sharper constructions give QMA-completeness of SIH3_33​ and of geometrically local SIH8_88​ with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH3_33​ and QMA-completeness of 1-Pinned Stoq-SIH4_44​. We also establish hardness results for uniformly system-size-dependent interactions and derive single-interaction formulations of the Hamiltonian quantum PCP conjecture, frustration-free, exponentially precise, and guided Local Hamiltonian problems. These results show that independently chosen local matrices and independently tunable coupling strengths are not necessary for a broad range of Hamiltonian-complexity phenomena.