{"id":"4f000f85-2fd0-4250-909b-fe5a3db30ed9","arxiv_id":"2608.08694","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A quantum graph-coloring framework with log-color encoding and a QFT-based mixer is presented; its chromatic-number term is flawed because label-sum minimization does not imply color-count minimization.","lead":"The paper proposes a quantum encoding for graph coloring that needs only logarithmically many qubits per color set, plus a new mixer and a penalty term meant to extract the chromatic number. The central penalty-term construction is unsound in general, because the smallest color-label sum need not use the smallest number of colors.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"One-body penalty minimizes sum of color labels, not number of colors; the ground state can use more colors than the chromatic number, so the central claim of Sec. III is false.","rationale":"The reader's analysis is sound and identifies the same single flaw I would flag. The central claim of Sec. III is not merely unproven; it is false, because the added penalty is linear in color labels, and linear-label minimization is exactly the minimum sum coloring problem. The counterexample is a standard construction, not an exotic pathology: a clique with enough pendant vertices. The paper's numerical tests do not include such a graph; all tested instances happen to have their minimum-sum optimum equal to the chromatic number, and success probabilities are computed against Gurobi colorings but do not test the distinction. Because the flaw invalidates the advertised ability to compute the chromatic number by a single ground-state optimization, the paper's main contribution fails. I see no reason to change the reader's rejection; the encoding and mixer issues are secondary and do not alter the verdict. The proposed enumeration test would settle the matter unambiguously, since the Hamiltonian is diagonal and finite.","tokens_in":11507,"tokens_out":8257,"duration_ms":88068,"concrete_test":"Take the 8-vertex graph G: edge AB, three leaves a1,a2,a3 attached only to A, and three leaves b1,b2,b3 attached only to B. Set eta=3 and define H_tot^c as in Eq. (12) with unit edge penalties and vertex coefficient 1/24. Enumerate all 3^8 proper colorings (or evaluate the diagonal Hamiltonian exactly) and compare minimum energies. The assignment (A,B)=(1,2), all six leaves=0 is proper with energy 3/24; every proper assignment using only two distinct labels has energy at least 4/24 (labels {0,1} give 4/24, while labels {0,2} and {1,2} are larger). Thus the minimum-energy state is reached by a 3-color coloring even though Gamma(G)=2. If this enumeration confirms the 3-color ground state, the Sec. III claim is falsified. This check needs only finite enumeration, not quantum emulation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the assertion after Eq. (13) that the ground state of H_tot^c colors G with the fewest colors. What the added vertex term actually minimizes is the sum of the color labels assigned to vertices, because N_i = Diag[0,1,...,eta-1,...] assigns label k to color k, and the vertex term is (1/(eta N_G)) sum_i N_i. Among proper colorings, the minimizer of label sum is the minimum sum coloring, which is a different optimization problem from minimizing the number of colors. A concrete witness: take a clique of size r and attach r+1 pendant leaves to each clique vertex. The graph is r-colorable, so the chromatic number is r. But the proper labeling in which the clique uses labels 1..r and every leaf uses label 0 uses r+1 distinct labels and has label-sum r(r+1)/2, while any r-label proper coloring has strictly larger label sum; for r=2 with three leaves per clique vertex the sums are 3 vs 4. Hence the ground state of Eq. (12) uses r+1 colors, contradicting the paper's central claim. Equation (13) only proves that violating an edge costs more than the maximum possible vertex penalty; it does not prove that minimizing label sum selects the fewest colors. The numerical graphs in Sec. III-A and Table I are cases where the two optima coincide, so the simulations do not expose the flaw.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a quantum framework for graph coloring in which each vertex's color is encoded in log_2(η) qubits, so that the total qubit count grows linearly in the number of vertices and logarithmically in the number of colors. It introduces a block-diagonal mixer that acts only on the feasible color subspace, and it adds a one-vertex term to the cost Hamiltonian in Eq. (12). The authors claim that the ground state of this Hamiltonian uses the smallest possible number of colors, i.e., the chromatic number, and they support this with adiabatic simulations on small graphs. The paper also extends the formulation to truck-loading problems with capacity constraints by adding Lagrangian penalty terms.","tokens_in":11817,"tokens_out":7569,"duration_ms":77149,"significance":"The efficient encoding and the construction of a feasible-subspace mixer are potentially useful ideas for quantum optimization. However, the central claim of the paper — that the ground state of the Hamiltonian in Eq. (12) yields the chromatic number — is mathematically incorrect. The one-vertex term minimizes the sum of color labels, which is the minimum sum coloring problem, not the minimum number of colors. These two objectives are known to diverge, and the paper provides a concrete counterexample family. Because the chromatic-number result is the main advertised contribution, the paper's significance is substantially weakened; the mixer alone may still be of interest, but the claimed breakthrough is not established.","major_comments":[{"comment":"The assertion that the ground state of H_tot^c colors the graph with the smallest number of colors is false. The vertex term (1/(η N_G)) Σ_i N_i with N_i = Diag[0,1,...,η−1,...] penalizes the sum of the color labels, so among proper colorings it selects the minimum sum coloring, not the minimum number of colors. A concrete counterexample is a graph consisting of a clique of size r with r+1 pendant leaves attached to each clique vertex. For r=2 and η=3, the graph is bipartite (chromatic number 2), but assigning the two clique vertices labels 1 and 2 and all leaves label 0 is a proper 3-coloring with label sum 3, whereas every proper 2-coloring has label sum at least 4 (e.g., labels 0 and 1 on the clique force the three leaves of one clique vertex to have label 1 and the three leaves of the other to have label 0, giving sum 4). Thus the ground state of Eq. (12) uses three colors, contradicting the stated claim.","section":"Section III, Eq. (12) and text after Eq. (13)"},{"comment":"The inequality in Eq. (13) only proves that the ground state cannot contain an edge violation, because any edge violation costs 1, which exceeds the maximum possible contribution (η−1)/η < 1 of the one-vertex term. It does not prove that among proper colorings the minimizer of the label sum uses the fewest colors. The sentence immediately following Eq. (13) ('the Ground State ... colors the graph with the smallest number of colors') is therefore unsupported by the argument presented.","section":"Section III, Eq. (13)"},{"comment":"The numerical tests do not expose the flaw because all tested graphs have the property that the minimum sum coloring uses the same number of colors as the chromatic number. The pentagon graph is an odd cycle, so it is not 2-colorable and the minimum sum coloring must use three colors; the other graphs are small and appear to have the same coincidence. No test is performed on graphs such as the clique-with-leaves family, where the two objectives provably differ. The statement in Section III-A that the Hamiltonian 'correctly determines the chromatic number for different graphs' is therefore not substantiated.","section":"Section III-A and Table I"},{"comment":"The abstract states that the method 'compute[s] the chromatic number', and Section VI repeats that the ground state is 'the optimal solution with the correct chromatic number'. Since this claim is false in general, these statements overstate the contribution. The framework may still be applicable to deciding η-colorability for a fixed number of colors and to constrained variants, but the chromatic-number estimation claim must be removed or replaced by a correct formulation, which would require a different objective than the simple one-vertex label sum.","section":"Abstract and Conclusion"}],"minor_comments":[{"comment":"The text says 'the second is the (n−k)×(n−k) identity matrix' when describing the block-diagonal matrix QFT_{k,n}. The total Hilbert space dimension is 2^n, so the second block should be (2^n − k) × (2^n − k). The current statement is dimensionally inconsistent for general n.","section":"Section II, after Eq. (10)"},{"comment":"The sum over q uses the expression 2^{p−1}, which appears to be a typo for 2^{q−1}.","section":"Section IV, Eq. (17)"},{"comment":"The sentence beginning 'considering all possible permutations of colors' is a fragment that does not form a complete sentence; it should be integrated with the preceding or following text.","section":"Section V, paragraph after Eq. (21)"},{"comment":"The sentence 'We use 8 for all graphs, except one of the first graph where we use 4 colors' is unclear. Please specify which graph uses 4 colors and which use 8.","section":"Table I caption"},{"comment":"The statement that the real-time evolution of the cost Hamiltonian uses at most N_conn 2^{2n} CNOT gates relies on the decomposition of the two-vertex interaction H(i,j); the reader would benefit from a brief explanation of why the Gray-code construction achieves this count for the specific diagonal form of H(i,j).","section":"Section II, paragraph on gate counting"}],"recommendation":"reject","confidential_remarks":"The central claim of Section III is contradicted by a simple, well-known example from the minimum sum coloring literature. The authors appear to have overlooked the distinction between minimizing the sum of color labels and minimizing the number of colors. This is not a subtle gap but a load-bearing error that invalidates the paper's main advertised result. I would strongly recommend rejection, unless the authors can reframe the contribution as a study of the feasible-subspace mixer and a solver for fixed-η graph coloring, without claiming chromatic-number estimation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi [Colleague],\n\nYou need to know two things about this one. First, the central claim — that the one-vertex term makes the ground state use the fewest colors — is false. Second, the encoding and mixer parts are okay but less novel than advertised.\n\nThe problem is in Eq. (11)-(12). The one-body term adds the color label of each vertex. So the Hamiltonian minimizes the sum of labels among proper colorings, which is the minimum sum coloring problem, not the chromatic number. The stress-test note is right: take a clique of size r and attach r+1 pendant leaves to each clique vertex. The graph is r-colorable, but the labeling that gives the clique labels 1..r and all leaves label 0 uses r+1 distinct labels and has a much smaller sum than any r-label proper coloring. For r=2 the sums are 3 vs 12. So the ground state uses r+1 colors. Eq. (13) only shows that a violated edge costs more than the maximum possible vertex penalty; it says nothing about minimizing the number of colors. The numerical tests in Sec. III-A are too small to expose the mismatch; the pentagon and the six graphs in Fig. 3 all happen to be cases where the two objectives coincide.\n\nWhat is actually good: the log-color encoding is sound and follows refs [30]-[32]. The block-diagonal mixer is a reasonable idea and the simulations show it can outperform the naive X mixer when the number of colors is not a power of two. But calling it novel is an overstatement; this is a Grover-type mixer restricted to the feasible subspace, a standard construction in the constrained QAOA literature (e.g., Hadfield et al.) that is not cited. The truck loading extension is a straightforward application of the same ideas, with the usual issue of tuning Lagrangian multipliers by hand.\n\nThe paper would need a major revision to be salvageable: drop or fix the chromatic-number claim, cite the minimum sum coloring literature, and acknowledge that the one-body term solves a different problem. Even then, the novelty is modest. I would not cite this paper in its current form. But I would send it to a referee rather than desk reject, because the flaw is subtle and the mixer/encoding portion deserves expert scrutiny. The authors are clearly thinking about the right things; the mistake is a mathematical one, not a sloppy one.","headline":"The chromatic-number result is unsound: the one-body term minimizes sum of color labels, not the number of colors, so the central claim of Sec. III is false despite a reasonable encoding and mixer.","tokens_in":12312,"tokens_out":5605,"would_cite":false,"duration_ms":59000,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a Hamiltonian whose ground state minimizes the sum of color labels will reveal the chromatic number of any graph in one shot, using only logarithmically many qubits per vertex.","keywords":["graph coloring","chromatic number","quantum adiabatic algorithm","logarithmic qubit encoding","feasible-subspace mixer","truck loading problem","Hamiltonian ground state"],"falsifier":"Compute the ground state of the proposed Hamiltonian, for example by exact diagonalization, for a small graph where the minimum-sum coloring uses more colors than the chromatic number, such as a triangle with at least four leaves attached to each vertex; if the ground state uses four colors rather than three, the central claim is refuted.","tokens_in":11310,"feed_emoji":"🎨","tokens_out":12432,"duration_ms":100203,"temperature":0.7,"pith_summary":"The paper proposes a quantum Hamiltonian formulation of graph coloring that encodes all η colors in only $\\lceil\\log_2\\eta\\rceil$ qubits per vertex. The central claim is that adding a single-vertex term that penalizes large color labels makes the ground state of the full Hamiltonian a proper coloring that uses exactly the chromatic number of colors. The authors also introduce a mixer Hamiltonian that acts only on valid color assignments, which they argue improves adiabatic performance when the encoding contains unused states. They validate the construction with small numerical simulations and extend it to constrained truck-loading problems with capacity limits. If the claim holds, the chromatic number would be obtainable from a single ground-state search rather than from a sequence of feasibility checks.","feed_headline":"A log-qubit encoding claims to return the chromatic number","feed_subtitle":"The method would yield the chromatic number from one measurement.","key_machinery":"The argument is carried by a compact color encoding in which each vertex has an $n$-qubit register with $n = \\lceil\\log_2\\eta\\rceil$, and only $\\eta$ of the $2^n$ computational states represent valid colors; a block-diagonal mixer $H_m^{k,n} = QFT_{k,n}\\, D_k\\, QFT_{k,n}^\\dagger$ that couples only the valid color states, built from a truncated quantum Fourier transform; the two-vertex diagonal penalty $H_C(i,j)$ that assigns positive energy to equal-color and invalid-color pairs; and the color-number operator $N_i$ whose sum over vertices penalizes large labels. The load-bearing step is the identification of the label sum with the color count: the paper assumes that minimizing $\\sum_i N_i$ over proper colorings is equivalent to minimizing the number of distinct colors used.","core_discovery":"On the paper's own terms, the central discovery is that the Hamiltonian $H_{\\mathrm{tot}}^c = \\sum_{\\langle i,j\\rangle} H_C(i,j) + \\frac{1}{\\eta N_G}\\sum_i N_i$ has a ground state that colors the graph with the smallest number of colors consistent with the coloring constraints, namely the chromatic number $\\Gamma$. The two-vertex term $H_C(i,j)$ forbids adjacent vertices from sharing a color, while the one-vertex operator $N_i = \\mathrm{Diag}[0,1,\\dots,\\eta-1,\\dots]$ assigns an energy cost equal to the color label, so the total cost prefers low labels. The normalization factor $1/(\\eta N_G)$ is chosen so that no combination of vertex terms can outweigh the penalty for an improper coloring. The authors verify on several small graphs that the sampled ground state uses exactly $\\Gamma$ colors, and they report that the feasible-subspace mixer raises the ground-state probability compared with the standard $\\sigma^x$ mixer.","pith_inferences":["If the label-sum shortcut is replaced by an explicit count of distinct colors, the same encoding and mixer machinery would apply to the minimum-sum coloring problem, a distinct NP-hard objective; the two objectives can be compared on the same graphs.","The numerical tests use small graphs, so a natural next step is to check how the adiabatic gap and required evolution time scale with graph size and degree, which the paper does not address.","Because the one-vertex term is a diagonal label sum, exact classical diagonalization of $H_{\\mathrm{tot}}^c$ on modest graphs reveals immediately whether the ground-state color count matches the chromatic number, providing a cheap benchmark that bypasses quantum hardware."],"forward_implications":["The chromatic number would be available from a single measurement of the ground state, removing the need to run separate coloring feasibility tests for each candidate number of colors.","The qubit count per vertex scales as $\\lceil\\log_2\\eta\\rceil$ rather than $\\eta$, so the encoding is substantially cheaper than the standard QUBO formulation on near-term hardware.","For graphs whose optimal coloring uses fewer colors than the encoding's maximum, the feasible-subspace mixer is reported to increase ground-state sampling probability compared with the $\\sigma^x$ mixer.","The framework extends to constraints such as truck capacities by adding weighted penalty terms, and the authors show parameter regimes where the ground state satisfies those constraints."],"supporting_citations":[{"why":"introduces the space-efficient graph-coloring embedding on which this encoding is built","marker":"[30]"},{"why":"shows a qudit-inspired logarithmic encoding for graph coloring, the other memory-efficient prior approach","marker":"[31]"},{"why":"Brooks' theorem bounds the chromatic number by $\\Delta+1$ and fixes how many colors the simulations must allow","marker":"[35]"},{"why":"quantum annealing in the transverse Ising model underlies the adiabatic evolution used to reach the ground state","marker":"[18]"},{"why":"the quantum adiabatic evolution algorithm for NP-complete problems is the search method applied here","marker":"[19]"},{"why":"the quantum circuit simulation package used to compile and run the numerical tests","marker":"[36]"},{"why":"the classical solver used to cross-check that the sampled ground states attain the true chromatic number","marker":"[38]"}],"fun_headline_variants":["Chromatic number from one quantum measurement","Log-qubit encoding returns chromatic number","Adiabatic quantum coloring with logarithmic qubits","Single quantum measurement yields chromatic number","Graph coloring in log qubits on a quantum computer"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes that minimizing the sum of the color labels assigned to vertices is equivalent to minimizing the number of distinct colors used, and this equivalence fails for some graphs, so the ground state could use more colors than the chromatic number.","fun_headline_variants_meta":{"raw":{"variants":["Chromatic number from one quantum measurement","Log-qubit encoding returns chromatic number","Adiabatic quantum coloring with logarithmic qubits","Single quantum measurement yields chromatic number","Graph coloring in log qubits on a quantum computer"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001003,"raw_usage":{"total_tokens":4168,"prompt_tokens":796,"completion_tokens":3372,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":412,"completion_tokens_details":{"reasoning_tokens":3307}},"tokens_in":412,"tokens_out":3372,"duration_ms":27765,"temperature":1.0,"reasoning_tokens":3307,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:29:27.124013+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the ground state of the proposed Hamiltonian, for example by exact diagonalization, for a small graph where the minimum-sum coloring uses more colors than the chromatic number, such as a triangle with at least four leaves attached to each vertex; if the ground state uses four colors rather than three, the central claim is refuted.","supporting_citations":[{"cited_title":"Quantum optimization for the graph coloring problem with space-efficient embedding,","cited_arxiv_id":null,"evidence_quote":"introduces the space-efficient graph-coloring embedding on which this encoding is built"},{"cited_title":"Qudit-inspired optimization for graph coloring,","cited_arxiv_id":null,"evidence_quote":"shows a qudit-inspired logarithmic encoding for graph coloring, the other memory-efficient prior approach"},{"cited_title":"On colouring the nodes of a network,","cited_arxiv_id":null,"evidence_quote":"the classical solver used to cross-check that the sampled ground states attain the true chromatic number"}],"review_version":1}