Accelerating the schedule for quantum-enhanced rail
The challenge
Real-world optimization problems, such as rail scheduling, are challenging to solve, even approximately. Quantum computing offers a solution, but errors block the usefulness of today’s devices.
Impact
6X
increase in solvable problem size and accelerated timeline to practical quantum advantage by up to 3 years, now estimated for 2028.
The outcome
Q-CTRL developed a quantum-enhanced rail scheduling solver with Network Rail utilizing Fire Opal’s performance optimization to solve problems of unprecedented scale, bringing practical quantum advantage within reach.
Quantum computing holds the promise of solving problems that are practically inaccessible with conventional methods. At Q-CTRL, our mission is to make quantum technology useful, which is why we design solutions that enable our customers to unlock the full potential of today’s quantum hardware, overcoming the challenges posed by current limits on scale and performance.
Approaching rail’s most complex problems with quantum computing
Across its vast and complex operations, the rail industry faces a variety of challenging problems at all levels of planning processes—from network design and train scheduling to crew management. These problems are formally mathematical optimization problems—a class of problems regarded as one of the fields with the greatest potential to benefit from quantum computing in the near term. In collaboration with Network Rail and the UK Department for Transport (DfT), we have therefore explored how quantum computing can enhance rail operations and worked toward accelerating its adoption, particularly in alignment with future rail objectives around digitization and automation. This £1M project was delivered to Innovate UK, the UK’s innovation agency, as part of the ‘SBRI: Quantum Catalyst Fund’ competition, which was run to accelerate the adoption of quantum solutions by the public sector and for the public benefit.
The problems that typically have to be solved by the rail industry involve many complex constraints and interdependencies; for instance, something as simple as the observation that two trains cannot occupy the same platform at the same time. Even though this seems very simple, mathematically incorporating this kind of limitation into an optimization problem quickly becomes very challenging. In fact it’s often impossible for conventional methods to find optimal or near-optimal solutions within a reasonable timeframe.
Through our exploration with Network Rail we’ve identified that near-term quantum computing has the potential to deliver approximate solutions faster and with higher-quality than alternative approaches. By combining Q-CTRL’s error suppression technology with problem-specific workflow development—supported by continuous exchange with Network Rail to align our problem formulations with real-world requirements, we have made important progress toward turning the promise of quantum computing into tangible benefits.
Our approach is to show, not to tell. So we ran these practically relevant problems on real IBM quantum computers, successfully identifying the correct solutions using over 100 qubits.
This represents up to 6X increase in accessible problem size compared to what is achievable without our tools and sets a world record for the largest constrained quantum optimization problem ever executed.
Even better is what comes next.
Comparing our solver’s capabilities with hardware provider roadmaps, we expect that our quantum solver will be able to outperform classical approaches as early as 2028. This is especially significant given the scale of nation-wide rail operations, where even modest improvements can lead to significant benefits in terms of efficiency, reliability, and sustainability.
Addressing the foundations—improving hardware performance
Before the potential of quantum computing to outperform alternative approaches on complex optimization problems can be realized, a major hurdle must be overcome: Current quantum devices are susceptible to environmental interference, resulting in errors which limit the usefulness of quantum computing today.
This is where Fire Opal comes in; our error-suppressing performance-management software that allows a user to extract maximum performance from current quantum hardware. Fire Opal has demonstrated impressive results on real quantum devices, improving solution quality and accuracy by orders of magnitude.
For optimization problems like those identified in our engagement with Network Rail and DfT, Fire Opal offers special functionality. Its optimization solver abstracts away the complexity of setting up and executing quantum circuits, with performance maximized by automated error suppression and error-aware algorithm execution. The solver has delivered impactful results, outperforming alternative quantum approaches and achieving more than 2,500X reduction in compute costs by reaching solutions faster.
Building on this, we achieved extraordinary results with our partners at Network Rail, and set world records for the most complex quantum optimization problems successfully executed to date. That means we didn’t just get something—we got the right answer!
An end-to-end quantum solver for rail scheduling
In our engagement with Network Rail and DfT, we identified rail scheduling as a particularly high-impact use case for quantum optimization (based on practical relevance, problem complexity, compatibility with quantum algorithms, and potential for resource-efficient quantum execution).
Rail scheduling comprises two key challenges: station routing, which defines the detailed paths trains take through stations, and train timetabling, which determines their optimal arrival and departure times at those stations. We developed quantum-compatible problem formulations that address each of these components individually, with the option to combine them to produce a comprehensive rail schedule.
As part of the engagement, we developed a problem-specific workflow for each rail scheduling component problem, building on Fire Opal’s optimization solver. These workflows enable end users to benefit from quantum-enhanced scheduling without requiring any quantum expertise. The entire process is abstracted away so an end user who specializes in rail scheduling can immediately take advantage of quantum computing.
First, a problem instance is created from user input. Preprocessing reduces the problem size by solving the “easy” part of the problem with classical (non-quantum) methods and leaving the “hard” part for the quantum solver; the reduced problem is solved using Fire Opal’s optimization solver. Finally, the quantum solver output is converted into a user-friendly format and returned together with solution visualizations and evaluations highlighting key metrics and any potential conflicts resulting from violated constraints.
We now take a closer look at the two rail scheduling component problems, individually outlining each problem, our quantum approach, and the results achieved.
Station routing
Station routing aims to assign trains to optimal paths through a station given their arrival and departure times. As the number of trains increases, the number of possible routing configurations quickly grows beyond practical limits. Additionally, a myriad of practical constraints must be satisfied to avoid conflicts and ensure feasible and safe operation, which complicates finding a solution. For example, trains may only be assigned to platforms that can accommodate their length, and no two trains may occupy the same route section or platform at the same time. Quantum computing is a promising approach for such complex, highly-constrained optimization problems, which has the potential to outperform classical approaches by generating high-quality approximate solutions maximizing passenger throughput.
Together with Network Rail, we developed a problem formulation for station routing in which each possible assignment of a train to a route is considered as an option. Rules are then imposed to ensure that only one option is selected per train and that no conflicting options are chosen for different trains. In this way, a wide range of practically relevant constraints can be incorporated. The resulting formulation, constituting a so-called Maximum Weight Independent Set problem, is well-suited for quantum computing. Our full solver workflow, including Fire Opal’s optimization solver, efficiently solves the station routing problem and returns multiple high-quality candidate solutions for planners to choose from based on operational goals.
Higher-quality and more flexible scheduling is a challenging but critical component for future rail services. Q-CTRL's work has shown how quantum computing can enable and potentially accelerate this capability, with promising results already on their roadmap towards a real-world quantum solver demonstration.Sarah Sharples, Chief Scientific Advisor, Department of Transport.
Through the integration of our customized solver workflow for station routing and Fire Opal’s error suppression, we were able to reach record-breaking scales for solving real-world problems on state-of-the-art quantum hardware. Specifically, we successfully found an optimal routing for 26 trains passing through London Bridge station (a major rail hub in London, UK) over an 18-minute period. This optimization accounted for the full station topology with 15 platforms, focusing on a limited area around the platforms, which can be extended in the future. It incorporated real train arrival and departure times, along with an indicative set of realistic constraints, resulting in a problem requiring 103 qubits.
Since the “greedy” local search results represent the baseline solver performance expected if the quantum algorithm execution were dominated by hardware errors, the superior performance of our solver highlights its effectiveness in minimizing the impact of errors.
By actively advancing solver development and error suppression techniques, complementing progress in quantum hardware, we expect our solver workflow to deliver real-world impact for station routing as soon as 2028.
Train timetabling
Train timetabling aims at constructing a schedule that determines optimal arrival and departure times of trains at stations across a rail network, which becomes increasingly difficult as more trains and stations are added. To ensure a safe, efficient, and reliable service, a valid solution has to respect a wide range of practical constraints. For example, travel times between stations have to be long enough to meet safety and energy requirements, but short enough to keep journeys convenient for passengers. These constraints add to the complexity of the problem making it difficult to find even near-optimal schedules at the problem scales needed in real-world rail operations. Again, this is where quantum computing has the potential to outperform classical approaches, reducing carbon emissions, expanding the number of available train journeys, and improving passenger satisfaction.
We co-designed a problem formulation that expresses train timetabling in terms of periodically occurring events (train arrivals and departures at stations) and the constraints that connect them, forming a so-called Periodic Event Scheduling Problem. This approach allows us to incorporate practically relevant considerations and naturally translates into a combinatorial optimization problem known as MaxSAT, which is again compatible with Fire Opal’s optimization solver.
Embedded within our full solver workflow, the optimization solver then efficiently addresses train timetabling. Notably, it returns not just a single schedule, but multiple high-quality candidate solutions, giving planners the flexibility to select the option that best fits their operational priorities.
Our problem-tailored solver workflow, combined with Fire Opal’s advanced error suppression techniques, pushes the boundaries of problem sizes that can be solved on state-of-the-art quantum devices and enables the consideration of realistic constraints. Compared to default algorithm execution without our tools, we successfully addressed problem instances 6X larger. This allowed us to identify optimal solutions for train timetabling instances at unprecedented scales requiring more than 100 qubits.
Through continuous solver development, we have already accelerated the projected timeline to practical quantum advantage by 2–3 years compared to the start of the project. Referencing IBM’s hardware development roadmap, we now estimate that our workflow could deliver real-world impact for train timetabling from 2028.
Bringing quantum advantage to market
Our collaboration with Network Rail and DfT demonstrates that quantum optimization is no longer just a theoretical curiosity, but that practical quantum advantage is within reach using systems coming online over the next few years.
We were pleasantly suprised to see the optimal routing of 26 trains over 18 minutes of real scheduling data for the full station topology being realized on a real quantum device, which otherwise wouldn't have been possible without using Q-CTRL's optimization solver. Nadia Hoodbhoy, Principal Engineer, Network Rail.
As quantum hardware capabilities advance, we will continue to refine our solver workflows and error-suppression tools. The collaboration has enabled us to move beyond abstract research and development, delivering a practical, high-impact product prototype. And rail scheduling is just the beginning.
We are excited to now bring this new productized solver to the transport industry to help deliver better solutions with faster computational runtime than the alternatives. Quantum advantage is coming soon.
Similar engagements have already allowed us to demonstrate the potential of quantum computing in real-world applications across various industries, solving transport problems for TfNSW, optimizing convoy routes for the Australian Army, and exploring quantum-powered logistics for Airbus and BMW.
Reach out to our expert team today to explore how we can help you tackle your optimization challenges.
