1 Introduction↩︎

The search for quantum computational advantage has largely focused on speed: can quantum hardware solve the same problem faster than classical hardware? This framing has produced mixed results for quantum annealing, with classical heuristics routinely matching D-Wave on standard benchmarks [1]–[4].

We propose a different question: can quantum hardware solve a harder formulation of a problem—one that is correct but classically intractable? This reframing—evaluating quantum capability rather than quantum speed—aligns with the quantum utility framework of McGeoch and Farré [4], which advocates assessing hardware on tasks where practical overhead and problem structure matter; for gate-model utility evidence see [5]. We study this question through the lens of compressed sensing—with applications from medical imaging [6] to communications—where the natural \(\ell_0\) optimization is NP-hard [7], [8] and classical methods must relax it to the convex \(\ell_1\) norm. The relaxation works when measurements are abundant, but fails in a critical regime—the relaxation gap—where information is sufficient for recovery but the convex surrogate cannot find the answer.

This gap is not an engineering limitation. It is a phase transition boundary, characterized precisely by Donoho and Tanner [9]–[11] for Gaussian measurement matrices. Below the boundary, \(\ell_1\) methods fail with certainty. Above it, they succeed with certainty. The boundary is universal across matrix ensembles.

We find, at \(n=32\), that D-Wave’s quantum annealer operates below this boundary—in the gap—recovering signals that even AMP [12], the Bayes-optimal classical algorithm for Gaussian compressed sensing, cannot find. This is not a speed advantage. It is preliminary evidence that quantum annealing exhibits recovery behavior not observed in any tested classical method at this problem scale—a difference that warrants further investigation at larger \(n\) and with stronger baselines.

We also show where this advantage ends. At \(n=64\), embedding overhead degrades the QPU, and AMP dominates. We characterize this scaling boundary honestly, providing a roadmap for what next-generation quantum hardware must achieve.

1.1 Contributions↩︎

1. We conduct 19,775 experiments across two problem scales, nine classical solvers (including AMP), and two D-Wave quantum modes—the most comprehensive benchmark of quantum annealing for compressed sensing to date.

2. We identify, at \(n=32\), a computational phase transition regime (the relaxation gap) where quantum annealing succeeds and all tested classical methods—including the Bayes-optimal AMP—fail (Fisher exact \(p=0.018\)).

3. We characterize the QUBO energy landscape, showing the true signal is the ground state but incorrect solutions occupy deeper local basins that trap classical search.

4. We map the scaling boundary: the advantage holds at \(n=32\), shifts to the hybrid solver at \(n=64\), and is bounded by embedding overhead at larger \(n\).

5. We establish AMP as the strongest classical competitor, fundamentally changing the baseline landscape for quantum-classical comparisons in compressed sensing.

2 Background↩︎

2.1 The \(\ell_0\) Sparse Recovery Problem↩︎

Given a \(k\)-sparse binary signal \(\mathbf{x} \in \{0,1\}^n\) and \(m < n\) measurements \(\mathbf{y} = \mathbf{Ax}\) where \(\mathbf{A} \in \mathbb{R}^{m \times n}\), recovery seeks the sparsest consistent solution. For binary \(\mathbf{x}\), this maps to a QUBO [13]: \[\min_{\mathbf{x} \in \{0,1\}^n} \|\mathbf{Ax} - \mathbf{y}\|_2^2 + \lambda \sum_i x_i \label{eq:qubo}\tag{1}\] with \(Q = \mathbf{A}^T\mathbf{A}\), which D-Wave solves natively as an Ising Hamiltonian.

2.2 The Donoho-Tanner Phase Transition↩︎

In a series of foundational works [9]–[11], Donoho and Tanner proved that \(\ell_1\) recovery exhibits a sharp phase transition: for Gaussian \(\mathbf{A}\), there exists a curve \(\rho(\delta; C)\) in the \((\delta, \rho)\) plane (where \(\delta = m/n\), \(\rho = k/m\)) such that \(\ell_1\) succeeds above and fails below. These works establish the precise threshold curves, empirical recovery probability contour maps, and finite-dimensional \(k/n\) vs.\(m/n\) phase diagrams used as reference boundaries throughout this paper. The transition is universal—it holds across Gaussian, Bernoulli, Fourier, Hadamard, and other matrix ensembles [9].

The relaxation gap is the region below \(\rho(\delta; C)\) but above the information-theoretic limit. Here, the signal is uniquely determined by the measurements, but no convex method can recover it. D-Wave solves the exact \(\ell_0\) QUBO in this gap without relaxation.

2.3 Classical Solvers↩︎

We test nine classical methods spanning four paradigms:

Convex relaxation: LASSO [14] and ISTA (proximal gradient on \(\ell_1\)).

Greedy pursuit: OMP (Orthogonal Matching Pursuit) and CoSaMP [15] (iterative support refinement).

Direct \(\ell_0\) heuristics: IHT (Iterative Hard Thresholding), SL0 [16] (smoothed \(\ell_0\)), and ILP (PuLP/CBC branch-and-bound solving the identical QUBO as D-Wave).

Bayesian inference: AMP (Approximate Message Passing) with Bernoulli prior [12]. AMP achieves the Bayes-optimal recovery threshold for i.i.d.Gaussian matrices and is the state-of-the-art baseline in compressed sensing phase transition theory. Its inclusion is essential for any claim of advantage over classical methods.

2.4 D-Wave Quantum Annealing↩︎

Quantum annealing [17] minimizes an objective by exploiting quantum fluctuations to escape local minima. We test two modes: Hybrid (LeapHybridBQMSampler, combining QPU with classical decomposition) and QPU-only (direct access via EmbeddingComposite, isolating the quantum contribution). QPU-only uses 1,000 reads at 20 \(\mu\)s annealing time on D-Wave’s Advantage system (Pegasus, 5,760 qubits) and Advantage2 (Zephyr, 4,800 qubits). For an overview of D-Wave architectures and benchmarking methodology see [4].

3 Experimental Design↩︎

3.1 Problem Instances↩︎

Binary sparse signals at \(n \in \{32, 64\}\) with sparsity \(k/n \in \{0.05\text{--}0.31\}\) and measurement ratios \(m/n \in \{0.19\text{--}0.81\}\). Gaussian measurement matrices \(A_{ij} \sim \mathcal{N}(0, 1/m)\). 30 seeds per configuration, deterministically generated. Total: 38 configurations per \(n\), 2,280 instances.

3.2 Scale↩︎

Total experiments: 19,775 (16,340 classical + 3,435 D-Wave). All solvers given equal 10-second time budgets. Classical hardware: Intel i7-10750H, 16 GB RAM.

3.3 Statistical Methods↩︎

Fisher’s exact test with Holm-Bonferroni correction for recovery rate comparisons. 95% Wilson score CIs for proportions. We pool classical trials when testing “can any classical method recover?” because all solvers face the identical QUBO landscape. Significance: \(\alpha = 0.05\).

4 Results↩︎

4.1 The Phase Transition at \(n=32\): D-Wave Crosses the Classical Boundary↩︎

Table 1 presents recovery rates at selected configurations. The central finding: at \(k=5\), \(m/n=0.19\), D-Wave achieves \(7\%\) exact recovery while every classical solver—including AMP—scores \(0\%\) across 250 combined trials (Fisher \(p = 0.018\) vs.pooled classical, justified because all solvers face the same landscape).

4.1.1 The headline: D-Wave recovers where AMP fails↩︎

AMP achieves the Bayes-optimal recovery threshold asymptotically for i.i.d.Gaussian matrices [12] and is the strongest known classical algorithm for this problem class. At \(k=5\), \(m/n=0.19\), AMP scores \(0\%\) (0/30). D-Wave scores \(7\%\) (2/30 for both hybrid and QPU). This is not a comparison against weak baselines—AMP represents the strongest known classical algorithm for this problem class. The fact that D-Wave exhibits nonzero recovery where AMP scores zero suggests the QUBO formulation may access solution structure not reached by posterior mean estimation at this finite problem size—though this interpretation requires validation at larger \(n\) and against stronger solvers.

When D-Wave fails at this configuration (28 of 30 trials), the failures are not catastrophic: mean Hamming distance from truth is \(5.0\) (out of \(k=5\) nonzero positions) with mean F1 score \(0.38\), indicating partial support recovery. The QPU finds the neighborhood of the correct solution but does not always reach the exact ground state.

4.1.2 AMP reshapes the competitive landscape↩︎

AMP outperforms all other classical solvers across most configurations, reaching \(80\%\) at \(k=2\), \(m/n=0.25\) (versus LASSO \(57\%\), ISTA \(63\%\)). At \(k=10\), \(m/n=0.50\), AMP achieves \(70\%\) where all non-AMP classical solvers score \(0\)–\(3\%\), far exceeding D-Wave’s \(20\%\). With AMP as the baseline, D-Wave’s advantage window is narrower than comparisons against LASSO alone would suggest, but the surviving advantage—against an asymptotically Bayes-optimal algorithm—is far more significant.

4.1.3 SL0 and the discrete landscape problem↩︎

SL0, a classical \(\ell_0\) approximation using smoothed Gaussian penalties, scores \(0\)–\(3\%\) across all configurations. Inspection reveals SL0 recovers the correct number of nonzero components but selects wrong positions—its continuous smoothing does not respect the discrete geometry of \(\{0,1\}^n\). This confirms the QUBO landscape is intrinsically hard for classical methods that approximate \(\ell_0\) continuously.

4.2 Scaling to \(n=64\): The Embedding Boundary↩︎

At \(n=64\), the picture inverts. AMP dominates everywhere. The QPU (now on Advantage2’s Zephyr topology) achieves \(22.5\%\) overall recovery but scores \(0\%\) at the critical low-measurement configurations. Parameter sweeps (20–500 \(\mu\)s annealing, 1,000–5,000 reads) confirm this is not a tuning issue. The bottleneck is embedding: 64 logical variables require chains of 9–13 physical qubits (420–525 total), and the dense \(\mathbf{A}^T\mathbf{A}\) coupling structure causes chain-break noise that degrades solution quality.

The hybrid solver partially compensates: at \(k=3\), \(m/n=0.20\), it achieves \(70\%\) (comparable to AMP’s \(73\%\)) by managing decomposition and embedding classically. This demonstrates that D-Wave’s production solver maintains competitiveness at \(n=64\) even where the QPU alone fails.

4.3 Energy Landscape: Why Quantum Succeeds Where Classical Fails↩︎

To understand the mechanism, we computed the QUBO energy of the true signal \(\mathbf{x}_{\text{true}}\) and compared it to D-Wave’s solutions across 1,139 QPU runs at \(n=32\).

At most operating points, \(\mathbf{x}_{\text{true}}\) is the QUBO ground state. At \(k=2\), \(m/n=0.25\): true signal energy \(-1.15 \pm 1.00\); D-Wave successes \(-1.42 \pm 0.95\) (at or below ground state); D-Wave failures \(-0.62 \pm 0.65\) (trapped in higher-energy local minima). Fig. 3 shows this energy separation.

The landscape has a characteristic structure: the correct solution sits in the ground state basin, surrounded by many shallower local minima separated by tall barriers. Classical methods—branch-and-bound (ILP), gradient descent (IHT), smooth penalty relaxation (SL0), even posterior mean estimation (AMP)—are systematically trapped in these shallower basins. Quantum annealing traverses these barriers—a process consistent with tunneling dynamics—reaching the ground state in a fraction of attempts.

Fig. 4 (right panel) maps the quantum advantage topology \(\Delta R = R_{\text{D-Wave}} - R_{\text{classical}}\) across the full \((k/n, m/n)\) plane. The positive (blue) region corresponds to the relaxation gap: the advantage is largest at low \(k/n\) and low \(m/n\), precisely where the Donoho-Tanner theory predicts \(\ell_1\) failure. This landscape structure—where the QUBO ground state is shallow relative to surrounding incorrect basins—may generalize to other dense QUBO problems arising from Gram matrices \(\mathbf{A}^T\mathbf{A}\), suggesting quantum annealing’s advantage is not specific to compressed sensing but to a broader class of dense quadratic optimization landscapes.

This explains both D-Wave’s success and its \(90\%\) ceiling at easy configurations: the QPU does not always reach the ground state, making it inferior to deterministic convex methods (LASSO, AMP) when the \(\ell_1\) relaxation is tight. The advantage concentrates precisely where the relaxation fails—the gap.

4.4 TSP Control: The Advantage Is Problem-Specific↩︎

On the Traveling Salesman Problem (\(n=50\)–\(500\)), LKH-3 [18] matches or exceeds D-Wave at all sizes, confirming the advantage is specific to problems where the QUBO formulation is natively suited to quantum annealing. TSP—where quantum and classical optimize the same objective—shows no quantum advantage with current hardware.

5 Discussion↩︎

5.1 What the Machine Reveals About the Landscape↩︎

The D-Wave results serve as a probe into the computational topology of sparse recovery. They reveal three regimes:

1. Below the gap (insufficient information): No method succeeds. The signal is not uniquely determined.

2. In the gap (relaxation fails): \(\ell_1\) methods and AMP fail at \(n=32\). D-Wave’s quantum annealing reaches the ground state more frequently than all tested classical methods. This is the regime of observed recovery advantage.

3. Above the gap (relaxation tight): Convex methods and AMP succeed deterministically. D-Wave plateaus at \({\sim}90\%\) due to stochastic annealing. Classical methods are superior.

The scaling from \(n=32\) to \(n=64\) reveals a fourth regime: the embedding boundary, where the physical connectivity of the QPU becomes the bottleneck. At \(n=64\), the dense QUBO requires chains of 9–13 physical qubits per logical variable, and chain-break noise overwhelms the quantum signal. The hybrid solver partially recovers by managing decomposition classically.

5.2 Comparison with Bayes-Optimal Inference↩︎

AMP’s inclusion is the most important methodological improvement in this work. Rigorous quantum benchmarking requires strong, problem-aware baselines [4]; previous versions (v1–v3) compared D-Wave against convex relaxations and greedy heuristics. AMP, as the Bayes-optimal algorithm for Gaussian matrices, represents the theoretical ceiling for classical inference. The fact that D-Wave exhibits nonzero recovery at \(k=5\), \(m/n=0.19\) where AMP scores zero is more significant than beating LASSO by 14 percentage points—it suggests the QUBO formulation may access solution structure not reached by posterior mean estimation at this scale, though this remains a hypothesis requiring larger-\(n\) confirmation.

Simultaneously, AMP narrows the advantage window: at \(k=2\) and \(k=10\), AMP matches or exceeds D-Wave. The advantage concentrates in a specific sparsity band (\(k/n \approx 0.10\)–\(0.20\)) at low measurement ratios—precisely the interior of the Donoho-Tanner relaxation gap.

5.3 Falsifiable Predictions↩︎

1. If Gurobi solves the QUBO with \(>50\%\) recovery at \(k=5\), \(m/n=0.19\) within 10 seconds, the ILP control was too weak.

2. If the relaxation gap closes at \(n=128\) on next-generation hardware (Advantage2 with native Zephyr connectivity), the advantage is scale-dependent.

3. If the gap disappears with structured (non-Gaussian) measurement matrices, the result is narrower than the universality of the Donoho-Tanner transition suggests.

5.4 Scaling Roadmap↩︎

The embedding boundary at \(n=64\) is a hardware limitation, not a physical one. D-Wave’s Advantage2 Zephyr topology provides 20-way qubit connectivity (versus 15 for Pegasus), reducing chain lengths from 10–13 to 9–10 at \(n=64\). Future systems with higher native connectivity or problem-specific embedding strategies could push the boundary to larger \(n\). We predict: if chain length can be held below \({\sim}5\) physical qubits per logical variable, the QPU advantage observed at \(n=32\) should extend to \(n=64\), because the underlying QUBO landscape hardness (dense \(\mathbf{A}^T\mathbf{A}\) with combinatorial local minima) is preserved at all \(n\).

5.5 Limitations↩︎

1. Scale: \(n=32\) is very small by compressed sensing standards. The effect collapses at \(n=64\). Confirmation requires \(n \in \{128, 256\}\) with improved embedding or next-generation hardware.

2. Effect size: 2/30 at the headline configuration is numerically fragile. It is unknown whether the effect survives higher trial counts (300–3000), \(\lambda\) optimization, or alternative matrix ensembles (Bernoulli, partial Fourier, structured). These validations are necessary before strong conclusions can be drawn.

3. Classical controls: The tested baselines do not include several stronger methods. Missing exact solvers: Gurobi, SCIP, CPLEX with branch-and-cut. Missing stochastic methods: parallel tempering, simulated quantum annealing, population annealing, digital annealing. Missing hardware-accelerated methods: GPU Ising solvers and tensor-network methods. The current claim is therefore “better than tested baselines,” not “better than classical computation.”

4. Mechanistic: The energy landscape analysis is correlational. Successful runs achieving lower energy than failures does not prove quantum tunneling—the same pattern is consistent with stochastic search, thermal effects, or classical randomized dynamics. Confirming the tunneling hypothesis requires spectral-gap analysis, reverse annealing experiments, pause-and-quench protocols, or quantum Monte Carlo comparisons.

5. Embedding: QPU performance at \(n=64\) is limited by chain length (9–13 qubits per logical variable), not physics. This may be an embedding artifact rather than a fundamental scaling limit.

6. Hybrid attribution: The hybrid solver combines quantum and classical components; its success at \(n=64\) does not isolate the quantum contribution.

7. Binary signals: Extension to continuous signals requires multi-bit QUBO encoding and is not addressed here.

6 Conclusion↩︎

We have mapped the computational phase transition boundary in binary sparse recovery and identified, at finite problem size (\(n=32\)), a regime where quantum annealing recovers signals that AMP—the Bayes-optimal classical algorithm—cannot find (\(p=0.018\)). At \(n=64\), embedding overhead limits the QPU, but the hybrid solver remains competitive. This recovery advantage concentrates in the relaxation gap: the regime below the Donoho-Tanner \(\ell_1\) threshold where a process consistent with quantum tunneling traverses landscape barriers that trap all tested classical methods in this finite-size setting.

This is an exploratory finite-size study, not a claim of universal quantum advantage. It maps where quantum annealing behavior diverges from tested classical methods in a specific, well-characterized problem class. The mechanistic explanation—consistent with barrier traversal via tunneling dynamics—remains a hypothesis: confirming it requires spectral-gap analysis, reverse annealing experiments, or quantum Monte Carlo comparisons not yet performed. What the data establish is the empirical map; what causes it remains open.

Code, problem instances, and experimental results are being actively developed and curated; a public repository will be released in conjunction with a future version of this work.

Acknowledgment↩︎

Supported by the Machine Perception & Cognitive Robotics Laboratory and the Center for Complex Systems at Florida Atlantic University. D-Wave experiments used the Advantage and Advantage2 systems via the Leap cloud service.

References↩︎