If the future of computing is quantum, theorists are the fortune tellers. Basically the entire concept of quantum computing can be traced back to a lecture given by famed theoretical physicist Richard Feynman in 1981, and theorists such as Umesh Vazirani, Paul Benioff, and Peter Shor figured out powerful applications of quantum computers long before they existed in even simplified form. Today, as quantum computers approach the milestone known as “quantum supremacy,” theory provides both a critical measuring stick and a roadmap to realizing the potential of this new approach.
One of those important benchmarks was analyzed by Bill Fefferman, a new assistant professor in the University of Chicago Department of Computer Science, and collaborators from his previous position at the University of California, Berkeley. In a paper last year for Nature Physics, Fefferman and his co-authors gave some of the strongest evidence that "random circuit sampling" should be easy for quantum computers but almost impossibly hard for their classical counterparts.
That paper gained renewed attention last month as gossip spread that Google had achieved quantum supremacy with a 53-qubit computer, using random circuit sampling as the test. Suddenly, Fefferman found himself fielding media calls on whether Google’s claim was verified. His answer: the jury is still out, but true quantum supremacy or not, we’re at an exciting time for quantum computation.
“I would call ‘quantum supremacy’ a starting point for the field; it's not the end goal, because we're not necessarily solving a useful problem.” Fefferman said. “But the tools that have been developed for it will be useful down the road for new applications. The next goal is to solve a hard task that is also rich in use value, because if it's useful but easy for classical computers, you would just use a classical computer.”
Fefferman first dove into complexity theory as a UChicago undergraduate in computer science and mathematics. When he started his PhD work at Caltech — Feynman’s home for much of his career — he discovered that much of that theory applied to the accelerating field of quantum information science, and started working with physicists and engineers who were paving the path toward building the first scalable quantum computers.
“It was very clear to me that the most exciting stuff was combining the sort of theoretical insights that I had been thinking and learning about with what was actually happening,” Fefferman said. “Talking with the physicists at Caltech was really instrumental, because they were the ones who said, ‘Wait a second, these results that you're talking about are really interesting, but what if we made them a little more realistic and a little bit more relevant to the physics?’”
That pursuit goes beyond benchmarks for quantum supremacy to new theory about how to deal with the biggest limitation of existing and near-future quantum computers: noise. The inherently fragile nature of qubits — the quantum counterpart to traditional computer bits — means that the accuracy of quantum calculations can suffer, limiting their use for simulation and optimization tasks. Figuring out novel theoretical approaches for reducing or working around this noise could lead to new algorithmic and engineering solutions that allow quantum computers to simulate molecular systems, unlocking their potential for physics, chemistry, and the design of new materials or drugs
“The original reason that Feynman proposed a quantum computer was to do quantum simulations,” Fefferman said. “His insight was just, if we want to simulate quantum mechanics, we probably need a programmable quantum computer. I think that going forward, that's what we're going to try to think about: what is the best way to simulate various quantum mechanical systems with a reasonably small quantum computer? I think that this inherently has a lot of use value.”
Fefferman is also interested in the theoretical side of quantum computing’s most-hyped “killer app” — the ability, outlined by Shor’s algorithm, to break today’s cryptography systems based on the computationally difficult task of integer factorization. Last year, he received a Young Investigator Award from the Air Force Office of Scientific Research to study the computational power of near-term quantum experiments as well the future of "quantum-safe cryptography.”
At UChicago he will work with colleagues studying quantum computing in the Departments of Computer Science and Physics, as well as the Chicago Quantum Exchange, a regional research hub based at the Pritzker School of Molecular Engineering with partners spanning national laboratories, universities, and industry. He’s also excited to develop both undergraduate and graduate courses that train tomorrow’s quantum computer scientists, taking students from the basics of quantum mechanics up to quantum supremacy, Shor’s algorithm, and the other approaches that these computers aspire to run in the future.
“I think Chicago is uniquely positioned to be a powerhouse in this field of quantum computing; we have all the pieces,” Fefferman said. “I see myself as sitting between a lot of those pieces, and I'm really excited to play the role of translator between many of these different areas.”