Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

Technical Summary: Generative Quantum Search for Combinatorial Optimization

Problem Statement
This research investigates whether shallow quantum samplers can outperform classical samplers in combinatorial optimization by placing a higher probability mass within a "classical recovery basin." The study adapts the Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI) architecture, originally developed for quantum chemistry, to the domain of graph optimization (specifically the Maximum Weighted Independent Set, MWIS). The core hypothesis is that a quantum sampler could generate a distribution of candidate solutions that, when refined by a classical repair and expansion algorithm, yields a higher success rate than classical samplers.

Methodology
The author proposes the GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search) framework, which follows a four-stage pipeline:

1. Generative Policy: A machine learning model (graph-conditioned policy) generates quantum circuit programs (e.g., QAOA parameters).
2. Quantum Sampling: The circuits are executed on a simulator or QPU (Piast-Q) to produce bitstrings (candidate solutions).
3. Classical Recovery: A problem-specific repair function fixes infeasible solutions, followed by a local expansion (e.g., $r$-flip neighborhood) to create a restricted search subspace.
4. Restricted Solver: An exact classical solver finds the optimal solution within this restricted subspace.

Key Theoretical Formulation
The paper formalizes the "quantum benefit" question using recovery-basin mass ($p_r$):
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
where $A_r(G)$ is the set of states that, after repair and $r$-flip expansion, contain the global optimum. The success probability with $B$ shots is $P_{success} = 1 - (1 - p_r)^B$. The study posits that the critical metric is not the size of the sampled subspace relative to the total space ($|S_Q|/2^n$), but the probability mass $p_r$ the sampler places in the recoverable basin.

Experimental Protocol

• Datasets: 150 MWIS instances with ground truths certified via CBC + brute-force verification.
• Baselines: Nine samplers were compared, including uniform random, greedy, simulated annealing (SA), tabu search, multi-start local search, Metropolis, warm-start QAOA, oracle QAOA (best-of-50 configurations), and a matched learned classical policy.
• Constraints: A preregistered, frozen protocol with a fixed budget of 200 shots per sampler.
• Hardware: Experiments included simulations and execution on the Piast-Q trapped-ion processor (20 qubits).

Key Results

1. Classical Dominance: Tabu search and Simulated Annealing (SA) significantly outperformed all quantum and learned classical samplers across all tested problem sizes ($n=16$ to $n=28$). Tabu search achieved a recovery-basin mass ($p_r$) ranging from 0.822 at $n=16$ to 0.944 at $n=18$, with values of 0.878 at $n=20$, 0.943 at $n=24$, and 0.901 at $n=28$. SA ranged from 0.088 to 0.428 across these sizes.
2. Quantum Underperformance: All quantum samplers (warm-start QAOA, oracle QAOA, and generative policies) lost to both SA and Tabu search at every problem size under the fair, preregistered protocol.
3. The "Oracle" Artifact: Previous positive results showing QAOA outperforming SA were identified as artifacts of per-instance configuration selection (an "oracle" upper bound). When evaluated with random configurations (a deployable method), oracle QAOA achieved $p_r = 0.014$ at $n=28$, far below SA's $0.088$.
4. Learned Classical Parity: A learned classical policy (140K parameters) achieved performance comparable to oracle QAOA ($p_r = 0.005–0.101$ vs. $0.014–0.113$), indicating the quantum circuit offers no structural advantage over a matched classical model in this setting.
5. Hardware Robustness: Experiments on Piast-Q showed 93.4% recovery consistency between QPU and simulator samples, confirming hardware robustness but revealing no quantum advantage in optimization quality.
6. Recovery Transition: The study mapped a "recovery transition" where classical recovery is sufficient for $n \le 16$ but begins to fail for $n \ge 20$ with 2-flip expansion. However, even in this transition regime, strong classical baselines (SA, Tabu) maintained superior performance.

Significance and Claims
The paper presents itself as a falsification study. Its primary claim is that under rigorous, preregistered evaluation with matched learned baselines, shallow QAOA-derived proposal distributions do not outperform matched classical proposal models for capturing classical recovery basins in MWIS.

• No Quantum Advantage: The author explicitly claims no quantum advantage for the GQO+QSS architecture in the tested regimes.
• Refutation of Previous Claims: The study attributes earlier positive results to the "oracle" effect of selecting the best configuration per instance, which is not a deployable method.
• Metric Correction: The paper argues that the "subspace fraction" ($|S_Q|/2^n$) is a tautological metric under fixed shot budgets and that recovery-basin mass ($p_r$) is the scientifically accurate quantity to measure.
• Future Direction: The author suggests that for quantum sampling to provide value, it must consistently place more mass in the recovery basin than strong classical baselines (like SA) in regimes where classical recovery fails ($n \ge 55$), a challenge that current shallow circuits have not met.

The work concludes that while the GQO+QSS architecture is a valid framework for hybrid optimization, current shallow quantum samplers do not provide a structural advantage over strong classical stochastic search methods for the specific task of MWIS recovery-basin capture.