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 CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
In the News

Alumnus Pranav Gokhale Named to Crain’s 40 Under 40

Nov 07, 2022
UChicago CS News

Prof. Diana Franklin Discusses Quantum Computing Education on Entangled Things Podcast

Nov 03, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

High School Students in College Prep Program Visit UChicago CS

Aug 23, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
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
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