Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.11383

Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

Jiří Guth Jarkovský, Patricia Bickert, Elisabeth Wybo, Martin Leib

quant-phSubmitted Jun 9, 2026• Announced Jun 11, 2026• 0 citations
arXivHTMLPDF

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.

Comments
10 pages, 2 figures. Submitted to IEEE Quantum Week 2026

Related papers

EMU circulation planning for Silesian Railways: case study and a quantum approach

Ewa Kędziera, Wojciech Gamon, Mátyás Koniorczyk +3 more

We study daily rolling stock circulation planning for electric multiple units (EMUs) on a regional passenger network, focusing on services where identical EMUs may be coupled in pairs on selected routes. Motivated by the operational needs of the regional operator Silesian Railways in Poland, we formulate an acyclic mixed-integer linear program on a one-day horizon that incorporates depot balance constraints, demand-driven seat and bicycle capacity limits, and simple crew availability constraints. Using a graph/hyper-graph representation of train movements, we first solve an ILP formulation. We then derive a Quadratic Unconstrained Binary Optimization (QUBO) reformulation and evaluate its solution by quantum annealing on D-Wave Advantage systems and by the classical quantum-inspired VeloxQ solver. In computational experiments on real-world instances from the Silesian network, with up to 404 train trips and 11 EMU types, the ILP approach yields high-quality daily circulation plans within at most about 40 minutes. The quantum and quantum-inspired solvers are restricted to substantially smaller sub-instances due to the large number of terms in the QUBO and embedding limitations in the case of quantum hardware. These results quantify the present frontier of QUBO-based methods for rolling stock circulation. They can be helpful in designing a hybrid classical-quantum approach.

quant-pharXiv:2512.19340•Dec 23, 2025

Formulation and quantum resolution of a railway timetabling problem

Grange, Camille, Valentina Pozzoli, François Ramond +1 more

Quantum computing has been a ground-breaking domain for several years. Its new computational paradigm promises to impact the railway transports domain through quantum algorithms that solve hard combinatorial problems where a good or optimal solution is needed. It could open interesting applications for hard real-time problems, integrated problems, etc. Thus, it is crucial to study the type of railway decision or optimization problems quantum computation could tackle and to what extent their solving could be improved. In this paper, we characterize the quantum approaches over classical methods on a problem of optimal timetabling design. This problem consists of finding the transportation plan maximizing the operating profit according to the customers' demand and the availability and cost of the network and the rolling stock. The combinatorial complexity of this problem prevents its efficient solving by current classical computers on large perimeters. Quantum computers could overcome this issue and provide better solutions within less time. We present two families of quantum algorithms for solving combinatorial problems: meta-heuristics (Quantum Approximate Optimization Algorithm, Quantum Annealing) and exact search algorithms (Grover's algorithm). First, we simplify the initial timetabling problem so that the current quantum technology can handle it. Then, we reformulate it for each kind of algorithm. Finally, a small case study and a real-life instance illustrate the implementation of quantum algorithms on available quantum devices.

•Jun 6, 2022•0 citations

Deep-Dive Research & Critique: IQM/Deutsche Bahn Hybrid Quantum Railway Scheduling

Rowan Brad Quni-Gudzinas

A deep-dive research analysis and red-team critique of IQM Quantum Computers and Deutsche Bahn's July 2026 hybrid quantum-classical railway scheduling demonstration. The work evaluates claims made in The Qubit Report article, the IQM technical whitepaper, and the arXiv preprint (arXiv:2606.11383). The critique finds the demonstration is an honest proof-of-concept, substantially overclaimed in marketing: p=1 QAOA on fewer than or equal to 20-qubit subgraphs adds zero demonstrated advantage over classical methods, the central finding was measured with a classical solver, and no classical baseline was reported. Genuine contribution identified: clean MWIS reformulation of rolling stock planning. Includes literature cross-reference, calibration register, and 5-role red-team adversarial challenge.

•Jul 22, 2026•0 citations

Quantum Optimization for Airline Itinerary and Scheduling: A QUBO and QAOA Approach

Vaibhav V. Khedekar

Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.

•Apr 22, 2025•0 citations

Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability

F. Picariello, G. Turati, R. Antonelli +10 more

The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.

quant-pharXiv:2512.10813•Dec 12, 2025•1 citation

Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA

Aniello Esposito, Tamuz Danzig

The Quantum approximate optimization algorithm (QAOA) is a leading hybrid classical-quantum algorithm for solving complex combinatorial optimization problems. QAOA-in-QAOA (QAOA2) uses a divide-and-conquer heuristic to solve large-scale Maximum Cut (MaxCut) problems, where many sub-graph problems can be solved in parallel. In this work, an implementation of the QAOA2method for the scalable solution of the MaxCut problem is presented, based on the Classiq platform. The framework is executed on an HPE-Cray EX supercomputer by means of the Message Passing Interface (MPI) and the SLURM workload manager. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated to understand if QAOA2could benefit from solving certain sub-graphs classically. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices. For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW.

arXiv:2406.17383•IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 27, 2024•9 citations
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.
We study daily rolling stock circulation planning for electric multiple units (EMUs) on a regional passenger network, focusing on services where identical EMUs may be coupled in pairs on selected routes. Motivated by the operational needs of the regional operator Silesian Railways in Poland, we formulate an acyclic mixed-integer linear program on a one-day horizon that incorporates depot balance constraints, demand-driven seat and bicycle capacity limits, and simple crew availability constraints. Using a graph/hyper-graph representation of train movements, we first solve an ILP formulation. We then derive a Quadratic Unconstrained Binary Optimization (QUBO) reformulation and evaluate its solution by quantum annealing on D-Wave Advantage systems and by the classical quantum-inspired VeloxQ solver. In computational experiments on real-world instances from the Silesian network, with up to 404 train trips and 11 EMU types, the ILP approach yields high-quality daily circulation plans within at most about 40 minutes. The quantum and quantum-inspired solvers are restricted to substantially smaller sub-instances due to the large number of terms in the QUBO and embedding limitations in the case of quantum hardware. These results quantify the present frontier of QUBO-based methods for rolling stock circulation. They can be helpful in designing a hybrid classical-quantum approach.
Quantum computing has been a ground-breaking domain for several years. Its new computational paradigm promises to impact the railway transports domain through quantum algorithms that solve hard combinatorial problems where a good or optimal solution is needed. It could open interesting applications for hard real-time problems, integrated problems, etc. Thus, it is crucial to study the type of railway decision or optimization problems quantum computation could tackle and to what extent their solving could be improved. In this paper, we characterize the quantum approaches over classical methods on a problem of optimal timetabling design. This problem consists of finding the transportation plan maximizing the operating profit according to the customers' demand and the availability and cost of the network and the rolling stock. The combinatorial complexity of this problem prevents its efficient solving by current classical computers on large perimeters. Quantum computers could overcome this issue and provide better solutions within less time. We present two families of quantum algorithms for solving combinatorial problems: meta-heuristics (Quantum Approximate Optimization Algorithm, Quantum Annealing) and exact search algorithms (Grover's algorithm). First, we simplify the initial timetabling problem so that the current quantum technology can handle it. Then, we reformulate it for each kind of algorithm. Finally, a small case study and a real-life instance illustrate the implementation of quantum algorithms on available quantum devices.
A deep-dive research analysis and red-team critique of IQM Quantum Computers and Deutsche Bahn's July 2026 hybrid quantum-classical railway scheduling demonstration. The work evaluates claims made in The Qubit Report article, the IQM technical whitepaper, and the arXiv preprint (arXiv:2606.11383). The critique finds the demonstration is an honest proof-of-concept, substantially overclaimed in marketing: p=1 QAOA on fewer than or equal to 20-qubit subgraphs adds zero demonstrated advantage over classical methods, the central finding was measured with a classical solver, and no classical baseline was reported. Genuine contribution identified: clean MWIS reformulation of rolling stock planning. Includes literature cross-reference, calibration register, and 5-role red-team adversarial challenge.
Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.
The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.
The Quantum approximate optimization algorithm (QAOA) is a leading hybrid classical-quantum algorithm for solving complex combinatorial optimization problems. QAOA-in-QAOA (QAOA2) uses a divide-and-conquer heuristic to solve large-scale Maximum Cut (MaxCut) problems, where many sub-graph problems can be solved in parallel. In this work, an implementation of the QAOA2method for the scalable solution of the MaxCut problem is presented, based on the Classiq platform. The framework is executed on an HPE-Cray EX supercomputer by means of the Message Passing Interface (MPI) and the SLURM workload manager. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated to understand if QAOA2could benefit from solving certain sub-graphs classically. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices. For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW.