Suppose you want to divide an established railway system into two train lines. How can you assign train stops to each line in a way that maximizes the number of stations which allow transfers?
This dilemma is a version of the “max cut” problem, an issue of combinatorial optimization (CO)—that is, finding the combination of points and connections that optimizes certain qualities of a network.
Rebekah Herrman
“Max cut is only the most basic example,” said Department of Industrial and Systems Engineering (ISE) Assistant Professor Rebekah Herrman, whose quantum computing research is focused on solving CO problems.
In a CO problem, testing every possible combination to find the best option is so time intensive as to be almost impossible. Even quantum computers can spend a long time on CO problems and only find approximate solutions.
Until recently, the best way to approximate solutions to CO problems was by using the Quantum Approximate Optimization Algorithm (QAOA), which debuted in 2014. QAOA is a program run on a quantum circuit made up of “gates.”
“A quantum gate has to follow certain properties,” said Herrman, “but it’s similar to classical logic gates.”
An “AND” gate would send a “yes” signal only if all of its inputs say “yes,” for example.
More complicated problems require more gates. Unfortunately, as the number of gates in a circuit increases, errors can sneak through, creating a noisy signal rather than a clear answer.
“Current quantum computing devices are filled with noise,” Herrman said. “A lot of research right now is determining how many times you have to repeat QAOA to get within 10% of the optimum solution.”
James Ostrowski
Herrman and her co-investigator, ISE Dan Doulet Faculty Fellow James Ostrowski, are determined to improve both the time scale and the quality of CO solutions—and they recently received a $400,000 National Science Foundation grant to do just that.
Their new algorithm, multi-angle QAOA (ma-QAOA), is a game-changer.
“On average, our modification gives the same result after one iteration that the original gives after three,” said Herrman.
Every CO problem has a unique value called the “operator.” In QAOA, each operator is given an “angle”, or length of time for which to operate.
“In ma-QAOA, we’re breaking the operator into smaller operators and allowing each smaller operator to be performed for different amounts of time,” said Herrman. “This makes the algorithm more flexible.”
For example, ma-QAOA has revealed that some of the gates used by QAOA aren’t necessary.
“We’re noticing that some gates have an angle of zero, so they do nothing,” Herrman said. “We can remove those gates from the circuit, making the next iteration go faster.”
The new funding will allow Herrman and Ostrowski to study ma-QAOA’s calculations in detail and find out how consistently it outperforms QAOA.
“The goal of this grant is to understand better why ma-QAOA performs better than the original, then design circuits based on this understanding,” said Herrman. “It’s exciting because it opens up a whole new area of questions related to quantum algorithms research.”