Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

Title: Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

Problem Statement
Decoded Quantum Interferometry (DQI) is a quantum algorithm proposed to tackle approximate combinatorial optimization, specifically families of max-LINSAT problems (including Max-XORSAT and Optimal Polynomial Intersection, OPI). While DQI offers strong theoretical performance guarantees and has been claimed to provide a super-polynomial quantum speed-up over known classical algorithms in specific parameter regimes (particularly for OPI), its empirical performance relative to classical methods remains under-explored. The central problem addressed in this work is whether classical sampling methods can emulate the optimization capabilities of DQI, thereby challenging or refining claims of quantum advantage. The authors investigate the complexity of DQI by analyzing the decision, search, and sampling versions of these optimization problems, noting that DQI natively solves the sampling problem, which induces a distribution biased toward high-scoring solutions.

Methodology
The authors employ a dual approach combining analytical characterization and large-scale numerical simulation:

1. Analytical Characterization: The authors derive a simplified analytical framework for DQI performance. They connect the expected performance of DQI to binomial statistics by analyzing the moments of the objective function under the DQI distribution. This analysis relies on the properties of the dual error-correcting code associated with the problem instance. They also identify theoretical obstructions to proving the classical hardness of sampling from the DQI distribution, specifically regarding the reduction from search to decision problems and the applicability of standard counting reductions.

2. Numerical Simulation (MCMC): To test empirical performance, the authors utilize Markov Chain Monte Carlo (MCMC) methods, specifically block-Gibbs sampling, to sample from the distribution induced by the DQI state.

   • Target Distribution: Since DQI output probabilities are efficiently computable classically, the authors construct a Markov chain whose stationary distribution matches the DQI output distribution $P(x) \propto P^2(f(x))$, where $P$ is a polynomial of degree $\ell$ and $f(x)$ is the objective function.
   • Algorithms: They compare two sampling strategies: "restart" (running independent chains for each new sample) and "keep-going" (continuing a single chain to find multiple distinct samples).
   • Benchmarks: The methods are tested on two problem families:
     • Max-XORSAT: Random sparse instances with $p=2$.
     • Optimal Polynomial Intersection (OPI): Instances based on Reed-Solomon codes with $p > 2$.
   • Scaling: Experiments scale up to over 1000 effective qubits for Max-XORSAT and beyond 150 effective qubits for OPI. The "equivalent number of qubits" ($n_p = n \lceil \log_2 p \rceil$) is used as the scaling parameter for OPI to allow direct comparison with quantum resource estimates.

Key Contributions

• Analytical Simplification: The paper provides a novel derivation of DQI performance moments using monomial bases rather than symmetric or Kravchuk polynomials. This reveals that a necessary condition for DQI success (high distance of the dual code) implies that the decision version of the problem is classically easy, shifting the focus of complexity analysis to the search and sampling versions.
• Identification of Obstructions: The authors identify specific obstacles in proving the classical hardness of DQI sampling, including the difficulty of reducing the search problem to the decision problem in the context of DQI's performance guarantees and the structured nature of the "good" solution set $S$.
• Empirical Benchmarking: The work presents the first comprehensive empirical study of classical sampling algorithms emulating DQI. It demonstrates that standard MCMC techniques can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes.

Results

• Max-XORSAT: For Max-XORSAT, the block-Gibbs sampling method achieves the DQI performance threshold with a runtime that scales polynomially (approximately $n^5$) with the number of qubits. This indicates that for this class of problems, classical sampling can efficiently match DQI's optimization performance.
• Optimal Polynomial Intersection (OPI): For OPI, where DQI claims a super-polynomial advantage, the MCMC runtime scales exponentially with the number of qubits ($n_p$). However, the base of this exponential growth is small, approximately 1.1 (specifically $1.096^{n_p}$).
• Sampling vs. Search: The qualitative scaling behavior for the sampling problem mirrors that of the search problem. The authors observe that the "keep-going" strategy is more efficient for Max-XORSAT (suggesting clustered solutions), while the "restart" strategy is more efficient for OPI (suggesting a lack of solution clustering or an overlap gap property).
• Threshold Sensitivity: When lowering the performance threshold for OPI, a phase transition is observed in the goodness-of-fit for runtime scaling: power-law fits are better for lower thresholds, while exponential fits become superior above a threshold of approximately 0.66. The DQI threshold for OPI lies well within the exponential regime.

Significance and Claims
The authors state that their findings do not refute existing claims of a super-polynomial quantum advantage for DQI, as the classical MCMC runtime for OPI does exhibit exponential growth. However, the paper argues for a more nuanced perspective on this advantage:

1. Small Exponential Base: The observed exponential base of ~1.1 is comparatively small, suggesting that classical algorithms may remain competitive with DQI for a wide range of practically relevant instance sizes, potentially only falling behind for very large instances.
2. Classical Emulation: The results demonstrate that classical sampling algorithms can closely match the optimization performance of DQI, challenging the notion that the quantum advantage is absolute or easily accessible for current problem sizes.
3. Complexity Landscape: The work clarifies that the complexity of DQI is deeply tied to the search and sampling versions of the problem, rather than the decision version, and that standard tools for proving sampling hardness may not apply directly to DQI.

In conclusion, the paper provides empirical evidence that while DQI may offer a theoretical speed-up, the practical quantum advantage is less stark than previously implied, with classical MCMC methods offering a viable and efficient alternative for many optimization tasks.