{"id":"d0015d6f-cde6-414f-ba27-a11e54d548fc","arxiv_id":"2608.01121","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Conditional on inverse-polynomial optimal sampling mass, the NP-HQ pipeline is a polynomial-time randomized scheme that recovers exact optima, and the paper adds a quantum-classical separation claim plus a small hardware test.","lead":"The paper shows that if a noisy quantum sampling circuit assigns an inverse-polynomial share of its output to optimal solutions of a constrained optimization problem, a classical repair and scoring step can recover an optimum in polynomial time. It argues that the bottleneck for classical computers is producing that sampling distribution, not processing it.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central premise is uninstanced and, within the paper's own dephased-envelope analysis, fails for the canonical TSP/assignment kernel: Cβ = |Ω*|/n^n, so Corollary 37 cannot yield q0 = Ω(n^{-k}).","rationale":"The reader's weakest assumption is exactly the inverse-polynomial optimal-mass premise. My stress-test sharpens it: not only is no concrete NP-hard family shown to satisfy Cβ ≥ c0 n^{-a}, but within the paper's own dephased Markov-chain model the condition is false for the assignment/TSP kernel on which the hardware section is built. The block-local XY mixer preserves the uniform product distribution, so Wp is uniform for all depths and the optimal-set envelope weight is exponentially small. This means Eq. (10), as derived from Corollary 37, cannot support the inverse-polynomial premise for the paper's prototype instances. The conditional theorem itself (if p_min inverse-polynomial, then FPRASq) is a straightforward Chernoff argument and is not wrong; the problem is that the antecedent is never satisfied, and the only analytic route offered to satisfy it fails on the canonical kernel. I therefore keep the reader's CONDITIONAL verdict: the framework may be repairable if a concrete kernel or coherent-interference argument establishes p_min, but as written the substantial claims (FPRASq, separation, hardware-informed improvement) have no verified instance. Agreement is partial because the reader left open the possibility that some family satisfies the envelope conditions; the present concern closes that route for the flagship kernel.","tokens_in":32205,"tokens_out":11605,"duration_ms":245971,"concrete_test":"Compute Cβ exactly for the n×n assignment kernel with m=nloc=n under Definition 1 and Eq. (5), e.g., p=1 and generic β, and verify that Wp(z;β)=n^{-n} on all z by direct diagonalization of the block-XY mixer transition matrix; then Cβ=|Ω*|/n^n. Supplement with exact-statevector CE-QAOA for n=4,...,10 (e.g., QOptlib wi4–dj10) over the coarse grid: if no grid point yields q0(Ω*) ≥ c n^{-k} for fixed k, the central premise is unverified. If the analytical identity holds, Corollary 37 cannot provide the premise.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The entire FPRASq, noise, HH-QAOA, and separation results rest on the premise p_min ≥ c n^{-k} (Eq. 18), which Theorem 17 only converts into a Chernoff bound. The paper sources this premise from Corollary 37 via the optimal-set envelope weight Cβ in Eq. (6). But for the OFM assignment/TSP kernel (Definition 1 with m=nloc=n), the envelope is exactly uniform: v(0)(z)=|⟨z|s0⟩|^2 = n^{-n}, and each Mβ is doubly stochastic (Lemma 34), so Wp(z;β)=[Mβp···Mβ1 v(0)](z)=n^{-n} for every p,β. Therefore Cβ = Σ_{x∈Ω*} Wp(x;β) = |Ω*|/n^n ≤ n!/n^n = exp(-Θ(n)). Thus Cβ ≥ c0 n^{-a} fails for every fixed a at sufficiently large n, so Eq. (10)/Corollary 37 cannot instantiate the inverse-polynomial premise on the flagship kernel. The premise could still be true coherently, but the paper explicitly disclaims a pointwise ordering between coherent and dephased probabilities (§2.3); no independent argument or concrete family is supplied. Consequently the central claim has no demonstrated instance.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a hybrid quantum–classical optimization pipeline (NP-HQ) built on the CE–QAOA/OFM kernel. Its main theoretical claim is that if the ideal CE–QAOA distribution assigns inverse-polynomial probability mass q0 ≥ c n^{-k} to the optimal feasible set, then independent-shot amplification, polynomial-time feasibility repair, and exact scoring yield an exact-hit FPRASq; the claim is extended to a noise-robust form via a total-variation Lipschitz bound, to a complexity-theoretic separation against classical samplers, and to a Heavy-Hitter QAOA refinement that reduces classical post-processing cost. The paper also reports hardware experiments on IBM Eagle r3 processors for QOptlib TSP instances with up to 100 logical variables, claiming to match or improve the reference tours. The theoretical derivations are conditional on the inverse-polynomial optimal-mass premise, which the paper sources to self-cited references and to an appendix (Appendix A.5) that requires additional envelope and phase-gap conditions.","tokens_in":32570,"tokens_out":8147,"duration_ms":96178,"significance":"If the inverse-polynomial optimal-mass premise were established for a concrete NP-hard family, the paper's FPRASq theorem, noise-to-shot-complexity translation, and repair-based post-processing framework would constitute a useful template for end-to-end quantum optimization. The conditional proofs are mostly elementary and correct: the Chernoff amplification argument in Theorem 17, the total-variation noise bound in Appendix A.6, and the repair lemmas in Section 3.1 are all cleanly presented. The heavy-hitter analysis is also logically sound. However, the paper does not provide any concrete instance where the central premise q0 ≥ c n^{-k} is verified. The only derivation offered (Corollary 37) requires Cβ ≥ c0 n^{-a} and sin²(δ/2) ≥ c1, and for the flagship assignment/TSP specialization, the dephased envelope weight is exactly uniform, giving Cβ = |Ω*|/n^n ≤ n!/n^n = exp(-Θ(n)), so the premise cannot be instantiated in that model. The hardware section lacks error bars, shot counts in the comparison tables, and any classical baseline. The paper's value is therefore as a rigorous conditional framework, not as an established polynomial-time quantum approximation scheme.","major_comments":[{"comment":"The central premise q0 ≥ c n^{-k}, on which Theorems 5, 17, and 30 all rest, is not instantiated for any concrete NP-hard family. Appendix A.5 derives it from the two further conditions Cβ ≥ c0 n^{-a} and sin²(δ/2) ≥ c1, but for the assignment/TSP specialization of Definition 1 with m = nloc = n, the initial diagonal v(0)(z) = |⟨z|s0⟩|² = n^{-n} is uniform, and each mixer transition matrix Mβ is doubly stochastic (Lemma 34). Hence Wp(z;β) = n^{-n} for every z and every β, giving Cβ = Σ_{x∈Ω*} Wp(x;β) = |Ω*|/n^n ≤ n!/n^n = exp(-Θ(n)). Thus Cβ ≥ c0 n^{-a} fails for every fixed a at sufficiently large n, so Corollary 37 cannot supply the inverse-polynomial premise on the paper's flagship kernel. The paper explicitly disclaims a pointwise ordering between coherent and dephased probabilities (§2.3), so the premise remains an unsupported assumption. The authors should either prove q0 ≥ c n^{-k} for a concrete kernel-admissible family (coherently, not only via the dephased reference law), or explicitly state that all main results are conditional on an assumption that is not established in this paper.","section":"§2.3, Eq. (10); Appendix A.5 (Corollary 37)"},{"comment":"The claimed quantum–classical separation is not a demonstrated separation. Theorem 21 shows that if a classical sampler achieved inverse-polynomial optimal overlap, standard repetition would place the promise search problem in BPP, implying NP ⊆ BPP; this is a valid conditional statement, but it does not establish that NP-HQ actually has such overlap, since that is precisely the unproven q0 premise. Theorem 22 is titled 'Perfect structural oracles do not yield inverse-polynomial optimal overlap,' but its proof merely assumes that some algorithm with oracle (A)–(C) achieves such overlap and derives a BPP containment; no lower bound against the oracles is proved. The separation is therefore entirely contingent on the uninstantiated premise, and the wording overstates what has been shown.","section":"§3.4, Theorems 21 and 22"},{"comment":"The hardware demonstration, which the abstract summarizes as matching or improving every tested QOptlib reference tour, is not statistically supported. Tables 3 and 5 report a single best repaired cost per instance with no error bars, no number of shots used in the comparison, no repetition statistics, and no classical baseline such as random sampling plus Hungarian repair or a standard TSP heuristic. Without these, the reported improvements (e.g., 12.5% on dj9) cannot be distinguished from noise or from the repair routine's deterministic output. The empirical section should report shot counts, multiple runs or confidence intervals, and a classical comparison before the 'match or improve' claim is made.","section":"§4, Tables 3 and 5"}],"minor_comments":[{"comment":"The text refers to 'the prolem Hamiltonian' (typo for 'problem Hamiltonian') near the beginning of Section 4; please correct.","section":"§4.1"},{"comment":"The implementation section states Qiskit 1.1.2, but Reference [49] cites Qiskit version 0.47; please reconcile the version and the reference.","section":"§4.2 and Reference [49]"},{"comment":"The benchmark name is spelled inconsistently as 'QOptlib' and 'QOPTLib'; please standardize to the official name used in Reference [3].","section":"Throughout"},{"comment":"Lemma 16 (column-swap repair with C(~x) ≤ C(x) + 3n w_max) is stated without proof or a precise pointer to the argument in Reference [46]; since Proposition 19 relies on this bound, a proof or a more specific reference should be provided.","section":"§3.2, Lemma 16"},{"comment":"The gap columns in Tables 6 and 7 report percentage deviations from exhaustive analysis of the raw histogram, but the table captions do not clarify this; please make the baseline explicit and consider whether the top-L compression gaps (e.g., 0.19% in Table 6) are within the noise of the hardware runs.","section":"§5.4, Tables 6 and 7"}],"recommendation":"major_revision","confidential_remarks":"The paper leans heavily on self-citations (Refs [1, 23, 24]) for the central inverse-polynomial optimal-mass premise, and the only derivation in this manuscript (Appendix A.5) fails for the assignment/TSP specialization in the dephased model. I would ask the editor to consider whether the journal should accept a paper whose main results are conditional on an unproved and possibly false premise. The hardware section is also far below the standard expected of an experimental quantum paper: no error bars, no shot counts in the comparison tables, and no classical baseline. If the paper is revised, the authors should clearly scope the claims as conditional theorems and either supply a concrete family satisfying the premise or remove the suggestion that such a family is known to exist."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is best read as a conditional framework rather than a demonstrated result. The machinery is clean: if you grant p_min = Ω(n^{-k}) on the optimal set, then the NP-HQ pipeline (CE-QAOA sampling, Hungarian repair, scoring) is an exact-hit FPRASq, the total-variation noise bound converts depth into a shot budget, and the heavy-hitter variant cuts post-processing by one power of n. The conditional theorems are elementary and, as far as I checked, correct. The writing is transparent about what is assumed, and the literature on constrained quantum optimization is covered reasonably.\n\nThe soft spot is the load-bearing premise. The paper borrows q0 ≥ c n^{-k} from the authors' earlier CE-QAOA papers, and Appendix A.5 tries to re-derive it via the dephased envelope weight Cβ. The stress-test note is right: for the assignment/TSP kernel in Definition 1, the initial distribution is exactly uniform over n^n strings, and every mixer transition is doubly stochastic, so Wp stays uniform. That gives Cβ = |Ω*|/n^n ≤ n!/n^n = exp(-Θ(n)). Corollary 37 therefore cannot produce an inverse-polynomial lower bound on this family. The paper does disclaim a pointwise ordering between coherent and dephased probabilities, so this does not refute the premise—it just leaves it with no demonstrated instance and removes the one concrete derivation that was offered.\n\nThe hardware section is real but modest: up to 100 logical qubits, single-layer CE-QAOA, and the output is compared to QOptlib references. Matching or improving those references is suggestive, but there is no classical baseline, no error bars, and no statistical analysis, so it should be read as a demonstration of the pipeline, not evidence for the FPRASq claim. The separation theorem is essentially a restatement of the premise: if a classical sampler could reproduce inverse-polynomial overlap on an NP-hard family, then NP ⊆ BPP by amplification. That is correct but does not add independent evidence.\n\nOverall, this is a serious paper worth a referee's time, but the referee should push hard on the missing instance of the central premise. The framework is coherent, the conditional results are solid, and the failure of the dephased envelope for the canonical kernel is an important caveat the authors should address. I would engage with it, but I would not cite it as evidence for quantum advantage in constrained optimization without seeing a concrete problem family that actually satisfies the premise.","headline":"A readable, honest conditional framework for quantum optimization whose central inverse-polynomial optimal-mass premise is never instanced, and whose own dephased envelope analysis actually fails for the flagship assignment/TSP kernel.","tokens_in":33025,"tokens_out":3768,"would_cite":false,"duration_ms":53399,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q17","68W20","90C27"],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"The paper claims that a constrained-QAOA sampler followed by deterministic feasibility repair and exact scoring becomes an exact-hit FPRASq in polynomial time whenever its ideal output puts inverse-polynomial probability on the optimal set.","keywords":["quantum approximation scheme","constrained optimization","QAOA","FPRAS","feasibility repair","heavy-hitter filtering","NISQ","quantum-classical separation"],"falsifier":"Compute the ideal (noiseless) CE-QAOA output distribution for a sequence of TSP or QAP instances with $n=10,20,40,80$; if the optimal-set probability $q_0$ decays faster than every inverse polynomial, or the envelope weight $C_\\beta$ drops below $c_0 n^{-a}$ with growing $a$, the exact-hit FPRASq premise fails on those instances.","tokens_in":32014,"feed_emoji":"⚛️","tokens_out":10719,"duration_ms":114108,"temperature":0.7,"pith_summary":"The paper sets out to close the loop between a quantum sampler and a classical optimizer: rather than treating QAOA as a heuristic whose raw outputs are used directly, it wraps the CE-QAOA sampling distribution in a deterministic checker, repair map, and scorer, and analyzes the pipeline's end-to-end runtime and success probability. The central claim is that if the ideal CE-QAOA circuit assigns at least $c n^{-k}$ probability to the globally optimal set, then the full pipeline is an exact-hit fully polynomial randomized approximation scheme (FPRASq): with $O(n^{k+1}\\log(1/\\delta))$ shots under noise it returns a global optimum with probability at least $1-\\delta$, in polynomial total runtime. The paper also claims a conditional separation: no polynomial-time classical sampler equipped with the same repair and scoring can reproduce that inverse-polynomial optimal overlap on an NP-hard kernel-admissible promise family unless NP is contained in BPP. The result pinpoints the sampling distribution, not the classical post-processing, as the locus of any quantum advantage, and it gives near-term hardware experiments a concrete performance target.","feed_headline":"Noisy quantum sampler plus repair yields polynomial-time guarantee","feed_subtitle":"Guarantee holds when the ideal circuit gives optimal strings inverse-polynomial weight; noise costs one extra power of n.","key_machinery":"The load-bearing mechanism is the inverse-polynomial optimal-mass premise $q_0 \\ge c n^{-k}$, obtained from the factorized reference distribution $\\Pr_p^{\\mathrm{ref}}[z] \\propto W_p(z;\\beta)\\, F_p(\\theta(z)-\\theta^\\star)$, where $W_p$ is the mixer-envelope distribution induced by the block-local XY mixer and $F_p$ is the Fejér phase filter of order $p$ peaking at the optimal wrapped phase $\\theta^\\star$. This identity converts a circuit-success question into a geometric one: whether the optimal-set envelope weight $C_\\beta$ and the wrapped phase gap $\\delta$ satisfy $C_\\beta \\ge c_0 n^{-a}$ and $\\sin^2(\\delta/2) \\ge c_1$, which yields $q_0 = \\Omega(n^{-a})$ dimension-free. The rest of the pipeline, deterministic feasibility repair by nearest-permutation projection (solved by the Hungarian algorithm) and exact scoring, preserves or increases the mass on the optimal set and turns the bound into a Chernoff-amplified shot count.","core_discovery":"On the paper's own terms, the discovery is that constrained quantum optimization can be made a provable polynomial-time randomized approximation scheme by composing three ingredients: the CE-QAOA kernel (a one-hot encoded subspace evolved by a block-local XY mixer and a diagonal cost Hamiltonian), a factorized reference model in which the mixer envelope and a Fejér phase filter control the output distribution, and a classical repair stage that projects any measured bit-matrix to the nearest permutation in Hamming distance. Given the inverse-polynomial optimal-mass premise $q_0 = \\Omega(n^{-k})$, Theorem 17 shows the output is exactly optimal with probability at least $1-\\delta$ after $O(n^k \\log(1/\\delta))$ shots; under a total-variation noise bound the shot budget becomes $O(p n^{k+1} \\log(1/\\delta))$ while retaining inverse-polynomial optimal mass. Outside that window, deterministic repair still guarantees feasibility and an instance-dependent $(1+\\varepsilon)$ approximation whenever the repair inflation is controlled. The separation theorem is conditional: if any polynomial-time classical sampler achieved inverse-polynomial optimal overlap uniformly on an NP-hard kernel-admissible promise family, standard amplification would put the promise search problem in BPP.","pith_inferences":["Editorial inference: the theorem's premise is the practical crux; a reader should treat the FPRASq guarantee as conditional until some concrete kernel-admissible problem family is shown to satisfy the envelope-weight and phase-gap bounds.","Editorial inference: the checker-repair-scorer template transfers beyond TSP to any constraint class with a polynomial-time feasibility oracle and a bounded repair map, so the same three-part pipeline could be instantiated for scheduling, packing, or matching problems.","Editorial inference: the quantum-informed heavy-hitter threshold provides a device-calibration diagnostic, because the threshold's validity window is exactly the regime where the noisy output distribution stays within total-variation distance of the ideal one.","Editorial inference: a natural testable extension is to measure the empirical optimal-mass exponent $k$ on larger instances and check whether it stays bounded; a growing exponent would falsify the premise for those instances."],"forward_implications":["Under the inverse-polynomial optimal-mass premise, the NP-HQ pipeline is an exact-hit FPRASq: it returns a global optimum with probability at least $1-\\delta$ in $O(n^k \\log(1/\\delta))$ shots, with no dependence on $\\varepsilon$.","Within the noise window of Theorem 5, retaining a $1/G(n,p)$ fraction of the ideal optimal mass keeps the guarantee, at the price of one extra power of $n$ in the shot budget, $O(p n^{k+1} \\log(1/\\delta))$.","Heavy-Hitter QAOA cuts the retained candidate set and classical post-processing by one power of $n$ (from $O(n^{k+1})$ to $O(n^k)$) without weakening the exact-hit guarantee.","The separation theorem locates any quantum advantage in the sampling distribution itself, because a classical sampler granted the same repair and perfect constraint-structure access would imply NP$\\subseteq$BPP if it matched the inverse-polynomial overlap.","On IBM Eagle r3 hardware, the repair pipeline matches or improves the published QOptlib reference tours on all tested instances with up to 100 logical variables."],"supporting_citations":[{"why":"supplies the factorized reference law and the inverse-polynomial optimal-mass premise that Theorem 17 relies on.","marker":"[1]"},{"why":"introduces the OFM kernel and the PHQC algorithm that NP-HQ extends with repair and scoring.","marker":"[23]"},{"why":"defines the NISQ oracle model used to state the conditional quantum-classical separation.","marker":"[2]"},{"why":"provides the Hungarian assignment algorithm used as the $O(n^3)$ deterministic repair primitive.","marker":"[20]"},{"why":"provides Edmonds' matching algorithm as an alternative feasibility-repair primitive.","marker":"[22]"},{"why":"supplies the swap-and-repair heuristic and its $3n w_{\\max}$ additive bound for the fallback approximation guarantee.","marker":"[46]"},{"why":"supplies the QOptlib TSP benchmark instances used in the hardware demonstration.","marker":"[3]"},{"why":"supplies the diamond-norm and trace-distance inequalities used to convert device noise into a shot budget.","marker":"[47]"}],"fun_headline_variants":["Quantum noisy sampler makes constrained optimization tractable","Repair turns noisy quantum sampling into polynomial-time algorithm","Polynomial-time approximation from quantum sampling plus repair","Heavy-Hitter QAOA: fewer samples, same guarantees","Quantum sampling gives provable polynomial-time approximation with repair"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the ideal circuit's probability on the optimal set is at least an inverse polynomial in $n$, a condition the paper derives from further untested conditions on the mixer envelope weight and the wrapped phase gap but does not certify for any concrete NP-hard family.","fun_headline_variants_meta":{"raw":{"variants":["Quantum noisy sampler makes constrained optimization tractable","Repair turns noisy quantum sampling into polynomial-time algorithm","Polynomial-time approximation from quantum sampling plus repair","Heavy-Hitter QAOA: fewer samples, same guarantees","Quantum sampling gives provable polynomial-time approximation with repair"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000621,"raw_usage":{"total_tokens":2935,"prompt_tokens":1056,"completion_tokens":1879,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":1804}},"tokens_in":672,"tokens_out":1879,"duration_ms":18906,"temperature":1.0,"reasoning_tokens":1804,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T01:00:43.354137+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the ideal (noiseless) CE-QAOA output distribution for a sequence of TSP or QAP instances with $n=10,20,40,80$; if the optimal-set probability $q_0$ decays faster than every inverse polynomial, or the envelope weight $C_\\beta$ drops below $c_0 n^{-a}$ with growing $a$, the exact-hit FPRASq premise fails on those instances.","supporting_citations":[{"cited_title":"Wilde.Quantum Information Theory","cited_arxiv_id":null,"evidence_quote":"supplies the diamond-norm and trace-distance inequalities used to convert device noise into a shot budget."}],"review_version":2}