{"id":"56a5e5dc-291f-49c8-923c-c356f643ae76","arxiv_id":"2508.07007","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A quantum-walk framing of Kruskal's algorithm: edge weights are inverted to define a Hamiltonian, and picking the highest transition-probability edges reproduces the MST, with a greedy degree cap for the constrained case.","lead":"The paper recasts the minimum spanning tree problem as a continuous-time quantum walk, encoding edge weights as inverse couplings and selecting edges by highest transition probability. For the degree-constrained variant it adds a greedy degree cap, reporting near-optimal results in simulations up to 10,000 vertices.","discovery_kind":"incremental","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Correctness of Quantum Kruskal rests on an unproven, empirically fitted short-time regime in which transition-probability order matches weight order; the paper supplies no bound for when higher-order interference terms reorder edges.","rationale":"The paper's central claim is that the MST is the tree maximizing cumulative transition probabilities and that sorting by P and applying a Kruskal-style cycle test reconstructs the (MDC-)MST. The proof depends entirely on the short-time truncation P approx tau^2/w^2. I examined whether this is an internal inconsistency or merely a missing guarantee. It is the latter, but it is fatal: Eq. (8) contains path-dependent second- and higher-order terms, and for any fixed tau > 0 these can, in principle, reorder P relative to 1/w^2. The empirical tau(V) fit and experiments on weights 1-20 do not establish correctness for arbitrary positive weights. This is essentially the reader's weakest assumption. I do not think the product-versus-sum objection in the reader's rationale is the strongest form: because any strictly increasing transform of edge weights preserves Kruskal's output, P approx tau^2/w^2 would be sufficient (if exactly true) to recover the MST. The real problem is that P is not proved to be such a transform. If P ordering differs from weight ordering, Theorem .1's cut-property proof fails; if P ordering matches, Algorithm 1 is Kruskal with a costly preprocessing step. The MDC heuristic only sorts and filters the same probabilities, so it inherits the weakness. The proposed exhaustive search at V=4 (or heavy-tailed larger V) would settle whether a counterexample exists: if one is found, the central claim is false; if none is found, the claim still lacks proof and the algorithm remains a disguised version of Kruskal. The reader's REJECT verdict stands.","tokens_in":15925,"tokens_out":8780,"duration_ms":96619,"concrete_test":"Exhaustive counterexample search: for V=4, enumerate all 20^6 assignments of integer weights in {1,...,20} to the six labeled edges. For each assignment, form H = D' - A' and compute the exact transition probabilities P(lambda|m) = |<lambda|e^{-i tau H}|m>|^2 at tau = 0.1 and at tau = 4/(pi*sqrt(4)) + 0.1. Compare the edge ordering by P descending with the ordering by w^{-2} descending. If any graph has edges e, f with w_e < w_f but P(e) < P(f), then Eq. (10) is false and the proof of Theorem .1 fails. Additionally record whether the V-1 highest-probability acyclic edges equal the true MST total weight; if not, the exact-MST claim is directly falsified. If no counterexample appears for weights 1-20, repeat with weights drawn log-uniformly over [1, 10^4] and tau in [0.05, 1.0], since the omitted two-hop interference terms scale as products of inverse weights and should reorder most readil","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing step is the passage from Eq. (8) to Eqs. (9)-(10). The paper truncates P(lambda|m) as tau^2 * w^{-2}_{lambda m} and then asserts that sorting by P is equivalent to sorting by weight. If P were any strictly increasing function of w^{-1}, the equivalence would hold because Kruskal's output is invariant under monotone transforms of edge costs. But Eq. (8) is not a function of the single edge weight: for finite tau it contains (tau^2/2! * sum_j w^{-1}_{lambda j} w^{-1}_{j m})^2 plus higher-order and cross terms that depend on every two-hop path through intermediate vertices. Nothing in the paper bounds these terms relative to the gaps between tau^2/w^2 values. The fitted tau(V) = 4/(pi*sqrt(V)) + 0.1 is empirical, obtained on random weights 1-20, and there is no proof that for arbitrary positive weights, at tau = tau(V), the ordering by P is identical to the ordering by w. Consequently Theorem .1 is unsupported: its proof invokes 'maximal p(e) crossing that cut, which by definition is the edge of minimal w(e),' and that definitional equivalence is exactly what has not been established. If the ordering ever differs, Algorithm 1 is not Kruskal and has no correctness guarantee; if it never differs, the quantum walk is an expensive way to recompute the weight ordering and Algorithm 1 is just Kruskal. The MDC extension inherits this: the constraint is enforced after probabilities are sorted, so the claimed MDC >= 5 near-optimality is no more robust than the unverified short-time ordering assumption.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a continuous-time quantum walk (CTQW) approach to the minimum spanning tree (MST) problem and its maximum-degree-constrained (MDC) variant. Vertices are encoded in log2(V) qubits and the Hamiltonian is taken from the weighted Laplacian with edge weights inverted (A'_ij = 1/w_ij). Transition probabilities P(j|i) = |<j|e^{-iHτ}|i>|^2 are computed, sorted in decreasing order, and edges are added greedily if they do not create a cycle (Quantum Kruskal). The authors claim that, in a short-time window, the V−1 highest probabilities form an exact MST, and that the MDC version returns optimal/near-optimal trees for Δ≥5. They also claim that the MST maximizes a Shannon-entropy measure and relate the construction to maximal-entropy random walks. Numerical experiments on complete graphs up to 10^4 vertices are reported.","tokens_in":16271,"tokens_out":15862,"duration_ms":175635,"significance":"If the central equivalence were proved, the log-qubit encoding would be an interesting representational economy, and the MDC heuristic results might be of practical interest. The paper does provide extensive numerical evidence that, for random weights in limited ranges, a fitted short-time window makes the greedy probability ordering reproduce Kruskal's choice. However, the correctness of the entire construction rests on this empirical short-time window: no rigorous bound is given, the proof of the main theorem is circular, and the entropy/MERW connection is asserted rather than derived. The paper also does not provide code or data. Hence the central claim is not established.","major_comments":[{"comment":"The load-bearing step is the passage from Eq. (8) to Eqs. (9)–(10). Eq. (8) contains terms of the form (τ^2/2! Σ_j w^{-1}_{λj} w^{-1}_{jm})^2 plus higher-order and cross terms, so for finite τ the probability P(λ|m) is not a function of the single edge weight w_{λm}. The paper truncates to P ≈ τ^2 w^{-2}_{λm} and then concludes that sorting by P is equivalent to sorting by w. No bound is provided for the neglected terms, and the fitted time τ(V) = 4/(π√V) + 0.1 (Fig. 3c) is obtained empirically on random weights in [1,20]; it cannot guarantee order preservation for arbitrary positive weights, where gaps between w^{-2} can be arbitrarily small. Consequently Theorem .1 is unsupported: the proof's statement that 'the edge of maximal p(e) crossing that cut, which by definition is the edge of minimal w(e)' is exactly the unproved assertion. If the ordering ever differs for some edge, Algorith","section":"Methods, Eqs. (8)–(10), and Theorem .1"},{"comment":"The claim that the MST maximizes the Shannon entropy of transition probabilities, and that this reflects MERW behavior, is not established. It is illustrated for one 4-vertex graph (Fig. 4) and then generalized. No derivation connects the finite-time CTQW probabilities to the MERW stationary distribution or entropy rate. This is not needed for Algorithm 1, but it is advertised in the abstract and conclusion; as stated it is an unsupported assertion.","section":"Shannon Entropy and MERW"},{"comment":"The MDC extension is a greedy heuristic that enforces the degree constraint after probability sorting. The observed success rates (Fig. 5b) are empirical and cannot justify the general claim 'for MDC bigger or equal to 6 all the cases result in a MST'. Since MDC-MST is NP-hard, no polynomial guarantee is expected, but the paper should present the MDC version as a heuristic and characterize when it can fail. The ad hoc explanation in terms of 'non-Markovian' behavior does not provide such a characterization.","section":"Algorithm 2 / MDC"}],"minor_comments":[{"comment":"The pseudocode sets D'_ii = 1/Dii and A'_ij = -1/Aij, which is inconsistent with Eq. (2) and the Methods definition A'_ij = 1/w_ij with H = D' - A'. As written, the pseudocode would give H = D' + A'.","section":"Algorithm 1, lines 4–5"},{"comment":"The phrase 'If the number of vertices (V) is a multiple of two' should presumably read 'a power of two'.","section":"Methods, encoding paragraph"},{"comment":"The constants ℏ and c are introduced and then set to 1; the definition of τ = ct and the sign convention in the expansion Eq. (7) should be stated consistently. Currently the reader must reverse-engineer the convention from the Trotter approximation.","section":"Eqs. (2), (7) and τ=ct"},{"comment":"The text describes 'solid lines' and 'dotted lines', while the captions refer to solid dots and markers; the legend should be clarified.","section":"Figs. 3a/3b captions and text"},{"comment":"Table II reports 'MST accuracy (MDC≥5) > 99%', while Fig. 5b reports 0.04% failures at Δ=5. These are consistent, but the paper should reconcile the statement 'from the MDC bigger or equal to 6 all the cases result in a MST' with the earlier text saying 'MDC exceeds 5'.","section":"Table II vs Fig. 5b"}],"recommendation":"reject","confidential_remarks":"The manuscript is best understood as a quantum-inspired heuristic with a substantial but unproven empirical component. The central equivalence is not proven, and the proof of Theorem .1 is circular. The novelty over classical Kruskal is limited: if the probability ordering were correct, the algorithm merely re-labels the weight ordering. I would not encourage resubmission unless the authors can provide a rigorous order-preservation bound for the short-time regime or a clear characterization of when the heuristic fails."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, this paper claims a quantum walk algorithm for MST with degree constraints, but the mechanism reduces to Kruskal's algorithm. The leading-order transition probability is tau^2/w^2, so sorting by probability is sorting by weight. Then the greedy selection is exactly Kruskal. The MDC trick is degree-constrained Kruskal, a known heuristic.\n\nThe serious problem is the paper's formal claim. It says the MST is the tree maximizing the product of transition probabilities, and Eq. (10) asserts this is equivalent to minimizing edge weights. That's wrong: the MST minimizes the sum of weights. Maximizing the product of 1/w^2 minimizes the product of weights, which is not the same objective. Unless all weights are special, the two orderings differ. The paper's own equations (8)-(9) show only a leading-term equivalence, and no bound covers the higher-order interference terms. The fitted time window tau(V) is empirical, not proven. So if the probability ordering matches the weight ordering, the algorithm is Kruskal; if it doesn't, there's no correctness guarantee.\n\nWhat's good: the paper is clearly written and candid about limitations. The numerical experiments up to 10^4 vertices are extensive, and for MDC >= 5 the heuristic reportedly matches exact MILP on nearly all tested cases. The entropy connection is interesting but supported only by a single 4-vertex example. The qubit scaling observation is fine, but the claimed quantum advantage is hand-wavy.\n\nThe main issue is a load-bearing mathematical error, not a minor bug. The core hypothesis is false as stated, and the algorithmic novelty is essentially Kruskal with a different sort key. An experienced referee would likely catch this quickly. Still, the paper is honest and the MDC experiments are useful, so it deserves referee time rather than a desk reject—but I would not cite it for correctness.","headline":"The quantum walk part reduces to Kruskal; the central equivalence claim (min sum vs max product) is wrong, though the MDC heuristic and experiments are honest.","tokens_in":16858,"tokens_out":3325,"would_cite":false,"duration_ms":31865,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"The paper claims that a continuous-time quantum walk with inverse-weight couplings encodes the minimum spanning tree as the highest-probability path, recoverable with O(log N) qubits.","keywords":["minimum spanning tree","maximum degree constraint","continuous-time quantum walk","Kruskal's algorithm","transition probabilities","quantum resource efficiency","Shannon entropy","maximal entropy random walk"],"falsifier":"Take a fully connected graph with, say, 16 vertices and choose edge weights so that two edges have nearly equal weights but very different numbers of length-2 paths connecting their endpoints. At the fitted τ(V), compute the continuous-time quantum walk transition probabilities and check whether the highest V−1 cycle-free probabilities still form the true MST. A single weight distribution where the second-order term reorders an edge pair, so that the greedy probability-ordered tree has a higher total weight than the MST, would falsify the short-time ordering claim in Eq. (9).","tokens_in":15768,"feed_emoji":"⚛️","tokens_out":8442,"duration_ms":92706,"temperature":0.7,"pith_summary":"The paper proposes that, on a fully connected graph, the minimum spanning tree is the tree whose edges have the largest cumulative quantum transition probabilities, once the Hamiltonian is built from inverse edge weights. At short evolution times, the transition probability between two vertices is shown to be approximately proportional to 1/$w^{2}$, so the highest-probability edges are precisely the lowest-weight edges; a greedy 'Quantum Kruskal' selection then recovers the MST. The authors report exact MST recovery for unconstrained graphs and optimal or near-optimal total weight for degree-constrained versions when the maximum allowed degree is at least 5, using a qubit count that scales as O(log N) instead of O($N^{2}$). If the claims hold, this would make large-scale MST and MDC-MST instances accessible to hybrid quantum-classical solvers and quantum-inspired classical heuristics, sidestepping the qubit bottleneck of QUBO-based approaches.","feed_headline":"A quantum walk singles out the minimum spanning tree","feed_subtitle":"Inverting edge weights makes the walk's most probable connections the lightest spanning tree.","key_machinery":"The central object is the inverse-weight Hamiltonian H = D′ − A′, where the off-diagonal coupling between vertices i and j is 1/w_ij instead of w_ij, driving a continuous-time quantum walk U(t) = $e^{{−iHt}}$. The load-bearing identity is the short-time expansion P(λ|m) ≈ $τ^{2}$ $w^{{-2}}$_{λm}, which converts the combinatorial problem of minimizing edge weights into an ordering problem on transition probabilities; the resulting 'Quantum Kruskal' algorithm greedily assembles the tree from the ordered probabilities, inheriting correctness from the classical cut property and exchange arguments.","core_discovery":"The central claim is that the MST is the spanning tree maximizing the product of single-step quantum transition probabilities, T = argmax_{T'} ∏_{(i,j)∈E_{T'}} P(j|i), with P(j|i) taken from a continuous-time quantum walk whose Hamiltonian H = D' − A' uses inverse edge weights as couplings. For short times, the expansion P(λ|m) ≈ $τ^{2}$ $w^{{-2}}$_{λm} shows that the ordering of transition probabilities is the reverse ordering of edge weights; maximizing the product over the V−1 chosen edges is therefore equivalent, by a monotone transformation, to minimizing the total edge weight. The paper proves by cut-property and exchange arguments that greedy selection of the highest-probability edges that do","pith_inferences":["Editorial extension: The equivalence between minimizing weights and maximizing the probability product only requires the edge-ordering to be preserved; if a rigorous bound on the second-order interference terms could be established for a broad class of weight distributions, the fitted τ(V) would become a provable guarantee rather than an empirical fit.","Editorial extension: The reported MDC failure modes (needing low-probability edges and degeneracy) suggest a concrete diagnosis: randomly perturbing near-degenerate weights should restore optimality at Δ = 2–4, isolating degeneracy as the main obstacle and potentially extending the exact regime.","Editorial extension: The interpretation that the MST is 'the most informative tree' suggests a testable bridge to network science: on real-world weighted graphs, the tree computed from quantum-walk probabilities should coincide with the MST whenever the graph is Markovian, and deviations may flag non-Markovian structures worth studying in their own right."],"forward_implications":["MDC-MST instances with degree bound Δ ≥ 5 can be solved to near-optimality on graphs with roughly 10^4 vertices using approximately 14 qubits, a dramatic reduction from the thousands or more required by Ising/QUBO formulations.","Because the ordering of transition probabilities is what matters, the method is robust to monotone rescaling of edge weights; the quantum walk effectively discovers the MST ordering rather than computing it by explicit comparisons.","The algorithm runs on near-term quantum hardware, since it only requires short-time coherent evolution and not ground-state preparation or variational optimization; classically it reduces to an O(N^3) quantum-inspired heuristic.","The empirical time window τ(V) links the number of coherent walk steps to Grover-style search on complete graphs, suggesting that the MST structure is sampled before interference scrambles the probability ordering.","The observed coincidence between the entropy-maximizing tree and the MST, in both constrained and unconstrained cases, implies that the method naturally outputs the tree that maximizes information content among spanning trees."],"supporting_citations":[{"why":"Kruskal's greedy algorithm, whose cut-property and exchange-argument correctness the Quantum Kruskal variant inherits.","marker":"[17]"},{"why":"Establishes the continuous-time quantum walk model on graphs, the dynamical framework supplying the transition probabilities.","marker":"[22]"},{"why":"Review reference for the quantum-walk Hamiltonian and evolution operator used in the formulation.","marker":"[25]"},{"why":"Trotter–Suzuki product formula used to justify the short-time expansion and the n=1 approximation.","marker":"[27]"},{"why":"Lucas's Ising/QUBO formulation of the MST, whose cubic qubit scaling the paper contrasts with its logarithmic scaling.","marker":"[2]"},{"why":"Fowler's D-Wave QUBO formulation, the baseline for the qubit-count comparison in Table I.","marker":"[4]"},{"why":"Maximal-entropy random walk theory used to connect the selected MST to maximum Shannon entropy among spanning trees.","marker":"[28]"}],"fun_headline_variants":["Quantum walk finds MST with inverted edge weights","Log-qubit quantum walk solves MST problem","Quantum walk outperforms classical for degree >4","Probability-driven walk locates minimum spanning tree","Quantum walk near-optimal for constrained MST"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The whole method rests on the assumption that within the chosen short evolution time, the transition-probability ordering is dominated by the 1/$w^{2}$ term, so the most probable edges are exactly the lowest-weight edges; the paper justifies this with a truncated Taylor expansion and an empirically fitted time window, not with a proof that higher-order interference terms never reorder the probabilities.","fun_headline_variants_meta":{"raw":{"variants":["Quantum walk finds MST with inverted edge weights","Log-qubit quantum walk solves MST problem","Quantum walk outperforms classical for degree >4","Probability-driven walk locates minimum spanning tree","Quantum walk near-optimal for constrained MST"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000253,"raw_usage":{"total_tokens":1393,"prompt_tokens":728,"completion_tokens":665,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":472,"completion_tokens_details":{"reasoning_tokens":598}},"tokens_in":472,"tokens_out":665,"duration_ms":8692,"temperature":1.0,"reasoning_tokens":598,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T22:24:16.876741+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a fully connected graph with, say, 16 vertices and choose edge weights so that two edges have nearly equal weights but very different numbers of length-2 paths connecting their endpoints. At the fitted τ(V), compute the continuous-time quantum walk transition probabilities and check whether the highest V−1 cycle-free probabilities still form the true MST. A single weight distribution where the second-order term reorders an edge pair, so that the greedy probability-ordered tree has a higher total weight than the MST, would falsify the short-time ordering claim in Eq. (9).","supporting_citations":[{"cited_title":"Assuncao, M","cited_arxiv_id":null,"evidence_quote":"Kruskal's greedy algorithm, whose cut-property and exchange-argument correctness the Quantum Kruskal variant inherits."},{"cited_title":"non-Markovian","cited_arxiv_id":null,"evidence_quote":"Lucas's Ising/QUBO formulation of the MST, whose cubic qubit scaling the paper contrasts with its logarithmic scaling."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Maximal-entropy random walk theory used to connect the selected MST to maximum Shannon entropy among spanning trees."}],"review_version":1}