{"id":"arxiv/2606.00806","url":"https://arxiv.org/abs/2606.00806","tags":["cs.ET","quant-ph"],"score":0,"title":"Computational Phase Transitions in Binary Compressed Sensing: Quantum Annealing Inside the Relaxation Gap","domain":"cs.ET","source":"arxiv","authors":["William Hahn","Natalia Romero"],"reviews":0,"subject":"cs.ET","summary":"We map the computational phase transition boundary in binary compressed sensing and identify a regime where D-Wave's quantum annealer recovers signals in a region where all tested classical methods fail, including Approximate Message Passing (AMP), which achieves the Bayes-optimal recovery threshold asymptotically for Gaussian matrices. In 19,775 experiments (n in {32, 64}, nine classical solvers, two D-Wave modes), we find that quantum annealing recovers sparse binary signals in the relaxation gap -- the regime below the Donoho-Tanner l1 phase transition where the l0 solution exists but…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-30","reactions":{}}