Computational Phase Transitions in Binary Compressed Sensing: Quantum Annealing Inside the Relaxation Gap

Natalia Romero; William Hahn

arxiv: 2606.00806 · v1 · pith:VXOJKYYJnew · submitted 2026-05-30 · 💻 cs.ET · quant-ph

Computational Phase Transitions in Binary Compressed Sensing: Quantum Annealing Inside the Relaxation Gap

William Hahn , Natalia Romero This is my paper

Pith reviewed 2026-06-28 17:34 UTC · model grok-4.3

classification 💻 cs.ET quant-ph

keywords binary compressed sensingquantum annealingphase transitionssparse recoveryrelaxation gapQUBOapproximate message passing

0 comments

The pith

Quantum annealing recovers sparse binary signals where all tested classical solvers including Bayes-optimal AMP fail.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper maps computational phase transitions for recovering sparse binary vectors from underdetermined linear measurements. It locates a relaxation gap below the Donoho-Tanner l1 threshold where the unique sparsest solution exists yet convex methods cannot find it. Experiments with n=32 and n=64 show D-Wave quantum annealing achieving positive exact-recovery rates in this gap while nine classical solvers, including asymptotically Bayes-optimal approximate message passing, record zero successes across hundreds of trials. The work matters because it isolates a concrete combinatorial inference setting in which the structure of the QUBO energy landscape appears to favor quantum dynamics over classical local search. The reported evidence remains limited to small finite-size instances.

Core claim

In binary compressed sensing there exists a relaxation gap below the Donoho-Tanner phase transition where the true sparse binary signal is the unique l0 minimizer and the ground state of the corresponding QUBO, yet l1 relaxation and other classical solvers fail to recover it. At n=32, k=5, m/n=0.19 the D-Wave annealer achieves 7 percent exact recovery while AMP and eight other solvers achieve zero percent across 250 trials. Energy-landscape analysis shows that incorrect solutions occupy shallower local basins than the true signal, a structure consistent with quantum tunneling allowing escape where classical search remains trapped.

What carries the argument

The relaxation gap: the parameter regime in binary compressed sensing below the Donoho-Tanner l1 phase transition in which the true sparse binary signal is the unique l0 solution but not recoverable by convex relaxation.

If this is right

At n=32 the quantum annealer records exact recoveries inside the relaxation gap while all tested classical methods record none.
The QUBO ground state coincides with the true signal, yet incorrect solutions sit in shallower local minima that trap classical search.
D-Wave hybrid solvers remain competitive with AMP at n=64 despite embedding overhead.
The reported advantage is observed only for these finite-size binary instances and requires confirmation at larger scales.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the gap persists at scale, quantum methods may systematically exploit landscape features that defeat local classical search in certain sparse-recovery problems.
Specialized classical heuristics tailored to the same QUBO instances could be tested to see whether they close the performance difference without quantum hardware.
Analogous relaxation-gap regimes may appear in other combinatorial inference tasks such as low-density parity-check decoding or community detection.

Load-bearing premise

The observed recovery difference arises from quantum annealing dynamics rather than from solver implementation details, embedding overhead, or incomplete tuning of the classical baselines on these small instances.

What would settle it

Repeating the recovery-rate comparison at n=128 with several thousand trials per solver and fully optimized classical baselines to determine whether the gap in success rates persists or closes.

Figures

Figures reproduced from arXiv: 2606.00806 by Natalia Romero, William Hahn.

**Figure 2.** Figure 2: Scaling comparison: n = 32 (solid, circles) versus n = 64 (dashed, squares) at matched sparsity ratios. Left: k/n ≈ 0.06. Right: k/n ≈ 0.16. The QPU advantage at n = 32 does not extend to n = 64, where AMP dominates. The embedding boundary is visible as the gap between QPU curves at the two scales. neling dynamics—reaching the ground state in a fraction of attempts [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: QUBO energy distribution for D-Wave QPU successes versus [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

**Figure 4.** Figure 4: Recovery heatmaps with Donoho-Tanner phase transition boundary [ [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗

read the original abstract

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 convex relaxations fail. At n=32, k=5, m/n=0.19, D-Wave achieves 7% exact recovery while AMP and eight other solvers score 0% across 250 combined trials (Fisher exact p=0.018). At n=64, embedding overhead limits the QPU, but D-Wave's hybrid solver remains competitive with AMP. Energy landscape analysis reveals that the QUBO ground state contains the true signal, but incorrect solutions occupy shallower local basins that trap classical search -- a structure consistent with quantum tunneling dynamics. To our knowledge, this constitutes preliminary finite-size evidence that quantum annealing succeeds in a narrow regime where all tested classical methods, including the Bayes-optimal AMP, fail within a well-characterized combinatorial inference problem. Confirmation at larger n, higher trial counts, and with stronger classical controls remains an open problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

At n=32 the paper reports D-Wave recovering 7% of binary signals inside the Donoho-Tanner gap where AMP and eight other solvers hit zero, but the gap is small and the classical runs may not have been pushed to their limit.

read the letter

The headline result is a narrow finite-size window at n=32, k=5, m/n=0.19 where the quantum annealer recovers the exact sparse binary vector in 7% of trials while AMP and the other classical solvers recover none across 250 runs, with a Fisher p-value of 0.018. They back this with 19k total trials, an energy-landscape argument that the true signal is the QUBO ground state, and the observation that classical methods get stuck in shallower basins.

What the work actually does is run a systematic comparison of nine classical solvers against two D-Wave modes on the same small instances and document the recovery rates inside the relaxation gap. The energy analysis is straightforward and the statistical test is reported plainly. They also flag the embedding overhead at n=64 and call the whole thing preliminary.

The soft spot is exactly the one the stress-test note flags: the 0% classical performance could reflect default parameters or incomplete tuning rather than an inherent barrier. At these sizes local search or better-tuned message passing often closes small gaps once you adjust iteration counts or initialization. The effect size is modest, n stays at 32-64, and no scaling argument is given that would survive larger instances. The claim that the structure is "consistent with quantum tunneling" is an interpretation, not a demonstration that classical methods cannot reach the ground state under stronger controls.

This is for people working on quantum heuristics for combinatorial inference or phase transitions in compressed sensing. A reader who wants to see whether the edge survives better classical baselines will get value from the raw trial counts and the explicit parameter settings. It is coherent on its own terms and engages the relevant literature on AMP and Donoho-Tanner, so it deserves a serious referee to check the experimental controls and ask for stronger classical comparisons.

Referee Report

2 major / 3 minor

Summary. The manuscript reports experimental findings in binary compressed sensing, asserting that D-Wave's quantum annealer can recover sparse binary signals in the 'relaxation gap'—a regime where the l0 solution exists but l1 relaxations fail—while nine classical solvers, including the Bayes-optimal Approximate Message Passing (AMP), achieve zero success. This is evidenced by 19,775 trials for n in {32,64}, with a key result at n=32, k=5, m/n=0.19 showing 7% exact recovery for D-Wave versus 0% for classical methods across 250 trials (Fisher exact test p=0.018). The paper includes energy landscape analysis suggesting that the QUBO ground state encodes the true signal but classical search is trapped in shallower local minima.

Significance. Should the central empirical observation hold after addressing baseline tuning, the work would provide finite-size evidence of a computational phase transition where quantum annealing succeeds in a combinatorial problem where classical methods fail, including asymptotically optimal ones. The extensive trial count and statistical testing are positive aspects. The result is preliminary due to small n and effect size, and the authors correctly note the need for larger-scale confirmation.

major comments (2)

[Results for n=32 (specific instance parameters k=5, m/n=0.19)] The headline claim at n=32, k=5, m/n=0.19 rests on D-Wave achieving 7% success while AMP and eight others achieve 0% in 250 trials. However, without explicit documentation of hyperparameter optimization, iteration limits, or instance-specific tuning for the classical solvers (particularly AMP), it is unclear if the 0% reflects fundamental failure or suboptimal configuration. This is load-bearing for the claim of quantum advantage over classical methods.
[Energy landscape analysis] The claim that 'incorrect solutions occupy shallower local basins that trap classical search' is used to motivate quantum tunneling. This section should include quantitative measures of basin depths or barrier heights (e.g., via specific energy differences or sampling statistics) to support the interpretation beyond qualitative description.

minor comments (3)

Specify the two D-Wave modes mentioned in the abstract and their respective performance in the main text or tables.
Add more details on the embedding quality and overhead for the D-Wave runs at n=64 to explain the limitations noted.
Ensure all solver parameters and random seeds are reported for full reproducibility of the 19,775 experiments.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review, the recognition of the trial volume and statistical testing, and the constructive major comments. We address each point below with clarifications and commitments to revision.

read point-by-point responses

Referee: [Results for n=32 (specific instance parameters k=5, m/n=0.19)] The headline claim at n=32, k=5, m/n=0.19 rests on D-Wave achieving 7% success while AMP and eight others achieve 0% in 250 trials. However, without explicit documentation of hyperparameter optimization, iteration limits, or instance-specific tuning for the classical solvers (particularly AMP), it is unclear if the 0% reflects fundamental failure or suboptimal configuration. This is load-bearing for the claim of quantum advantage over classical methods.

Authors: We agree that the absence of explicit hyperparameter documentation leaves the classical baselines open to the interpretation raised. The original experiments used standard library defaults and literature-recommended Bayes-optimal parameters for AMP (no per-instance retuning), together with default settings for the other eight solvers. In the revision we will add a dedicated appendix that lists the precise software versions, all hyperparameter values, iteration budgets, and any early-stopping criteria applied to each solver. This will allow readers to reproduce the exact classical configurations and assess whether further tuning could close the observed gap. revision: yes
Referee: [Energy landscape analysis] The claim that 'incorrect solutions occupy shallower local basins that trap classical search' is used to motivate quantum tunneling. This section should include quantitative measures of basin depths or barrier heights (e.g., via specific energy differences or sampling statistics) to support the interpretation beyond qualitative description.

Authors: We concur that quantitative characterization is needed to move the landscape discussion beyond qualitative description. The revision will augment the energy-landscape section with (i) the measured energy gap between the true-signal ground state and the nearest incorrect local minima, (ii) the distribution of basin depths obtained from exhaustive enumeration on the n=32 instances, and (iii) sampling statistics (mean and variance of escape energies) from both classical local-search trajectories and the D-Wave annealer. These numbers will be reported for the representative (k=5, m/n=0.19) ensemble. revision: yes

Circularity Check

0 steps flagged

No circularity: purely experimental comparison with no derivations or fitted predictions

full rationale

The paper reports direct empirical results from 19,775 experiments on finite-size instances (n=32,64), comparing D-Wave recovery rates against nine classical solvers including Bayes-optimal AMP. No equations, ansatzes, uniqueness theorems, or predictions are derived; the claims consist of measured success percentages and a Fisher test on observed counts. No self-citations are load-bearing for any central premise, and no fitted inputs are relabeled as predictions. The work is self-contained against external benchmarks (solver performance on the tested instances).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard Donoho-Tanner phase transition for l1 recovery and the QUBO encoding of binary compressed sensing; no new free parameters or invented entities are introduced.

axioms (1)

domain assumption Existence of an l0 solution below the Donoho-Tanner threshold but above the l1 threshold (the relaxation gap).
Invoked to define the target regime.

pith-pipeline@v0.9.1-grok · 5785 in / 1169 out tokens · 26328 ms · 2026-06-28T17:34:20.925399+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references

[1]

Defininganddetectingquantumspeedup,

T.F.Rønnowet al.,“Defininganddetectingquantumspeedup,” Science, vol. 345, no. 6195, pp. 420–424, 2014

2014
[2]

Quantum annealing for combinatorial opti- mization: A benchmarking study,

S. Yarkoniet al., “Quantum annealing for combinatorial opti- mization: A benchmarking study,”Eur. Phys. J. ST, vol. 231, pp. 1–18, 2022

2022
[3]

Adiabatic quantum computation,

T. Albash and D. A. Lidar, “Adiabatic quantum computation,” Rev. Mod. Phys., vol. 90, p. 015002, 2018

2018
[4]

Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing,

D. L. Donoho and J. Tanner, “Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing,”Phil. Trans. R. Soc. A, vol. 367, no. 1906, pp. 4273–4293, 2009

1906
[5]

Preciseundersamplingtheorems,

D.L.DonohoandJ.Tanner,“Preciseundersamplingtheorems,” Proc. IEEE, vol. 98, no. 6, pp. 913–924, 2010

2010
[6]

Counting faces of randomly- projected polytopes when the projection radically lowers dimen- sion,

D. L. Donoho and J. Tanner, “Counting faces of randomly- projected polytopes when the projection radically lowers dimen- sion,”J. Amer. Math. Soc., vol. 22, no. 1, pp. 1–53, 2009

2009
[7]

Message-passing algorithms for compressed sensing,

D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,”Proc. Natl. Acad. Sci. USA, vol. 106, no. 45, pp. 18914–18919, 2009

2009
[8]

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,

E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,”IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, 2006

2006
[9]

Compressed sensing,

D. L. Donoho, “Compressed sensing,”IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289–1306, 2006

2006
[10]

Quantum annealing in the transverse Ising model,

T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,”Phys. Rev. E, vol. 58, no. 5, pp. 5355– 5363, 1998

1998
[11]

Regression shrinkage and selection via the lasso,

R. Tibshirani, “Regression shrinkage and selection via the lasso,”J. R. Stat. Soc. B, vol. 58, no. 1, pp. 267–288, 1996

1996
[12]

Needell and J

D. Needell and J. A. Tropp, “CoSaMP,”Appl. Comput. Har- mon. Anal., vol. 26, no. 3, pp. 301–321, 2009

2009
[13]

A fast approach for overcomplete sparse decomposition based on smoothedℓ 0 norm,

H. Mohimani, M. Babaie-Zadeh, and C. Jutten, “A fast approach for overcomplete sparse decomposition based on smoothedℓ 0 norm,”IEEE Trans. Signal Process., vol. 57, no. 1, pp. 289–301, 2009

2009
[14]

Evidence for the utility of quantum computing before fault tolerance,

Y. Kimet al., “Evidence for the utility of quantum computing before fault tolerance,”Nature, vol. 618, pp. 500–505, 2023

2023
[15]

Sparse MRI,

M. Lustig, D. Donoho, and J. M. Pauly, “Sparse MRI,”Magn. Reson. Med., vol. 58, no. 6, pp. 1182–1195, 2007

2007
[16]

AneffectiveimplementationoftheLin-Kernighan traveling salesman heuristic,

K.Helsgaun,“AneffectiveimplementationoftheLin-Kernighan traveling salesman heuristic,”Eur. J. Oper. Res., vol. 126, no. 1, pp. 106–130, 2000

2000
[17]

The unconstrained binary quadratic programming problem: a survey,

G. Kochenbergeret al., “The unconstrained binary quadratic programming problem: a survey,”J. Comb. Optim., vol. 28, no. 1, pp. 58–81, 2014

2014
[18]

Milestones on the quantum utility highway: quantum annealing case study,

C. C. McGeoch and P. Farré, “Milestones on the quantum utility highway: quantum annealing case study,”ACM Trans. Quantum Comput., vol. 5, no. 1, 2024

2024

[1] [1]

Defininganddetectingquantumspeedup,

T.F.Rønnowet al.,“Defininganddetectingquantumspeedup,” Science, vol. 345, no. 6195, pp. 420–424, 2014

2014

[2] [2]

Quantum annealing for combinatorial opti- mization: A benchmarking study,

S. Yarkoniet al., “Quantum annealing for combinatorial opti- mization: A benchmarking study,”Eur. Phys. J. ST, vol. 231, pp. 1–18, 2022

2022

[3] [3]

Adiabatic quantum computation,

T. Albash and D. A. Lidar, “Adiabatic quantum computation,” Rev. Mod. Phys., vol. 90, p. 015002, 2018

2018

[4] [4]

Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing,

D. L. Donoho and J. Tanner, “Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing,”Phil. Trans. R. Soc. A, vol. 367, no. 1906, pp. 4273–4293, 2009

1906

[5] [5]

Preciseundersamplingtheorems,

D.L.DonohoandJ.Tanner,“Preciseundersamplingtheorems,” Proc. IEEE, vol. 98, no. 6, pp. 913–924, 2010

2010

[6] [6]

Counting faces of randomly- projected polytopes when the projection radically lowers dimen- sion,

D. L. Donoho and J. Tanner, “Counting faces of randomly- projected polytopes when the projection radically lowers dimen- sion,”J. Amer. Math. Soc., vol. 22, no. 1, pp. 1–53, 2009

2009

[7] [7]

Message-passing algorithms for compressed sensing,

D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,”Proc. Natl. Acad. Sci. USA, vol. 106, no. 45, pp. 18914–18919, 2009

2009

[8] [8]

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,

E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,”IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, 2006

2006

[9] [9]

Compressed sensing,

D. L. Donoho, “Compressed sensing,”IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289–1306, 2006

2006

[10] [10]

Quantum annealing in the transverse Ising model,

T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,”Phys. Rev. E, vol. 58, no. 5, pp. 5355– 5363, 1998

1998

[11] [11]

Regression shrinkage and selection via the lasso,

R. Tibshirani, “Regression shrinkage and selection via the lasso,”J. R. Stat. Soc. B, vol. 58, no. 1, pp. 267–288, 1996

1996

[12] [12]

Needell and J

D. Needell and J. A. Tropp, “CoSaMP,”Appl. Comput. Har- mon. Anal., vol. 26, no. 3, pp. 301–321, 2009

2009

[13] [13]

A fast approach for overcomplete sparse decomposition based on smoothedℓ 0 norm,

H. Mohimani, M. Babaie-Zadeh, and C. Jutten, “A fast approach for overcomplete sparse decomposition based on smoothedℓ 0 norm,”IEEE Trans. Signal Process., vol. 57, no. 1, pp. 289–301, 2009

2009

[14] [14]

Evidence for the utility of quantum computing before fault tolerance,

Y. Kimet al., “Evidence for the utility of quantum computing before fault tolerance,”Nature, vol. 618, pp. 500–505, 2023

2023

[15] [15]

Sparse MRI,

M. Lustig, D. Donoho, and J. M. Pauly, “Sparse MRI,”Magn. Reson. Med., vol. 58, no. 6, pp. 1182–1195, 2007

2007

[16] [16]

AneffectiveimplementationoftheLin-Kernighan traveling salesman heuristic,

K.Helsgaun,“AneffectiveimplementationoftheLin-Kernighan traveling salesman heuristic,”Eur. J. Oper. Res., vol. 126, no. 1, pp. 106–130, 2000

2000

[17] [17]

The unconstrained binary quadratic programming problem: a survey,

G. Kochenbergeret al., “The unconstrained binary quadratic programming problem: a survey,”J. Comb. Optim., vol. 28, no. 1, pp. 58–81, 2014

2014

[18] [18]

Milestones on the quantum utility highway: quantum annealing case study,

C. C. McGeoch and P. Farré, “Milestones on the quantum utility highway: quantum annealing case study,”ACM Trans. Quantum Comput., vol. 5, no. 1, 2024

2024