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