How a quantum computer tackles a surprisingly difficult airport problem

At first glance, quantum computers seem like machines that only will exist in the far-off future. And in a way, they are. Currently, the processing power that these devices have are limited by the number of qubits they contain, which are the quantum equivalent of the 0-or-1 bits you’ve probably heard about with classical computers.

The engineers behind the most ambitious quantum projects have said that they can orchestrate together hundreds of qubits, but because these qubits have unique yet ephemeral quantum properties, like superposition and entanglement, keeping them in the ideal state is a tough task. All this added together means that the problems that researchers have touted that quantum computers could be better at than classical machines have still not been fully realized.

Scientists say that in general, quantum machines could be better at solving problems involving optimization operations, nature simulations, and searching through unstructured databases. But without real-world applications, it can all seem very abstract.

The flight gate assignment challenge

A group of researchers working with IBM have been crafting and testing special algorithms for specific problems that work with quantum circuits. That means the broad category of optimization tasks becomes a more specific problem, like finding the best gate to put connecting flights in at an airport.

Here are the requirements for the problem: The computer needs to find the most optimal gates to assign incoming and connecting flights to in an airport in order to minimize the passenger travel time. In this sense, travel time to and from gates, number of passengers, the presence of a flight at a gate or not—these all become variables in a complex series of math equations.

Essentially, each qubit represents either the gate or the flight. So the number of qubits you need to solve this problem is the number of gates multiplied by the number of flights, explains Karl Jansen, a research physicist at DESY (a particle physics research center in Germany) and an author of the preprint paper on the algorithm.

How a ‘Hamiltonian’ is involved

In order to perform the operation on a quantum device, first they have to integrate all of this information into something called a “Hamiltonian,” which is a quantum mechanical function that measures the total energy of a system. The system, in this case, would be the connections in the airport. “If you find the minimal energy, then this corresponds to the optimal path through the airport for all passengers to find the optimal connections,” says Jansen. “This energy function, this Hamiltonian, is horribly complicated and scales exponentially. There is no way to do this on a classical computer. However, you can translate this Hamiltonian into a quantum circuit.”

In their study, Jansen and his colleagues only worked with around 20 qubits, which is not much and doesn’t offer an edge over the best classical algorithms directed at the problem today. At the moment it doesn’t really make sense to compare the solution time or accuracy to a classical calculation. “For this it would need 100 or 200 functioning qubits,” he notes. “What we want to know is if I make my problem size larger and larger, so I go to a larger and larger airport, is there at some point an advantage to using quantum mechanical principles to solve the problem.”

Superposition, entanglement and interference

It’s important to note that controlling these machines means that the best minds across a wide number of industries, from applied math to chemistry to physics, must work together to design clever quantum algorithms, or instructions that tell the quantum computer what operations to perform and how. These algorithms are by nature different from classical algorithms. They can involve higher-level math, like linear algebra and matrices. “The fundamental descriptions of the systems are different,” says Jeannette Garcia, senior research manager for quantum applications and software team at IBM Research. “Namely, we have superposition and entanglement and this concept of interference.”

Although it is still to be proven, many researchers think that by using superposition, they can pack more information into the problem, and with entanglement, they could find more correlations, such as if a certain flight is correlated with another flight and another gate because they’re both domestic.

Every answer that a quantum computer gives is basically a probability, Garcia explains. A lot of work goes into formulating ways to combine answers together in a creative way to come up with the most probable answer over many repeating trials. That is what interference is—adding up or subtracting waveforms. The entanglement piece in particular is promising for chemistry but also for machine learning. “In machine learning datasets, you might have data that’s super correlated, so in other words, they are not independent from each other,” Garcia says. “This is what entanglement is. We can put that in and program that into what we’re studying as a way to conserve resources in the end, and computational power.”

And while the new algorithm from Jansen’s team can’t really be used to make airports more efficient today, it can be translated to a variety of other problems. “Once we found really good ways of solving the flight gate assignment problem, we transferred the algorithms and improvements to these problems we are looking at for particle tracking, both at CERN but also at DESY,” Jansen said.

In addition, you can apply the same formulation to other logistics problems such as optimizing bus routes or traffic light placements in a city. You just have to modify the information of the problem and what numbers you put into the coefficients and the binary variables. “For me, this was a good attempt to find a solution for the flight gate assignment problem,” Jansen says. “Now I’m looking at other instances where I can use this mathematical formulation to solve other problems.”