Recent advancements in quantum computing have driven the scientific community’s quest to solve a certain class of complex problems for which quantum computers would be better suited than traditional supercomputers. To improve the efficiency with which quantum computers can solve these problems, scientists are investigating the use of artificial intelligence approaches.
“Combinatorial optimization problems are those for which the solution space gets exponentially larger as you expand the number of decision variables,” said Argonne computer scientist Prasanna Balaprakash. “In one traditional example, you can find the shortest route for a salesman who needs to visit a few cities once by enumerating all possible routes, but given a couple thousand cities, the number of possible routes far exceeds the number of stars in the universe; even the fastest supercomputers cannot find the shortest route in a reasonable time.”
Developed recently, QAOA is considered as one of the leading candidates for demonstrating the advantage of quantum computers. QAOA is a hybrid quantum-classical algorithm that uses both classical and quantum computers for approximately solving combinatorial optimization problems.
The new algorithm developed at Argonne learns how to configure QAOA through a feedback mechanism. A particularity of the proposed algorithm is that it can be trained on smaller problem instances, and the trained model can adapt QAOA to larger problem instances. “It’s a bit like having a self-driving car in traffic,” Balaprakash said. “The algorithm can detect when it needs to make adjustments in the ‘dials’ it uses to do the computation.”
The QAOA could have significant benefits for solving combinatorial problems that arise with 5G wireless communications. According to Balaprakash, a scientific problem called Max-Cut can be used to model how different wireless devices talk to each other at the same time with minimum interference between them. Solving such problems at scale is challenging, yet is important for optimal wireless spectrum management.
Using machine learning to optimize the quantum algorithm involves training it with “rewards” and “penalties” depending on how well it performs, said Sami Khairy, a study author and graduate student at the Illinois Institute of Technology. “It’s an iterative procedure that allows us to improve how the computation is running,” he said. “It learns a better way to assign new parameters, and we want to assign good parameters as fast as possible.”
One of the big advantages of doing this kind of machine learning involves the ability to generalize the principles of the findings over the broader class of problem instances, Khairy explained. “We’ve designed an optimization algorithm that works for several instances,” he said. “In previous studies, it was as if we were training one driver to drive one kind of car; here, we have the ability to train our driver to adapt to many different kinds of cars, in real time.”