{"id":"dadf40fb-7715-44cb-a45c-7a3cc02898f8","arxiv_id":"2412.14932","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The claimed QMA1-hardness of sparse balancedness and sparse bipartitedness is not established, because the main spectral equivalence is false.","lead":"This paper claims that detecting a balanced component in a sparse signed graph, or a bipartite component in a sparse unsigned graph, is QMA1-hard under a succinct circuit-access input model. The central reduction from clique homology relies on a proposed equivalence between Hodge Laplacians and signed graph Laplacians that fails on a simple two-edge example.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1's claimed unitary equivalence fails because the Hodge Laplacian diagonal counts p+1 faces plus cofaces, while the signed graph Laplacian diagonal counts distinct lower/upper neighbors; these are unequal in general, and the clique-complex restriction does not fix it.","rationale":"I read the paper as attempting to show QMA1-hardness of testing balanced and bipartite components by mapping clique homology to spectral properties of signed and unsigned graph Laplacians. The load-bearing step is Proposition 1, which is used to transfer kernel non-triviality from the Hodge Laplacian to the signed graph Laplacian. The reader identifies a concrete diagonal mismatch in the proof: the Hodge diagonal counts the p+1 faces of a simplex plus its cofaces, whereas a simple graph Laplacian diagonal counts adjacent vertices. This is not a mere normalization artifact; it changes the kernel, as the two-edge path example demonstrates. I independently verified the matrix entries for that example: with the paper's sign convention, the lower-adjacency contribution to the off-diagonal is -1, the upper contribution is 0, and the diagonal of L_p is 2, while the constructed graph has degree 1. Hence the Hodge Laplacian and the graph Laplacian are not unitarily equivalent, and the kernel is different. Because this example is a clique complex of a path graph, the failure also invalidates the reduction from clique homology on the very input family the paper targets. The promise variants and containment-in-QMA arguments are not affected by this flaw, but they do not establish hardness. I see no way to repair the main theorems without changing the graph construction or the sign/diagonal structure, so the reader's REJECT verdict is appropriate and I would leave it unchanged.","tokens_in":26205,"tokens_out":7811,"duration_ms":64551,"concrete_test":"Compute the p=1 Combinatorial Hodge Laplacian of the clique complex of the path graph on vertices {0,1,2} and compare it with the signed graph Laplacian produced by Proposition 1. The former is [[2,-1],[-1,2]] with no zero eigenvalue; the latter is [[1,-1],[-1,1]] with a zero eigenvalue. If the two matrices differ in diagonal entries or zero-eigenvalue multiplicity, Proposition 1 is false and the reduction fails even on input instances of the claimed hardness family.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reduction in Section III.D hinges on Proposition 1, which asserts that the Combinatorial Hodge Laplacian L_p^Gamma is unitarily equivalent to the signed graph Laplacian of the constructed graph G_s. The proof in Section III.C computes the diagonal of L_p as p+1+deg^up(sigma) (around Eqs. 19-23) and then identifies this with the degree of vertex sigma in G_s. This identification is false: the graph degree counts distinct p-simplices that are lower- or upper-adjacent to sigma, not the p+1 faces of sigma plus its cofaces. In general a face of sigma may be contained in no other p-simplex, and a coface contributes one graph neighbor, not deg^up(sigma) as a count of cofaces. A concrete counterexample already lies in the family used for the reduction: take the clique complex of the path graph on vertices {0,1,2} at p=1. The two 1-simplices {0,1} and {1,2} are lower-adjacent but not upper-adjacent. The Hodge Laplacian is [[2,-1],[-1,2]] (diagonal p+1=2, kernel trivial), while the graph from Proposition 1 has one negative edge and Laplacian [[1,-1],[-1,1]] (diagonal 1, kernel nontrivial). Thus the kernel is not preserved, and the completeness and soundness steps of Theorem 1 collapse. Theorem 2 inherits the failure through its reduction from sparse balancedness. The limitation is not external to the paper's assumptions; it is an internal inconsistency in the central construction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to prove QMA1-hardness of two graph problems: deciding whether a sparse signed graph has a balanced connected component (Theorem 1) and deciding whether a sparse unsigned graph has a bipartite connected component (Theorem 2). The proofs are built on Proposition 1, which asserts a unitary equivalence between the p-th Combinatorial Hodge Laplacian of an abstract simplicial complex and the signed Laplacian of a graph whose vertices are the p-simplices and whose edges correspond to lower and upper adjacency. The authors introduce a marked sparse-access model, give QMA containment arguments for promise variants via block encodings, and connect their results to hardness of spectral properties of stoquastic Hamiltonians.","tokens_in":26501,"tokens_out":7828,"duration_ms":61466,"significance":"If the main equivalence were correct, the paper would establish new QMA1-hardness results for natural network-science properties and would add another example of hard spectral questions for stoquastic Hamiltonians. The paper is clearly organized, and the treatment of sparse access and the QMA containment arguments are useful. However, the central unitary equivalence is false, so the two hardness theorems are not established; the proposed reduction fails on an elementary example within the intended reduction family.","major_comments":[{"comment":"The claimed unitary equivalence is invalid because the diagonal entries of the two Laplacians do not match. In Eq. (20), the upper Laplacian diagonal is deg^up(sigma), the number of (p+1)-cofaces of sigma, while the degree of sigma in the upper-adjacency graph G^up_s counts upper-adjacent p-simplices, which equals (p+1) times the number of cofaces for p >= 1. Similarly, the lower Laplacian diagonal is p+1, but the degree in the lower-adjacency graph counts distinct p-simplices sharing a face with sigma, which need not equal p+1. A concrete counterexample from the reduction family is Gamma = Cl(P_3), the clique complex of the path on three vertices, at p=1. The two 1-simplices give L_1 = [[2,-1],[-1,2]] with trivial kernel, whereas the graph constructed in Proposition 1 is a single edge with signed Laplacian [[1,-1],[-1,1]] and nontrivial kernel. These matrices are not unitarily equivalent, so Proposition 1 is false.","section":"Section III.C, Proposition 1 and Eqs. (19)-(23)"},{"comment":"Because Proposition 1 is the only bridge from clique homology to balanced components, the completeness and soundness steps of Theorem 1 collapse. The counterexample above is a no-instance of clique homology (trivial first homology) that maps to a yes-instance of sparse balancedness (the single-edge signed graph is balanced), so the reduction is not sound. The proof also states that the Combinatorial Hodge Laplacian has a diagonal counting the non-zero entries per row; this is false, since the diagonal entry p+1+deg^up(sigma) is not the number of non-zero off-diagonal entries. Thus the hardness of sparse balancedness is unsupported.","section":"Section III.D, Theorem 1"},{"comment":"Theorem 2 inherits the failure of Theorem 1. The Zaslavsky negative-subdivision reduction from balancedness to bipartiteness (Proposition 15) is valid, but it is applied to an input whose QMA1-hardness has not been established because Proposition 1 is false. Consequently, the QMA1-hardness of sparse bipartitedness is also unsupported.","section":"Section IV.C, Theorem 2"}],"minor_comments":[{"comment":"Definition 2 for marked sparse access to signed graphs is repeated verbatim in the introduction and again in Section II.C; the duplicate definitions should be renumbered and consolidated.","section":"Section II.C"},{"comment":"The notation sng(sigma cap tau, partial sigma) is a typo: the second argument should be sigma, not partial sigma, since the sign function sng is defined on pairs of simplices. The same notational slip appears in the sign formula in Proposition 1.","section":"Section III.C, Eq. (23)"},{"comment":"The soundness inequality contains a misplaced parenthesis: it writes <psi|I_notV)|psi> instead of <psi|I_notV|psi>; this should be corrected.","section":"Section III.F, proof of Proposition 2"},{"comment":"The final sentence, 'as another example of testing properties related to the eigenspace of a stoquastic Hamiltonians are quantumly hard in the sparse input model for the graph', contains a grammatical error and should be rephrased.","section":"Abstract"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, the short version: the paper advertises QMA1-hardness for testing balanced components in sparse signed graphs and bipartite components in sparse unsigned graphs, but the main reduction is built on Proposition 1, and Proposition 1 is false. The reader's counterexample is correct and lands directly: take the clique complex of the path on three vertices at p=1. The two edges form a complex with Hodge Laplacian [[2,-1],[-1,2]] (kernel trivial), while the Proposition 1 construction yields a single signed edge with graph Laplacian [[1,-1],[-1,1]] (kernel nontrivial). These are not unitarily equivalent, so the zero-eigenvalue correspondence collapses, and with it the completeness and soundness of Theorem 1. Theorem 2 inherits the failure.\n\nThe root issue is in the diagonal computation. The Hodge Laplacian's diagonal counts, for each p-simplex, its p+1 faces (always present) plus its cofaces. The graph Laplacian's diagonal counts distinct lower- and upper-adjacent p-simplices. Those are different: a face need not be contained in another p-simplex, and a coface contributes one graph neighbor, not deg^up. The proof around Equation 22 identifies the two without justification, and the example shows they genuinely differ.\n\nWhat is good: the paper is clearly written, the sparse-access formalism is careful, and the containment-in-QMA arguments (Propositions 2 and 3) look plausible and self-contained. The Zaslavsky negative-subdivision reduction from balance to bipartiteness is a nice, correct observation, and the authors take care to preserve sparse access through it. The related-work discussion is honest and the open questions are sensible. If Proposition 1 could be repaired or replaced, the overall strategy might still work, but as it stands the hardness results are unsupported.\n\nWho this is for: someone working on quantum Hamiltonian complexity might read the containment arguments or the Zaslavsky reduction, but the headline claims are not substantiated. It deserves a referee because the error is subtle and the intended result is significant, but a referee should be asked to focus on Proposition 1. My recommendation: do not accept as is; require repair of the reduction or an explicit statement of a restricted family where the equivalence holds.","headline":"The paper's QMA1-hardness claims rest on a false unitary equivalence; the Hodge Laplacian diagonal does not match the signed graph degree, and the two-edge path is a counterexample.","tokens_in":27059,"tokens_out":3198,"would_cite":false,"duration_ms":26239,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q17","05C50","55U10"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"Testing balanced and bipartite components in sparse graphs is QMA1-hard.","keywords":["QMA1-hardness","sparse balancedness","sparse bipartitedness","Combinatorial Hodge Laplacian","signed graph Laplacian","clique homology","signless Laplacian","stoquastic Hamiltonian"],"falsifier":"Compute the Combinatorial Hodge Laplacian at $p=1$ for the simplicial complex consisting of two edges sharing a vertex, and compare it with the signed Laplacian of the graph whose two vertices are those edges joined by the single edge between them: the former has diagonal entries $2$, the latter has diagonal entries $1$, so the claimed unitary equivalence fails on this instance unless signs or diagonal contributions are modified.","tokens_in":25973,"feed_emoji":"⚖️","tokens_out":9881,"duration_ms":82057,"temperature":0.7,"pith_summary":"The paper sets out to prove that two basic structural tests on succinctly presented sparse graphs are quantumly hard: deciding whether a signed graph contains a balanced connected component, and deciding whether an unsigned graph contains a bipartite connected component. A balanced component is one whose vertices can be split into two groups so that edges inside a group are positive and edges between groups are negative; a bipartite component is one whose vertices split so that every edge crosses the split. The route is a chain of spectral equivalences: the $p$-th Combinatorial Hodge Laplacian of a simplicial complex is claimed to be unitarily equivalent to the signed Laplacian of a graph built from the $p$-simplices, so holes in a clique complex become balanced components of a signed graph, and a known negative-subdivision construction carries balanced components to bipartite components. Because clique homology is already known to be QMA1-hard, the paper concludes that sparse balancedness and sparse bipartitedness are QMA1-hard, with promise versions of both contained in QMA. A sympathetic reader cares because these are natural network-science properties, and the bipartite test adds an example where a spectral property of a stoquastic Hamiltonian is quantumly hard.","feed_headline":"Balanced and bipartite component tests are QMA1-hard","feed_subtitle":"A homology-to-graph reduction puts two network-science detection tasks into the hardest quantum class.","key_machinery":"The machine that carries the argument is the unitary equivalence $L_p^{\\Gamma} \\simeq L_{G_s}$ between the $p$-th Combinatorial Hodge Laplacian of a simplicial complex and the signed Laplacian of a graph $G_s$ on $p$-simplices. In matrix terms, the equivalence asserts that off-diagonal entries match products of face-orientation signs, with signs $s(\\sigma,\\tau)=-\\bigl(\\mathrm{sng}(\\sigma\\cap\\tau,\\sigma)\\,\\mathrm{sng}(\\sigma\\cap\\tau,\\tau)+\\mathrm{sng}(\\sigma,\\sigma\\cup\\tau)\\,\\mathrm{sng}(\\tau,\\sigma\\cup\\tau)\\bigr)$, and that diagonal entries equal degrees in the constructed graph. Around that identity sit two standard facts it mobilizes: $\\ker L_p^{\\Gamma}\\cong H_p(\\Gamma)$, so kernel non-triviality detects holes, and a signed graph has a balanced component exactly when its signed Laplacian has a zero eigenvalue. The second half of the proof machinery is the negative-subdivision construction, which replaces each positive edge by a two-edge path through a new vertex and turns balance into bipartiteness while keeping the graph sparse.","core_discovery":"The central discovery is a dictionary between simplicial complexes and signed graphs. The paper's Proposition 1 states that for any abstract simplicial complex $\\Gamma$ and dimension $p$, the Combinatorial Hodge Laplacian $L_p^{\\Gamma}$ is unitarily equivalent to the signed graph Laplacian $L_{G_s}$ of a graph whose vertices are the $p$-simplices of $\\Gamma$; edges connect $p$-simplices that are either lower-adjacent (share a $(p-1)$-face) or upper-adjacent (lie in a common $(p+1)$-simplex), and the edge signs are products of oriented incidence signs. Since the kernel of $L_p^{\\Gamma}$ is isomorphic to the $p$-homology of $\\Gamma$, a non-trivial kernel in the clique complex is recast as a zero eigenvalue of a signed graph Laplacian, which is exactly the condition for a balanced connected component. The paper then applies the negative-subdivision operation, replacing positive edges by paths through new vertices, to convert balance into bipartiteness in an unsigned graph with comparable size and sparse access. The paper argues both steps can be implemented by polynomial-size classical circuits that provide sparse access in the marked (and, by an auxiliary construction, traditional) model, yielding the two QMA1-hardness theorems.","pith_inferences":["The unitary equivalence, if it holds, would let spectral quantities of signed graphs (such as algebraic conflict measures) be transported to Combinatorial Hodge Laplacians and back, potentially giving new bounds on simplicial holes from signed-graph Cheeger inequalities; this direction is not explored in the paper.","The balance-to-bipartite half of the chain is independent of the Hodge-to-signed-graph step, so if the latter's diagonal-counting premise failed, a corrected diagonal (for example a weighted or looped graph variant) could still salvage the hardness conclusions through a different spectral characterisation.","A direct test of the equivalence on small complexes with known kernels, such as the boundary of a triangle at $p=1$ or a path of two edges, would separate a genuine spectral dictionary from a purely formal matrix similarity and is cheap to run.","These hardness results suggest that classical heuristics for balanced or bipartite component detection, which are polynomial-time on explicit graphs, must fail on succinctly specified sparse families unless the input is expanded to explicit form, an observation the paper leaves mostly implicit."],"forward_implications":["Sparse balancedness and sparse bipartitedness are each QMA1-hard, so under the stated sparse-oracle input model both tasks are as hard as any problem admitting a perfect-completeness quantum witness.","The promise variants in which the smallest eigenvalue of the relevant Laplacian is either zero or at least inverse-polynomial are contained in QMA, placing them inside the quantum class rather than outside it.","Because the marked sparse-access model can be converted to the traditional sparse-access model for these problems, the hardness is not an artifact of the marked encoding.","Bipartite-component testing becomes another spectral property of a stoquastic Hamiltonian that is quantumly hard, complementing the known hardness of excited-state energies of stoquastic Hamiltonians.","The reduction transfers hardness from topological data analysis (clique homology) to network-science concepts (balance and bipartiteness), giving a complexity-theoretic bridge between the two areas."],"supporting_citations":[{"why":"Supplies the starting hardness result that clique homology is QMA1-hard, the problem the reductions begin from.","marker":"[5]"},{"why":"Provides the construction the paper extends to express the upper Combinatorial Hodge Laplacian as a signed graph Laplacian.","marker":"[20]"},{"why":"Gives the negative-subdivision operation that turns balanced signed components into bipartite unsigned components.","marker":"[7]"},{"why":"Establishes that the kernel of the Combinatorial Hodge Laplacian is isomorphic to homology, the bridge from holes to kernels.","marker":"[39]"},{"why":"Proves a connected signed graph is balanced exactly when its signed Laplacian has a zero eigenvalue, the spectral test used in the reductions.","marker":"[37]"},{"why":"Shows the kernel of the signless Laplacian counts bipartite connected components, needed for the QMA containment of sparse bipartitedness.","marker":"[23]"},{"why":"Characterizes the smallest eigenvalue of a graph, supporting the signless-Laplacian bipartite-component characterization.","marker":"[42]"},{"why":"Provides the block-encoding construction for sparse matrices used to place the promise variants in QMA.","marker":"[14]"}],"fun_headline_variants":["Sparse graph balance and bipartite tests are QMA1-hard","Balanced and bipartite component tests proven QMA1-hard","QMA1-hard: sparse graph balance and bipartite tests","From homology to hardness: graph component tests are QMA1-hard","Simplicial homology yields QMA1-hard graph tests"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the diagonal entries of the Hodge Laplacian matching the degrees of the vertices in the constructed signed graph; if a simplex's faces and cofaces do not produce exactly those neighbor counts, the equivalence breaks.","fun_headline_variants_meta":{"raw":{"variants":["Sparse graph balance and bipartite tests are QMA1-hard","Balanced and bipartite component tests proven QMA1-hard","QMA1-hard: sparse graph balance and bipartite tests","From homology to hardness: graph component tests are QMA1-hard","Simplicial homology yields QMA1-hard graph tests"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002008,"raw_usage":{"total_tokens":7871,"prompt_tokens":1025,"completion_tokens":6846,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":641,"completion_tokens_details":{"reasoning_tokens":6759}},"tokens_in":641,"tokens_out":6846,"duration_ms":34804,"temperature":1.0,"reasoning_tokens":6759,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:47:53.337929+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the Combinatorial Hodge Laplacian at $p=1$ for the simplicial complex consisting of two edges sharing a vertex, and compare it with the signed Laplacian of the graph whose two vertices are those edges joined by the single edge between them: the former has diagonal entries $2$, the latter has diagonal entries $1$, so the claimed unitary equivalence fails on this instance unless signs or diagonal contributions are modified.","supporting_citations":[{"cited_title":"Zaslavsky, Negative (and positive) circles in signed gra phs: A problem collection, AKCE International Journal of Gr aphs and Combinatorics 15, 31 (2018)","cited_arxiv_id":null,"evidence_quote":"Gives the negative-subdivision operation that turns balanced signed components into bipartite unsigned components."},{"cited_title":"Friedman, Computing betti numbers via combinatorial lap lacians, in Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (1996) pp","cited_arxiv_id":null,"evidence_quote":"Establishes that the kernel of the Combinatorial Hodge Laplacian is isomorphic to homology, the bridge from holes to kernels."},{"cited_title":"Kunegis, S","cited_arxiv_id":null,"evidence_quote":"Proves a connected signed graph is balanced exactly when its signed Laplacian has a zero eigenvalue, the spectral test used in the reductions."},{"cited_title":"Cvetković, P","cited_arxiv_id":null,"evidence_quote":"Shows the kernel of the signless Laplacian counts bipartite connected components, needed for the QMA containment of sparse bipartitedness."},{"cited_title":"Desai and V","cited_arxiv_id":null,"evidence_quote":"Characterizes the smallest eigenvalue of a graph, supporting the signless-Laplacian bipartite-component characterization."},{"cited_title":"Camps, L","cited_arxiv_id":null,"evidence_quote":"Provides the block-encoding construction for sparse matrices used to place the promise variants in QMA."}],"review_version":1}