{"id":"f5234feb-5f92-4a4c-aea1-638c526d24bd","arxiv_id":"2512.20326","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For any graph with m edges, the Quantum Max Cut energy is at least m/4·(1 + 8/(3π)·1/(ϑ(complement)−1)).","lead":"This paper proves a new lower bound on Quantum Max Cut, a quantum version of the classic Max Cut problem, using the Lovász theta function from graph theory. The proof uses randomized rounding to construct product states that achieve the bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 appears sound; the load-bearing issue is that the abstract advertises a Shearer/triangle-free bound and a Δ-relaxed bound that are not proved or even mentioned in the body.","rationale":"The reader's weakest_assumption identifies Lemma 2 of BOV14 as the fragile point. I do not share that concern: Lemma 2 is a published, standard result, and the paper's use of it is a straightforward substitution; even if the proof were restated, it would not change the argument. The reader's rationale, however, also flags the unproved Shearer and relaxed bounds in the abstract, which I agree is the real load-bearing issue. The theorem itself is sound and the derivation of the expectation is correct, with only minor notation slips (e.g., Eq. 14 mixes r and 3, and Definition 5/ϑ inequality has a likely complement typo). Because the missing support affects claims that are part of the advertised abstract but not the core theorem, conditional acceptance remains appropriate: the author should either prove the additional claims or remove them from the abstract. Thus the verdict is unchanged, but the basis is the abstract/body mismatch rather than the cited lemma.","tokens_in":4676,"tokens_out":16672,"duration_ms":165192,"concrete_test":"Search the full body (excluding the abstract and references) for 'Shearer', 'Carlson', 'triangle-free', and 'Δ ≤' or 'maximum degree'. If no theorem or proof establishes qmc(G) ≥ m/4 + 2m^{3/4}/(3π) for triangle-free graphs and no derivation of ϑ(\\bar{G}) - 1 ≤ Δ appears, then the abstract is unsupported. The minimal corrective action is to remove the unproved claims from the abstract or add the missing arguments and citations.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem (Theorem 4, Eq. 9) is not seriously at risk: the proof follows from Lemma 2 of BOV14, Lemma 3, and the substitution of the Lovász theta vectors, and the constant 8/(3π) is computed correctly for r=3. The external lemma is a standard published result, so citing it is not a real vulnerability. The genuine problem is a mismatch between the paper's advertised contributions and its supported content. The abstract states two additional results: (i) 'A relaxed bound follows from ϑ(\\bar{G}) - 1 ≤ Δ for graphs with maximum degree Δ,' and (ii) 'We also extend results by Carlson et al. and Shearer and show that qmc(G) ≥ m/4 + 2m^{3/4}/(3π) for all triangle-free graphs with m edges.' Neither statement appears in the body. There is no theorem, proof, or even a reference to Carlson et al. or Shearer anywhere after the abstract. The triangle-free bound is not a corollary of Theorem 4, because Theorem 4 gives a denominator of ϑ(\\bar{G}) - 1, which can grow with n, and converting that into a universal m^{3/4} surplus would require an additional Shearer-type argument that the manuscript does not provide. This is a verifiability gap in the paper as submitted: a reader cannot check the advertised claims, and one of them may require substantial extra work. It does not invalidate Eq. (9), but it means the paper overclaims relative to its proofs.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a lower bound on the Quantum Max Cut value qmc(G) in terms of the Lovász theta function of the complement. Using the Karger–Motwani–Sudan vector formulation of ϑ(\\bar G), the author applies a random Gaussian rounding map from R^n to the Bloch sphere (the r=3 case of a lemma by Briët–de Oliveira Filho–Vallentin) and obtains qmc(G) ≥ (m/4)(1 + 8/(3π) · 1/(ϑ(\\bar G)-1)). The bound is attained in expectation by a product state. The paper also sketches an extension to the vector chromatic number and to an XX-type Hamiltonian, and the abstract advertises a relaxation via ϑ(\\bar G)-1 ≤ Δ and a Shearer-type m^{3/4} bound for triangle-free graphs.","tokens_in":5066,"tokens_out":15679,"duration_ms":134961,"significance":"If the main theorem is correct, it is a clean quantum analogue of the Balla–Janzer–Sudakov bound for classical Max Cut, with an explicit constant 8/(3π) ≈ 0.8488 and the notable feature that the witness is a product state. The proof is self-contained modulo the standard BOV14 formula and is not fitted to data; Lemma 3 and the constant computation are correct. The advertised extra results, however, are not established in the body, and one advertised inequality is false as stated. The paper should be acceptable after the overclaims are removed or proved and the notation is fixed.","major_comments":[{"comment":"The abstract promises two results that do not appear in the body: (i) a relaxed bound from ϑ(\\bar G)-1 ≤ Δ, and (ii) qmc(G) ≥ m/4 + 2m^{3/4}/(3π) for triangle-free graphs, 'extend[ing] results by Carlson et al. and Shearer'. There is no theorem, proof, or reference to these works after the abstract. Eq. (9) alone cannot yield the triangle-free bound without additional control of ϑ(\\bar G) as a function of m. This gap affects the title as well as the abstract. Please either supply the missing proofs or delete the unsupported claims.","section":"Abstract; §3 (Theorem 4)"},{"comment":"The notation ϑ(G) vs ϑ(\\bar G) is inconsistent. The abstract uses ϑ(\\bar G), the theorem statement and Eq. (14) use ϑ(G), and the proof says 'vectors that realize the Lovász theta function ϑ(G) of its complement G', presumably \\bar G. Under Definition 1, the equality ⟨x_u,x_v⟩ = -1/(κ-1) holds for non-edges of the graph whose theta is computed; Eq. (10) applies it to edges of G, which is only correct if the function is evaluated on \\bar G. Please standardize the notation and rewrite the garbled sentence after Definition 1.","section":"Theorem 4 Eq. (9); Definition 1; Eq. (10)"},{"comment":"The advertised inequality ϑ(\\bar G)-1 ≤ Δ for graphs of maximum degree Δ is not proved and, on the paper's Definition 1, is false for the edgeless graph on n vertices: Δ=0, \\bar G=K_n, and the condition in Definition 1 is vacuous for K_n, giving ϑ(K_n)=2, hence ϑ(\\bar G)-1=1>0. If the intended statement excludes edgeless graphs or uses a different theta normalization, the qualification must be stated; otherwise the claim should be removed.","section":"Abstract (relaxed bound)"}],"minor_comments":[{"comment":"'Grothendiek's identity' should be 'Grothendieck's identity'.","section":"After Eq. (7)"},{"comment":"The sentence 'The definition of for ϑ( G) has uv∉E(G) replaced by uv∈E(G)' is ungrammatical and unclear; please rewrite.","section":"After Definition 1"},{"comment":"'strenghtened' should be 'strengthened'.","section":"Abstract"},{"comment":"There is an extra closing parenthesis in '1/(ϑ(G)-1))'; also the formula should use ϑ(\\bar G) consistently.","section":"Eq. (9) and Eq. (14)"},{"comment":"The abstract states that the proof 'can be strengthened by the vector chromatic number', but the body only gives a remark without a formal statement or proof. If kept, state it as a proposition or corollary with a one-line proof.","section":"Abstract; §3"},{"comment":"The displayed formula appears to be missing a '/' between 'tr(H_qmc ϱ_GP)' and 'qmc(G)'. Please clarify the expression.","section":"Appendix A, Eq. (20)"}],"recommendation":"major_revision","confidential_remarks":"The mismatch between the abstract/title and the body is the main obstacle. The core theorem is solid, so I do not recommend rejection, but the author must either provide proofs for the Shearer and Δ-relaxation claims or remove them. The false Δ claim for edgeless graphs is a concrete error that should be caught in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core theorem is real. qmc(G) ≥ m/4·(1 + 8/(3π)·1/(ϑ(Ḡ)−1)) is proved cleanly using BOV rounding with r=3 and the lemma that F̂(r, x·y) ≤ x·y for nonpositive inner products. The constant 8/(3π) is computed correctly, and the probabilistic method step is valid. The result is a genuine extension of BJS24 from classical Max Cut to Quantum Max Cut, achieved by product states, and the dependence on ϑ(Ḡ) is new. That part deserves to be published.\n\nThe problem is the abstract sells more than the paper delivers. It advertises a relaxed bound from ϑ(Ḡ)−1 ≤ Δ and a Shearer/Carlson-style triangle-free bound qmc(G) ≥ m/4 + 2m^{3/4}/(3π). Neither is stated as a theorem, no proof is sketched, and Carlson and Shearer are not even referenced. A reader cannot check those claims from the manuscript. The triangle-free bound does not follow from Theorem 4 alone, since ϑ(Ḡ)−1 can grow with n; converting it into an m^{3/4} surplus would require a separate argument. This is an overclaim in the abstract, and the author should either prove those statements or remove them.\n\nThere are minor notation slips: Eq. (14) has a stray closing parenthesis, and Appendix A writes σ^z for the Y component in the product state (y_i^y σ^z instead of σ^y). These are cosmetic.\n\nThe core proof is short, elegant, and self-contained modulo a standard published lemma from BOV14; citing it is not a vulnerability. The paper is worth a serious referee, but the referee should insist that the abstract match the proven content. With the extra claims removed or proved, this becomes a solid, publishable note.","headline":"Core Lovász-theta bound for Quantum Max Cut is sound and new, but the abstract promises Shearer/Carlson-type and degree-relaxed results that appear nowhere in the body.","tokens_in":5465,"tokens_out":1862,"would_cite":true,"duration_ms":18324,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","05C50","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Quantum Max Cut energy is pinned from below by the Lovász theta function of the complement graph.","keywords":["Quantum Max Cut","Lovász theta function","anti-ferromagnetic Heisenberg model","randomized rounding","product states","lower bound","vector chromatic number","triangle-free graphs"],"falsifier":"Diagonalize the quantum Max Cut Hamiltonian for a small graph whose theta function is known (e.g., a cycle or complete bipartite graph) and check the inequality numerically; any violation would disprove Theorem 4. Alternatively, directly test the cited rounding lemma by sampling random Gaussian matrices for two fixed unit vectors with inner product −1/2 and comparing the empirical mean of y_u·y_v to the hypergeometric prediction.","tokens_in":4563,"feed_emoji":"⚛️","tokens_out":5799,"duration_ms":55053,"temperature":0.7,"pith_summary":"This paper proves a lower bound on Quantum Max Cut, the problem of finding the largest eigenvalue of an anti-ferromagnetic Heisenberg Hamiltonian on a graph. For any graph with m edges, the quantum Max Cut energy is at least (m/4)(1 + 8/(3π) · 1/(ϑ(Ḡ)−1)), where ϑ(Ḡ) is the Lovász theta function of the complement. The bound is achieved by product states, so no entanglement is required to reach it. This extends a classical Max Cut bound to the quantum setting with a larger constant, and it also yields a graph-dependent certificate of high energy in quantum magnetic systems.","feed_headline":"Lovász theta sets a floor for quantum Max Cut","feed_subtitle":"A product-state rounding yields an 8/(3π) surplus that beats the classical Max Cut constant.","key_machinery":"The central object is the Lovász theta function of the complement graph, defined by unit vectors whose inner products on complementary edges equal −1/(ϑ(Ḡ)−1). The argument's engine is a randomized rounding: sample a 3×n matrix of independent standard normals, normalize the projections of the theta vectors, and interpret the resulting unit 3-vectors as Bloch vectors of single-qubit product states. A cited lemma gives the expected inner product of two such normalized Gaussian projections as a hypergeometric series; a term-by-term inequality converts this into a lower bound on the Hamiltonian expectation.","core_discovery":"The central claim is that the Lovász theta function of the complement graph controls the energy of Quantum Max Cut. Explicitly, for every graph G with m edges, qmc(G) ≥ (m/4)(1 + 8/(3π) · 1/(ϑ(Ḡ)−1)). The proof constructs a product state by taking vectors that realize the theta function, rounding them to the Bloch sphere via a random Gaussian matrix, and showing via a known randomized-rounding lemma that the expected energy of the resulting state meets the bound. The constant 8/(3π) ≈ 0.8488 improves on the classical 2/π ≈ 0.6366 that appears in the analogous Max Cut bound.","pith_inferences":["If the product-state bound is nearly tight for certain graph families, then entanglement offers little advantage on those instances; testing random graphs or theta-extremal graphs could reveal where the constant 8/(3π) can be improved.","The degree-based corollary may offer a practical, easy-to-compute certificate of nonzero ground-state energy for anti-ferromagnetic Heisenberg models on large lattices, without solving the full quantum problem.","The hypergeometric expansion suggests a general recipe: for r-dimensional local Hilbert spaces, the same rounding gives a family of theta-based lower bounds with constants depending on r, which could be explored for qudits.","Since the bound also holds with the vector chromatic number in place of the theta function, any graph where the two differ yields a stronger bound, potentially linking quantum Max Cut to approximate graph coloring guarantees."],"forward_implications":["For any graph, the quantum Max Cut energy exceeds m/4 by a surplus inversely proportional to ϑ(Ḡ)−1, so graphs whose complements have small theta function are guaranteed large quantum cut energy.","The bound is achieved by product states, implying that entanglement is unnecessary for this guarantee—a quantum analog of classical randomized rounding.","The relaxed bound ϑ(Ḡ)−1 ≤ Δ for maximum degree Δ yields qmc(G) ≥ (m/4)(1 + 8/(3πΔ)), applicable to bounded-degree quantum spin systems.","The same rounding method extends to other Hamiltonians, e.g., the XX model, giving qmc_XX(G) ≥ (m/4)(1 + π/(4(ϑ(Ḡ)−1))).","The abstract also claims that for triangle-free graphs with m edges, qmc(G) ≥ m/4 + 2m^(3/4)/(3π), extending Shearer-type extremal bounds to the quantum setting."],"fun_headline_variants":["Quantum Max Cut bound beats classical via theta","Lovász theta lifts quantum Max Cut floor","Theta function powers quantum Max Cut bound","Quantum Max Cut gets theta boost over classical","Lovász theta improves quantum Max Cut lower bound"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire lower bound rests on a cited formula for the expected inner product of two independently Gaussian-normalized unit vectors; if that formula were incorrect, the energy computation that yields the bound would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Quantum Max Cut bound beats classical via theta","Lovász theta lifts quantum Max Cut floor","Theta function powers quantum Max Cut bound","Quantum Max Cut gets theta boost over classical","Lovász theta improves quantum Max Cut lower bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000573,"raw_usage":{"total_tokens":2546,"prompt_tokens":749,"completion_tokens":1797,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":1729}},"tokens_in":493,"tokens_out":1797,"duration_ms":13320,"temperature":1.0,"reasoning_tokens":1729,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T14:23:28.912110+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Diagonalize the quantum Max Cut Hamiltonian for a small graph whose theta function is known (e.g., a cycle or complete bipartite graph) and check the inequality numerically; any violation would disprove Theorem 4. Alternatively, directly test the cited rounding lemma by sampling random Gaussian matrices for two fixed unit vectors with inner product −1/2 and comparing the empirical mean of y_u·y_v to the hypergeometric prediction.","supporting_citations":[],"review_version":1}