Generative Quantum Search for Combinatorial Optimization: A Preregistered Falsification Study of Shallow QAOA-Derived Proposal Distributions for Classically Refined Solution Subspaces
We port the Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI) architecture from quantum chemistry to combinatorial graph optimization. Our framework, GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search), formalizes the key quantity as recovery-basin mass p_r(q,G) = Pr[x ~ q contains a state in A_r(G)], where A_r(G) is the set of states whose r-flip expansion after repair intersects the optimal solution set. We test whether shallow quantum samplers (QAOA, learned generative policy) can place more probability mass in the recovery basin than strong classical samplers for MWIS (Maximum Weighted Independent Set). All 150 ground truths are certified with CBC + brute-force verification. Exact recovery-basin masks are enumerated for all n<=20 instances. Nine samplers are compared on a preregistered held-out test set. Result: Scenario C (falsification). Tabu search dominates (p_r=0.82-0.94), SA is second, and all quantum samplers lose to both at every problem size. The learned classical policy matches oracle QAOA, confirming no structural quantum advantage. The earlier positive oracle result was an artifact of per-instance best-of-50 configuration selection. We claim no quantum advantage.
We port the Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI) architecture from quantum chemistry to combinatorial graph optimization. Our framework, GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search), formalizes the key quantity as recovery-basin mass p_r(q,G) = Pr[x ~ q contains a state in A_r(G)], where A_r(G) is the set of states whose r-flip expansion after repair intersects the optimal solution set. We test whether shallow quantum samplers (QAOA, learned generative policy) can place more probability mass in the recovery basin than strong classical samplers for MWIS (Maximum Weighted Independent Set). All 150 ground truths are certified with CBC + brute-force verification. Exact recovery-basin masks are enumerated for all n<=20 instances. Nine samplers are compared on a preregistered held-out test set. Result: Scenario C (falsification). Tabu search dominates (p_r=0.82-0.94), SA is second, and all quantum samplers lose to both at every problem size. The learned classical policy matches oracle QAOA, confirming no structural quantum advantage. The earlier positive oracle result was an artifact of per-instance best-of-50 configuration selection. We claim no quantum advantage.
Abstract We port the Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI) architecture from quantum chemistry to combinatorial graph optimization. Our framework, GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search), follows the same principle: ML generates circuit programs, quantum samplers produce bitstrings, classical recovery repairs and expands them into a restricted subspace, and a classical solver finds the optimum within that subspace. We formalize the key quantity as the recovery-basin mass pr(qθ,G) = Prx∼qθ [x ∈ Ar(G)], where Ar(G) = {x : Er(R(x))∩X∗(G) ̸= ∅} is the preimage of the optimal set under repair R and r-flip expansion Er. Under B independent shots, success probability becomes Psuccess = 1 − (1 − pr)B. The quantum-benefit question reduces to: does pr(qquantum,G) > pr(qclassical,G)? We test this on MaximumWeighted Independent Set (MWIS) with a preregistered, frozen protocol. All 150 ground truths are certified with CBC + brute-force verification. Exact recovery-basin masks are enumerated for all n ≤ 20 instances. Nine samplers are compared on a held-out test set: uniform, greedy, simulated annealing, tabu search, multi-start local search, Metropolis, warm-start QAOA, oracle QAOA, and a matched learned classical policy. Key findings: 1. Tabu search dominates at all sizes (pr = 0.82–0.94), followed by simulated annealing. All quantum samplers and the learned classical policy lose to both at every problem size under the frozen test protocol. 2. Oracle QAOA loses to SA under fair evaluation: With random QAOA configurations (not per-instance optimized), oracle QAOA achieves pr = 0.014 at n = 28 vs SA’s 0.088. The earlier positive result (pr = 0.185 vs 0.130) required per-instance best-of-50 configuration selection—an oracle upper bound, not a deployable method. 3. Learned classical policy matches oracle QAOA: A matched 140K-parameter classical policy achieves pr = 0.005–0.101, comparable to oracle QAOA’s 0.014–0.113. The quantum circuit’s proposal distribution provides no structural advantage over a matched learned classical model in this setting. 4. Recovery-basin masks reveal the phase structure: At r = 2, uniform-sampling Precover drops from 0.975 (n = 16) to 0.775 (n = 20) at B = 200, identifying the regime where sampler quality matters. 5. Hardware robustness without advantage: 136 cores on Piast-Q show 93.4% recovery consistency between QPU and simulator, but no basin-mass advantage. This is a falsification study: Under rigorous, preregistered evaluation with matched learned baselines, shallow QAOA-derived proposal distributions do not outperform matched classical proposal models, and both lose to strong classical baselines (SA, tabu). The earlier positive oracle result was an artifact of per-instance configuration selection. We claim no quantum advantage.
Sample-based quantum diagonalization (SQD), equivalently quantum-selected configuration interaction (QSCI), has become a centre of gravity of pre-fault-tolerant quantum chemistry: a processor samples electronic configurations and the Hamiltonian is diagonalized classically in the resulting subspace. Accuracy is governed entirely by which configurations enter it -- a machine-learning selection problem, made acute by a coupon-collector bottleneck. We review the generative and learned selectors by what each generates and the signal it exploits, and identify one gap: no reward-proportional generative-flow-network proposer has been built for tail discovery. On the field's central question -- whether the quantum sampler beats classical selected CI -- the negative verdict is not ours to claim: priority belongs to Reinholdt et al. [JCTC 21, 6811 (2025)], and polynomial-time classical estimation of the flagship circuits has reinforced it. We state that verdict at the precision a falsifiable claim requires -- it concerns reproducible, same-active-space comparisons on molecular electronic structure -- and weigh the claims outside those qualifiers. We show that alpha-string weights are not invariant under rotations inside degenerate orbital shells, so determinant counts are undefined until the orbital gauge is declared. We distil a ten-element benchmarking standard and apply it to our own deposit, which returned defects that changed numbers printed here and retracted one from v1. FCI-exact experiments confirm one prediction and refute another: the single generative advantage we find keeps no consistent sign along the dissociation coordinate at device-calibrated noise and reverses under a symmetric readout model. It does beat a noise-matched classical recovery loop on N2 by a margin five seeds cannot resolve, and loses by over a factor of two to a classical selector that needs no sampler.
Quantum-selected configuration interaction (QSCI) has emerged as a feasible approach for approximating electronic ground states on noisy quantum devices toward large-system demonstrations. In QSCI, Slater determinants are sampled from a quantum-prepared state, and the Hamiltonian is then diagonalized in the sampled subspace. To create a high-quality subspace under hardware constraints, the design of the state-preparation circuit is crucial. Here, we present a Generative Quantum Eigensolver (GQE)-based framework that optimizes ansatz structures using a Transformer policy trained on the QSCI subspace energy. We validate the framework on N2 in active spaces of up to 32 qubits. We found that the optimized circuits reach chemical precision with substantially lower gate counts than time-evolved circuits. Quantitatively, this corresponds to an average reduction of 98% in the required two-qubit gate count relative to the single-step first-order Trotterized approximation and 83% relative to the qDRIFT approximation. Furthermore, the resulting wavefunctions are competitive with heat-bath configuration interaction (HCI) in terms of compactness. In stretched-bond, strongly correlated regimes, they achieve chemical precision with subspaces that are 50% smaller than those required by HCI.
Demonstrating quantum advantage for combinatorial optimization requires more than standalone algorithmic results; it calls for end-to-end case studies that integrate problem modelling, quantum execution, and classical refinement into practical workflows. This paper presents a sandbox platform for experimenting with hybrid quantum-classical workflows in graph optimization, enabling the systematic study of end-to-end optimization pipelines. Using our platform, we investigate three classically intractable and mutually reducible graph problems -- Minimum Vertex Cover, Maximum Independent Set, and Maximum Clique -- by transforming them into an unconstrained problem and solving the resulting instances with QAOA on IBM platforms. Our workflow combines classical pre-processing to reduce instance size, quantum optimization on the reduced problem, and classical postprocessing to map quantum outputs to high-quality feasible solutions, thereby avoiding direct constraint encoding in the quantum circuit. We evaluate the approach on synthetic graphs, benchmark instances, and real-world networks, and report hardware experiments on IBM Quantum System One at PINQ2 in Bromont, Quebec, powered by IBM's 156-qubit Heron r2 processor on graphs up to 128 vertices, with circuits involving up to 128 qubits and 13,555 two-qubit gates. The results illustrate how sandbox-style end-to-end experimentation can expose bottlenecks, clarify the role of classical-quantum workload partitioning, and provide domain experts and practitioners with a practical guide for interpreting quantum optimization outputs and assessing quantum utility on the road to quantum advantage in combinatorial optimization.
Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.
We introduce Quantum-Informed Surrogate Sampling (QISS), a post-processing framework that generates candidate solutions to combinatorial optimization problems from low-weight correlations of shallow quantum circuits. The quantum device estimates local observables, which are directly accessible by repeated measurements and for which a wide range of error-mitigation tools are available, while candidate solutions are generated classically without explicit dependence on the combinatorial optimization problem itself. We evaluate QISS on Maximum Cut and Maximum Independent Set problems on N variables and show that only O(N) low-order correlators from shallow circuits suffice to produce competitive solutions that surpass vanilla QAOA. For MaxCut on 3-regular graphs, QISS from p=3 QAOA correlators outperforms vanilla QAOA at p=17 on average, with further improvements possible by warm-starting QAOA. We validate the procedure on the 54-qubit IQM Emerald quantum device and demonstrate its noise resilience. Our results support a regime for near-term optimization in which shallow circuits serve not as direct samplers but as generators of informative statistics for scalable classical sampling.