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.”

The hypertree subgraph seen by the QAOA at p = 2 for the hyperedge (1, 2, . . . , q) on a (D + 1)-regular q-uniform hypergraph with girth > 2p + 1, for q = 3 and D = 2. (from Joao Basso et al, 2022)

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.”

Related News

More UChicago CS stories from this research area.
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
UChicago CS News

EPiQC Post-Doc Pens Op-Ed on Potential of Quantum Computing for Chemistry

Jun 24, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

UChicago CS Spinout Acquired by Quantum Ecosystem Leader ColdQuanta

May 10, 2022
UChicago CS News Quantum Computing Benchmark Receives Best Paper Award

Apr 14, 2022
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
UChicago CS News

In-Fridge Controller Could Scale Up Quantum Computers, Award-Winning UChicago Research Finds

Jan 10, 2022
UChicago CS News

EPiQC Research Receives Best Paper Award at IEEE Quantum Week

Oct 22, 2021
UChicago CS News

UChicago and EPiQC Alum Yongshan Ding Joins Yale in Faculty Position

Oct 08, 2021
UChicago CS News

Five UChicago CS Students Named to Siebel Scholars 2022 Class

Sep 23, 2021
UChicago CS News

UChicago Researchers Excel in IBM Quantum Open Science Challenge

Jul 30, 2021
UChicago CS News

Largest-Ever DSI Summer Lab Adds 55 Students, New Social Impact Track

Jul 13, 2021
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube