Alexander Schmidhuber

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 $\calP$, HDQI prepares a purification of the density matrix $$\rho_\calP(H) = \calP^2(H)/\Tr[\calP^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 $\calP(x)$ to approximate $\exp(-\beta x/2)$ yields Gibbs states at inverse temperature $\beta$; other choices of $\calP$ prepare approximate ground states, microcanonical ensembles, and other spectral filters. The decoding problem inherits structural properties of $H$; in particular, local Hamiltonians map to 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 a class of nearly commuting Pauli 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, color code, and Haah's cubic code -- but also develop a matching efficient classical algorithm for this task, thereby delineating the boundary of efficient classical simulation. For a non-commuting semiclassical spin glass and commuting stabilizer code Hamiltonians with quantum defects, HDQI provably prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical preprocessing. These results position HDQI as a versatile new algorithmic primitive, connecting quantum state preparation to classical decoding.

Community detection is a foundational problem in data science concerned with detecting clustering structure in datasets. A natural extension is hypergraph community detection, which aims to capture higher-order correlations beyond pairwise interactions. In this work, we develop a quantum algorithm for hypergraph community detection and show that it achieves a quartic (power-of-four) speedup over the best known classical algorithm, along with superpolynomial savings in space. The speedup is based on a quantized version of the Kikuchi method and arises from the efficient preparation of a guiding state that has enhanced overlap with the solution space. To support our main result, we prove matching low-coordinate degree function lower bounds, a generalization of sum-of-squares and low-degree likelihood ratio lower bounds, which establishes that the classical baseline algorithm over which we achieve a quartic quantum speedup is (nearly) optimal. Our work constitutes a general framework for identifying when our guiding state–based approach, rooted in the Kikuchi hierarchy, can yield super-quadratic quantum speedups. We suggest that a quantity known as marginal order, which captures the presence of a tradeoff between signal-to-noise ratio and computational cost, effectively determines the existence of quantum Kikuchi-guided algorithms.