{"id":"49ed14eb-a18a-43bd-8834-fcaec064d9d8","arxiv_id":"2507.05373","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A standard graph partitioner and circuit-cutting toolkit shrink a 13-node VRP from 156 qubits to 6-qubit subcircuits, but the quality of the 13-node solution is not reported.","lead":"This preprint cuts a 13-stop vehicle routing problem into small pieces so each piece fits on a tiny quantum chip, reporting large reductions in required qubits and circuit depth. It does not show the actual quality of the stitched-together 13-stop route, so the 'quantum utility' claim is not yet backed by results.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The cost function in Eq. 9 omits MTZ subtour-elimination constraints, so the QAOA objective encodes a cycle cover rather than a TSP/VRP; solution-cost claims are therefore not evidence of solving the declared problem.","rationale":"The reader's weakest assumption concerns whether METIS partitioning preserves the optimal VRP solution space. That is a legitimate concern and is explicitly acknowledged by the authors as unresolved. However, an even more fundamental issue is that the QUBO Hamiltonian in Eq. 9 does not encode the TSP/VRP correctly: it enforces only degree and depot constraints, omitting the subtour-elimination constraints that distinguish a single Hamiltonian cycle from a disjoint cycle cover. This is not a matter of heuristic quality or partitioning; it is an internal inconsistency with the stated MTZ formulation. If the objective function admits invalid subtours with low energy, QAOA may converge to solutions that are not routes at all, and the solution-cost comparisons in Fig. 4 become meaningless as evidence for solving VRPs. The resource-reduction numbers in Tables III, IV, and VI are internally consistent and likely reproducible, but the abstract's feasibility and quantum-utility claims rest on solving the actual routing problem, not merely on shrinking circuits. The reader's rejection is therefore well-founded, and our different emphasis on the missing subtour constraints does not change the verdict. We also note that the amplitude-encoding experiment did not reconstruct the expectation value, and the 13-node solution cost is deferred, further weakening the central claim.","tokens_in":12361,"tokens_out":4656,"duration_ms":54717,"concrete_test":"Select a symmetric 4-node TSP with one vehicle (depot plus 3 cities). Using the edge weights and λ values from the paper (or a range of λ), brute-force enumerate all 2^6 binary strings that satisfy Eqs. 4–5 and compute H_c from Eq. 9. Show that the minimum-energy string can be two disjoint directed cycles (e.g., depot→A→depot and B→C→B) with energy less than or equal to the optimal single tour 0→A→B→C→0. If such a string exists, Eq. 9 is not a valid TSP encoding. A second check: add MTZ subtour-elimination penalties to H_c and rerun the n=8, K=2 and n=9, K=2 cases; if the measured solution costs or route validity change materially, the paper's comparisons are affected.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim requires that the quantum-optimized cost H_c corresponds to the VRP/TSP objective. In Section II-A, the authors state that Eq. 9 is the MTZ formulation (Eqs. 2–7). However, Eqs. 4–7 enforce only in/out degree per node and depot degree K; they do not include the MTZ subtour-elimination inequalities (e.g., u_i - u_j + n x_ij <= n-1 for i,j >= 1). Consequently, the ground state of H_c can be a collection of disjoint cycles (a cycle cover), not a single Hamiltonian cycle. QAOA minimizing H_c therefore may return invalid routes with low energy; the reported observation that valid paths were measured only a handful of times is consistent with a cost landscape that does not penalize subtours. Because the solution-cost comparisons in Fig. 4 are claimed to demonstrate competitive VRP solutions, and the 13-node cost is explicitly deferred, this missing constraint is the most load-bearing flaw: even with perfect partitioning and circuit cutting, the quantum routine would be solving a different optimization problem. The resource-reduction tables can be correct and yet the feasibility and quantum-utility claims still fail.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a two-level decomposition for solving Vehicle Routing Problems (VRP) with QAOA. A problem-level decomposition (PLD) uses METIS to partition a VRP into several single-vehicle TSPs, and a circuit-level decomposition (CLD) uses circuit cutting/knitting to reduce each TSP circuit to smaller subcircuits. The authors report large reductions in qubit count, circuit depth, and two-qubit-gate count for instances up to a 13-node, 5-vehicle VRP (from 156 qubits, depth 534, and 3432 CX gates to at most 6 qubits, depth 25, and 16 CX gates). They also compare solution costs with Google OR-Tools for n=7, 8, and 9 instances and describe an amplitude encoding that could not be fully executed due to cutting overhead. The abstract claims that these results demonstrate feasibility of solving previously intractable VRPs and provide early evidence of quantum utility.","tokens_in":12527,"tokens_out":6927,"duration_ms":86193,"significance":"If the resource-reduction claims are correct, the paper provides a concrete, directly checkable example of circuit cutting: Tables III and IV support the 96% qubit, 95% depth, and 99.5% two-qubit-gate reductions by simple arithmetic. The use of brute-force verification for small TSP partitions and the comparison with an external classical tool are appropriate methodological choices. However, the central feasibility claim is not supported by the reported experimental results. The submitted manuscript explicitly defers the 13-node solution-cost results, the amplitude-encoding results are declared incomplete, and the QUBO Hamiltonian in Eq. (9) does not enforce the MTZ subtour-elimination constraints that are needed for the problem to be a TSP/VRP rather than a cycle-cover problem. Consequently, the paper currently demonstrates that large resource reductions are possible on paper, but not that the decomposed quantum routine solves the declared routing problem or that its solutions are competitive. The significance of the paper as a feasibility demonstration therefore remains unestablished until these load-bearing gaps are addressed.","major_comments":[{"comment":"The Hamiltonian Hc in Eq. (9) is claimed to derive from the MTZ formulation in Section II-A, but Eqs. (4)-(7) enforce only in/out degree constraints and depot degree K. They do not include the MTZ subtour-elimination inequalities (e.g., u_i - u_j + n x_ij <= n-1 for i,j >= 1). As a result, the ground state of Hc can be a collection of disjoint cycles rather than a single Hamiltonian cycle. Since QAOA minimizes Hc, the reported 'optimal' routes need not be valid TSP/VRP solutions, and the solution-cost comparisons in Fig. 4 do not establish that the quantum routine solves the declared problem. This issue is load-bearing and must be fixed by adding proper subtour-elimination penalties, or by changing the encoding, and then rerunning the experiments.","section":"Section III-A and Conclusion"},{"comment":"The paper's headline claim concerns a 13-node, 5-vehicle VRP, but the only 13-node results presented are the resource counts in Tables III and IV. The text states, 'We plan to include results for the 13 node partitions in our final draft,' which means the central feasibility claim—that this VRP can be solved with the proposed hybrid method—is not supported by any submitted result. Similarly, Section III-B reports that for the amplitude encoding the expectation value could not be reconstructed, so the abstract's statement that the method is demonstrated on amplitude encoding is not supported. The authors should either provide these missing results or substantially narrow the claims.","section":"Section II-B and IV"},{"comment":"The validity of PLD rests on the assumption that partitioning the VRP into independent TSPs preserves enough of the optimal solution space, but this is not established. The authors acknowledge in Section IV that 'It is not obvious how to most efficiently partition the graph in a way that does not eliminate possible high quality solutions,' and Section III-A attributes the n=7 failure to graph partitioning. Without an analysis of the cost gap introduced by METIS partitions, or at least a systematic empirical study over multiple instances, the claim that the decomposition yields 'satisfactory results' is unsupported. The n=8 and n=9 cases where the quantum/PLD solution beats OR-Tools may reflect the partition chosen rather than the quantum optimization, and this ambiguity needs to be resolved.","section":"Section II-E and III-A"},{"comment":"The circuit-cutting pipeline reconstructs only the expectation value of the cost operator, not a solution eigenstate, as stated in Section II-E. The paper then presents solution costs and route frequencies in Section III-A. An expectation value over a reconstructed density matrix does not necessarily correspond to any feasible VRP route, especially when the cost operator is the incomplete QUBO from Eq. (9). The reported observation that valid paths appeared only 'a handful of times' in 100,000 shots further suggests the output distribution is not concentrated on valid routes. The authors should clarify exactly how the costs in Fig. 4 were computed and provide evidence that the reconstructed quantities correspond to feasible route costs.","section":"Section II-E and III-A"}],"minor_comments":[{"comment":"The product notation 'pY p=0' is confusing and the index/appearance of p is not standard; the expression should be rewritten as a product over the QAOA layers, e.g., U(γ,β) = Π_{i=1}^{p} e^{-iγ_i H_c} e^{-iβ_i H_d} followed by the initial Hadamard layer.","section":"Table V caption"},{"comment":"The caption says '10.2 is the original seven node, two vehicle VRP' but the instance is a ten-node VRP; the text should say ten-node.","section":"Conclusion"},{"comment":"The conclusion states that the 13-node instance is reduced to circuits with 'a depth of only 55 gates,' but Tables III and IV report maximum depths of 18/45 before cutting and 10/25 after cutting for the 13-node partitions; the number 55 appears to be a typo and should be reconciled.","section":"Section II-A"},{"comment":"Equation (2) sums over i,j ∈ {1,...,n} but the depot is node 0 and later equations use 0; the indexing should be made consistent throughout the formulation.","section":"Section III-A"},{"comment":"The experimental setup for OR-Tools is not described: no time limit, solver parameters, or termination criteria are given, so the comparison in Fig. 4 is not reproducible. Please provide this information.","section":"Section III-A"}],"recommendation":"major_revision","confidential_remarks":"The manuscript appears to be an early-stage work-in-progress: the 13-node results are explicitly deferred, the amplitude-encoding section is incomplete, and there is an unresolved mismatch between the stated MTZ formulation and the QUBO actually used. I did not see signs of deliberate misrepresentation—the limitations are honestly disclosed—but the current text is not publishable as a complete research paper. If the authors can supply the missing results and correct the QUBO, the resource-reduction portion of the paper could become a useful contribution. If those results cannot be provided, the appropriate outcome would be rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things. The resource-reduction numbers in Tables III and IV are real arithmetic: cutting a 156-qubit VRP down to 6-qubit subcircuits is exactly what the tables show, and those reductions are definitional consequences of the decomposition. But the central feasibility claim rests on a broken cost function. Eq. 9 is labeled MTZ yet contains only the degree constraints, not the subtour-elimination inequalities. The ground state of that Hamiltonian can be a set of disjoint cycles, so QAOA is minimizing a cycle cover, not a TSP/VRP. The authors even report valid paths appearing only a handful of times in 100,000 shots; that is precisely what a subtour-permissive landscape looks like.\n\nWhat the paper does well: the two-level decomposition is a sensible engineering composition of METIS, QUBO/QAOA, and circuit cutting, and the paper is transparent about its limits—it flags the unresolved partitioning question, admits the amplitude-encoding experiment did not reconstruct the expectation value, and explicitly defers the 13-node cost results. The resource tables are internally consistent and would be reproducible if code were released.\n\nSoft spots, in proportion. The missing subtour constraint is load-bearing; the n=7 case already shows a partitioning failure, and the n=8/n=9 solution-quality claims have no error bars and no described OR-Tools baseline. No code or data accompany the paper. The abstract's 'quantum utility' phrasing is far beyond what simulated p=1 QAOA on a decomposed proxy can support.\n\nWho it is for: someone tracking circuit-cutting pipelines might take away the resource-reduction numbers, but as a demonstration of solving VRPs it does not hold up. I would not desk-reject it outright—the errors are identifiable and fixable, and a referee's report could redirect the paper toward a defensible engineering note. But the claim in the abstract, as written, is not supported. I'd send it back for major revision with explicit instructions to fix the Hamiltonian, run the deferred 13-node comparison, and present error bars.","headline":"Resource reductions check out, but Eq. 9 omits MTZ subtour constraints, so QAOA solves a cycle cover rather than the declared VRP; the abstract's feasibility claim fails.","tokens_in":13147,"tokens_out":3778,"would_cite":false,"duration_ms":44554,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68","90C27"],"pacs":["03.67.-a","03.67.Ac"],"model":"deepseek-v4-flash","headline":"A two-level quantum-classical decomposition solves a 13-node, 5-vehicle routing problem—normally 156 qubits—with subcircuits of at most 6 qubits and depth 25, at costs comparable to classical heuristics.","keywords":["vehicle routing problem","quantum approximate optimization algorithm","circuit cutting","circuit knitting","graph partitioning","traveling salesman problem","QUBO encoding","amplitude encoding"],"falsifier":"Take a small VRP with a known optimal solution, run the PLD pipeline with the same K, and ask whether the optimal route's node assignment appears in any METIS partition; if the best summed TSP cost over those partitions is measurably above the true optimum, the decomposition's central feasibility claim fails.","tokens_in":12076,"feed_emoji":"🚚","tokens_out":13593,"duration_ms":142212,"temperature":0.7,"pith_summary":"The paper tries to establish that large Vehicle Routing Problems, which need too many qubits for near-term quantum computers in their standard encoding, can be solved by cutting them into smaller pieces at two levels. First, a graph partitioner splits the VRP into independent single-vehicle Traveling Salesman Problems; second, each TSP's QAOA circuit is cut into subcircuits whose expectation values are stitched back together classically. For a 13-node, 5-vehicle instance, the original 156-qubit, depth-534, 3432-two-qubit-gate circuit is reduced to subcircuits of at most 6 qubits, depth 25, and 16 two-qubit gates. The authors report that 5 of 6 tested TSP partitions matched brute-force optima, and that total route costs beat Google OR-Tools on 8- and 9-node instances while losing on their 7-node case, a failure they attribute to partitioning. If the claim holds, current small QPUs can approach VRPs previously out of reach for quantum simulators, which the authors call early evidence of quantum utility.","feed_headline":"Two-step cut shrinks 156-qubit routing problem to 6 qubits","feed_subtitle":"A 96% qubit cut and 99.5% fewer two-qubit gates, with route costs competitive with OR-Tools.","key_machinery":"The central mechanism is the two-level decomposition itself. Problem-Level Decomposition removes the depot node, uses the METIS graph partitioner to divide the remaining nodes into K connected subgraphs (one per vehicle), and reattaches the depot to each subgraph, turning the VRP into K independent TSPs. Circuit-Level Decomposition then takes each TSP's QAOA circuit, maps it through Qiskit's circuit-cutting add-on based on the CutQC method, splits it into fragments, runs each fragment separately, and reconstructs the expectation value of the cost Hamiltonian by classical knitting. The paper also contrasts two encodings: the standard QUBO edge encoding, where each edge is one qubit, and a newer amplitude encoding, where edges are basis states and far fewer qubits are needed but circuit depth is much higher.","core_discovery":"On the paper's own terms, the discovery is that a hybrid two-level decomposition makes a 13-node VRP with five vehicles—encoded with one qubit per edge, 156 qubits total—executable as a set of much smaller quantum circuits without sacrificing solution quality versus classical heuristics. Combining METIS problem-level partitioning with circuit-level cutting of a QAOA ansatz, the largest required subcircuit has 6 qubits, 25 layers of depth, and 16 two-qubit gates; this is a 96% cut in qubits, 95% in depth, and 99.5% in two-qubit gates relative to the full circuit. Five of the six small TSP instances produced by partitioning matched the brute-force optimum, and for the 8- and 9-node VRPs the summed decomposed cost was lower than Google OR-Tools' solution, while the 7-node case favored OR-Tools. The authors present this as evidence that VRPs previously too complex for quantum simulators are now within reach, with the caveat that the amplitude encoding, despite needing fewer qubits, could not be knitted back together with current tools.","pith_inferences":["The paper's own 7-node counterexample and its stated uncertainty about METIS partitioning imply that the method's practical reach will be set by the partitioner; replacing minimum-edge-cut with a cost- and hardware-aware partitioning criterion is the natural next step.","Because the paper had to drop QAOA from ten layers to one to keep the knitting overhead manageable, the resource-reduction numbers and the utility claim come from shallow circuits; deeper ansätze would require the circuit-knitting overhead reductions the authors cite as ongoing work.","The manuscript explicitly defers route-level results for the 13-node partitions to a later draft, so the headline 'too complex for simulators' claim at that size rests on resource counts plus a statement that the optimal route appeared rarely among 100,000 shots; readers should look for the completed route table before treating the 13-node demonstration as fully shown."],"forward_implications":["A 13-node, five-vehicle VRP that needs 156 qubits and a depth-534 circuit can be run as subcircuits of 6 qubits, depth 25, and 16 two-qubit gates, so any current small QPU or simulator can attempt instances previously blocked by width.","If the partition preserves good routes, the same recipe applies to any VRP variant expressible as a QUBO: decompose by vehicle, solve each TSP with QAOA, cut the circuits, and sum the TSP costs.","The reported 5-of-6 TSP partitions matching brute force suggests decomposition does not always destroy solution quality on small instances; on 8- and 9-node VRPs the hybrid solution beat OR-Tools, so the method can be competitive with classical heuristics.","Because the amplitude encoding cuts qubits further (10-node VRP partitions to 4-5 qubits before cutting), progress in circuit-knitting overhead and depth cutting would directly extend this approach to qubit-frugal encodings."],"supporting_citations":[{"why":"Supplies the Miller-Tucker-Zemlin formulation whose objective and constraints become the QUBO cost function.","marker":"[9]"},{"why":"Defines QAOA, the variational algorithm whose ansatz and driver Hamiltonian are used for every TSP.","marker":"[28]"},{"why":"Provides CutQC, the circuit-cutting and knitting method underlying Circuit-Level Decomposition.","marker":"[33]"},{"why":"Gives the standard QUBO-to-Ising mapping used for the edge encoding of each TSP.","marker":"[34]"},{"why":"Defines the amplitude encoding of the TSP used as the qubit-frugal alternative.","marker":"[35]"},{"why":"METIS is the graph partitioner that performs Problem-Level Decomposition into TSPs.","marker":"[37]"},{"why":"Qiskit Aer is the noiseless simulator on which all circuits were executed.","marker":"[42]"},{"why":"Qiskit Addon Cutting is the implementation of circuit cutting used to generate and reconstruct subcircuits.","marker":"[43]"}],"fun_headline_variants":["Quantum VRP solved with 6-qubit pieces after 96% qubit cut","Hybrid cut makes 156-qubit routing fit on 6 qubits","Decompose to conquer: quantum routing drops to 6 qubits","QAOA VRP decomposed: 99.5% fewer gates, still beats OR-Tools","Hybrid decomposition shrinks quantum routing from 156 to 6 qubits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that splitting the full VRP graph into independent single-vehicle TSPs with METIS keeps at least one high-quality route intact; the authors explicitly say it is not obvious how to partition without discarding good solutions, point to the 7-node case as a partition-related failure, and defer route-level results for the 13-node instance to a later draft.","fun_headline_variants_meta":{"raw":{"variants":["Quantum VRP solved with 6-qubit pieces after 96% qubit cut","Hybrid cut makes 156-qubit routing fit on 6 qubits","Decompose to conquer: quantum routing drops to 6 qubits","QAOA VRP decomposed: 99.5% fewer gates, still beats OR-Tools","Hybrid decomposition shrinks quantum routing from 156 to 6 qubits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000626,"raw_usage":{"total_tokens":2887,"prompt_tokens":924,"completion_tokens":1963,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":1857}},"tokens_in":540,"tokens_out":1963,"duration_ms":16773,"temperature":1.0,"reasoning_tokens":1857,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:28:07.758593+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small VRP with a known optimal solution, run the PLD pipeline with the same K, and ask whether the optimal route's node assignment appears in any METIS partition; if the best summed TSP cost over those partitions is measurably above the true optimum, the decomposition's central feasibility claim fails.","supporting_citations":[{"cited_title":"Integer programming formulation of traveling salesman problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the Miller-Tucker-Zemlin formulation whose objective and constraints become the QUBO cost function."},{"cited_title":"Cutqc: using small quantum computers for large quantum circuit evaluations,","cited_arxiv_id":null,"evidence_quote":"Provides CutQC, the circuit-cutting and knitting method underlying Circuit-Level Decomposition."},{"cited_title":"Efficient encoding of the traveling salesperson problem on a quantum computer,","cited_arxiv_id":null,"evidence_quote":"Defines the amplitude encoding of the TSP used as the qubit-frugal alternative."},{"cited_title":"[Online]","cited_arxiv_id":null,"evidence_quote":"METIS is the graph partitioner that performs Problem-Level Decomposition into TSPs."}],"review_version":1}