{"id":"08486e1f-abd0-43be-b9b9-fb53cc17c463","arxiv_id":"2506.18594","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"QAOA plus quantum subspace expansion systematically improves MIS solutions on small random graphs, with a fitted gate-count crossover extrapolated to about 75 nodes.","lead":"A quantum computing preprint adds a subspace-mixing step on top of the QAOA optimization algorithm and reports better solutions for the maximum independent set problem on random graphs. The author estimates that for graphs larger than about 75 nodes, the added step becomes cheaper than plain QAOA in logical gate count, based on a fitted scaling extrapolation.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The N*>75 crossover is unsupported as written: Eq. (14) inverts the fidelity ratio required by Eq. (12), and the Fermi-Dirac extrapolation lacks reported fit parameters or validation beyond N=10.","rationale":"The manuscript contains a genuinely interesting application of QSE to QAOA and demonstrates consistent improvement over QAOA on small graphs (N≤10), including near-unit fidelities at K=8 and detailed logical gate-count estimates. However, the headline crossover at N>75 is not robust: the printed Eq. (14) is algebraically inverted relative to the cost model in Eq. (12), making the quantitative claim internally inconsistent as written. Even after correcting that typo, the extrapolation rests entirely on an empirical functional form fitted to 9 data points without reporting fit parameters or uncertainties. The paper itself disclaims the precise value, so the specific 'greater than 75' statement should be treated as illustrative at best. These issues support the reader's CONDITIONAL verdict: the contribution is credible as a small-N demonstration, but the quantitative crossover needs correction and validation before the claim can be accepted. I therefore leave the verdict unchanged, while noting the concrete checks that would settle the concern.","tokens_in":118,"tokens_out":10062,"duration_ms":112526,"concrete_test":"Re-derive the crossover condition from Eq. (12) and Table II: it should be F_QSE/F_QAOA = βQSE(1+e^{NαQAOA})/[βQAOA(1+e^{NαQSE})] > 2K(√ρN)^3. Then re-run the fidelity fits on the N=2..10 data (or obtain the omitted parameters from the author) and compute N* using the corrected inequality. As a sensitivity check, also fit an alternative decay form (e.g., F(N)=a e^{-bN}+c) to the same data. If the corrected N* is not within the range 50–100, or if the alternative fit changes N* by more than a factor of two, the specific claim 'greater than 75' should be withdrawn.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative claim (abstract, Sec. VIII.C) is that QAOA-plus-QSE surpasses QAOA for Erdős-Rényi graphs with N>75 using K=8 trial states. This rests on Eq. (14), which states the crossover is the smallest N satisfying βQAOA/(1+e^{NαQAOA}) × (1+e^{NαQSE})/βQSE > 2K(√ρN)^3. The left-hand side is F_QAOA/F_QSE, not the F_QSE/F_QAOA ratio required by the cost model in Eq. (12). For the intended regime α_QSE < α_QAOA (QSE decays more slowly), the printed ratio decays exponentially with N and cannot cross the growing polynomial right-hand side; the stated N*=75 cannot be obtained from Eq. (14) as written. Moreover, the Fermi-Dirac form in Sec. V is introduced as a 'simple empirical fit' and is fitted to only N=2..10 (14 random graphs per size, Fig. 8), with no reported α, β, or uncertainties. The crossover is exponentially sensitive to α_QAOA−α_QSE; without these parameters the specific value 75 has no demonstrable support. The author's own caveat that 'the precise value obtained here bears little meaning' (Sec. VIII.C) concedes this limitation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes appending a quantum subspace expansion (QSE) step, formulated as a generator coordinate method, on top of a QAOA-prepared state for the maximum independent set problem on Erdős–Rényi graphs. The QSE kernel matrix elements are estimated with Hadamard tests, and the resulting generalized eigenvalue problem is solved classically. Numerical statevector experiments for graph sizes N=2 to 10 (14 random graphs per size) show systematic improvements in approximation ratio, fidelity, Hamming-weight error, and parity error when QSE with up to K=8 trial states is added. A cost model in logical CNOT and T gates is developed for three kernel-evaluation strategies, and a Fermi–Dirac fit to the fidelity data is used to extrapolate a graph-size crossover N*≈75 beyond which QSE is claimed to surpass plain QAOA. The paper also discusses an LCU-based re-encoding of the QSE state and compares the three kernel-estimation methods.","tokens_in":18555,"tokens_out":4306,"duration_ms":48038,"significance":"If the numerical results are taken at face value, the paper contributes a useful and simple post-processing layer for QAOA: the QSE step demonstrably raises fidelity and approximation ratio for small MIS instances, and the detailed logical-gate accounting for the Hadamard/Pauli, real-time-evolution, and LCU approaches is a valuable reference. The main quantitative claim, however, is the extrapolated crossover at N*≈75, and that claim currently rests on an equation-level inversion error and on an unvalidated empirical scaling law fitted to only nine data points. The core small-N result is likely sound, but the headline crossover is not supported as written and needs either substantial correction and validation or removal/qualification.","major_comments":[{"comment":"The fidelity ratio in Eq. (14) is inverted relative to the cost condition in Eq. (12). Eq. (12) requires F(GCM)/F(QAOA) to exceed a polynomial factor, but the left-hand side of Eq. (14) is β_QAOA/(1+e^{Nα_QAOA}) × (1+e^{Nα_QSE})/β_QSE = F_QAOA/F_QSE. Since the stated fits have α_QSE < α_QAOA, this ratio decays exponentially with N and cannot cross the growing polynomial right-hand side; therefore the reported value N*=75 cannot be obtained from Eq. (14) as printed. The corrected condition should place F_QSE/F_QAOA on the left, and the factor 2K should be reconciled with the 4(K−1)(1+1/L′) factor appearing in Eq. (12).","section":"Sec. VIII.C, Eq. (14)"},{"comment":"The Fermi–Dirac form F(N)=β(1+e^{αN})^{-1} is introduced as a simple empirical fit and is fitted only to N=2..10 with 14 graphs per size, but the manuscript reports no fitted values of α and β, no goodness-of-fit measures, and no uncertainty estimates. The crossover location is exponentially sensitive to the difference α_QAOA−α_QSE, so extrapolating this fit to N≈75 is not quantitatively justified. The statement in the abstract and conclusion that the approach surpasses QAOA for graphs of size greater than 75 is therefore unsupported by the evidence shown. The authors should either supply validation of the scaling law (for example, tests at larger N or on held-out graph densities) with explicit fit uncertainties, or rewrite the abstract and conclusion to present N* as only an illustrative extrapolation, consistent with the caveat already stated in Sec. VIII.C.","section":"Secs. V and VIII.C"},{"comment":"The statement that 'the QSE is guaranteed to deliver improved solution with respect to the QAOA' is too strong if applied to the fidelity rather than the variational energy. The trial subspace includes the QAOA state when the evolution-time grid contains t=0, so the generalized-eigenvalue solution cannot have higher energy than the QAOA state; however, the K=3 row in Fig. 7 shows that the fidelity can deteriorate relative to QAOA. The sentence should specify that the guarantee applies to the cost value, not to the fidelity.","section":"Sec. VIII.A"}],"minor_comments":[{"comment":"There are several typographical errors: 'Addtionally' (Sec. I), 'Erdös' (abstract and elsewhere) should be 'Erdős', 'degrade' should be 'degrades' (Sec. VIII.C), 'correpond' in the Fig. 8 caption, 'yieding' and 'smaler' (App. B), 'assummption' (App. A.2), and a missing closing parenthesis after 'see App. B' in Sec. IV.","section":"Throughout"},{"comment":"The caption states that the shaded areas correspond to one standard deviation, but it does not specify whether the spread is over the 14 random graph instances only or also includes the QAOA angle optimization runs; please clarify.","section":"Fig. 8 caption"},{"comment":"The parameters L′ and ε_cut are introduced in the text, but the relation between L′ and the number of layers L used in the cost estimate of Eq. (12) and Eq. (14) is not made explicit near their first use; please define all symbols consistently.","section":"Sec. VIII.A"}],"recommendation":"major_revision","confidential_remarks":"The manuscript does not mention a code or data repository, which limits independent reproducibility of the numerical claims. The central issue for publication is the crossover claim: the equation-level inversion in Eq. (14) and the unvalidated Fermi–Dirac extrapolation make the abstract's N*>75 statement unreliable. I would ask the editor to require the authors to correct Eq. (14), reconcile it with Eq. (12), and either substantiate the extrapolation with fit parameters and validation or substantially soften the abstract and conclusion. The small-N QSE improvement and the logical-resource analysis are likely sound and can form the basis of a solid revised paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is worth knowing: adding a quantum subspace expansion (QSE) layer on top of QAOA gives clear, systematic fidelity and approximation-ratio gains for maximum independent set on small Erdős–Rényi graphs, and the gate-count model is a useful template for early-FTQC cost estimates. That part deserves a serious referee.\n\nWhat is actually new: the QSE/GCM post-processing combination for combinatorial optimization, relative to the many-body applications in the cited literature, with a concrete resource comparison of Pauli, RTE, and LCU kernel estimation in CNOT and T gates. The N=2–10 statevector results (14 graphs per size) are direct evidence and are not circular: the improved fidelity is observed, not derived from the fit. The paper is honestly written about many of its own limitations.\n\nThe soft spot is the quantitative headline. Eq. (12) requires F_QSE/F_QAOA to exceed a growing threshold. Eq. (14) prints the inverse ratio, F_QAOA/F_QSE, so the left-hand side decays exponentially while the right-hand side grows polynomially; as written, there is no crossover at any N. The claimed N*=75 presumably comes from the corrected ratio, but then the Fermi-Dirac fit is an empirical curve over N=2 to 10, with no reported fit parameters or uncertainties, and the crossover is exponentially sensitive to the exponent difference. The author’s caveat that the precise value “bears little meaning” is appropriate, but the abstract still presents 75 as an estimate, and the conclusion repeats it without that caveat. Also, “guaranteed improvement” (Sec. VIII.A) is too strong given the K=3 parity-sector failure on K+3,3; the improvement is guaranteed in the variational sense only if the full generalized eigenvalue problem is solved stably.\n\nRecommendation: send to peer review. The methodological combination and the small-N numerics are solid and reproducible in principle; the extrapolation and Eq. (14) need correction, and the resource analysis would benefit from a more cautious presentation. This is a legitimate contribution with a real error in the central quantitative claim—fixable, but not ignorable.","headline":"QAOA + QSE is a credible small-N improvement for MIS, but the N=75 crossover rests on an inverted ratio in Eq. (14) and an uncontrolled Fermi-Dirac extrapolation.","tokens_in":19082,"tokens_out":2286,"would_cite":true,"duration_ms":25138,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"QAOA plus a quantum subspace expansion step systematically improves maximum-independent-set solutions and overtakes plain QAOA beyond about 75 nodes.","keywords":["QAOA","quantum subspace expansion","generator coordinate method","maximum independent set","Erdős–Rényi graphs","approximation ratio","fidelity","gate count"],"falsifier":"Run the QAOA-plus-QSE protocol on Erdős–Rényi graphs of density $1/2$ with $L=20$ and $K=8$ at $N=20,30,50,75$; if the measured fidelity ratio $F_\\mathrm{QSE}/F_\\mathrm{QAOA}$ stops increasing along the fitted curve, or if the logical CNOT/T counts at a fixed approximation ratio do not favour QSE, the predicted crossover at $N>75$ is refuted.","tokens_in":17963,"feed_emoji":"⚛️","tokens_out":14289,"duration_ms":130226,"temperature":0.7,"pith_summary":"The paper sets out to show that appending a quantum subspace expansion (QSE) step to a QAOA-prepared state systematically improves the approximation ratio and fidelity for the maximum independent set problem on Erdős–Rényi graphs. In simulations on graphs with 2 to 10 nodes, adding eight trial states roughly doubles the approximation ratio at $N=10$ and raises the fidelity from about 0.15 to above 0.96, while also correcting the Hamming-weight and parity errors left by QAOA. Combining a fitted fidelity curve with logical CNOT and T gate counts for three kernel-estimation strategies, the paper estimates that QAOA-plus-QSE surpasses plain QAOA in cost-to-solution for graphs above about 75 nodes. This matters because QSE is a post-processing layer that can be added on top of an existing optimiser rather than a replacement for it.","feed_headline":"Eight trial states push QAOA past plain QAOA on graphs over 75 nodes","feed_subtitle":"Post-processing lifts QAOA fidelity from 0.15 to 0.96 at ten nodes.","key_machinery":"The central object is the quantum subspace expansion (QSE), a generator-coordinate method in which the QAOA output $|\\Phi_0\\rangle$ is used to build $K$ trial states $|\\chi_k\\rangle = e^{-i\\hat{H}_C t_k}|\\Phi_0\\rangle$ at equally spaced times $t_k$, and the cost Hamiltonian is diagonalised in the span of these states through the generalised eigenvalue problem $H f = E S f$. Uniform time spacing gives the Hamiltonian and overlap kernels an index-difference (Toeplitz) structure, so the number of matrix elements to estimate grows only linearly in $K$. The overlap kernel is regularised by deleting eigenvectors with eigenvalues below $\\varepsilon_\\text{cut}=10^{-3}$. The cost comparison is carried by the inequality $\\frac{F_\\mathrm{GCM}}{F_\\mathrm{QAOA}} \\gtrsim 4(K-1)(1+1/L') f$, with $f$ set by the kernel-estimation circuit, and by leading-order CNOT/T counts for three estimation strategies: direct Pauli grouping, real-time-evolution finite differences, and linear combination of unitaries.","core_discovery":"The central claim is that a generator-coordinate method in its quantum subspace expansion form, applied to the state produced by a QAOA circuit, yields systematically better solutions to the maximum independent set problem, with the improvement growing as the number $K$ of trial states increases. For Erdős–Rényi graphs of average density $1/2$ and a 20-layer QAOA optimised one layer at a time, the QSE step improves the approximation ratio and fidelity at every tested size ($N=2$ to $10$) and drives the Hamming-weight and parity errors essentially to zero. A Fermi-Dirac fit to the fidelity decay, combined with explicit leading-order CNOT and T gate counts for three ways of computing the Hamiltonian and overlap kernels, gives the estimate that $K=8$ trial states already make the combined method cheaper per solution than plain QAOA for graphs with more than about 75 nodes. The same construction, on a regular time grid, can implement a Gaussian energy filter or imaginary-time evolution, which is what makes the subspace expansion improve with $K$.","pith_inferences":["Editorial: the specific crossover $N\\approx75$ is an extrapolation from a fit on $N=2$ to $10$; if the true fidelity decay deviates from the fitted Fermi-Dirac curves, the crossover could move substantially or disappear, even though the small-$N$ improvements are direct numerical results.","Editorial: the gate-count comparison fixes the QAOA depth at $L=20$ and sequential layer-by-layer optimisation; allowing the depth to grow with $N$ may erode the advantage, while using QSE to reduce the depth needed for a target accuracy may strengthen it.","Editorial: since the QSE construction acts as a Gaussian energy filter, the same eight-state recipe might serve as a verification or error-mitigation layer: a large gap between the filtered energy and the bare variational energy could flag a failed QAOA optimisation."],"forward_implications":["For Erdős–Rényi graphs of density $1/2$ and a fixed 20-layer QAOA, the estimated crossover graph size beyond which QAOA-plus-QSE beats plain QAOA in logical-gate cost is about 75 at $K=8$; larger $K$ is expected to lower that threshold.","At every tested size and on both the cube graph and the $K^+_{3,3}$ graph, the QSE step improves approximation ratio and fidelity monotonically with $K$; $K=8$ gives fidelity above 0.98 on the two test graphs and above 0.96 at $N=10$ on random graphs.","Because the QSE layer is independent of how the initial state was prepared, the same post-processing can be stacked on QAOA variants, warm-started circuits, or adiabatic protocols, as the conclusion argues.","Under the optimistic assumption that QAOA finds near-optimal solutions, the real-time-evolution kernel estimator has the best asymptotic leading-order gate count among the three methods considered, scaling as $N^2 \\log^p N$ rather than $N^5$ or $N^6/\\log^2 N$."],"supporting_citations":[{"why":"Defines the QAOA ansatz and variational cost that serves as both the starting state and the baseline for the comparison.","marker":"[23]"},{"why":"Introduces the quantum subspace expansion algorithm with real-time-evolved trial states whose Hamiltonian kernels are estimated on a quantum computer.","marker":"[29]"},{"why":"Shows the GCM on a quantum computer and the automatic symmetry restoration that the paper relies on to fix QAOA's wrong parity and Hamming weight.","marker":"[30]"},{"why":"Introduces quantum filter diagonalisation, the equal-time-grid real-time evolution scheme underlying the paper's trial-state basis.","marker":"[67]"},{"why":"Provides the overlap-matrix truncation method the paper uses to stabilise the generalised eigenvalue equation.","marker":"[75]"},{"why":"Supplies convergence and stability theory for quantum subspace diagonalisation that justifies the truncated kernel diagonalisation.","marker":"[76]"},{"why":"Gives the linear-combination-of-unitaries construction used for kernel evaluation and for re-encoding the mixed GCM state.","marker":"[78]"},{"why":"Provides the optimal Clifford+T z-rotation decomposition whose T-gate counts enter the cost comparison.","marker":"[83]"},{"why":"Supplies the Toffoli decomposition used to convert controlled multi-qubit gates into CNOT and T gates in the gate-count tables.","marker":"[85]"}],"fun_headline_variants":["Eight trial states tip QAOA past plain QAOA for graphs over 75","Subspace expansion lifts QAOA fidelity from 0.15 to 0.96 at ten nodes","Generator-coordinate method systematically beats QAOA on MIS","QAOA with subspace expansion turns 0.15 fidelity into 0.96 at N=10"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the fidelity decay of QAOA and of QAOA-plus-QSE, measured only for graphs of 2 to 10 nodes, keeps following the fitted S-shaped Fermi-Dirac curves introduced in Sec. V and used in Sec. VIII.C all the way to 75 nodes and beyond; the paper itself says the precise extrapolated value 'bears little meaning,' but the claimed advantage beyond 75 nodes is exactly that extrapolation.","fun_headline_variants_meta":{"raw":{"variants":["Eight trial states tip QAOA past plain QAOA for graphs over 75","Subspace expansion lifts QAOA fidelity from 0.15 to 0.96 at ten nodes","Generator-coordinate method systematically beats QAOA on MIS","QAOA with subspace expansion turns 0.15 fidelity into 0.96 at N=10"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001073,"raw_usage":{"total_tokens":4478,"prompt_tokens":915,"completion_tokens":3563,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":3475}},"tokens_in":531,"tokens_out":3563,"duration_ms":25796,"temperature":1.0,"reasoning_tokens":3475,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:47:00.715077+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the QAOA-plus-QSE protocol on Erdős–Rényi graphs of density $1/2$ with $L=20$ and $K=8$ at $N=20,30,50,75$; if the measured fidelity ratio $F_\\mathrm{QSE}/F_\\mathrm{QAOA}$ stops increasing along the fitted curve, or if the logical CNOT/T counts at a fixed approximation ratio do not favour QSE, the predicted crossover at $N>75$ is refuted.","supporting_citations":[{"cited_title":"Iterative Layerwise Training for Quantum Approximate Optimization Algorithm","cited_arxiv_id":"2309.13552","evidence_quote":"Introduces the quantum subspace expansion algorithm with real-time-evolved trial states whose Hamiltonian kernels are estimated on a quantum computer."},{"cited_title":"Quantum algorithms for generator coordinate methods","cited_arxiv_id":"2212.09205","evidence_quote":"Shows the GCM on a quantum computer and the automatic symmetry restoration that the paper relies on to fix QAOA's wrong parity and Hamming weight."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the overlap-matrix truncation method the paper uses to stabilise the generalised eigenvalue equation."},{"cited_title":"Analysis of the generator coordinate method in a study of shape isomerism in 194Hg,","cited_arxiv_id":null,"evidence_quote":"Gives the linear-combination-of-unitaries construction used for kernel evaluation and for re-encoding the mixed GCM state."},{"cited_title":"Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound- constrained optimization,","cited_arxiv_id":null,"evidence_quote":"Provides the optimal Clifford+T z-rotation decomposition whose T-gate counts enter the cost comparison."}],"review_version":1}