Bill Fefferman, a postdoctoral researcher in the Joint Center for Quantum Information and Computer Science (QuICS), uses quantum complexity theory to identify problems that quantum computers can solve more efficiently than classical computers.
While there are quantum algorithms for difficult computational problems like factoring integers, theorists do not have a formal proof that classical computers—currently in use today—cannot efficiently solve this problem.
Fefferman works on finding problems that even the most sophisticated classical computers wouldn’t be able to solve efficiently.
“We believe that quantum computers can efficiently solve problems that cannot be solved classically, but that’s actually a conjecture we can’t prove at the moment,” he says. “What I do is try to make that belief rigorous, showing formally that quantum computers can do things classical computers can’t.”
To this end, Fefferman looks for problems that are provably more difficult than factoring but that quantum computers can still solve. He is also interested in practical problems that researchers can test on existing quantum computers.
A lot of theoretical work focuses on algorithms that only idealized, large-scale quantum computers could solve, but Fefferman has more immediate uses for more limited existing forms of quantum computation.
“My interest is to focus on problems we can solve currently with our present quantum devices,” he says, “and then still show that these problems are still interesting and useful on a theoretical level.”
Once researchers establish what quantum computers can do, it will also be easier to determine what they can’t do, he says. This will be important for quantum and post-quantum cryptography, another interest of Fefferman’s.
Most of modern cryptography is based on the presumed hardness of factoring, which quantum computers would easily be able to solve. A new method of encryption that even quantum computers can’t break will soon be necessary, he says.
Stephen Jordan, a QuICS fellow and a physicist at the National Institute of Standards and Technology (NIST), says Fefferman works with great care on substantial problems in his field.
“Bill studies some of the most foundational questions about quantum computing,” he says. “In particular, he is carrying out a long-term research program to clarify the power of quantum computers relative to classical computational complexity classes such as NP [nondeterministic polynomial time] and its generalizations. This is an ambitious project requiring much patience and persistence.”
Fefferman began working in QuICS in September 2014 after receiving a Ph.D. in computer science at the California Institute of Technology.
QuICS is a partnership between the University of Maryland and NIST. It is one of 16 centers and labs in the University of Maryland Institute for Advanced Computer Studies.
—Story by Joe Zimmermann