Curator's Take
AI Commentary
This article shows that a carefully tuned Markov‑chain Monte Carlo sampler can reproduce the approximation ratios promised by decoded quantum interferometry (DQI) on problems as large as a thousand effective qubits, directly challenging claims of a near‑term quantum speedup for those tasks. By linking DQI’s output distribution to simple binomial statistics and then exploiting its efficiently computable probabilities, the authors demonstrate that classical sampling can keep pace with the quantum approach across both max‑XORSAT and OPI benchmarks. The result underscores the growing relevance of quantum‑inspired algorithms and suggests that any practical advantage for DQI will have to overcome not just theoretical complexity but also increasingly powerful classical baselines.
— Mark Eatherly
Summary
Optimization problems are among the leading candidates for industrially relevant quantum advantage. Decoded quantum interferometry (DQI) has been proposed to tackle approximate optimization, establishing a connection to classical decoding problems. While previous work has primarily focused on the theoretical complexity of DQI, comparatively little is known about its empirical performance relative to classical algorithms. In this work, we shed further light on the complexity of DQI and investigate numerically whether classical sampling methods can emulate the optimization capabilities of DQI. We first present a simplified analytical characterization of DQI that connects its expected performance to binomial statistics, and we identify concrete obstacles in further studying the complexity of DQI. Exploiting the fact that DQI output probabilities are efficiently computable, we apply Markov chain Monte Carlo (MCMC) techniques, particularly block-Gibbs sampling, to sample from the induced distribution. We study the runtime scaling of these methods for two optimization problems called max-XORSAT, where we reach beyond $1000$ effective qubits; and OPI, where we reach beyond $150$ effective qubits. Our results show that MCMC algorithms can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes. In OPI, in the regime where a super-polynomial advantage is claimed for DQI, we observe an empirical runtime for MCMC that scales approximately as $1.1^{n}$, indicating exponential growth with a comparatively small base. Our findings do not refute existing quantum advantage claims but provide new empirical evidence that classical sampling algorithms can closely match DQI's optimization performance, offering a more nuanced perspective on the practical advantage of DQI.