Computer Scientists at Rice University and the University of Edinburgh are not just thinking outside the box, they are imagining algorithms where boxes don’t exist --in the emerging world of quantum computing. “Algorithmic Foundations for Variational Quantum Algorithms” is the topic of new research by Anastasios Kyrillidis, Rice’s Noah Harding Assistant Professor in Computer Science, and Petros Wallden, a lecturer in the School of Informatics at the University of Edinburgh.
“We used to think of algorithms in a ‘classical’ way --where using if-then-else or for-loops in an algorithm is considered de facto and given,” said Kyrillidis.
“Now, rewire your way of thinking: try to solve the same problem without the ‘comfort’ of classical operations. Rethink the algorithm itself and its complexity. This is a great black box that challenges us to redefine algorithms. Petros and I are diving in with the hope we will end up with gains over classical computing.”
With prototypes of quantum computers still in the construction and verification stage, researchers continue questioning the best ways to utilize that hardware for practical purposes. One proposed technique, the Quantum Approximate Optimization Algorithm (QAOA), may more efficiently solve optimization problems with quantum computers by predicting ‘good enough’ answers rather than the ‘best’ answer. This is the technique upon which Kyrillidis and Wallden plan to base their research.
Kyrillidis said, “QAOA is a generic framework that can describe a diverse set of problems, from finding the ground or excited states of quantum systems to connecting with more ‘tropical’ applications such as quantum neural networks.
“The general idea is to parameterize a quantum-based optimization objective with a small set of classical variables, then use a quantum computer simulator to find the right parameters — via classical algorithms — to solve a quantum problem.”
Essentially, Kyrillidis and Wallden combine the strengths of classical and quantum computing — like bringing the single best major league pitcher, outfielder, catcher, and batter together on the same field.
“Despite the generality of QAOA –which can be used to solve classical CS problems like MaxCUT or MaxSAT and general problems such as finance optimization problems—its objective is as simple as the principal component analysis problem in classical computing, machine learning, and data science,” said Kyrillidis.
“It turns out that we are looking for a solution (vector) that maximizes or minimizes a very simple objective (quadratic function) but ‘navigates’ within the solution space in a very peculiar, quantum-based way. Overall, QAOA has many nice properties; using it to understand the problem may be easier than with other more complicated scenarios, while simultaneously offering a quite broad application set.”
As much as he’s come to appreciate the possibilities of QAOA, Kyrillidis acknowledges it is not a one-size-fits-all solution; for example, QAOA will not run a laptop’s operating system and it is not a likely substitute for gradient descent in training a neural network.
He said, “QAOA’s greatest potential is in combinatorial problems, such as selecting the best path between nodes in a graph. It could also be incorporated to select binary values to classify objects — like nodes in a graph — into classes or to select financial stocks that maximize return while minimizing uncertainty. These are just a few of the applications we envision for our
work.”
Wallden was an obvious choice for the project because his primary research interests are in the fields of quantum cryptography, quantum computation, and quantum information theory. When Kyrillidis reached out to Wallden about a research collaboration, he discovered they shared both a fascination with QAOA and a Greek heritage.
“From the beginning, our collaboration felt smooth and natural,” said Kyrillidis. “This is one of the ‘simplest’ scenarios for connections between quantum computing and classical optimization, my own research area. And this property of that type of quantum algorithm setting really intrigued me.”
Their research is funded by a Rice-Edinburgh Strategic Collaboration Award. Kyrillidis and Wallden hope to complete their work in December and publish their findings in 2024.