Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Generative Quantum Search for Combinatorial Optimization: A Preregistered Falsification Study of Shallow QAOA-Derived Proposal Distributions for Classically Refined Solution Subspaces

David Vesterlund

Published Sep 28, 2026• 0 citations
Publisher

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), 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.

DOI
10.5281/zenodo.23013242

Related papers

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

David Vesterlund

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.

•Oct 13, 2026•0 citations

Machine learning for sample-based quantum diagonalization: a review of generative configuration recovery and the classical-simulability frontier

Nicolás Bonilla Vargas

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.

quant-pharXiv:2608.05314•Aug 7, 2026•3 citations

Generative Circuit Design for Quantum-Selected Configuration Interaction

Ryota Kemmoku, Qi Gao, Shu Kanno +4 more

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.

quant-pharXiv:2604.09756•Apr 13, 2026•7 citations

Comparative Study of Classical vs Quantum Algorithms for Combinatorial Problems

Daniel Popescu, Helena Petrov

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 Frontiers Journal•Mar 28, 2024•0 citations

Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization

Chinonso Onah, Stuart Hadfield, Kristel Michielsen

Constrained quantum samplers often produce infeasible outputs that retain information about good feasible solutions. We develop a post-measurement framework that constructs problem-dependent classical feasibility maps from constraint-violation statistics and pushes the raw quantum sampling law forward onto the feasible set. The probability of each repaired solution is the total raw mass of its repair preimage, enlarging the successful sampling event from a target feasible set to its full repair preimage. We derive exact identities for repaired success and expected cost, and separate repair-basin geometry from sampler-dependent probability concentration. For noisy implementations, we distinguish leakage from the encoded subspace from concentration loss within it. For permutation constraints, Hungarian maximum-overlap repair provides an O(n^3) implementation, which we study on traveling-salesman problems (TSP). We derive conditional repaired-success bounds and quantify how basin aggregation reduces the absolute-transfer budget required by these bounds. Noiseless simulations show that optimal repair basins contain selectively overweighted infeasible contributors. For an n=10 TSP instance, pushforward repair recovered the optimum using approximately 10^3 shots, compared with 10^6 shots in the original CE-QAOA workflow without repair. On a 127-qubit IBM processor, using encodings of up to 100 qubits, repaired candidates match reference tours on smaller benchmarks and improve them on larger instances. These results establish concentration of quantum probability on useful repair preimages as a design principle for constrained quantum optimization.

quant-pharXiv:2611.00759•Nov 3, 2026•0 citations

Quantum-informed surrogate sampling for combinatorial optimization

Elisabeth Wybo, Jernej Rudi Finžgar

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.

quant-pharXiv:2607.22372•Jul 27, 2026•2 citations
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.
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.
Constrained quantum samplers often produce infeasible outputs that retain information about good feasible solutions. We develop a post-measurement framework that constructs problem-dependent classical feasibility maps from constraint-violation statistics and pushes the raw quantum sampling law forward onto the feasible set. The probability of each repaired solution is the total raw mass of its repair preimage, enlarging the successful sampling event from a target feasible set to its full repair preimage. We derive exact identities for repaired success and expected cost, and separate repair-basin geometry from sampler-dependent probability concentration. For noisy implementations, we distinguish leakage from the encoded subspace from concentration loss within it. For permutation constraints, Hungarian maximum-overlap repair provides an O(n^3) implementation, which we study on traveling-salesman problems (TSP). We derive conditional repaired-success bounds and quantify how basin aggregation reduces the absolute-transfer budget required by these bounds. Noiseless simulations show that optimal repair basins contain selectively overweighted infeasible contributors. For an n=10 TSP instance, pushforward repair recovered the optimum using approximately 10^3 shots, compared with 10^6 shots in the original CE-QAOA workflow without repair. On a 127-qubit IBM processor, using encodings of up to 100 qubits, repaired candidates match reference tours on smaller benchmarks and improve them on larger instances. These results establish concentration of quantum probability on useful repair preimages as a design principle for constrained quantum optimization.
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 NNN variables and show that only O(N)O(N)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=3p=3p=3 QAOA correlators outperforms vanilla QAOA at p=17p=17p=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.