{"id":"e56f9ce8-1e48-4c7b-bc74-0345e032dfde","arxiv_id":"2509.00170","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For unweighted graphs, path graphs require at least n-1 global coupling layers, every graph can be compiled in at most 2.5n+2 layers, and perfect matching compilations are tied to Hadamard matrices.","lead":"This paper proves new limits on how few global entangling steps are needed to implement Max-Cut QAOA circuits on trapped-ion quantum computers, and it gives a faster optimization model for finding the best compilations. The results are useful because shorter circuits tolerate less noise, which matters for near-term quantum hardware.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 8's clique lower bound is false and contradicts Theorem 2: for K3∪K3, Theorem 2 gives gc=2 while Theorem 8 claims gc≥3, so the abstract's clique-bound claim and the combining paragraph are unsupported.","rationale":"The paper's main headline claims — the path lower bound gc(P_n) ≥ n−1 (Corollary 4), the universal upper bound gc(G) ≤ 2.5n+2 (Theorem 13), and the Hadamard equivalence gc(PM_q) = q iff a Hadamard matrix of order q exists (Theorem 11) — appear mathematically sound after independent checking. The path lower bound follows correctly from the spectral lower bound in Corollary 2 because path eigenvalues are distinct. The Union of Double-Stars construction partitions edges around chosen nonadjacent centers, uses shared all-ones rows correctly, and yields the stated row count. The Hadamard proof is also internally consistent: the forward direction correctly uses rank to force tr(W) ∈ {±1}, extracts the odd columns, and derives HH^T diagonal from H^T W H = ±I. The load-bearing defect I found is the false clique lower bound Theorem 8, which is contradicted by the paper's own Theorem 2. This matters because the abstract advertises sharper bounds for cliques, and the later summary paragraph relies on Theorem 8 to assert gc(K_q∪K_{n−q}) ∈ {q, q+1, q+2}. Since the error is a concrete rank miscalculation rather than a subtle modeling assumption, it should be corrected before publication; however, it does not invalidate the central theoretical advances on paths, general graphs, or perfect matchings. Secondary issues I noted but did not treat as load-bearing: the displayed formula in Theorem 10 appears to use the wrong coefficient on K_V ((1−q)/4 instead of the correct 1−q/4), the big-M constant M = 10 in Section IV.I is much smaller than the proven bound in [21] and could exclude feasible solutions, and the promised GitHub link for code and data is missing from the text, preventing exact reproduction of the numerical section. These support keeping the reader's CONDITIONAL verdict rather than upgrading to full acceptance.","tokens_in":21665,"tokens_out":29871,"duration_ms":278368,"concrete_test":"For the 6-vertex graph K_3∪K_3, run Algorithm 2 (or enumerate all P ∈ {±1}^{k×6} with first column fixed to 1 for k = 1,2,3 and solve the linear system for W). Theorem 2 predicts the minimum k is 2; Theorem 8 predicts k ≥ 3. If k = 2 is found, Theorem 8 is refuted. Equivalently, recompute rank(A + I) for this graph: A + I = J_3 ⊕ J_3 has rank 2, so min_α rank(A + αI) = 2 < 3, directly contradicting the case analysis in Theorem 8.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 8 asserts gc(K_q∪K_{n−q}) ≥ q for q ≤ n/2. This is false. For q = 3, n = 6, K_3∪K_3 is a disjoint union of two cliques with (a,b) = (3,3) ≠ (1,1), so Theorem 2 (proved in Appendix A) gives gc = 2. Theorem 8 would force gc ≥ 3, an internal contradiction. The error is in the rank case analysis: for α = 1, the last n−q rows of A + αI are claimed to be linearly independent, but for K_3∪K_3 they are identical — A + I = J_3 ⊕ J_3 has rank 2, not 3. Corollary 2 only yields n − max mult = 6 − 4 = 2. Consequently, the claimed lower bounds for clique families, the 'q ≤ gc ≤ q+2' summary, and the abstract's statement of sharper bounds for cliques are incorrect as written. This is a genuine mathematical defect, not merely a missing edge case. The headline path lower bound (Corollary 4), the Union of Double-Stars bound (Theorem 13), and the Hadamard equivalence (Theorem 11) do not rely on Theorem 8, so those central claims remain standing pending independent verification.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the graph coupling number gc(G), the minimum number of global MS-gate layers (with single-qubit bit flips) needed to realize a Max-Cut cost Hamiltonian for an unweighted graph G, formalized as a decomposition A = P^T W P ⊙ J with P ∈ {±1}^{k×n} and W diagonal. The main claimed contributions are: a spectral lower bound n − max mult(λ) ≤ gc(G); a lower bound gc(P_n) ≥ n−1 establishing order-optimality of the Union of Stars construction; an improved general upper bound gc(G) ≤ 2.5n+2 via a new Union of Double-Stars construction; family-specific bounds for cliques, perfect matchings, paths, and cycles; an equivalence between gc(PM_q) = q and the existence of a Hadamard matrix of order q; and a compact mixed-integer program (CMIPGC) with numerical comparisons against the exponential-size MIP of Rajakumar et al. The path lower bound, the double-star upper bound, and the Hadamard equivalence are substantial and appear internally correct. However, the clique lower bound stated in Theorem 8 is false and contradicts the paper's own Theorem 2, and several supporting arguments (Corollary 6, Algorithm 1, and the big-M choice) need correction before the paper can be accepted.","tokens_in":21949,"tokens_out":20511,"duration_ms":187463,"significance":"If the remaining issues are fixed, the paper would make solid contributions. The spectral lower bound is a clean and broadly applicable tool; the path lower bound is the first evidence of order-optimality of the existing Union of Stars construction; the Union of Double-Stars improves a known general upper bound; and the Hadamard equivalence is an elegant and surprising bridge between a compilation problem and a famous open conjecture. The compact MIP is polynomially sized and empirically outperforms the exponential baseline on the reported instances, and the authors state that code and data are publicly available. The false clique theorem is a genuine defect, but it is localized: the path, double-star, and Hadamard results do not depend on it. The paper merits a major revision rather than rejection, provided the incorrect claims are removed or corrected and the supporting proofs are made complete.","major_comments":[{"comment":"Theorem 8 is false as stated. For G = K_q ∪ K_{n−q} with q, n−q ≥ 2, the matrix A + I is the direct sum J_q ⊕ J_{n−q} of all-ones matrices, whose rank is 2, not n−q; the asserted 'last n−q rows are linearly independent' fails because those rows are identical. Corollary 2 therefore gives only gc(G) ≥ 2 for such graphs. This contradicts the paper's own Theorem 2, which gives gc(K_q ∪ K_{n−q}) = 2 whenever (q, n−q) ≠ (1,1). For example, K_3 ∪ K_3 has gc = 2 by Theorem 2, while Theorem 8 would force gc ≥ 3. Consequently, the bullet 'q ≤ gc(K_q ∪ K_{n−q}) ≤ q+2' in Section IV.F and the abstract's claim of sharper bounds for cliques are unsupported as written. This section should be rewritten; the correct lower bound for these graphs is 2, and the meaningful upper bound is already supplied by Theorem 2.","section":"Section IV.E, Theorem 8"},{"comment":"The proof of Corollary 6 is not valid as written. It sets G1 = G2 = K_q ∪ K_{n−q}, so Theorem 4 is applied to a single graph and the two cases do not distinguish anything; the subsequent construction 'adding rows' from G2 to G1 is vacuous when the graphs are identical. If the intended second graph is the complement K_{q,n−q}, then Theorem 4 gives |gc(G1) − gc(G2)| ≤ 1 rather than ≤ 2, and the claimed bound min{q, n−q} + 2 requires a different argument. This comment is related to Major Comment 1, but it is independent: the corollary's proof should be rewritten and its relation to Theorem 2 clarified.","section":"Section IV.F, Corollary 6"},{"comment":"The feasibility claim for the Union of Double-Stars is under-specified. Theorem 12 defines the double-star edge set using arbitrary pairwise-disjoint sets V3, V4, V5, V6, but Algorithm 1 never states how these sets are chosen for a given non-adjacent pair (v1, v2). If V6 contains a neighbor of v1 or v2, then the corresponding edge is not in the double-star and is not eliminated, so the statement that 'the proposed double-stars and the final clique partition the edges of the original graph' is not justified. The construction can be repaired by taking V3 = N(v1) \\ N(v2), V4 = N(v1) ∩ N(v2), V5 = N(v2) \\ N(v1), and V6 as the remaining vertices, but this choice must be stated explicitly and used in the proof of Theorem 13.","section":"Section IV.H, Theorem 13 and Algorithm 1"},{"comment":"The choice M = 10 for the big-M constant is unsupported and can invalidate the numerical results. The paper itself notes that Rajakumar et al. [21, Theorem 8] gives |W_{r,r}| ≤ (3n−2)(3n−1)/2, which is far larger than 10 for all but very small n. If an optimal weight exceeds 10 in magnitude, constraints (6)–(7) (and the linking constraint (2)) cut off the optimal solution, so both the primal and dual bounds reported in Table I may be incorrect. Either use the proven big-M bound, prove a tighter bound valid for the present formulation, or clearly label the reported experiments as heuristic under an unverified big-M assumption.","section":"Section IV.I, constraints (2), (6), (7)"}],"minor_comments":[{"comment":"The reference to 'Corollary 2' for the uniform behavior of vertices in the same column class is incorrect; the relevant statement is Remark 2 in Section IV.A.","section":"Theorem 12 proof"},{"comment":"The proof relies on several 'brute force verifies' claims (e.g., systems (A1)–(A3) and the 5–8 corner cases) without providing the verification code or a symbolic derivation; please make these checks reproducible, or state explicitly that Theorem 3 is a computation-assisted result. Note that the perfect-matching gap q ≤ gc(PM_q) ≤ q+1 follows from Corollaries 3 and 7 and does not require Theorem 3.","section":"Appendix A, proof of Theorem 3"},{"comment":"The coefficient in the displayed decomposition should read (q−1)/4 K_n rather than 'q−1/4 K_n' to avoid ambiguity.","section":"Section IV.F, Theorem 9"},{"comment":"The exhaustive search 'over all possible matrices P ∈ {±1}^{5×6}' is not by itself enough to prove optimality; please state that all k < 6 were enumerated using Algorithm 2 (or provide the script), and indicate how the first-column reduction and row symmetries were applied.","section":"Lemma 2"},{"comment":"The notation 'n − max_{λ∈spec(A)} mult(λ)' is correct for diagonalizable A but the proof should explicitly note that the minimum is attained at an eigenvalue of A; as written the case enumeration already covers this, but a one-sentence clarification would help.","section":"Section IV.D, Corollary 2"}],"recommendation":"major_revision","confidential_remarks":"The false Theorem 8 creates an internal contradiction with Theorem 2 that the authors should confront directly; it is not a typo and it affects the abstract and the Section IV.F summary. That said, the path lower bound, the 2.5n+2 construction, and the Hadamard equivalence appear to be the paper's strongest contributions and do not rely on the faulty clique theorem. I would encourage the editor to seek a revised version rather than reject, but the revisions must include a complete rewrite of the clique-family claims and a resolution of the big-M issue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has genuine value. The spectral lower bound (Theorem 7/Corollary 2) is a clean linear-algebra argument, and applying it to paths to get gc(P_n) ≥ n−1 correctly establishes order-optimality of the Union of Stars construction. The Union of Double-Stars is a clever way to shave the general upper bound from 3n−2 to 2.5n+2; the construction is explicit and the proof checks out. The Hadamard equivalence for perfect matchings is the most striking result—it ties gc(PM_q) to a famous open problem, and the proof is sound once you note that the diagonal of HH^T is automatically q for ±1 rows. The compact MIP is also a reasonable effort to replace the exponential formulation, and it does produce better dual bounds on larger instances.\n\nThe soft spot is Theorem 8. The stress-test note is correct: the claim gc(K_q ∪ K_{n−q}) ≥ q is false. For K_3 ∪ K_3, Theorem 2 says gc=2, but Theorem 8 forces gc≥3. The rank argument fails because the last n−q rows of A+I are identical, not independent. This invalidates the 'q ≤ gc ≤ q+2' summary and the abstract's mention of sharper bounds for cliques. The upper bound q+2 is fine, but the lower bound must be withdrawn or corrected. Since the main headline results don't rely on Theorem 8, the paper's core is still standing, but the clique section and the combining paragraph need revision.\n\nThe numerics are less compelling than the text suggests. Looking at Table I, CMIPGC gets better dual bounds but worse primal bounds on several instances (9-1, 10-1, 12-2, 13-1), so 'outperforms' overstates it. The big-M constant M=10 is asserted without proof, and the GitHub link is missing, so the experiments are not reproducible as written.\n\nWho is this for? Researchers working on MS-based compilation for QAOA, or on the graph coupling number as a graph parameter. The path lower bound and 2.5n+2 construction are worth knowing; the clique part should not be trusted until fixed.\n\nRecommendation: send to peer review, but be explicit that Theorem 8 is false. If the authors correct that theorem and soften the numerical claims, this becomes a solid contribution.","headline":"Real contributions in the path lower bound, the 2.5n+2 construction, and the Hadamard equivalence, but Theorem 8's clique lower bound is false and the numerical claims are overstated.","tokens_in":22498,"tokens_out":4292,"would_cite":true,"duration_ms":39192,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A23","05B20","90C11","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"Path graphs prove QAOA coupling compilation needs n−1 global layers, and Hadamard matrices decide the perfect-matching gap.","keywords":["quantum approximate optimization algorithm","Max-Cut problem","trapped-ion quantum computing","graph coupling number","Mølmer–Sørensen gates","mixed-integer programming","Hadamard matrices","cost Hamiltonian compilation"],"falsifier":"Solve the Graph Coupling Problem exactly for PM_6 by exhaustive enumeration of P ∈ {±1}^{7×12}. The theorem predicts the minimum is 7, since no Hadamard matrix of order 6 exists; a feasible 6-row solution would refute the Hadamard equivalence. As a weaker test, run the same exhaustive search on all graphs with n=6 vertices and compare the minimum to n minus the largest eigenvalue multiplicity; any graph whose gc is smaller than that bound would refute the spectral lower bound.","tokens_in":21441,"feed_emoji":"⚛️","tokens_out":6204,"duration_ms":56064,"temperature":0.7,"pith_summary":"This paper studies how few global entangling layers are needed to implement the Max-Cut cost Hamiltonian of QAOA on trapped-ion hardware, where the native operation couples all qubits at once. The authors work with the graph coupling number gc(G), the minimum number of Mølmer–Sørensen layers in a compilation that uses only global couplings and single-qubit bit flips. They prove that path graphs require gc(P_n) ≥ n−1 layers, showing that the prior Union of Stars construction is optimal in order, and they improve the general upper bound from 3n−2 to 2.5n+2 with a new Union of Double-Stars construction. They also show that deciding whether a perfect matching on q edges needs q or q+1 layers is exactly equivalent to the existence of a Hadamard matrix of order q. A compact mixed-integer program with polynomial size outperforms the earlier exponential formulation on small random graphs.","feed_headline":"Path graphs force n−1 layers in QAOA coupling compilation","feed_subtitle":"A double-star construction compiles any unweighted Max-Cut graph in at most 2.5n+2 global gates.","key_machinery":"The load-bearing object is the spin-biclique decomposition: a row of P in {±1}^{k×n} encodes a partition of the vertex set, and the matrix p p^T ⊙ J is the adjacency matrix of a complete graph whose edge signs are −1 across a cut and +1 inside each side. The identity A + tr(W)I = P^T W P converts the Hadamard product into an ordinary matrix product, so rank(W) = ||W||_0 bounds rank(A + tr(W)I); together with the spectral corollary this gives all lower bounds. The Union of Double-Stars construction uses the observation that any two non-adjacent vertices can be processed with five shared rows, one all-ones row reused across all double-stars, yielding the 2.5n+2 upper bound.","core_discovery":"The central discovery is that the minimal number of global MS layers in a bit-flip compilation of a Max-Cut cost Hamiltonian equals the minimum rank of a signed decomposition of the graph's adjacency matrix, and that this number is controlled by spectral degeneracy. For any unweighted graph, gc(G) is at least n minus the largest eigenvalue multiplicity of its adjacency matrix; this yields gc(P_n) ≥ n−1 and makes the earlier Union of Stars bound order-optimal. For perfect matchings, the gap collapses to one: gc(PM_q) equals q exactly when a Hadamard matrix of order q exists, and otherwise equals q+1, so closing the gap is equivalent to resolving the Hadamard conjecture. Replacing the star-by-star decomposition by a double-star decomposition reduces the universal upper bound from 3n−2 to 2.5n+2, and the paper's polynomial-size MIP, called CMIPGC, finds better primal bounds than the exponential MIP on the tested random graphs up to 20 vertices.","pith_inferences":["If the spectral lower bound were tight for broader graph families, graphs with highly degenerate adjacency spectra would be the cheapest to compile, suggesting a spectral heuristic for ordering decomposition algorithms.","The Hadamard equivalence turns the Hadamard conjecture into a circuit-design question: an explicit q-layer circuit for PM_q at any q divisible by 4 would construct an order-q Hadamard matrix, giving a concrete compilation route to the conjecture.","The empirical appearance of an all-ones row in every optimal P suggests a normalization that, if proved, would imply gc(G)=gc(complement); a testable next step is exhaustive verification on all graphs up to n=8.","The small big-M constant used in the experiments is far below the proven bound, so a systematic study of valid big-M ranges could shrink the MIP further; this is an experiment suggested by the paper's results, not a claim the paper makes."],"forward_implications":["Every unweighted graph on n vertices admits a Max-Cut cost Hamiltonian circuit with at most 2.5n+2 global MS gates, improving the previous 3n−2 guarantee.","Any QAOA Max-Cut compilation of a path graph P_n needs at least n−1 MS layers, so the earlier Union of Stars construction cannot be asymptotically improved by more than a constant factor.","For a perfect matching on q edges, exactly q layers are possible if and only if a Hadamard matrix of order q exists; in particular, gc(PM_4)=4 while gc(PM_6)=7.","No unweighted graph has graph coupling number 3, and the only graphs with gc=2 are bicliques K_{a,b} with (a,b) not (1,1) and disjoint unions K_a ∪ K_b with (a,b) not (1,1).","The new polynomial-size MIP uses the spectral lower bound as a cutting plane and the combinatorial constructions as warm starts, giving valid upper bounds that improve on the exponential-size baseline on larger random instances."],"supporting_citations":[{"why":"Defines the Graph Coupling Problem and the graph coupling number, and supplies the Union of Stars 3n−2 construction and the exponential-size MIP that this paper improves.","marker":"[21]"},{"why":"Provides the eigenvalue spectra of complete graphs and paths used to prove the lower bounds for those families.","marker":"[4]"},{"why":"Supplies the rank inequality rank(AB) ≤ min{rank A, rank B} that underlies the spectral lower bound.","marker":"[22]"},{"why":"Gives the background on Hadamard matrices, including the divisibility condition, used in the equivalence for perfect matchings.","marker":"[10]"},{"why":"Provides the linearization inequalities (Padberg cuts) used in the compact MIP formulation.","marker":"[18]"}],"fun_headline_variants":["QAOA coupling layers tied to adjacency spectral degeneracy","Hadamard conjecture equivalence found for QAOA coupling ranks","Double-star compilation cuts QAOA upper bound to 2.5n+2","Path graphs need n-1 global layers for QAOA compilation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theory assumes that every compiled circuit corresponds exactly to a decomposition A = P^T W P ⊙ J with arbitrary real weights on the global MS layers, and that no other native two-qubit gates are available; if hardware allows additional gates or restricts the achievable weights, these bounds are not guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["QAOA coupling layers tied to adjacency spectral degeneracy","Hadamard conjecture equivalence found for QAOA coupling ranks","Double-star compilation cuts QAOA upper bound to 2.5n+2","Path graphs need n-1 global layers for QAOA compilation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000582,"raw_usage":{"total_tokens":2789,"prompt_tokens":1043,"completion_tokens":1746,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":659,"completion_tokens_details":{"reasoning_tokens":1674}},"tokens_in":659,"tokens_out":1746,"duration_ms":12185,"temperature":1.0,"reasoning_tokens":1674,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:42:45.613215+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve the Graph Coupling Problem exactly for PM_6 by exhaustive enumeration of P ∈ {±1}^{7×12}. The theorem predicts the minimum is 7, since no Hadamard matrix of order 6 exists; a feasible 6-row solution would refute the Hadamard equivalence. As a weaker test, run the same exhaustive search on all graphs with n=6 vertices and compare the minimum to n minus the largest eigenvalue multiplicity; any graph whose gc is smaller than that bound would refute the spectral lower bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the eigenvalue spectra of complete graphs and paths used to prove the lower bounds for those families."},{"cited_title":"Practical guidelines for solving difficult mixed integer linear programs","cited_arxiv_id":null,"evidence_quote":"Supplies the rank inequality rank(AB) ≤ min{rank A, rank B} that underlies the spectral lower bound."},{"cited_title":"Quadratic reformulations of nonlinear binary optimization problems","cited_arxiv_id":null,"evidence_quote":"Gives the background on Hadamard matrices, including the divisibility condition, used in the equivalence for perfect matchings."},{"cited_title":"Rydberg-mediated entanglement in a two-dimensional neutral atom qubit array","cited_arxiv_id":null,"evidence_quote":"Provides the linearization inequalities (Padberg cuts) used in the compact MIP formulation."}],"review_version":2}