Quantum computer can solve Real Optimization Problems
Quantum computers can solve optimization problems more effectively than traditional computers. Quantum computers have already managed to transcend ordinary computers in the resolution of some tasks-unfortunately, absolutely pointless ones. The next milestone is to get them to do some practical stuff. Researchers at the Swedish Chalmers University of Technology have demonstrated that a tiny yet well-functioning quantum computer has been able to solve a small part of the real logistics dilemma in the aviation industry.
All airlines face scheduling issues. For example, assigning individual aircraft to different routes is a problem of optimization that is increasing very exponentially in scale and difficulty as the number of routes and aircraft grows. In recent years, interest in developing quantum computers has gained tremendous traction, and feverish work is ongoing in several parts of the world. Google’s science team achieved a big advance in 2019 as their quantum machine managed to conquer a problem far quicker than the world’s fastest supercomputer. The downside is that the task solved had little practical utility whatsoever-it was selected because it was found to be easy to solve for a quantum computer, but very complicated for a classical computer.
Quantum computers already have shown their ability to surpass ordinary computers in solving certain tasks, but until now, those tasks have had no practical use.
It is therefore an important activity now to identify useful, relevant problems outside the scope of ordinary computers, but which could be solved by a comparatively small quantum computer. Researchers have successfully applied the Quantum Approximate Optimization Algorithm (QAOA) on a quantum computer consisting of a two-qubit processor to solve the problem of assigning aircraft to routes in operation.
“We want to be sure that the quantum computer we are developing can help solve relevant problems early on. Therefore, we work in close collaboration with industrial companies,” says theoretical physicist Giulia Ferrini, one of the leaders of Chalmers University of Technology’s quantum computer project, which started in 2018.
Together with Göran Johansson, Giulia Ferrini led the theoretical work when a team of researchers at Chalmers, including an industrial doctoral student at Jeppesen, an aviation logistics firm, recently demonstrated that a quantum computer would solve a real problem in the aviation industry. The two-qubit algorithm Both airlines are faced with scheduling issues. For example, assigning individual aircraft to different routes is a problem of optimisation, one that rises very quickly in scale and difficulty as the number of routes and aircraft increases.
Researchers expect that quantum computers will potentially be better suited to cope with such issues than today’s computers. The fundamental building block of the quantum computer—the qubit—is built on radically different ideas than the building blocks of today’s computers, enabling them to process large quantities of information with very few qubits.
However, owing to their particular nature and purpose, quantum computers must be designed in ways other than traditional computers. One suggested an algorithm that is thought to be useful on early quantum computers is the so-called Quantum Approximate Optimization Algorithm (QAOA). The Chalmers research team has now successfully applied this algorithm on their quantum computer-a two-qubit processor-and has demonstrated that it can successfully solve the problem of assigning aircraft to routes. In this first demonstration, the outcome could quickly be checked as the size was very small-only two aircraft were involved.
Potential to handle several aircraft with this achievement, the researchers first demonstrated that the QAOA algorithm would solve the problem of assigning aircraft to routes in operation. They have even managed to run the algorithm one step higher than anybody before, a feat that takes very good hardware and precise power.
“We have shown that we have the ability to map relevant problems onto our quantum processor. We still have a small number of qubits, but they work well. Our plan has been to first make everything work very well on a small scale, before scaling up,” says Jonas Bylander, senior researcher in experimental architecture, and one of the founders of the quantum computer project.
The researchers have simulated the solution of the same optimization problem for up to 278 aircraft, which would involve a quantum computer with 25 qubits. Chalmers’ Giulia Ferrini said, “The results remained good as we scaled up. This suggests that the QAOA algorithm has the potential to solve this type of problem at even larger scales.”
“The results remained good as we scaled up. This suggests that the QAOA algorithm has the potential to solve this type of problem at even larger scales,” says Giulia Ferrini. Overcoming today’s best computers will, though, require even larger machines. Chalmers researchers have already started scaling up and are currently working on five quantum bits. The target is to produce at least 20 qubits by 2021 while retaining high efficiency.
