Speaker
Description
Decoded Quantum Interferometry (DQI) is a recently proposed quantum optimization framework that prepares a probability distribution biased toward high-quality solutions, with claims of quantum advantage for the Optimal Polynomial Intersection (OPI) problem. 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 investigate whether classical sampling methods can emulate the optimization capabilities of DQI. Exploiting the fact that DQI output probabilities are efficiently computable, we apply standard Markov chain Monte Carlo (MCMC) techniques, particularly block-Gibbs sampling, to sample from the induced distribution. We benchmark these methods on large instances of max-XORSAT and OPI, reaching regimes exceeding 100 effective qubits where exponential quantum advantage has been proposed. Our results show that classical MCMC algorithms can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes. For OPI, we observe an empirical runtime that scales approximately as $1.1^{n}$, indicating exponential growth with a comparatively small base. In addition, we present a simplified analytical characterization of DQI that connects its expected performance to binomial statistics and clarifies the distinction between optimization and sampling as computational tasks. 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 in practice, offering a more nuanced perspective on the practical computational advantage of DQI.
| Topic | Quantum algorithms for machine learning applications |
|---|---|
| Additional Topic | Hybrid quantum-classical approaches for learning and optimization |