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.
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.
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.
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.
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.
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.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.
Near-term quantum approaches to combinatorial optimization are limited by qubit counts, circuit fidelity, sampling cost, and the difficulty of encoding constraints, while machine learning is increasingly used to configure and control quantum optimization workflows. We call such workflows adaptive: decisions conventionally fixed in advance, from formulation and penalties to shot budgets, backends, and whether to invoke a quantum processor at all, are made by learned policies that respond to the instance, the progress of the solve, or the hardware. This review examines three paradigms, AI for quantum optimization, quantum for AI-driven optimization, and AI-quantum co-optimization, and organizes the literature by the decision being learned rather than by application. A structured search identified a 119-paper corpus, of which 67 papers form an evidence core coded in detail. The evidence is considerably stronger for AI-assisted quantum optimization than for the reverse direction: learning already reduces quantum evaluations, improves initialization, supports decomposition and penalty control, and mitigates noise, whereas evidence that quantum computation improves learned optimizers remains largely confined to small-scale simulation. Experimental controls are thin: of 52 studies in the three paradigms, 22 include no classical baseline, the quantum contribution is fully isolated in 10 of 24 where an ablation applies, and the median largest experiment uses 16 qubits. We introduce an M0-M5 evidence hierarchy, from simulation to practical quantum advantage, and find no broadly convincing result at the highest level. We argue that scaling is increasingly a systems problem: the question is not only whether a problem fits on a quantum processor, but how classical and quantum resources should be allocated across the optimization process.