Pith. sign in

REVIEW 3 major objections 5 minor 35 references

Feasibility-Preserving Quantum Search for Constrained Transportation Routing

T0 review · 3 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Pith's one-line read A column-wise swap mixer keeps quantum routing search inside the feasible solution space, and on small TSP and VRP instances that architectural choice determines how much probability lands on usable low-cost routes.

desk verdict The central feasibility-preservation theorem is false: the inter-vehicle XY term swaps a single customer bit, not the whole column, so the proposed QAOA+ mixer can leak into two-customers-per-position states. read the letter →

arxiv 2608.05394 v1 pith:3AT7IAIS submitted 2026-08-05 quant-ph

classification quant-ph
keywords VehicleRoutingProblemTravelingSalespersonConstrainedoptimizationQuantumAlternatingOperatorAnsatzFeasibility-preservingmixerQUBO
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that for constrained transportation routing, feasibility can be built into quantum search instead of only patched on with penalty terms. It introduces a column-wise swap mixer for the Quantum Alternating Operator Ansatz, QAOA+, and proves in Proposition 1 that this mixer never moves a feasible route assignment into an assignment-infeasible one. On small TSP and VRP instances, it compares penalty-based QUBO-QAOA with penalty-free QAOA+ and a hybrid version; the mixer-based variants concentrate more sampled probability on feasible low-cost routes. If the claim holds, constraint handling in near-term quantum optimization becomes a question of designing admissible transitions, not of calibrating penalties.

What carries the argument

The load-bearing object is the column-wise swap mixer $U_M = U_{\mathrm{search}}(\beta)\,U_{\mathrm{jump}}(\pi/4)$, assembled from two-qubit XY-exchange terms $X_p X_q + Y_p Y_q$ acting on the vehicle–position–customer encoding. A column is a route-position block in one vehicle's assignment table, and a swap exchanges customer assignments either within a vehicle (resequencing a route) or across vehicles (reassigning customers). On basis states, an XY term sends $|01\rangle \leftrightarrow |10\rangle$ and vanishes on $|00\rangle$ and $|11\rangle$, so the mixer only pivots between assignments that differ by exchanging two one-hot entries. The proof of Proposition 1 relies on this support property to conclude that both the full-swap jumper and the partial-swap search ingredient preserve the one-hot and customer-count constraints, and therefore preserve $\mathcal{H}_F$.

What would settle it

Enumerate all feasible basis states for the paper's two-vehicle, three-customer, three-position encoding, apply $U_{\mathrm{jump}}(\pi/4)$ and $U_{\mathrm{search}}(\beta)$ to each, and check whether any output state has a vehicle with two customers in the same position; one such transition falsifies Proposition 1 under the at-most-one-hot encoding used in the experiments.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that feasibility can be made a property of the search operator rather than the objective. Under a vehicle–position–customer bit encoding, the proposed column-wise swap mixer is built from XY-exchange couplings; it has a jumper component that performs full column swaps at a fixed $\pi/4$ angle and a search component that performs partial swaps with a tunable angle. Proposition 1 asserts that both components map the feasible Hilbert space into itself, so a QAOA+ circuit that starts in a feasible state never acquires amplitude on assignment-infeasible states. The numerical comparison on small instances then shows that this architectural choice changes sampling behavior: QUBO-QAOA spreads probability over feasible and infeasible high-energy states, while QAOA+ and Hybrid QAOA+ concentrate more mass on feasible low-cost routes. The paper presents the difference between the TSP result, where the hybrid's added penalty guidance concentrates probability near the optimum, and the VRP result, where penalty-free QAOA+ preserves exploration and reaches the optimum at both tested depths.

Load-bearing premise

The guarantee rests on the assumption that every elementary XY swap sends every feasible assignment to another feasible assignment, where the proof uses exactly-one-hot states even though the experiments run on at-most-one-hot blocks with empty positions allowed.

Editorial extensions

If this is right

  • A QAOA+ run initialized in a feasible superposition keeps zero amplitude on assignment-infeasible route configurations, eliminating the need for assignment penalties in the mixer-based variants.
  • On the tested small instances, penalty-based QUBO-QAOA spends a large part of its measurement shots on infeasible states; the mixer-based variants obtain substantially higher feasible-route sampling fractions.
  • In the compact TSP feasible space, adding a small penalty guidance to the feasibility-preserving mixer concentrates about 45% of sampled probability within 5% of the optimum at depth $p=2$.
  • In the multi-vehicle VRP instance, penalty-free QAOA+ finds the optimal cost 30.0 at both $p=2$ and $p=3$, whereas deeper hybrid penalty guidance converges to a suboptimal feasible route at cost 33.0.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Since the proof's feasible set is defined with exactly one customer per position while the experiments use at-most-one-hot blocks with empty slots, a natural extension is to carry the invariance argument through the at-most-one-hot case; the paper leaves that derivation to follow-up work.
  • The TSP/VRP reversal suggests a design rule the authors do not state: for compact, symmetric feasible regions use mild penalty guidance, and for multi-vehicle decomposable regions prefer pure mixer feasibility preservation.
  • A testable next step is to add capacity or time-window constraints and define the allowed swap set so both resulting routes remain resource-feasible; this would test whether the mechanism extends beyond one-hot structure.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes a quantum alternating operator ansatz (QAOA+) framework for TSP and VRP in which feasibility is enforced by a custom 'column-wise swap' mixer rather than by QUBO penalty terms alone. The authors introduce a jumper mixer (full XY swaps) and a search mixer (partial XY swaps), and they compare three architectures—penalty-based QUBO-QAOA, penalty-free QAOA+, and Hybrid QAOA+—on small instances using a classical simulator. The central theoretical claim is Proposition 1: the column-wise swap mixer preserves the feasible Hilbert space H_F. I find that the proof of Proposition 1 is incorrect, and the formal definition of the feasible set conflicts with the encoding used in the experiments; these are load-bearing defects that invalidate the paper's main claim as stated.

Significance. If Proposition 1 were correct, the paper would make a useful methodological contribution by transferring feasibility-preserving neighborhood logic from classical routing heuristics into quantum mixer design, and the controlled comparison of three constraint-handling architectures would be a valuable empirical reference. The paper is clearly written, the experimental setup is transparent, and the authors are appropriately cautious about scalability claims. However, the central feasibility-preservation guarantee fails under the paper's own definitions, and the numerical results therefore do not provide evidence for the claimed architectural benefit. The core idea may be salvageable with a redesigned mixer, but the present manuscript does not establish it.

major comments (3)
  1. [§3.5, Proposition 1 proof, Eqs. (18) and (19)] Part (i) of the proof is incorrect. The inter-vehicle term of H_jump couples the same customer index c across two vehicles at the same position k: X_{a1,c,k}X_{a2,c,k} + Y_{a1,c,k}Y_{a2,c,k}. On a feasible basis state in which vehicle a1 has customer c at position k and vehicle a2 has a different customer c' at the same position, this term acts on the two c-qubits as |10> -> 2|01>, producing a state in which vehicle a2 contains both c and c' at position k. This violates the one-hot constraint sum_c x_{a2,c,k} = 1, even under the exact-one-hot definition used in Proposition 1. The assertion that each g_pq maps feasible basis states to feasible basis states is therefore false, and the power-series argument for U_jump does not go through. Leakage occurs for the very inter-vehicle moves that the mixer is designed to permit.
  2. [§3.5, definition of Ω_F, vs. §3.3 encoding] The formal feasible set Ω_F requires sum_c x_{a,c,k} = 1 for every vehicle-position pair (a,k), i.e., exactly one customer per position. Section 3.3, however, explicitly defines the block encoding as at-most-one-hot, with the all-zero block representing an unused route position. For the VRP instance used in Section 4 (|A|=2, K=3, |C|=3), there are 6 vehicle-position slots but only 3 customers, so no bitstring can satisfy the exact-one-hot condition; Ω_F is empty. This makes the formal feasibility-preservation claim vacuous under its own definition, while the numerical experiments and the notion of 'feasible routes' in Section 3.6 rely on a different, at-most-one-hot feasibility notion that is never formalized. The inconsistency is load-bearing because Proposition 1 is stated for an empty subspace.
  3. [§3.5, Eq. (20) and Proposition 1 part (ii)] Part (ii) is circular. N_local is defined as the set of index pairs whose exchange preserves the one-hot and permutation constraints, so H_search is feasibility-preserving by construction; the proof merely restates the definition. The substantive claim therefore rests entirely on the jumper mixer, whose proof fails as noted in the first comment. Moreover, if Ω_F is empty, the condition 'exchanging ... in any feasible assignment yields another feasible assignment' is vacuously satisfied by all pairs, making N_local ill-defined with respect to the actual encoding used in the experiments.
minor comments (5)
  1. [Abstract] The sentence 'using column-wise swap moves, it restricts evolution to feasible configurations' is a comma splice; it should be rephrased, e.g., 'which restricts evolution to feasible configurations.'
  2. [§3.3] The text introduces the binary variable as x_{a,i,k} but the rest of the paper uses x_{a,c,k}; the index naming should be made consistent.
  3. [Table 6] For TSP QAOA+ at p=3, the table reports 'Failed*' for the cost ratio but also reports a near-optimal sampling probability of 0.011; the footnote should clarify under what decoding rule a run can be 'failed' while still producing near-optimal samples.
  4. [References] The reference to Hansen and Mladenović is missing the character 'ć' in the author name and the title of the 2001 work is incomplete.
  5. [§3.7, Table 5] The penalty weight λ1 is set to 60 for QUBO, 5 for Hybrid QAOA+, and 0 for QAOA+, but the text does not justify the factor-of-12 difference between QUBO and Hybrid; adding a sentence on how these values were calibrated would improve reproducibility.

Circularity Check

1 steps flagged · score 4.0 of 10

The search-mixer half of Proposition 1 is definitional: H_search is restricted to N_local, which is defined as the set of swaps that preserve feasibility, so the proof restates the construction rather than deriving a guarantee; the jumper-mixer half is non-circular but its proof fails for inter-vehicle swaps.

  1. self definitional [Section 3.5, Eqs. (20)-(21), Proposition 1 proof part (ii)]
    "By definition, N_local contains only index pairs (i, j) such that exchanging the corresponding assignment variables yields another feasible assignment. Each term in H_search therefore generates partial swaps between two assignment variables whose exchange preserves feasibility."

    The claimed feasibility preservation of U_search is not derived from any independent property; it is immediate from the definition of N_local as exactly the set of feasible swaps. The proof of Proposition 1(ii) restates the construction: H_search is built only from pairs whose exchange already preserves the one-hot and permutation constraints, so H_search H_F ⊆ H_F and U_search H_F ⊆ H_F hold by definition. Thus the search-mixer guarantee is an input to the construction, not an independently proven result. The non-circular part of the central claim, preservation under U_jump, is not rescued by this definitional step.

full rationale

The derivation has two independent mixer components. The search mixer proof is tautological: N_local is defined as the set of swaps that preserve feasibility, so Proposition 1(ii) merely restates the construction rather than proving a substantive guarantee. This is a genuine self-definitional step, but it is only half of the central claim. The jumper mixer preservation claim is not circular; it is a substantive claim about all same-position XY couplings. That substantive claim is, however, false as written for inter-vehicle couplings: swapping the same customer qubit between two occupied vehicle-position columns can leave one column empty and the other doubly occupied, so the one-hot constraint is violated. In addition, the formal feasible set Ω_F uses an exactly-one-hot condition per vehicle-position slot, while Section 3.3 adopts an at-most-one-hot encoding with empty slots, and for the 2-vehicle, 3-customer VRP instance Ω_F is empty. These are correctness gaps, not additional circularity. The numerical comparison is benchmarked against Gurobi classical optima and QUBO-QAOA baselines and does not fit the theoretical feasibility claim, so the empirical portion is not circular. Overall, the paper has partial circularity in one of the two mixer proofs, while the independent part fails on other grounds.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

No new physical entities are introduced. The jumper and search mixers are algorithmic operators, not postulated objects with external falsifiable handles.

free parameters (4)
  • lambda_1 (assignment penalty weight) = QUBO: 60; Hybrid: 5; QAOA+: 0
    Hand-selected from max-cost normalization (c_max) to balance feasibility enforcement and search flexibility; not derived and no sensitivity analysis is reported.
  • lambda_2 (contiguity penalty weight) = 15
    Calibrated from the mean cost c_bar approximately 6.8; not derived from first principles and no sensitivity study is provided.
  • jumper rotation angle = pi/4
    Fixed to perform deterministic swaps between feasible configurations; chosen rather than optimized and not justified by an independent principle.
  • circuit depth p = 2, 3
    Selected to keep depth NISQ-compatible and to allow both intra- and inter-vehicle swaps; only two values are tested, not a scan.
assumptions (5)
  • standard math The DFJ MIP formulations for TSP and VRP (Eqs 1-12) correctly describe the classical problems and the Gurobi optima are valid.
    Used as benchmark in Sections 3.2 and 3.7; standard routing formulation.
  • domain assumption The vehicle-position-customer encoding with at-most-one-hot blocks represents all feasible routes and can be mapped to qubits.
    Section 3.3 uses at-most-one-hot to allow empty positions; this is a modeling choice.
  • ad hoc to paper Proposition 1 defines feasible configurations with exactly one-hot per vehicle-position rather than at-most-one-hot.
    Section 3.5 defines Omega_F with sum_c x = 1 for all a,k, which contradicts the encoding and makes the feasible set empty for the VRP instance.
  • ad hoc to paper Each XY term in Eq 18 preserves the one-hot and permutation constraints independently.
    The proof of Proposition 1 treats each g_pq term as mapping feasible basis states to feasible basis states, which is false for inter-vehicle swaps when the receiving vehicle already has a customer at that position.
  • ad hoc to paper N_local contains only index pairs whose exchange preserves feasibility, making H_search feasibility-preserving by construction.
    The search mixer guarantee is definitional rather than derived, as stated around Eq 20.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Feasibility-Preserving Quantum Search for Constrained Transportation Routing." pith.science (2026). https://pith.science/paper/3AT7IAIS

@misc{pith2026260805394,
  author       = {Pith},
  title        = {Pith review of: Feasibility-Preserving Quantum Search for Constrained Transportation Routing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3AT7IAIS}},
  note         = {Machine review of arXiv:2608.05394}
}
read the original abstract

Transportation routing problems such as the Traveling Salesperson Problem (TSP) and the Vehicle Routing Problem (VRP) are characterized by strict feasibility requirements involving customer assignment and visit rules, route sequencing, and depot-return logic alongside cost minimization. Most quantum routing formulations adopt Quadratic Unconstrained Binary Optimization (QUBO) encodings, where feasibility is incorporated indirectly via penalty terms in the cost Hamiltonian. While convenient for standard implementations of the Quantum Approximate Optimization Algorithm (QAOA), QUBO encodings allow the quantum search dynamics to allocate substantial probability to infeasible route configurations. This study develops a transportation-grounded constraint-aware Quantum Alternating Operator Ansatz (QAOA+) framework that embeds feasibility-preserving logic directly into the search operator. We introduce a custom mixer that functions as a quantum analogue of feasibility-preserving routing neighborhoods, using column-wise swap moves, it restricts evolution to feasible configurations while enabling structured exploration of valid routes. We compare three constraint-handling architectures: penalty-based QUBO QAOA, penalty free QAOA+ with the feasibility-preserving mixer, and a Hybrid QAOA+ combining mixer based feasibility with and penalty guidance. Results on small TSP and VRP instances show that constraint-handling architecture strongly influences feasible-route sampling, convergence behavior, and probability concentration over low-cost feasible routes. These findings position constraint-aware quantum search as a methodological extension of transportation routing search approaches, where feasibility is enforced through admissible quantum transitions rather than post-hoc penalties.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 17 canonical work pages

  1. [4]

    https://doi.org/10.3389/fict.2017.00029 28 Nielsen, M., Chuang, I.,

  2. [5]

    Journal of Quantum Computing 6, 25–51

    IQAOA for Two Routing Problems: A Methodological Contribution with Application to TSP and VRP. Journal of Quantum Computing 6, 25–51. https://doi.org/10.32604/jqc.2024.048792 Cattelan, M., Yarkoni, S.,

  3. [11]

    https://doi.org/10.1038/s41598-024-76967-w Fuchs, F.G., Lye, K.O., Nilsen, H.M., Stasik, A.J., Sartor, G.,

  4. [12]

    https://doi.org/10.3390/a12020034 Hansen, P., Mladenovi, N.,

  5. [13]

    https://doi.org/10.1038/s41598-023-38787-2 Farhi, E., Goldstone, J., Gutmann, S.,

  6. [14]

    Ștefan, Leon, F.,

    https://doi.org/10.1038/s41598-024-70649-3 Curuliuc, C. Ștefan, Leon, F.,

  7. [15]

    https://doi.org/10.3390/a15060202 Glover, F., Kochenberger, G., Du, Y.,

  8. [16]

    https://doi.org/10.3390/app16041690 Dantzig, G., Fulkerson, R., Johnson, S.,

Show all 35 references
  1. [17]

    Quantum bridge analytics I: a tutorial on formulating and using QUBO models. Ann. Oper. Res. 314, 141–183. https://doi.org/10.1007/s10479- 022-04634-2 Glover, F., Laguna, M., Martí, R.,

  2. [20]

    Ising formulations of many NP problems. Front. Phys. 2, 1–14. https://doi.org/10.3389/fphy.2014.00005 Mahmoudi, M., Zhou, X.,

  3. [21]

    Transportation Research Part B: Methodological 89, 19–42

    Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space- time network representations. Transportation Research Part B: Methodological 89, 19–42. https://doi.org/10.1016/j.trb...

  4. [25]

    Transportation Research Part B: Methodological 100, 115–137

    A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transportation Research Part B: Methodological 100, 115–137. https://doi.org/10.1016/j.trb.2017.02.003 Paradiso, R., Roberti, R., Ulmer, M.,

  5. [26]

    https://doi.org/10.1016/j.trb.2024.103137 Schumacher, B.,

  6. [27]

    arXiv preprint arXiv:2501.03194+

    Shots and variance on noisy quantum circuits. arXiv preprint arXiv:2501.03194+. Sidorov, K., Morozov, A.,

  7. [28]

    arXiv preprint arXiv:2105.10950

    A review of approaches to modeling applied vehicle routing problems. arXiv preprint arXiv:2105.10950. Symons, B.C.B., Galvin, D., Sahin, E., Alexandrov, V., Mensa, S.,

  8. [30]

    https://doi.org/10.3390/app112110295 Wu, Z., Yaman, H.,

  9. [32]

    Transportation Research Part B: Methodological

    A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones. Transportation Research Part B: Methodological. https://doi.org/10.1016/j.trb.2023.03.003 Yao, Y., Zhu, X., Dong, H., Wu, S., Wu, H., Carol Tong, L., Zhou, X.,

  10. [33]

    Transportation Research Part B: Methodological 129, 156–174

    ADMM-based problem decomposition scheme for vehicle routing problem with time windows. Transportation Research Part B: Methodological 129, 156–174. https://doi.org/10.1016/j.trb.2019.09.009 Zhou, H., Qin, H., Cheng, C., Rousseau, L.M.,

  11. [34]

    Transportation Research Part B: Methodological 168, 124–150

    An exact algorithm for the two-echelon vehicle routing problem with drones. Transportation Research Part B: Methodological 168, 124–150. https://doi.org/10.1016/j.trb.2023.01.002 Zhuang, Y., Azfar, T., Wang, Y., Sun, W., Wang, X., Guo, Q., Ke, R.,

  12. [35]

    Chain 1, 138–149

    Quantum Computing in Intelligent Transportation Systems: A Survey. Chain 1, 138–149. https://doi.org/10.23919/chain.2024.000007

  13. [56]

    https://doi.org/10.1088/1751-8121/ad00f0 Tan, S.Y., Yeh, W.C.,

  14. [192]

    https://doi.org/10.1016/j.trb.2024.103149 Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E.G., Venturelli, D., Biswas, R.,

  15. [198]

    https://doi.org/10.1016/j.trb.2025.103234 Neukart, F., Compostella, G., Seidel, C., von Dollen, D., Yarkoni, S., Parney, B.,

  16. [200]

    https://doi.org/10.1016/j.trb.2025.103314 Xia, Y., Zeng, W., Zhang, C., Yang, H.,

  17. [1981]

    Networks 11, 221–227

    Complexity of vehicle routing and scheduling problems. Networks 11, 221–227. https://doi.org/10.1002/net.3230110211 Lucas, A.,

  18. [2014]

    arXiv preprint arXiv:1411.4028

    A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1411.4028. Feynman, R.P.,

  19. [2016]

    Finding approximate solutions of NP-hard optimization and TSP problems using elephant search algorithm. J. Supercomput. 72, 3960–3992. https://doi.org/10.1007/s11227-016-1739-2 Dixit, V. V., Niu, C.,

  20. [2017]

    Transportation Research Part B: Methodological 95, 169–195

    Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological 95, 169–195. https://doi.org/10.1016/j.trb.2016.10.013 Karp, R.M.,

  21. [2018]

    arXiv preprint arXiv:1811.11538

    Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models. arXiv preprint arXiv:1811.11538. 27 Glover, F., Kochenberger, G., Hennig, R., Du, Y.,

  22. [2019]

    arXiv:1905.12134

    Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth. arXiv:1905.12134. Ozbaygin, G., Ekin Karasan, O., Savelsbergh, M., Yaman, H.,

  23. [2021]

    Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nat. Phys. 17, 332–336. https://doi.org/10.1038/s41567-020-01105-y Huang, Y., Zhao, L., Van Woensel, T., Gross, J.P.,

  24. [2022]

    Springer, pp

    Penalty Weights in QUBO Formulations: Permutation Problems, in: Evolutionary Computation InCombinatorial Optimization: 22nd European Conferenc. Springer, pp. 159–174. https://doi.org/10.1007/978-3-031-04148-8_11 Azad, U., Behera, B.K., Ahmed, E.A., Panigrahi, P.K., Farouk, A.,

  25. [2023]

    IEEE Transactions on Intelligent Transportation Systems 24, 7564–7573

    Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm. IEEE Transactions on Intelligent Transportation Systems 24, 7564–7573. https://doi.org/10.1109/TITS.2022.3172241 Borndörfer, R., Grötschel, M., Löbel, A.,

  26. [2024]

    A review of recent advances in time- dependent vehicle routing. Eur. J. Oper. Res. https://doi.org/10.1016/j.ejor.2024.06.016 Ayodele, M.,

  27. [2025]

    arXiv:2505.01214

    A Warm-start QAOA based approach using a swap- based mixer for the TSP: theoretical considerations, implementation and experiments. arXiv:2505.01214. Bourreau, E., Fleury, G., Lacomme, P.,

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.