Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

This paper presents a hybrid divide-and-conquer framework that reformulates rolling stock planning as a Maximum-Weight Independent Set problem and evaluates the Quantum Approximate Optimization Algorithm (QAOA) on both classical simulators and the IQM Emerald quantum device, demonstrating that increasing subgraph sizes within this approach effectively bridges the gap between approximate and exact solution methods.

The Gist

Imagine you are the conductor of a massive railway company. You have a schedule with 190 specific train trips that need to happen over two days. Your job is to figure out which physical train goes on which trip.

But there are rules:

1. Maintenance: Every train must stop at a specific station (like Hamburg) for a 2-hour check-up every few thousand kilometers.
2. Continuity: A train can't magically teleport; it has to finish one trip and start the next from the same station.
3. Cost: If a train has to move without passengers (an "empty trip") to get to its next job, that costs money (fuel, wear and tear). You want to minimize these empty miles.

This is the Rolling Stock Planning problem. It's a giant puzzle where you have to fit all the trips together into loops (called "cycles") that start and end in the same place, obey the maintenance rules, and cost the least amount of money.

The Problem: Too Many Possibilities

The number of ways you can arrange these trains is astronomically huge. It's like trying to solve a Sudoku puzzle where the grid is the size of a football field and the rules keep changing. Even the fastest supercomputers struggle to find the perfect arrangement for a schedule this big.

The Solution: A Hybrid "Divide and Conquer" Strategy

The authors propose a clever trick. Instead of trying to solve the whole giant puzzle at once, they break it into smaller, manageable chunks.

Think of it like organizing a massive library. Instead of trying to shelve every single book in the world at once, you:

1. Pick a small section of the library.
2. Sort those books perfectly.
3. Put them on the shelf.
4. Move to the next section.

They call this a Divide-and-Conquer algorithm. They take the big problem, cut out a small piece (a "subgraph"), solve that piece, and then move on.

The Secret Weapon: Quantum Computers

Here is where it gets sci-fi. To solve those small pieces, they use a mix of old-school computers and a new type of computer called a Quantum Computer.

• The Classical Computer: It's like a very fast, logical librarian. It can solve small puzzles quickly but gets stuck on huge ones.
• The Quantum Computer (QAOA): Think of this as a "super-intuitive" librarian. It doesn't just look at one path at a time; it explores many possibilities simultaneously. It uses a method called the Quantum Approximate Optimization Algorithm (QAOA).

The paper tested this quantum librarian on a real quantum machine (called IQM Emerald) and also simulated it on a classical computer.

How They Tested It

The researchers compared three ways to solve those small puzzle pieces:

1. The Greedy Approach: A simple, fast method that picks the "best" looking option right now without looking ahead. (Like picking the nearest book without checking if it fits the genre).
2. The Exact Solver: A slow, perfect method that checks every single possibility to find the absolute best answer.
3. The Quantum Solver (QAOA): The "intuitive" approach that tries to find a very good answer quickly.

What They Found

1. Bigger Chunks are Better: When they made the "small pieces" of the puzzle larger, the overall solution got better. It's like if you organize a whole aisle of books at once instead of just one shelf, you can see the bigger picture and make smarter choices.
2. Quantum is Promising: The quantum solver (QAOA) performed almost as well as the perfect, slow "Exact Solver," but much faster. Even though the quantum computer was small and not perfect yet, it showed it could find high-quality solutions that were very close to the best possible ones.
3. The "Pruning" Step: Sometimes the quantum computer gives a messy answer (like suggesting two trains go to the same place at the same time). The authors use a "pruning" tool to clean up these mistakes, removing the conflicts to make the solution valid.

The Bottom Line

This paper doesn't claim that quantum computers have solved the world's railway problems yet. Instead, it shows a roadmap.

They proved that by breaking a massive, impossible problem into smaller pieces and using a quantum computer to solve those pieces, you can get very good results. It's a bridge between the slow, perfect methods of the past and the fast, powerful methods of the future.

In short: They took a giant, messy railway schedule, chopped it up, used a quantum computer to tidy up the small pieces, and showed that this hybrid approach works better than just guessing or using only old-school computers.

Technical Summary

Technical Summary: Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

Problem Definition
The paper addresses the Rolling Stock Planning problem, a complex optimization challenge in railway management. The objective is to assign physical trains to a scheduled timetable of trips while minimizing operational costs, specifically defined as "empty kilometers" (distance traveled without passengers). The problem instance considered involves 190 trips over two days across five stations, subject to strict constraints:

• Cyclic Operation: Each train must complete a cycle that returns to its starting station.
• Maintenance: Every cycle must include a mandatory maintenance stop at a designated station for a fixed duration.
• Distance Limits: Cycles cannot exceed a maximum distance ($l_{max}$) before maintenance is required.
• Empty Trips: Trains may traverse "empty trips" (non-scheduled movements) to connect scheduled trips or reach maintenance stations, incurring cost but ensuring feasibility.

The authors note that while the problem is constrained, they do not model network capacity constraints (e.g., station parking limits or route congestion), assuming unlimited capacity for the scope of this study.

Methodology
The authors propose a hybrid quantum-classical divide-and-conquer algorithm to tackle the computational complexity of the problem, which scales exponentially with the number of trips.

1. Mapping to Maximum-Weight Independent Set (MWIS):
   The problem is first reformulated as an MWIS problem on a graph.

   • Nodes: Represent feasible train cycles generated from the timetable.
   • Edges: Connect nodes if the corresponding cycles are mutually incompatible (i.e., they both service the same scheduled trip).
   • Weights: Assigned to nodes based on a heuristic objective function ($w_i = 2d_{full} - d_{empty}$), prioritizing the coverage of passenger trips over pure cost reduction.
   • Goal: Find an independent set (a set of non-conflicting cycles) with the maximum total weight.

2. Cycle Generation Strategy:
   To manage the explosion of possible cycles, the authors employ a two-mode generation process:

   • Mode 1: Generates cycles using only scheduled trips (no empty trips).
   • Mode 2: Activated when the number of unserviced trips falls below a threshold (40 trips) or no further Mode 1 cycles can be formed. This mode allows empty trips, significantly expanding the solution space to ensure all remaining trips can be covered.

3. Hybrid Divide-and-Conquer Framework:
   Since the full MWIS graph is too large for current solvers, the algorithm iteratively solves smaller subgraphs:

   • Subgraph Selection: A heuristic selects a subgraph of size $k$ (e.g., 20 to 300 nodes). The selection strategy prioritizes cycles that service the highest number of full trips, balancing solution quality with diversity.
   • Subgraph Solving: The MWIS problem on the selected subgraph is solved using various methods:
     • Classical Exact Solver: Used as a baseline.
     • Greedy Algorithm: A classical baseline selecting nodes based on weight-to-degree ratio.
     • QAOA (Quantum Approximate Optimization Algorithm): Implemented with depth $p=1$ and $p=5$. The problem is mapped to a diagonal spin-glass Hamiltonian with a penalty term for edge violations.
     • Random Sampling: Used as a lower-bound benchmark.
   • Pruning: Since QAOA and random sampling may produce invalid sets (containing connected nodes), a pruning procedure removes nodes with the lowest weight-to-degree ratios until a valid independent set is formed.
   • Global Update: Selected cycles are added to the global solution, and conflicting nodes are removed from the global graph. The process repeats until all trips are serviced.

Key Results
The authors evaluated the algorithm using classical simulation and execution on the IQM Emerald quantum device.

• Solver Comparison (Fixed Subgraph Size): With a small subgraph size ($k=20$), the performance difference between the greedy algorithm, exact classical solvers, and QAOA ($p=1, p=5$) was negligible. However, the results showed that higher-depth QAOA ($p=5$) tended to approach the solution quality of the exact solver, despite being a polynomial-time algorithm compared to the exponential-time exact solver.
• Impact of Subgraph Size: A critical finding was the positive correlation between subgraph size and solution quality. As the subgraph size increased (up to 300 nodes), the number of empty kilometers decreased significantly (negative slope with $p \approx 10^{-9}$). This suggests that solving larger subproblems yields better global solutions, even if the subgraph solver itself is approximate.
• Quantum Execution: The paper reports results from running $p=1$ QAOA on the IQM Emerald quantum computer, demonstrating the feasibility of executing the algorithm on current hardware, though the solution quality was comparable to classical simulation and random sampling for the tested parameters.

Significance and Claims
The paper positions its work as a practical pathway for applying near-term quantum computers to realistic industrial optimization problems before hardware is capable of solving the full problem directly.

• Bridging the Gap: The hybrid framework effectively bridges the gap between fast, approximate polynomial-time solvers (like greedy algorithms) and slow, exact exponential-time methods.
• Scalability: The authors argue that their approach allows quantum algorithms to be applied to subproblems compatible with current hardware limitations, while a classical outer loop orchestrates the overall optimization.
• Quantum Advantage Potential: The results suggest a scenario where the depth of the QAOA algorithm ($p$) needs only to grow polynomially with subgraph size to achieve approximately optimal solutions, offering a potential quantum advantage over exact classical methods for large-scale instances.
• Modesty: The authors acknowledge limitations, noting that the current cycle generation step is a bottleneck for larger timetables and that the effectiveness of the pruning procedure may degrade as subgraph sizes increase. They do not claim that QAOA currently outperforms classical exact solvers on the full problem, but rather that the hybrid architecture enables the exploration of larger solution spaces than previously possible with quantum resources alone.