Navigating the Growing Complexity of Flight Gate Optimization with IonQ Aria
When arriving at an airport, travelers experience a variety of pre-made decisions, whether it’s gate number, luggage drop-off area, or pre-boarding time. For airport personnel, these decisions are based on an even larger pool of possible scenarios that include variations like the time it takes to offload passengers in between flights, weather conditions, refueling time, and flight crew rotations. These scenarios are all outputs of optimization problems, where airport personnel and flight operators are tasked with finding the best solution from all feasible solutions. With so many moving parts and intertwining contact points, the airline industry is investing in quantum computers to more accurately and efficiently analyze optimization problems which can contain dozens to hundreds of variables.
Take one common airport inconvenience: flight delays due to no available or open gates . A simple solution would be to move the departing or arriving flight to a different gate. But then how long will the previous gate remain open once the departing or arriving flight has been relocated? How long will it take to move baggage from one gate to another? How far do passengers need to travel from one side of the terminal to the other? Optimization problems such as these fall under the more general class of problems called quadratic assignment problems (QAPs) which in their full, dense form are extremely challenging to solve using today’s classical computers. Hence, heuristic methods are often required to solve such problems in a reasonable time (i.e. reasonable being a few minutes to a few hours rather than days or weeks). Quantum computers on the other hand may be able to tackle such problems at scale (i.e. very large number of optimization problems with dozens of variables) and provide solutions that could beat classical heuristics.
In September 2023, researchers from Deutsches Elektronen-Synchrotron (DESY) – a German-based research center for fundamental science – and IonQ demonstrated the ability to run combinatorial optimization equations on IonQ’s Aria quantum system. Flight gate optimization is a simplified version of the larger QAP, yet represents a significant technical milestone in demonstrating quantum’s potential in tackling this species of problem in the aircraft industry. IonQ and DESY explored how to better match inbound and outbound flights at airport gates. The goal was to reduce the time travelers spent going from arrival to departure gates and the time planes sat idle at gates before taking off again, while also increasing the number of planes serviced per day at a gate.
Previous attempts at solving the same problem include quantum annealing experiments on the DWAVE Quantum Annealer [1] and on IBMs QPU [2]. The experiments on the DWAVE quantum annealer were performed using 84 variables with 7 flights and 12 gates. The quantum annealer is not a gate based quantum computer and cannot control the interactions between qubits directly. The encoding here requires (#flights)*(#gates) as qubits to encode the binary variables. Since the DWAVE machine utilizes a chimera graph with several physical qubits to encode a single logical qubit which represents a variable, the actual number of physical qubits required to encode the problem goes as O(N^4) where N is the total number of variables in the problem. This is very large scaling and our encoding method is much more efficient as described below. The other experiment [2] was run on a gate based QPU from IBM, and the encoding again was a log-linear encoding requiring fewer qubits to encode the binary variables; however, this approach required separability of the problem into different smaller sets using a graph coloring approach. The largest system that was tackled was 24 flights and 8 gates but these were separated into 3 banks of 8 flights and 8 gates each. The IBM system does not have all to all connectivity and therefore, with larger systems, the circuit depth will undoubtedly increase due to the number of swap gates needed to make distant non-nearest neighbor qubits interact.
The methodology used by IonQ and DESY is different from previous approaches for solving the same problem. The standard method of encoding the problem is to use a binary variable to represent each flight/gates. This embedding requires (#flights)*(#gates) binary variables or qubits to encode the problem. We used a logarithmic-linear encoding for the flight-gate optimization. One set of variables (gates) was encoded logarithmically while the other set of variables (flights) was encoded linearly. This gave an exponential advantage in the embedding of the problem. The Hamiltonian for the problem needed to be re-engineered to work with this encoding. IonQ and DESY were able to run several instances of the problem of varying sizes from 8 variables (2 flights and 4 gates) which required 4 qubits to 36 variables (9 flights and 4 gates) which required 18 qubits using the IonQ Aria QPU. Two instances of the problem with 8 and 12 variables were fully optimized on the IonQ Aria QPU while the larger instances with 28, 32 and 36 variables, respectively, were optimized on the simulator and the optimal parameters were used to run an inference job on the QPU to estimate the probabilities of measuring the different solutions. All the simulations and the QPU optimizations were run as a hybrid quantum-classical optimization using COBYLA as the classical optimizer. The full optimization runs on the Aria QPU sampled at each iteration with 1000 shots while the inference jobs on the QPU were sampled at 10000 shots. A few of the results are shown in the figures below.
While the aforementioned results were achieved on Aria, IonQ believes its algorithms can scale to support IonQ Forte and account for an even larger problem set of 144 variables – potentially 12 flights across 8 gates. IonQ’s future system is even expected to process 640 variable scenarios – potentially 25 flights across 16 gates – leaps ahead of other quantum companies that claim their systems can tackle only 84 variables.
A research paper summarizing IonQ and DESY’s research [3] will be published in the coming months. However, the teams are excited by the early results displayed today.
"We are pleased by the initial results we’re seeing in running quadratic assignment problems across IonQ’s quantum hardware and our collaboration with the IonQ team,” said Dr. Karl Jansen, the head of the Center for Quantum Technology and Applications (CQTA) at DESY. "The learnings gathered here can easily apply to other research and industries where the presence of multiple variables creates too complex of a problem for classical systems to handle."
The IonQ and DESY approach is not likely to be deployed in an airport in the immediate future, as that was not the goal of the project. The companies and organizations with the most momentum in quantum are often not trying to deploy production applications on the currently available systems, they are interested in the second-order effects of trying to solve hard problems with innovative quantum approaches. These second-order effects include creating intellectual property, building readiness, encouraging a culture of innovation, discovering new classical approaches, informing and developing application roadmaps, and more. Together, IonQ and DESY have unlocked new avenues for optimizing gate assignments, streamlining operations, and enhancing passenger experiences.
While today’s optimization problem is specific to the airline industry, its general principles and functions can easily translate to other industries, such as finance, agriculture, and medicine. The power of quantum truly shines when applied to problem sets that include countless inputs and variables, and the IonQ team is excited to explore how quantum computing may reveal new solutions for some of the world’s most complex equations.
References:
Tobias Stollenwerk, Elisabeth Lobe, and Martin Jung., Flight gate assignment with a quantum annealer In International Workshop on Quantum Technology and Optimization Problems, pages 99–110, Springer, 2019
Hamed Mohammadbagherpoor, Patrick Dreher, Mohannad Ibrahim, Young-Hyun Oh, James Hall, Richard E Stone, and Mirela Stojkovic, Exploring airline gate-scheduling optimization using quantum computers, arXiv preprint arXiv:2111.09472 2021.
Yahui Chai, Evgeny Epifanovsky, Karl Jansen, Ananth Kaushik, Stefan Kühn, Simulating the flight gate assignment problem on a trapped ion quantum computer, arXiv preprint arXiv:2309.09686v1