Id: arxiv/2611.10283 Url: https://arxiv.org/abs/2611.10283 Tags: quant-ph, cond-mat.dis-nn, cs.DS Score: 0 Title: Regev's Reduction Reaches Reconstruction Domain: quant-ph Source: arxiv Authors: Stephen P. Jordan, Quynh T. Nguyen, Leo Zhou Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-06 Page: https://delphi.science/r/arxiv/2611.10283 Regev's reduction uses a quantum Fourier transform to carry out reductions between various problems related to lattices and codes. We apply it to the problem of sampling from Gibbs distributions of certain classical spin glass Hamiltonians, which can equivalently be thought of as cost functions for average-case instances of an optimization problem called $D$-regular max-$k$-LINSAT. This problem becomes hard at low temperature. Here, we use a quantum decoding algorithm called Belief Propagation with Quantum Messages (BPQM) to solve the decoding problem arising from Regev's reduction. Our main…