pith. sign in

arxiv: 2606.11383 · v1 · pith:JF7QXKQYnew · submitted 2026-06-09 · 🪐 quant-ph

Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

Ji\v{r}\'i Guth Jarkovsk\'y , Patricia Bickert , Elisabeth Wybo , Martin Leib This is my paper

Pith reviewed 2026-06-27 13:05 UTC · model grok-4.3

classification 🪐 quant-ph
keywords rolling stock planningquantum approximate optimization algorithmmaximum weight independent sethybrid quantum-classical algorithmrailway optimizationdivide-and-conquer
0
0 comments X

The pith

A hybrid divide-and-conquer solver using QAOA finds higher-quality rolling stock plans as subgraph size grows.

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

The paper reformulates rolling stock planning for 190 trips over two days, including mandatory maintenance stops, as a maximum-weight independent set problem on a graph whose nodes are feasible train cycles. It introduces a hybrid algorithm that repeatedly extracts subgraphs from this graph and solves the subproblem either with exact classical methods or with the Quantum Approximate Optimization Algorithm. Experiments compare these solvers and track how solution quality changes when the subgraph size is increased, both in classical simulation and on the IQM Emerald quantum processor. A sympathetic reader would care because the approach shows a concrete route to handle large constrained scheduling instances that are otherwise intractable.

Core claim

The hybrid framework iteratively selects subgraphs and solves the MWIS problem using QAOA or exact classical methods; solution quality improves as subgraph size is increased, allowing the method to bridge polynomial-time approximate solvers and exponential-time exact methods on the 190-trip instance.

What carries the argument

The hybrid divide-and-conquer algorithm that decomposes the MWIS graph into subgraphs solved by QAOA or classical exact solvers.

If this is right

  • Solution quality scales positively with the size of the subgraphs that are solved exactly or with QAOA.
  • QAOA can be embedded inside an existing classical planning workflow without replacing the entire solver.
  • The same decomposition works when the subgraph solver is swapped between simulation, exact classical code, and real quantum hardware.
  • The gap between fast approximate and slow exact methods narrows as larger subproblems become tractable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same subgraph decomposition could be applied to other transportation scheduling problems that reduce to weighted independent sets.
  • If the subgraph selector itself is made adaptive, the number of expensive exact or quantum calls might drop further.
  • Running the same pipeline on instances with several hundred trips would test whether the observed scaling continues or saturates.

Load-bearing premise

The MWIS formulation on the cycle graph fully encodes every operational constraint without losing feasible solutions or admitting invalid ones.

What would settle it

On the 190-trip instance, increasing subgraph size produces no measurable rise in solution quality or yields plans that violate maintenance or compatibility rules when checked against the original problem data.

Figures

Figures reproduced from arXiv: 2606.11383 by Elisabeth Wybo, Ji\v{r}\'i Guth Jarkovsk\'y, Martin Leib, Patricia Bickert.

Figure 1
Figure 1. Figure 1: Results showing the performance of various methods to solve the subgraph MWIS, with subgraph size kept fixed at 20 (and the greedy algorithm [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Results showing the performance (measured by the number of empty kilometers) of the algorithm using the classical exact MWIS solver, as a function [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
read the original abstract

Rolling stock planning is a complex optimization problem in railway management that involves assigning physical trains to scheduled trips while minimizing operational costs. In this work, we address a specific instance of this problem featuring 190 trips over two days, subject to constraints such as mandatory maintenance stops. We reformulate the problem as a Maximum-Weight Independent Set (MWIS) problem on a graph where nodes represent feasible train cycles. To handle the computational complexity of the large search space, we propose a hybrid divide-and-conquer algorithm. This approach iteratively selects subgraphs and solves the MWIS problem using various solvers, including exact classical methods and the Quantum Approximate Optimization Algorithm (QAOA). We evaluate the algorithm's performance by comparing these methods and analyzing the scaling with respect to subgraph size, with QAOA assessed through both classical simulation and execution on a quantum device (IQM Emerald). Our results indicate that increasing the subgraph size generally improves solution quality, demonstrating that the hybrid framework can effectively bridge the gap between polynomial-time approximate solvers and exponential-time exact methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper reformulates rolling-stock planning (190 trips, maintenance constraints) as a Maximum-Weight Independent Set (MWIS) instance whose nodes are feasible train cycles, then applies a hybrid divide-and-conquer procedure that extracts subgraphs and solves the MWIS subproblems with exact classical methods and with QAOA (simulated and on IQM Emerald hardware). It reports that solution quality improves with subgraph size and concludes that the framework bridges polynomial-time approximate solvers and exponential-time exact methods.

Significance. If the MWIS encoding is shown to be faithful, the work supplies a concrete, hardware-executed demonstration of QAOA on a structured real-world combinatorial problem together with an empirical scaling study on subgraphs; the hybrid divide-and-conquer template itself is reusable for other large MWIS instances.

major comments (2)
  1. [Abstract] Abstract: the claim that nodes are “feasible train cycles” and that the graph “encodes constraints such as mandatory maintenance stops” supplies no explicit construction showing how train compatibility, depot capacity, or time-window constraints are captured by node weights or by the independence condition. Without this mapping, measured improvements on the MWIS instance do not establish validity for the original rolling-stock problem.
  2. [Abstract] Abstract / evaluation section: performance trends versus subgraph size are presented without quantitative error bars, without an explicit statement of how maintenance constraints are encoded in the MWIS formulation, and without a direct baseline comparison against a commercial MIP solver on the identical 190-trip instance.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address each major comment below and indicate the revisions we will undertake.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that nodes are “feasible train cycles” and that the graph “encodes constraints such as mandatory maintenance stops” supplies no explicit construction showing how train compatibility, depot capacity, or time-window constraints are captured by node weights or by the independence condition. Without this mapping, measured improvements on the MWIS instance do not establish validity for the original rolling-stock problem.

    Authors: We acknowledge that the abstract is too concise and does not supply the explicit mapping. The manuscript body (Section 2) defines nodes as feasible cycles that already incorporate maintenance stops and compatibility rules, with weights encoding operational cost and the independence condition enforcing non-overlapping assignments. To address the referee’s concern directly, we will expand the abstract with a short description of this construction and add a clarifying paragraph or small diagram in the main text that shows how the listed constraints map to the MWIS instance. revision: yes

  2. Referee: [Abstract] Abstract / evaluation section: performance trends versus subgraph size are presented without quantitative error bars, without an explicit statement of how maintenance constraints are encoded in the MWIS formulation, and without a direct baseline comparison against a commercial MIP solver on the identical 190-trip instance.

    Authors: We agree that error bars are needed and will recompute and display them for all subgraph-size scaling plots. The explicit encoding statement will be added as noted in the first response. For the MIP baseline, we will include direct comparisons against a commercial solver on the same subgraphs used in the QAOA experiments. On the full 190-trip instance we will add a discussion of why an exact MIP solve is intractable within reasonable time limits and report any feasible bounds or partial solutions obtained; a complete optimal solution for the full instance may remain out of reach, which is precisely why the hybrid approach is proposed. revision: partial

Circularity Check

0 steps flagged

No circularity: solution quality measured by direct external comparison on MWIS instances

full rationale

The paper reformulates rolling-stock planning as MWIS on a cycle graph whose nodes are feasible train cycles, then evaluates QAOA (and classical solvers) on induced subgraphs by comparing output weights against exact solvers on the identical subgraphs. No equation reduces reported quality gains to a fitted parameter, no self-citation supplies a load-bearing uniqueness theorem, and no ansatz is smuggled in. The scaling result is therefore an empirical observation against an independent benchmark rather than a definitional identity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard graph-theoretic modeling of scheduling constraints and on the correctness of the QAOA ansatz; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • domain assumption The rolling-stock constraints can be exactly encoded as conflicts in an MWIS instance on a cycle graph.
    Stated when the problem is reformulated as MWIS.
  • domain assumption QAOA on subgraphs of increasing size produces monotonically improving global solutions when stitched together.
    Implicit in the scaling analysis reported in the abstract.

pith-pipeline@v0.9.1-grok · 5715 in / 1399 out tokens · 20771 ms · 2026-06-27T13:05:33.781653+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 5 canonical work pages

  1. [1]

    Design and application of quantum algorithms for railway optimisation problems,

    C. Grange, “Design and application of quantum algorithms for railway optimisation problems,” Theses, Universit ´e de Montpellier, Jul. 2024. [Online]. Available: https://hal.science/tel-04671228

    2024

  2. [2]

    Optimising rolling stock planning including maintenance with constraint programming and quantum annealing,

    P. Bickert, C. Grozea, R. Hans, M. Koch, C. Riehn, and A. Wolf, “Optimising rolling stock planning including maintenance with constraint programming and quantum annealing,” 2023. [Online]. Available: https://arxiv.org/abs/2109.07212

    arXiv 2023

  3. [3]

    Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing,

    K. Domino, A. Kundu, ¨O. Salehi, and K. Krawiec, “Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing,”Quantum Information Processing, vol. 21, no. 9, p. 337, Sep 2022. [Online]. Available: https://doi.org/10.1007/ s11128-022-03670-y

    2022

  4. [4]

    Quantum annealing in the nisq era: Railway conflict management,

    K. Domino, M. Koniorczyk, K. Krawiec, K. Jałowiecki, S. Deffner, and B. Gardas, “Quantum annealing in the nisq era: Railway conflict management,”Entropy, vol. 25, no. 2, 2023. [Online]. Available: https://www.mdpi.com/1099-4300/25/2/191

    2023

  5. [5]

    Applying the quantum approximate optimization algorithm to the tail-assignment problem,

    P. Vikst ˚al, M. Gr ¨onkvist, M. Svensson, M. Andersson, G. Johansson, and G. Ferrini, “Applying the quantum approximate optimization algorithm to the tail-assignment problem,”Phys. Rev. Appl., vol. 14, p. 034009, Sep 2020. [Online]. Available: https://link.aps.org/doi/10.1103/ PhysRevApplied.14.034009

    2020

  6. [6]

    Optimization of flight routes: Quantum approximate optimization algorithm for the tail assignment problem,

    M. Gili, P. S. Sebastian, and A. Bl ´azquez-Garc´ıa, “Optimization of flight routes: Quantum approximate optimization algorithm for the tail assignment problem,” 2024. [Online]. Available: https: //arxiv.org/abs/2412.12773

    arXiv 2024

  7. [7]

    Missing puzzle pieces in the performance landscape of the quantum approximate optimization algorithm,

    E. Wybo and M. Leib, “Missing puzzle pieces in the performance landscape of the quantum approximate optimization algorithm,” Quantum, vol. 9, p. 1892, Oct. 2025. [Online]. Available: http: //dx.doi.org/10.22331/q-2025-10-22-1892

    work page doi:10.22331/q-2025-10-22-1892 2025

  8. [8]

    A scalable quantum-enhanced greedy algorithm for maximum independent set problems,

    E. Wybo, J. R ¨onkk¨o, O. Hirviniemi, J. R. Fin ˇzgar, and M. Leib, “A scalable quantum-enhanced greedy algorithm for maximum independent set problems,” 2026. [Online]. Available: https://arxiv.org/ abs/2601.21923

    arXiv 2026

  9. [9]

    A note on greedy algorithms for the maximum weighted independent set problem,

    S. Sakai, M. Togasaki, and K. Yamazaki, “A note on greedy algorithms for the maximum weighted independent set problem,”Discrete Applied Mathematics, vol. 126, no. 2, pp. 313–322, 2003. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0166218X02002056

    2003

  10. [10]

    A quantum approximate optimization algorithm,

    E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” 2014. [Online]. Available: https://arxiv.org/abs/ 1411.4028

    Pith/arXiv arXiv 2014

  11. [11]

    Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics , author =

    T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse ising model,”Phys. Rev. E, vol. 58, pp. 5355–5363, Nov 1998. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevE.58.5355

    work page doi:10.1103/physreve.58.5355 1998

  12. [12]

    Optimizing variational quantum algorithms using pontryagin’s mini- mum principle,

    Z.-C. Yang, A. Rahmani, A. Shabani, H. Neven, and C. Chamon, “Optimizing variational quantum algorithms using pontryagin’s mini- mum principle,”Phys. Rev. X, vol. 7, p. 021027, May 2017. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevX.7.021027

    work page doi:10.1103/physrevx.7.021027 2017

  13. [13]

    Exploring network structure, dynamics, and function using networkx,

    A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using networkx,” inProceedings of the 7th Python in Science Conference, G. Varoquaux, T. Vaught, and J. Millman, Eds., Pasadena, CA USA, 2008, pp. 11 – 15

    2008

  14. [14]

    Expectation values from the single-layer quantum approximate optimization algorithm on ising problems,

    A. Ozaeta, W. van Dam, and P. L. McMahon, “Expectation values from the single-layer quantum approximate optimization algorithm on ising problems,”Quantum Science and Technology, vol. 7, no. 4, p. 045036, sep 2022. [Online]. Available: https://doi.org/10.1088/2058-9565/ac9013

    work page doi:10.1088/2058-9565/ac9013 2022

  15. [15]

    Toward a linear-ramp qaoa protocol: evidence of a scaling advantage in solving some combinatorial optimization problems,

    J. A. Monta ˜nez-Barrera and K. Michielsen, “Toward a linear-ramp qaoa protocol: evidence of a scaling advantage in solving some combinatorial optimization problems,”npj Quantum Information, vol. 11, no. 1, p. 131, Aug 2025. [Online]. Available: https: //doi.org/10.1038/s41534-025-01082-1

    work page doi:10.1038/s41534-025-01082-1 2025

  16. [16]

    Completeness in standard and differential approximation classes: Poly-(d)apx- and (d)ptas-completeness,

    C. Bazgan, B. Escoffier, and V . T. Paschos, “Completeness in standard and differential approximation classes: Poly-(d)apx- and (d)ptas-completeness,”Theoretical Computer Science, vol. 339, no. 2, pp. 272–292, 2005. [Online]. Available: https://www.sciencedirect.com/ science/article/pii/S030439750500126X APPENDIX Here we consider how many cycles there are...

    2005

  17. [17]

    First, we expand the variabled≈ nt′ mT ′ (ignoring rounding up/down)

    Leading Term inn:Now we focus on the scaling with n, so we need to isolate any dependency on it. First, we expand the variabled≈ nt′ mT ′ (ignoring rounding up/down). This allows us to simplify the upper limit of the sum to j n/m+d−1 d k ≈ n/m+ nt′ mT ′ −1 nt′ mT ′ ≈ T ′ t′ + 1 Similarly, the upper term in the binomial coefficient is simplified as n m −(k...