We propose a Gibbs state preparation algorithm that exploits algebraic structure in the Hamiltonian. Our starting point is Hamiltonian Decoded Quantum Interferometry (HDQI), a recent algorithm that reduces Gibbs state preparation for Pauli Hamiltonians to decoding error-correcting codes. We introduce quantum decoding HDQI (QD-HDQI), replacing HDQI's coherent classical decoder by a quantum decoder that can exploit interference between different errors.
For commuting Pauli Hamiltonians, our reduction is efficient and the associated quantum decoding problem corresponds to transmitting the associated symplectic code over i.i.d. pure-state classical-quantum channels. For uniformly random Hamiltonian signs, the vanishing-error threshold of an efficient decoder directly determines the lowest temperature that our algorithm can reach. Even using only classical decoders, this improves upon HDQI's achievable inverse temperature from linear to square-root in the correctable error fraction; quantum decoders can improve further by tolerating still stronger noise. A similar picture extends to the noncommuting regime previously handled by HDQI, where now the noise is correlated within small, independent blocks.
We study two such quantum decoders in our QD-HDQI Gibbs sampling framework. The first, based on unambiguous state discrimination, works efficiently for arbitrary binary linear codes. However, we "dequantize" this strategy for commuting Hamiltonians, contributing a classical rejection sampler that matches its temperature threshold. The second is belief propagation with quantum messages (BPQM), a quantum generalization of classical belief propagation. We show that for certain dilute spin glasses, BPQM's decoding threshold exceeds the Shannon limit for classical decoding, reaching temperatures inaccessible to any classical decoder within our framework.
We propose a Gibbs state preparation algorithm that exploits algebraic structure in the Hamiltonian. Our starting point is Hamiltonian Decoded Quantum Interferometry (HDQI), a recent algorithm that reduces Gibbs state preparation for Pauli Hamiltonians to decoding error-correcting codes. We introduce quantum decoding HDQI (QD-HDQI), replacing HDQI's coherent classical decoder by a quantum decoder that can exploit interference between different errors.
For commuting Pauli Hamiltonians, our reduction is efficient and the associated quantum decoding problem corresponds to transmitting the associated symplectic code over i.i.d. pure-state classical-quantum channels. For uniformly random Hamiltonian signs, the vanishing-error threshold of an efficient decoder directly determines the lowest temperature that our algorithm can reach. Even using only classical decoders, this improves upon HDQI's achievable inverse temperature from linear to square-root in the correctable error fraction; quantum decoders can improve further by tolerating still stronger noise. A similar picture extends to the noncommuting regime previously handled by HDQI, where now the noise is correlated within small, independent blocks.
We study two such quantum decoders in our QD-HDQI Gibbs sampling framework. The first, based on unambiguous state discrimination, works efficiently for arbitrary binary linear codes. However, we "dequantize" this strategy for commuting Hamiltonians, contributing a classical rejection sampler that matches its temperature threshold. The second is belief propagation with quantum messages (BPQM), a quantum generalization of classical belief propagation. We show that for certain dilute spin glasses, BPQM's decoding threshold exceeds the Shannon limit for classical decoding, reaching temperatures inaccessible to any classical decoder within our framework.
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 HA to a target HB. 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, KA for the source and KB for the target, with the Pauli-label matrix as parity-check matrix as in DQI. Starting from the canonical thermofield double (TFD) of HA, a Bell transform, a reversible label map, and a coherent decoder for the quotient code KB/KA prepare an approximate TFD of HB, 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 drel, the fewest terms in any such relation. It can far exceed the ordinary distance dord, the fewest terms in any target relation, which bounds the uniform exact decoding radius of DQI and HDQI. We show that linear 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=3 and drel=Θ(m). To our knowledge, this gives a new class of efficiently preparable TFDs.
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-ℓ polynomial P, HDQI prepares a purification of the density matrix ρP(H)∝P2(H) by solving a combination of two tasks: decoding ℓ 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.
In this work, we study the Hamiltonian Decoded Quantum Interferometry (HDQI) for the general Hamiltonians H=∑iciPi on an n-qubit system, where the coefficients ci∈R and Pi are Pauli operators. We show that, given access to an appropriate decoding oracle, there exist efficient quantum algorithms for preparing the state ρP(H)=Tr[P2(H)]P2(H), where P(H) denotes the matrix function induced by a univariate polynomial 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.
Decoded quantum interferometry (DQI) and its Hamiltonian extension (HDQI) prepare states whose amplitudes are low-degree polynomials of an objective, using Fourier transforms and coherent decoding. We recast this approach as quantum state transduction through algebra homomorphisms. We transfer an efficiently preparable operator state of a degree-D polynomial in a source Hamiltonian HA to the corresponding polynomial state of a target Hamiltonian HB=π(HA), where π is a unital ∗-homomorphism between the finite-dimensional source and target C∗-algebras. The transduction uses operator Fourier transforms and relative decoding to recover source operators rather than individual term-selection labels. The relative distance drel is the first degree at which source and target traces disagree. We prove that 2D<drel is equivalent to preserving all inner products between degree-D polynomials. Moreover, drel≥dord, where dord is the ordinary distance used in (H)DQI, and we give families with dord=O(1) but drel=Θ(n) and efficient decoders. Our framework replaces the complicated pilot state preparation by the more modular task of preparing a source polynomial state. DQI and HDQI arise as relation-free special cases. The framework accommodates nonuniform coefficients and noncommuting interactions and extends to fermionic, qudit, and bosonic systems, with applications to approximate optimization and Gibbs sampling. As evidence of advantages, for a nonlinear pairwise variant of optimal polynomial intersection where constant dord limits DQI-style preparations, relative decoding yields an ideal quantum score of 0.643 versus 0.606 for the best tested classical heuristic, a gap exceeding 3 percentage points.
We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising k-spin glasses (or Max-k-XORSAT) on random Erdős-Rényi hypergraphs with average degree D≥k. In a temperature range beginning asymptotically at the predicted dynamical phase transition, βdyn(k,D)=(2lnk)/D×[1+ok→∞(1)], we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when D=αk with fixed α>1, both Prange's algorithm and DQI can sample at any inverse temperature β<tanh−1(1/α) for sufficiently large k, well beyond the dynamical threshold βdyn∼2lnk/(αk). Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.
Decoded Quantum Interferometry (DQI) is a recently introduced quantum algorithm that reduces discrete optimization to decoding with potential advantages over the best-known polynomial-time classical algorithms for certain Max-LINSAT problems. In its original formulation, however, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest. In this work, we develop multivariate Decoded Quantum Interferometry (multivariate DQI) for weighted optimization problems, focusing on the weighted Max-LINSAT problem over a prime field. Grouping constraints into N blocks by distinct weights, we introduce multivariate DQI states built from N-variable polynomials of bounded total degree, and derive a closed-form asymptotic expression for both their optimal expectation value and their concentration behavior. We give an explicit preparation circuit using a single decoder call, and extend the analysis to imperfect decoding. We also show that, for certain weighted OPI problems, multivariate DQI outperforms a natural weighted analogue of Prange's algorithm, which serves as the weighted counterpart of the classical benchmark used in the unweighted setting. Finally, we extend the ideas to Hamiltonian DQI, obtaining approximate Gibbs states for commuting Pauli Hamiltonians with block structure.