First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022
As technology companies race to build bigger and better quantum computers, a parallel pursuit seeks the algorithms and applications that will make those new architectures truly revolutionary. One benchmark is the perennial computational problem of optimization, used for everything from logistics to engineering to finance. Where classical computers struggle with optimization in complex systems, quantum computers may provide a new shortcut.
Before he started at UChicago CS, first-year PhD student Kunal Marwaha was part of a multi-institutional team that mathematically tested the potential of a leading candidate: the quantum approximate optimization algorithm (QAOA). Their research received an Outstanding Paper Award at the upcoming Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC).
“There are still a lot of questions about what we can use quantum computers for,” Marwaha said. “We’re making progress on the engineering side, but we’re still uncertain about what they might be good for, or how much more powerful they’ll be than regular computers. In this line of research, we try to understand if optimization is a good use case for quantum computing, and if so, whether the QAOA is a good algorithm to use.”
One of Marwaha’s co-authors, Edward Farhi of MIT, first published the QAOA in 2014. The QAOA is designed to work on near-term architectures that should be available in the next decade, perhaps providing an early example of meaningful “quantum advantage.” Since its publication, Farhi and others have mathematically analyzed whether the algorithm performs better than its classical counterparts, with mixed results.
“There have now been two instances where the QAOA performed better than every known algorithm; but later, we found new competitive classical algorithms,” Marwaha said. “It’s a healthy rivalry, because the race is improving what we can do with algorithms for optimization.”
The newest paper takes that mathematical evaluation further than ever before. The QAOA operates in steps, with each pass coming closer to the best possible solution. For the first time, Marwaha, Farhi, and their co-authors Joao Basso (Google), Benjamin Villalonga (Google), and Leo Zhou (Caltech) were able to analyze the QAOA up to 20 steps on a canonical optimization problem called Maximum Cut. Because today’s quantum computers aren’t powerful enough to run the algorithm — and a typical consumer computer maxed out at around 15 steps — the authors borrowed computational resources from Google to do the analysis.
“This is one of the first times we’ve been able to study the QAOA at high depth,” Marwaha said. “That gives us better tools to get to the bottom of the question: is the QAOA useful or not? I think it’s important to know either way, because if it’s useful, let’s keep studying it and let’s keep applying it. If it’s not, let’s redirect our money and attention towards other potential uses for quantum computing.”
Marwaha will continue exploring these questions at UChicago CS, with assistant professor Bill Fefferman as his advisor. With Fefferman also searching for the first evidence of quantum advantage, as well as the department’s connections with EPiQC and the Chicago Quantum Exchange, Marwaha is excited to continue exploring and building quantum computing’s future.
“For me, the motivator is: Quantum computers are coming, but we don’t know what to use them for, and we don’t know how powerful they are,” Marwaha said. “This work was a great way to get started. I’d like to dive deeper into the limitations of quantum computers and how that relates to classical computers, both by studying quantum algorithms and by thinking about complexity.”
