The quantum computers have arrived, but they still have issues. Despite incredible promise, the quantum architectures available today remain limited in scale and handicapped by error and noise, falling short thus far of the killer app that would launch a new era of computing. With a new NSF CAREER Award, UChicago Computer Science Assistant Professor Bill Fefferman will pursue the theory and algorithms needed to leap this hurdle, discovering the unique talents that even today’s imperfect quantum computers can do better than their classical counterparts.

The CAREER Award is the National Science Foundation’s most prestigious program for early-career faculty, given to candidates with the potential to advance their field through research and education. Fefferman, who joined UChicago CS in 2019, has already established himself as a promising figure at the intersection of quantum computing theory and experimentation.

In previous work at the University of California, Berkeley, Fefferman helped establish that a task called quantum random circuit sampling could hold the key to demonstrating “quantum supremacy” — proof that quantum computers can solve problems that would be prohibitively time-consuming or even impossible for a classical computer. When Google claimed in 2019 that it had demonstrated this important achievement with their 53-qubit machine, they used this task, though observers (including Fefferman) remained skeptical but cautiously optimistic.

Either way, quantum random circuit sampling is a bit contrived, Fefferman says, without obvious applications beyond comparing quantum and classical computers. For the field to continue its explosive growth, a more useful problem-solving task must be found. And while theorists have already created unique algorithms solvable by the theoretical, much larger quantum computers of the future, there’s an urgent need for practical quantum advantage on the machines available today.

“My proposal is about how we can take the lessons that we've learned from quantum supremacy research, which is not a priori about solving a useful problem, and turn that around, so that we can solve this eventual goal of obtaining a dramatic quantum advantage for a useful computational problem,” Fefferman said.

To begin, he’ll return to the quantum random circuit sampling problem, examining it through the lens of “noisy intermediate scale quantum” (NISQ) computers — the small, error-prone hardware that is available today. While Fefferman’s previous work established that a hypothetical “noiseless” quantum computer could beat any classical computer on this task, the theory is less developed for the actual machines available to researchers today and in the near future.

“We're seeing exciting devices being built at a reasonable scale, where, for the first time, we really expect that they are solving problems that are past the capabilities of a reasonable classical computer,” Fefferman said. “But the main hurdle that we're trying to get over is the effect of uncorrected noise and errors in these quantum systems, and whether or not there's still a quantum advantage when we model these imperfections.”

By determining the theoretical capabilities of today’s limited systems on the quantum random circuit sampling task — and how hard it would be for a classical computer to match this presumably lower bar — Fefferman hopes to reveal insights that could then be transferred to more useful algorithms for the existent quantum computers. For now, he’s tight-lipped on what those specific problems might be, as that pursuit is one of the hottest challenges in the field. But he’s confident that better characterizing the limitations of noise and restricted resources on the current vanguard will help realize the promise of quantum computing more quickly.

“First we're trying to solidify the foundations for why we believe these existing quantum computers have solved, or will solve in the very near term, hard problems,” Fefferman said. “But that's not enough. We really want to take that next step and use the theory developed for these initial demonstrations as a basis for something of great utility.”

The CAREER award will also support Fefferman’s mentoring and teaching of future quantum computer scientists in this very new and fast-growing field. In Spring 2020, Fefferman debuted his new “experimental quantum complexity theory” course, which he hopes to expand to undergraduates with diverse backgrounds from across the sciences.

“What I’m trying to get across is this idea that we can teach quantum computing and be both theoretically deep and experimentally relevant,” Fefferman said. “Currently, we have these brilliant classes on the theory of quantum computing, but they do not address experimental implementation. We also have classes where students learn hands-on practical things, but they are less focused on the theory — what you would actually do with these computers and how you can argue rigorously that they're solving a difficult problem. My goal is to put theory and practice together. This will lead us to new ideas at the intersection of computer science, math, and physics, which will be crucial for the future of quantum computing.”