REVIEW 3 major objections 6 minor 1 cited by
Lov\'asz theta and Shearer lower bounds on Quantum Max Cut
T0 review · 3 major / 6 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read Quantum Max Cut energy is pinned from below by the Lovász theta function of the complement graph.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Abstract; §3 (Theorem 4)] 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.
- [Theorem 4 Eq. (9); Definition 1; Eq. (10)] 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.
- [Abstract (relaxed bound)] 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.
minor comments (6)
- [After Eq. (7)] 'Grothendiek's identity' should be 'Grothendieck's identity'.
- [After Definition 1] The sentence 'The definition of for ϑ( G) has uv∉E(G) replaced by uv∈E(G)' is ungrammatical and unclear; please rewrite.
- [Abstract] 'strenghtened' should be 'strengthened'.
- [Eq. (9) and Eq. (14)] There is an extra closing parenthesis in '1/(ϑ(G)-1))'; also the formula should use ϑ(\bar G) consistently.
- [Abstract; §3] 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.
- [Appendix A, Eq. (20)] The displayed formula appears to be missing a '/' between 'tr(H_qmc ϱ_GP)' and 'qmc(G)'. Please clarify the expression.
Circularity Check
No circularity: Theorem 4 is derived from external lemmas and standard definitions, with no fitted inputs or self-citation chains.
full rationale
The paper's central result, Theorem 4 (Eq. 9), is obtained by combining Definition 1 (the Lovász theta function, quoted from KMS98), Lemma 2 (the Briet–de Oliveira Filho–Vallentin rounding identity, quoted from BOV14 as a published external lemma), Lemma 3 (a simple coefficient-wise bound on the hypergeometric series), and the elementary numerical constant in Eq. (15). The Lovász theta vectors are fed as input to a randomized rounding procedure, and the bound follows by exact expectation computation; no parameter is fitted to the target quantity and no prediction is renamed from an input. The proof is self-contained modulo the cited external lemmas, which are themselves standard published results and are not authored by the present paper's author. The manuscript does have a verifiability gap unrelated to circularity: the abstract advertises a Shearer/triangle-free bound and a relaxed Δ-bound that are not proved or even stated in the body. However, that is missing support, not circular reasoning, and it does not undermine the derivation of Eq. (9). There is also no self-citation of the author used as load-bearing evidence. Therefore the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- domain assumption Lemma 2 of [BOV14] (expectation of normalized Gaussian inner products)
- standard math Definition 1: existence of Lovász theta vectors with ⟨x_u, x_v⟩ = −1/(ϑ(\bar{G})−1) for all edges uv∈E(G)
- standard math Hypergeometric function coefficients are positive
- ad hoc to paper Abstract's relaxed bound ϑ(\bar{G})−1 ≤ Δ for maximum-degree-Δ graphs
- ad hoc to paper Abstract's Shearer bound qmc(G) ≥ m/4 + 2m^{3/4}/(3π) for triangle-free graphs
Cite this review
Pith. "Pith review of Lov\'asz theta and Shearer lower bounds on Quantum Max Cut." pith.science (2026). https://pith.science/paper/QNOR3KYY
@misc{pith2026251220326,
author = {Pith},
title = {Pith review of: Lov\'asz theta and Shearer lower bounds on Quantum Max Cut},
year = {2026},
howpublished = {\url{https://pith.science/paper/QNOR3KYY}},
note = {Machine review of arXiv:2512.20326}
}
abstract
Quantum Max Cut is a problem relevant to computer science and many-body quantum physics due to its links to classical Max Cut and the anti-ferromagnetic Heisenberg Hamiltonian. We prove a lower bound to quantum Max Cut of a graph in terms of the Lov\'asz theta function of its complement. For a graph with $m$ edges, $\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3\pi}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state. The proof can be strenghtened by the vector chromatic number and extends a result by Balla, Janzer, and Sudakov on classical Max Cut. A relaxed bound follows from $\vartheta(\bar{G}) - 1 \leq \Delta$ for graphs with maximum degree $\Delta$, making it interesting for practically relevant quantum many-body systems. We also extend results by Carlson et al. and Shearer and show that $\text{qmc}(G) \geq \frac{m}{4} + \frac{2m^{3/4}}{3 \pi}$ for all triangle-free graphs with $m$ edges.
Forward citations
Cited by 1 Pith paper
-
Convergence rates of Sum-of-Hermitian-Squares Hierarchies for the Pauli algebra
Explicit convergence rates for noncommutative SOS hierarchies on the Pauli algebra are bounded using smallest roots of Krawtchouk polynomials.
Reference graph
Works this paper leans on
-
[1]
On MaxCut and the Lovász theta function
Igor Balla, Oliver Janzer, and Benny Sudakov. On MaxCut and the Lovász theta function. Proceedings of the American Mathematical Society , 152:1871–1879, 2024
2024
-
[2]
Grothendieck inequalities for semidefinite programs with rank constraint
Jop Briët, Fernando Mário de Oliveira Filho , and Frank Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. Theory of Computing , 10(4):77–105, 2014
2014
-
[3]
Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut
Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut . In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) , volume 145 of Leibniz International Proceedings in Informatics (LIPIc...
2019
-
[4]
Résumé des résultats essentiels dans la théorie des produits tensoriels topologiques et des espaces nucléaires
Alexander Grothendieck. Résumé des résultats essentiels dans la théorie des produits tensoriels topologiques et des espaces nucléaires. Annales de l'Institut Fourier , 4:73–112, 1952
1952
-
[5]
Goemans and David P
Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM , 42(6):1115–1145, 1995
1995
-
[6]
Approximate graph coloring by semidefinite programming
David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM , 45(2):246–265, 1998
1998
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.