REVIEW 2 major objections 4 minor 18 references
Quantum chromatic numbers of some graphs in Hamming schemes
T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read For n=4t−1 and distance 2t, the Hamming graph has quantum chromatic number exactly n+1.
desk verdict A genuinely new exact quantum chromatic number family with a repairable gap in the spectral lower-bound proof; worth refereeing. 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 machinery has four pieces: the Hamming graph H_{n,ℓ}, whose vertices are strings in F_2^n and whose edges join strings at Hamming distance ℓ; Krawtchouk polynomials, which turn the eigenvalue problem into coefficient extraction from (1−x)^ℓ(1+x)^{n−ℓ}; the spectral lower bound χ_q ≥ 1 + λ_max/|λ_min|; and an explicit projection-valued coloring constructed from the same phases used for Hadamard graphs, taken in dimension 2ℓ. The product theorem uses the observation that when both factors saturate the spectral bound, the product's quantum chromatic number is the minimum of the two factors' values.
What would settle it
One could compute the numbers ρ(r) from equations (26)–(27) for a fixed t, say t=3 (n=11, ℓ=6), and compare all negative values with −\binom{11}{6}/11; if any is smaller, the claimed quantum chromatic number is wrong. A direct check of the ordering step for all j up to ⌊t/2⌋ would settle whether the proof's inequality is strict where it needs to be.
Extended reading notes
Core claim
The central discovery is Theorem 3.2: for the Cayley graph H_{4t−1,2t} on $F_2^{{4t−1}}$ with edges between vectors at Hamming distance 2t, the quantum chromatic number is χ_q = 4t = n+1. The proof computes the full spectrum using Krawtchouk polynomials: the eigenvalue attached to a vector of weight r is given by two closed binomial formulas, and the minimum eigenvalue is −\binom{4t−1}{2t}/(4t−1). The spectral lower bound χ_q ≥ 1 + λ_max/|λ_min| then gives 4t, and an explicit set of 4t projections on $C^{{4t}}$, built by embedding each vertex into V_{4t} with a zero last coordinate, provides a valid quantum coloring, so the bound is tight.
Load-bearing premise
The lower bound 4t rests on identifying the most negative eigenvalue of H_{4t−1,2t} as the one attached to vectors of weight 1 and 2; if some other eigenvalue were more negative, the claimed quantum chromatic number would be too low.
Editorial extensions
If this is right
- Every t ≥ 1 gives a new graph on 4t−1 bits whose quantum chromatic number is exactly 4t, forming a second infinite family alongside Hadamard graphs.
- Because χ_q(H) ≤ χ(H), each of these graphs has classical chromatic number at least 4t = n+1.
- For n=4t+2 and ℓ=2t+2, the quantum chromatic number lies between ℓ and 2ℓ, with the upper bound coming from an explicit coloring into dimension 2ℓ.
- Products such as H_{4t,2t} × H_{4s,2s} have quantum chromatic number equal to the smaller of the two factors when both factors saturate the spectral bound.
- The spectrum of H_{n,ℓ} admits closed binomial formulas whenever n−2ℓ is small, which is what makes the exact values and bounds accessible.
Reading between the lines
- A natural next test is the range 2ℓ < n, which the paper leaves open: one could run the same spectral computation to get a lower bound and look for a coloring dimension smaller than 2ℓ.
- If the classical chromatic number of H_{4t−1,2t} can be shown to exceed 4t, these graphs would exhibit quantum advantage; the paper does not prove such a gap.
- The embedding trick of adding one zero coordinate suggests a broader construction: any Hamming graph with ℓ ≥ n/2 can be quantum-colored with 2ℓ colors, so the exact boundary case is a special case where the spectrum and the coloring match.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies quantum chromatic numbers of Hamming graphs H_{n,ℓ} = Cay(F_2^n, S), where S is the set of weight-ℓ vectors. It first reproves the known result χ_q(H_n) = n for Hadamard graphs H_n with n = 4t using Krawtchouk polynomials. The main new result, Theorem 3.2, claims that for n = 4t−1 and ℓ = 2t the spectrum of H_{n,ℓ} has the explicit form in (22) and that χ_q(H_{n,ℓ}) = n+1 = 4t, with the lower bound obtained from Lemma 2.4 and the upper bound from an explicit 4t-color quantum coloring. The paper also gives a general upper bound χ_q(H_{n,ℓ}) ≤ 2ℓ for ℓ ≥ n/2 (Theorem 3.4), bounds for H_{4t+2,2t+2} (Proposition 3.5), and exact values for products of such graphs (Theorem 3.10).
Significance. If the main theorem is fully established, it provides a new infinite family of graphs—other than complete graphs, cycles, bipartite graphs, and Hadamard graphs—whose quantum chromatic numbers are exactly determined. The upper bound is an explicit quantum coloring, and the spectral formulas are derived from standard Krawtchouk identities and group characters with no fitted parameters, which are strengths of the paper. The product results are natural corollaries of the main theorem and known spectral bounds. The significance of the paper depends on a correct and complete proof of the spectral claim in Theorem 3.2.
major comments (2)
- [Section 3.2.1, after Eq. (28)] The proof that λ_min = ρ(1) relies on the strict inequality |ρ(4j+2)|/|ρ(4j−2)| < 1 for 1 ≤ j ≤ ⌊t/2⌋, but this inequality is not always strict: for t = 4 and j = 2, and also for t = 2 and j = 1, the ratio equals 1. Since Eq. (29) derives the lower bound χ_q ≥ 4t from the asserted value of λ_min, this is a load-bearing gap in the argument as written. The theorem is likely true and the gap is repairable, e.g., by restricting to r ≤ (4t−1)/2, using the symmetry ρ(r) = ρ(n−r), and proving a non-strict comparison that still shows every negative eigenvalue has magnitude at most |ρ(1)|; the authors must supply this corrected argument.
- [Section 3.2.2, Proposition 3.5] The lower bound ℓ ≤ χ_q(H_{4t+2,2t+2}) depends on the assertion "It is a routine to check that λ_min = −C(n,ℓ)/(2t+1)", but no verification is provided. In light of the eigenvalue-ordering error in Theorem 3.2, this step cannot be left as a routine check; the authors should either prove the eigenvalue ordering for this case or give a precise reference where the spectrum and its minimum eigenvalue are established.
minor comments (4)
- [Throughout] There are several typographical errors: "Krawchouk" should be "Krawtchouk" (e.g., in the abstract and Eq. (6)), "shcems" appears in Section 1, "Menamara" and "Mcnamara" are used inconsistently for the same reference, and "unite vector" and "orthnormal" appear in Section 2.1.1.
- [Section 3.1] The transition from Eq. (17) to the claim that λ_min = −C(n,n/2)/(n−1) is described as "easy to see" without a monotonicity argument for the sequence in (17); a short justification would make the reproof of the Hadamard-graph result self-contained.
- [Section 2.5, Eq. (15)] The notation Kℓ(r) is introduced without specifying the parameters n and q, which can be confusing because Krawtchouk polynomials depend on n and q; the authors should write K_{n,q}^ℓ(r) or explicitly state the suppressed parameters.
- [References] References [12] and [16] are incomplete (no journal or publisher details, only arXiv identifiers); the authors should update them to the published versions if they exist.
Circularity Check
No significant circularity: the main result follows from external spectral bounds, standard Krawtchouk identities, and an explicit quantum coloring.
full rationale
The paper's central result, Theorem 3.2 (chi_q(H_{4t-1,2t}) = 4t), is derived from two independent ingredients: the spectral lower bound chi_q(G) >= 1 + lambda_max/|lambda_min|, quoted from Elphick and Wocjan [4] and Ganesan [7], and an explicit construction of a quantum coloring using projections P^alpha_x on C^{4t}. The spectrum itself is computed from standard Krawtchouk polynomial identities cited to Levenshtein [11]; no parameter is fitted and no target value is assumed. The upper bound is verified directly by checking completeness and orthogonality of the constructed operators. The only self-citation is Feng's survey [5] in the introduction, which is contextual and not load-bearing. The possible issue raised about strictness of the ratio |rho(4j+2)|/|rho(4j-2)| < 1 is a correctness or proof-gap concern, not circularity: even if the inequality fails at a boundary, that does not make the theorem its own input. No step in the derivation chain reduces by construction to its own conclusion.
Assumptions & free parameters
assumptions (4)
- standard math Eigenvalues of normal Cayley graphs are given by group characters (Lemma 2.5).
- standard math Krawtchouk polynomial properties, especially the reciprocal law (Theorem 2.6.3).
- domain assumption Spectral lower bound χ_q(Γ) ≥ 1 + λ_1/|λ_n| (Lemma 2.4, from Elphick and Wocjan).
- domain assumption The explicit quantum coloring construction for Hadamard graphs from Menamara (Section 3.1).
Cite this review
Pith. "Pith review of Quantum chromatic numbers of some graphs in Hamming schemes." pith.science (2026). https://pith.science/paper/KEIG2Q2F
@misc{pith2026241209904,
author = {Pith},
title = {Pith review of: Quantum chromatic numbers of some graphs in Hamming schemes},
year = {2026},
howpublished = {\url{https://pith.science/paper/KEIG2Q2F}},
note = {Machine review of arXiv:2412.09904}
}
abstract
The study of quantum chromatic numbers of graphs is a hot research topic in recent years. However, the infinite family of graphs with known quantum chromatic numbers are rare, as far as we know, the only known such graphs (except for complete graphs, cycles, bipartite graphs and some trivial cases) are the Hadamard graphs $H_n$ with $2^n$ vertices and $n$ a multiple of $4$. In this paper, we consider the graphs in Hamming schemes, we determined the quantum chromatic numbers of one class of such graphs. Notably, this is the second known family of graphs whose quantum chromatic numbers are explicitly determined except for some cases aforementioned. We also provide some bounds for the quantum chromatic numbers of some other graphs in Hamming schemes. Consequently, we can obtain the quantum chromatic numbers of products of some graphs.
Reference graph
Works this paper leans on
-
[1]
David Avis, Jun Hasegawa, Yosuke Kikuchi, and Yuuya Sasaki, A qu antum protocol to win the graph colouring game on all hadamard graphs, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E89-A, 5(2006), 1378-1381
work page 2006
-
[2]
Cameron, Ashley Montanaro, Michael W
Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simon e Severini, and An- dreas Winter, On the quantum chromatic number of a graph, Electr on. J. Combin. 14(2007), No. 1, Research Paper 81, 15 pages
work page 2007
-
[3]
Martin, Quantum isomorphism of graphs from association schemes, J
Ada Chan and William J. Martin, Quantum isomorphism of graphs from association schemes, J. Combin. Theory, Ser. B, 164(2024), 340-363
work page 2024
-
[4]
Clive Elphick and Pawel Wocjan, Spectral lower bounds for the qu antum chromatic num- ber of a graph, J. Combin. Theory, Ser. A, 168(2019), 338-347
work page 2019
-
[5]
Hebei Normal Uni- versity (Natural Science), 17(5)(2023), 433-446
Keqin Feng, Quantum chromatic numbers: A survey (in Chinese), J. Hebei Normal Uni- versity (Natural Science), 17(5)(2023), 433-446
work page 2023
-
[6]
Peter Frankl and Vojtech R¨ odl, Forbidden intersections, Tra ns. Amer. Math. Soc. 300(1)(1987), 259-286
work page 1987
-
[7]
Priyanga Ganesan, Spectral bounds for the quantum chromat ic number of quantum graphs, Linear Algebra Appl. 674(2023), 351-376
work page 2023
- [8]
Show all 18 references
-
[9]
Zhengfeng Ji, Binary constraint system games and locally commut ative reductions, ArXiv abs/1310.3794 (2013)
2013 arXiv
-
[10]
Klappenecker, M
A. Klappenecker, M. R¨ otteler, I. E. Spharlinski, A Winterhof, On approximately sym- metric informationally complete positive operator-valued measures and related systems of quantum states. J. Math Phys. A, 46(2005): 082104
2005
-
[11]
Levenshtein, Krawtchouk polynomials and universal b ounds for codes and designs in Hamming spaces, IEEE Trans
Vladimir I. Levenshtein, Krawtchouk polynomials and universal b ounds for codes and designs in Hamming spaces, IEEE Trans. Inform. Theory, 41(1995 ), 1303-1321
1995
-
[12]
Menamara, ArXiv: 2410
A.M. Menamara, ArXiv: 2410. 0042 v2 [math. OA], 14, Oct. 2024
2024
-
[13]
Murty, Ramanujan graphs, J
M.R. Murty, Ramanujan graphs, J. Ramanujan Math. Sco. 18, No. 1(2003), 1-20. 16
2003
-
[14]
Nilsen and I.L
M.A. Nilsen and I.L. Chuang, Quantum computation and quantum in formation, Cam- bridge University Press, 2000
2000
-
[15]
Peres, Quantum Theory: Concepts and Methods
A. Peres, Quantum Theory: Concepts and Methods. Kluwer Ac ademic Publishers, Boston, 1995
1995
-
[16]
Santiago, A.M
R. Santiago, A.M. Mcnamara, Quantum chromatic numbers of pr oducts of graphs, ArXiv:2408.11911v1 [math.OA], 21 Aug 2024
2024 arXiv
-
[17]
Steinberg, Representation Theory of Finite Groups: An Int roductory Approach
B. Steinberg, Representation Theory of Finite Groups: An Int roductory Approach. Uni- versitext. Springer New York, NY, 2011. DOI: 10.1007/978-1-46 14-0776-8-7
2011 doi
-
[18]
Note that if wt(a) = r, we denote by ρn ℓ (r)(= K n ℓ (r)) the eigenvalue of Hn,ℓ corresponding to a
Appendix For readers convenience, we provide some tables on the spectra o f some Hamming graphs. Note that if wt(a) = r, we denote by ρn ℓ (r)(= K n ℓ (r)) the eigenvalue of Hn,ℓ corresponding to a. Table 1. ρ3 ℓ (r) n = 3 ℓ = 0 1 2 3 r = 0 1 3 3 1 1 1 1 -1 -1 2 1 -1 -1 1 3 1 ...
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.