{"id":"ea65bc19-77b1-43a9-8b17-56c9f87ee29d","arxiv_id":"2501.01058","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A Grover-based quantum genetic algorithm with divide-and-conquer is applied to MaxCut, but the oracle threshold as written marks no valid solutions.","lead":"The authors propose a quantum genetic algorithm that combines Grover search with graph partitioning to approximate MaxCut solutions on a simulator. They report exact optima on complete graphs and competitive results on random graphs, but the described circuit contains a threshold error that breaks the search mechanism.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The oracle threshold in Section 4.6 is set to |E|, but no cut value can exceed |E|, so the oracle marks no states and the reported Grover-based optimization cannot occur as described.","rationale":"The reader's weakest_assumption correctly identifies the same load-bearing flaw: Section 4.6 defines the oracle threshold as |E|, which makes the oracle mark an empty set because no MaxCut value exceeds the total number of edges. This is a genuine internal inconsistency rather than a disagreement with external consensus. The paper's strongest claim is that a Grover-based QGA with graph contraction returns exact MaxCut values on complete graphs and near-SDP results on random graphs; that claim requires the oracle to reliably separate high-fitness states from low-fitness states. As written, it cannot. I considered whether another concern might be more central, such as the divide-and-conquer heuristic losing boundary edges, but the paper itself acknowledges that limitation and even argues complete graphs are special because binary symmetry avoids boundary-edge loss. The oracle threshold, by contrast, is a silent failure that invalidates the core amplification step for every graph type, including complete graphs. The proposed test is concrete and would settle the matter: checking the actual implemented threshold in the linked code. If the code uses a different threshold, the appropriate verdict would be CONDITIONAL rather than REJECT, because the paper's central mechanism is then merely misdocumented. However, based on the manuscript text alone, the reader's REJECT verdict is fully supported, and no verdict change is needed.","tokens_in":15135,"tokens_out":1737,"duration_ms":18807,"concrete_test":"Inspect the public repository https://github.com/pauloaviana/maxcut-qga and identify the exact oracle threshold constant used in the Qiskit implementation. Concretely, locate the adder/comparator construction and log the basis states for which the oracle applies a phase flip on a small graph such as K_3. If the threshold is |E| = 3, the marked set is empty, confirming the internal contradiction. If a different threshold (e.g., floor(|E|/2)) is used, re-run Table 1 row n=3 with that threshold and verify that the reported optimal cut is produced; this would show the paper misstates the threshold but the framework can still work.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central mechanism of the proposed QGA is the oracle that marks high-fitness solutions before Grover amplification. In Section 4.6, the oracle condition is defined as g(f(u), T) = 1 if f(u) > T, with T explicitly set to |E|, the total number of edges. Since every valid cut satisfies f(u) ≤ |E|, and equality is impossible for the complete graphs used in Table 1 (e.g., K_3 has max cut 2 < |E| = 3), the marked set is empty. With zero marked states, Grover's algorithm leaves the uniform superposition unchanged up to an irrelevant global phase, and repeated measurement returns solutions with probabilities proportional only to their count, not their fitness. Thus the paper's own circuit description cannot explain the reported 'consistently achieves the true optimal MaxCut values' or the 92–96% median ratios in Tables 2–3. The results would instead require a different threshold, such as T = floor(|E|/2) or an adaptive threshold based on the current best fitness, but that threshold is nowhere specified. This is not merely a typographical issue: the convergence argument in Algorithm 1 and the complexity claim O(√(2^{M-1})) depend on a nonempty marked set of high-fitness states. As written, the central claim is internally contradicted by the oracle definition, so the numerical results are unexplained by the described algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a quantum genetic algorithm (QGA) for MaxCut. The algorithm encodes vertex partitions in a superposition, computes cut values into a fitness register via a unitary operator, applies an oracle that flips phases of states with fitness above a threshold T, and uses Grover diffusion to amplify those states. To scale beyond the available qubit register, the authors propose a divide-and-conquer heuristic that partitions graphs, solves subgraphs with the QGA, and merges solutions by graph contraction. The paper claims exact optimal MaxCut values on complete graphs, median solutions at 92--96% of the SDP values on Erdős--Rényi random graphs, and a Grover query complexity of O(sqrt(2^{M-1})). A GitHub repository and SDP comparisons are provided.","tokens_in":15417,"tokens_out":7941,"duration_ms":80135,"significance":"If the mechanism were correct, the paper would offer an interesting NISQ-era heuristic that combines Grover-style amplitude amplification with divide-and-conquer for MaxCut, with potential generalization to other combinatorial problems. The use of the analytically known complete-graph optimum and the direct comparison against SDP are appropriate validation choices, and the paper is honest about the loss of boundary edges in graph contraction. However, the central mechanism is internally inconsistent as written: the oracle threshold of |E| marks no states, so the reported results cannot follow from the described circuit. The complexity analysis also conflates search-space dimension, fitness-register width, and qubit count. These are load-bearing defects, not presentation issues, and they invalidate the empirical and theoretical claims in the current form.","major_comments":[{"comment":"The oracle is defined with T = |E| and g(f(u),T) = 1 iff f(u) > T. Since every cut value satisfies f(u) <= |E|, and f(u) = |E| is possible only when every edge is cut (i.e., the graph is bipartite and the cut is a proper 2-coloring), the marked set is empty for the complete graphs and Erdős--Rényi graphs in Tables 1--3. For example, K3 has max cut 2 < 3 = |E|. With zero marked states, Grover iteration leaves the uniform superposition unchanged up to a global phase, so measurements sample all partitions uniformly and are independent of their cut values. Consequently the abstract's claims and the results in Tables 1--3 cannot follow from the described algorithm. The paper must either use a threshold that is actually attainable and below the maximum cut value, consistent with the lower-bound discussion in Section 4.4, or specify an adaptive threshold scheme such as Durr--Hoyer maximum finding; as written, Section 4.6 contradicts the algorithm's stated convergence behavior.","section":"Section 4.6 and Algorithm 1"},{"comment":"The query complexity is derived as O(sqrt(2^{M-1})) by writing N = 2^M / 2. This conflates the fitness-register width M with the search space. The search is over vertex partitions, whose number is 2^{|V|}; the factor 2 for 'two exact solutions' would affect the number of marked states, not the dimension of the fitness register. With exactly two marked states, the Grover iteration count should be O(sqrt(2^{|V|}/2)), not O(sqrt(2^{M-1})). As written, the claimed complexity is independent of the number of vertices and is therefore not supported.","section":"Algorithm 1, step 6, and Section 4.8"},{"comment":"The resource formula f(|V|,n,M,m) = |V|*n + 2*(M+m) + 3 treats the Grover iteration count m as an additive number of qubits. Grover iterations are repeated applications of the same oracle and diffusion circuits; they increase circuit depth, not qubit width. The formula also appears to insert m = O(sqrt(2^M)) as though it were a register size. The derived bound g(n) is garbled: a complete graph has |E| = n(n-1)/2, so M = ceil(log2(n(n-1)/2)), not the expression used in the manuscript. This invalidates the stated minimum-qubit-requirement claim.","section":"Section 4.8"},{"comment":"The convergence loop is not specified. The text says the cycle is repeated until the threshold ceases to improve, but Algorithm 1 has no threshold update rule, stopping criterion, or specification of how many repetitions and measurement shots are used. Table 3 reports 'best picks after multiple runs' without defining the number of runs or the selection procedure. Under the circuit as described, whose actual behavior is uniform sampling, a 'best of many runs' is just random search. Without these details, the empirical tables cannot be interpreted as evidence for the proposed algorithm.","section":"Sections 4.2.1 and 5.4"}],"minor_comments":[{"comment":"There are duplicated references: the Goemans--Williamson SDP paper appears as [10], [11], and [12], Shor appears as both [45] and [46], and Nielsen--Chuang appears as both [33] and [34]. The bibliography should be consolidated.","section":"References"},{"comment":"There are numerous typographical and rendering errors, including 'tThen' in Section 4.2.1, 'Erd˝os-R´enyi' in the abstract, 'respectivelly' and 'proposted' in Section 5, and 'withing the theoretical limit' in Section 5.3.","section":"Throughout"},{"comment":"The function signature f: {G,K} -> N is unclear; the fitness function should be defined on the space of partitions, e.g., {0,1}^{|V|}, rather than on the unexplained symbols G and K.","section":"Section 4.5"},{"comment":"The CNOT matrix and behavior are referenced with 'Figure ??', indicating a missing or unresolved cross-reference.","section":"Section 2.1"},{"comment":"The experimental setup does not report the number of runs, number of measurement shots, random seeds, simulator version, or details of the METIS partitioning and boundary-edge handling, which are needed for reproducibility.","section":"Section 5.1"}],"recommendation":"reject","confidential_remarks":"The stress-test concern about the empty oracle set lands exactly: Section 4.6 defines a threshold that no cut can exceed, so the reported optimal and near-optimal results are unexplained by the described circuit. The complexity analysis in Section 4.8 has additional independent errors. These are central, not peripheral, defects; in my view the manuscript is not acceptable even in major-revision form unless the authors replace the oracle mechanism with a correct one and re-derive both the convergence and complexity claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this is a new application of the reduced quantum genetic algorithm plus Grover and graph contraction to MaxCut, but the oracle in Section 4.6 marks no states because it sets T=|E| and marks f(u)>|E|. As written, the algorithm cannot do what the tables claim. The marked set is empty, Grover does nothing, and the reported results look like random sampling with best-of-many-shots selection. Credit where due: the paper is clearly structured, cites the analytical complete-graph optimum correctly, includes code, and is honest about losing boundary edges in contraction. The complete-graph experiments would be a nice check with a corrected oracle, and the SDP baseline is reasonable. Soft spots, in order of severity. First, the oracle threshold. f(u)>|E| is never true. The convergence argument in Algorithm 1 and the O(sqrt(2^{M-1})) complexity claim both depend on a nonempty marked set. If the intended threshold is current-best fitness or floor(|E|/2), it is not stated, and the GitHub implementation would need to be checked against the text. Second, Section 4.8's complexity analysis conflates vertex-encoding qubits with fitness-register qubits; the square-root speedup is inherited from Grover and the cost per oracle call is ignored. Third, the statistics are thin: no error bars, Table 3 selects the best of several runs, and each G(n,p) instance is a single graph, so the 92-96% claim is overly precise. The median values on random graphs sit near the random-cut expectation, which is consistent with the empty-oracle reading. I would not desk-reject this. The error is specific and correctable, and the paper deserves referee time to check whether a corrected oracle reproduces the tables. As written, the central claim does not hold, so the verdict has to be major revision or reject pending revision.","headline":"A legitimate new combination of RQGA, Grover, and graph contraction for MaxCut, but the oracle threshold as written marks no states, so the reported results cannot follow from the described circuit.","tokens_in":15951,"tokens_out":4980,"would_cite":false,"duration_ms":49535,"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":"This paper proposes a quantum genetic algorithm that encodes all MaxCut partitions in superposition, amplifies high-fitness cuts with Grover search, and uses divide-and-conquer contraction, reporting exact optimal values on complete…","keywords":["MaxCut","quantum genetic algorithm","Grover's algorithm","divide and conquer","graph contraction","semidefinite programming","combinatorial optimization","NISQ"],"falsifier":"Build the Section 4.6 oracle for any small graph, set the threshold to $T=|E|$, and enumerate the truth table of $f(u)>T$ over all $2^{|V|}$ partitions: the predicate is false for every partition, so a complete Grover iteration leaves the uniform superposition unchanged and measuring gives no better than a random cut, directly contradicting the reported convergence.","tokens_in":14926,"feed_emoji":"⚡️","tokens_out":10989,"duration_ms":90702,"temperature":0.7,"pith_summary":"The paper sets out to show that MaxCut, a hard combinatorial optimization problem, can be handled by a quantum genetic algorithm that replaces classical crossover and mutation with Grover search. It encodes all candidate partitions in a superposition, computes each cut's value in a quantum register, amplifies the best cuts, and uses graph partitioning and contraction to fit large graphs onto a small quantum register. On complete graphs the reported method returns the true optimal cut for every tested instance, and on Erdős–Rényi random graphs it produces median solutions within 92–96% of the semidefinite programming (SDP) baseline, with best runs often reaching or exceeding SDP. A sympathetic reader would take the paper's contribution to be a concrete, near-term-hardware template for turning Grover search into a reusable optimizer rather than a proof of quantum advantage over classical heuristics.","feed_headline":"Grover-based genetic algorithm returns exact MaxCut on complete graphs","feed_subtitle":"Split-and-contract quantum search also lands within 92–96% of SDP on random graphs.","key_machinery":"The load-bearing object is the Grover search circuit, specifically the oracle-diffuser pair. The authors define an oracle that marks basis states by the condition $f(u) > T$, where $f(u)$ is the cut value stored in the fitness register and $T$ is said to be the total number of edges $|E|$; since $f(u) \\le |E|$ for every cut, this threshold as written marks no states, so the convergence mechanism in the paper needs a different threshold to be well-defined. The fitness values are computed by a reversible circuit built from CNOT and Toffoli gates, and the comparison $f(u)>T$ is implemented with a quantum ripple-carry adder. Around this core, the algorithm wraps a divide-and-conquer layer: graph partitioning into subgraphs, independent local QGA optimization, and graph contraction into a meta-graph whose edge weights encode the boundary connections, using the $\\mathbb{Z}_2$ symmetry of MaxCut to make subgraph flips harmless.","core_discovery":"At the paper's center is the claim that MaxCut can be attacked by a quantum genetic algorithm in which no genetic operators are needed. All candidate partitions are loaded into a single superposition, a reversible fitness circuit computes each partition's cut value into a fitness register, and a Grover oracle built from a quantum ripple-carry adder flips the phase of states whose cut value exceeds a threshold $T$. Repeated Grover diffusion then amplifies those high-fitness states, and a measurement returns a good partition. To handle graphs larger than the available qubits, the algorithm recursively partitions the graph, solves each subgraph independently, and contracts the subgraphs into a weighted meta-graph, exploiting the $\\mathbb{Z}_2$ symmetry of MaxCut so a subgraph solution and its complement are treated as equivalent. The paper reports that on complete graphs this procedure returns the exact MaxCut $\\lfloor n^2/4 \\rfloor$ for every tested size, while SDP gives at most about 99.7% there, and on Erdős–Rényi graphs the median QGA value is 92–96% of the SDP value, with the best of several runs often matching or beating SDP.","pith_inferences":["A corrected threshold would make the Grover mechanism concrete: shifting $T$ from $|E|$ to something like $\\lfloor |E|/2 \\rfloor$ (or a dynamic value) gives a non-empty marked set and makes the claimed convergence testable on small simulators.","The exactness on complete graphs is a special case of the contraction heuristic: because complete graphs have uniform boundary structure, merging subgraphs costs no edges, whereas on sparse graphs boundary-edge loss is real, so the 92–96% median on Erdős–Rényi graphs is the more typical operating regime.","Section 4.8's resource formula adds the Grover iteration count $m$ to the qubit count as if it were a register dimension; correcting that conflation would change the reported scaling and should be settled before using the complexity result for hardware estimates."],"forward_implications":["If the reported complete-graph results hold, the QGA would outperform the SDP baseline on the tested range, returning exact cut values while SDP saturates near 99.7%.","The $O(\\sqrt{2^M})$ query count gives a quadratic speedup over exhaustive enumeration of cuts, although the search space itself is exponential in the number of vertices.","The divide-and-conquer contraction makes the algorithm executable with a small qubit register on larger graphs, at the cost of losing boundary edges between subgraphs.","On Erdős–Rényi graphs, median values within 92–96% of SDP and best runs at or above SDP suggest the framework is competitive as a heuristic, not just as an exact solver for complete graphs.","The same oracle-plus-contraction skeleton could be adapted to other binary assignment problems, as the conclusion suggests for weighted MaxCut and related combinatorial problems."],"supporting_citations":[{"why":"Supplies the Grover search subroutine whose oracle and diffuser carry the algorithm.","marker":"[15]"},{"why":"Defines the semidefinite-programming baseline that the QGA results are compared against.","marker":"[10]"},{"why":"Provides the exact MaxCut formula for complete graphs that the QGA claims to match.","marker":"[7]"},{"why":"Introduces the reduced quantum genetic algorithm framework that this paper extends.","marker":"[51]"},{"why":"Gives the quantum ripple-carry adder used to compare fitness values in the oracle.","marker":"[5]"},{"why":"Inspires the divide-and-conquer graph contraction heuristic for large graphs.","marker":"[56]"},{"why":"Shows a prior application of the reduced quantum genetic algorithm to graph coloring.","marker":"[1]"}],"fun_headline_variants":["Grover finds exact MaxCut on complete graphs","No genetic operators needed: Grover solves MaxCut exactly on complete graphs","Quantum genetic algorithm nears SDP on random MaxCut graphs","Split-and-conquer quantum search exact on complete graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the oracle marks a non-empty set of high-fitness states, yet the stated threshold $T=|E|$ makes the marked set empty because every cut value is at most $|E|$.","fun_headline_variants_meta":{"raw":{"variants":["Grover finds exact MaxCut on complete graphs","No genetic operators needed: Grover solves MaxCut exactly on complete graphs","Quantum genetic algorithm nears SDP on random MaxCut graphs","Split-and-conquer quantum search exact on complete graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001721,"raw_usage":{"total_tokens":6832,"prompt_tokens":998,"completion_tokens":5834,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":5766}},"tokens_in":614,"tokens_out":5834,"duration_ms":37992,"temperature":1.0,"reasoning_tokens":5766,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:35:44.874735+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build the Section 4.6 oracle for any small graph, set the threshold to $T=|E|$, and enumerate the truth table of $f(u)>T$ over all $2^{|V|}$ partitions: the predicate is false for every partition, so a complete Grover iteration leaves the uniform superposition unchanged and measuring gives no better than a random cut, directly contradicting the reported convergence.","supporting_citations":[{"cited_title":"A fast quantum mechanical algorithm for database search","cited_arxiv_id":null,"evidence_quote":"Supplies the Grover search subroutine whose oracle and diffuser carry the algorithm."},{"cited_title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","cited_arxiv_id":null,"evidence_quote":"Defines the semidefinite-programming baseline that the QGA results are compared against."},{"cited_title":"Some extremal properties of bipartite subgraphs","cited_arxiv_id":null,"evidence_quote":"Provides the exact MaxCut formula for complete graphs that the QGA claims to match."},{"cited_title":"Cuccaro et al","cited_arxiv_id":null,"evidence_quote":"Gives the quantum ripple-carry adder used to compare fitness values in the oracle."},{"cited_title":"Qaoa-in-QAOA: Solving large-scale MaxCut problems on small quantum machines","cited_arxiv_id":null,"evidence_quote":"Inspires the divide-and-conquer graph contraction heuristic for large graphs."},{"cited_title":"Graph coloring using the reduced quantum genetic algorithm","cited_arxiv_id":null,"evidence_quote":"Shows a prior application of the reduced quantum genetic algorithm to graph coloring."}],"review_version":1}