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.

Argonne scientists use AI to identify new materials for carbon capture

Feb 19, 2024

New research unites quantum engineering and artificial intelligence

Jan 29, 2024

Group From UChicago CS To Present Four Papers at Most Prestigious International Quantum Conference

Jan 09, 2024

UChicago Scientists Make New Discovery Proving Entanglement Is Responsible for Computational Hardness In Quantum Systems

Jul 25, 2023

Virtual Bakery Game Serves Up Both Cupcakes and Quantum Concepts For K-12 Students

Mar 27, 2023
Students posing at competition

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023

Assistant Professor Robert Rand Receives Air Force Young Investigator Grant

Dec 19, 2022
Professor Fred Chong advising students

Prof. Fred Chong Reappointed to National Quantum Initiative Advisory Committee

Dec 13, 2022

Professor Fred Chong Named IEEE Fellow

Dec 09, 2022

Associate Professor Diana Franklin Named ACM Distinguished Member

Dec 07, 2022
Haifeng Xu

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
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