IBM and ExxonMobil are building quantum algorithms to solve this giant optimization problem

Research teams from energy giant ExxonMobil and IBM have been working together to find quantum solutions to one of the most complex problems of our time: managing the tens of thousands of merchant ships crossing the oceans every day to deliver the goods that we use every day.  

The scientists lifted the lid on the progress that they have made so far and presented the different strategies that they have been using to model maritime routing on existing quantum devices, with the ultimate goal of optimizing the management of fleets.  

ExxonMobil was the first energy company to join IBM’s quantum Network in 2019, and has expressed a keen interest in using the technology to explore various applications, ranging from the simulation of new materials to solving optimization problems. 

Now, it appears that part of the energy company’s work was dedicated to tapping quantum capabilities to calculate journeys that minimize the distance and time traveled by merchant ships across the globe. 

On a worldwide scale, the equation is immense – intractable, in fact, for classical computers. About 90% of world trade relies on maritime shipping, with more than 50,000 ships, themselves carrying up to 200,000 containers each, moving around every day to transport goods with a total value of $14 trillion.  

The more the number of ships and journeys increase, the bigger the problem becomes. As IBM and ExxonMobil’s teams put it in a blog post detailing their research: “Logistically speaking, this isn’t the ‘traveling salesperson problem.'”  

While this type of exponentially growing problem can only be solved with simplifications and approximations on classical computers, the challenge is well-suited to quantum technologies. Quantum computers can effectively leverage a special dual state that is taken on by quantum bits, or qubits, to run many calculations at once; meaning that even the largest problems could be resolved in much less time than is possible on a classical computer.  

“We wanted to see whether quantum computers could transform how we solve such complex optimization problems and provide more accurate solutions in less computational times,” said the researchers. 

Although the theory behind the potential of quantum computing is well-established, it remains to be found how quantum devices can be used in practice to solve a real-world problem such as the global routing of merchant ships. In mathematical terms, this means finding the right quantum algorithms that could be used to most effectively model the industry’s routing problems, on current or near-term devices. 

To do so, IBM and ExxonMobil’s teams started with widely-used mathematical representations of the problem, which account for factors such as the routes traveled, the potential movements between port locations and the order in which each location is visited on a particular route. There are many existing ways to formulate the equation, one of which is called the quadratic unconstrained binary optimization (QUBO) technique, and which is often used in classical computer science. 

The next question was to find out whether well-known models like QUBO can be solved with quantum algorithms – and if so, which solvers work better. Using IBM’s Qiskit optimization module, which was released last year to assist developers in building quantum optimization algorithms, the team tested various quantum algorithms labeled with unbeatably exotic names: the Variational Quantum Eigensolver (VQE), the Quantum Approximate Optimization Algorithm (QAOA), and Alternating Direction Method of Multiplier (ADMM) solvers. 

After running the algorithms on a simulated quantum device, the researchers found that models like QUBO could effectively be solved by quantum algorithms, and that depending on the size of the problem, some solvers showed better results than others. 

In another promising finding, the team said that the experiment showed some degree of inexactness in solving QUBOs is tolerable. “This is a promising feature to handle the inherent noise affecting the quantum algorithms on real devices,” said the researchers.  

Of course, while the results suggest that quantum algorithms could provide real-world value, the research was carried out on devices that are still technically limited, and the experiments can only remain small-scale. The idea, however, is to develop working algorithms now, to be ready to harness the power of a fully-fledged quantum computer when as soon as the technology develops. 

“As a result of our joint research, ExxonMobil now has a greater understanding of the modelling possibilities, quantum solvers available, and potential alternatives for routing problems in any industry,” said the researchers. 

What applies to merchant ships, in effect, can also work in other settings. Routing problems are not inherent to the shipping industry, and the scientists confirmed that their findings could easily be transferred to any vehicle optimization problem that has time constraints, such as goods delivery, ride-sharing services or urban waste management. 

In fact, ExxonMobil is not the first company to look at ways to use quantum computing techniques to solve optimization problems. Electronics manufacturer OTI Lumionics, for example, has been using QUBO representations to find the most optimal simulation of next-generation OLED materials. Instead of using gate-based quantum computers to run the problem, however, the company has been developing quantum-inspired algorithms to solve calculations on classical Microsoft Azure hardware, with encouraging results

The mathematical formulas and solution algorithms are described in detail in the research paper, and the ExxonMobil/IBM team stressed that their use is not restricted. The researchers encouraged their colleagues to reproduce their findings to advance the global field of quantum solvers.