A postdoctoral researcher in the Joint Center for Quantum Information and Computer Science (QuICS) is trying to understand the power of quantum computers by expanding a set of conventional—and imaginatively named—tools.
Although quantum computers would be able to simulate complex physics and factor large numbers faster than their modern counterparts, researchers are not entirely sure where their advantages begin and end.
The quest to chart this landscape has introduced Cedric Lin, a QuICS Hartree Fellow, to a collection of computational problems named after the legendary King Arthur and the wizard Merlin, as well as theoretical models of quantum computers that involve imaginary live bombs.
Lin says that these theoretical approaches can help etch out the boundaries between quantum computers and ordinary computers. And they offer a blend of computer science and physics that Lin found appealing even as an undergraduate. “It ended up just happening that there was this field that combined math, computer science and physics together,” Lin says, “and I find it very interesting.”
A common way to study the capabilities of computers is to consider how much time an algorithm needs to solve a particular problem. However, it is often difficult to prove relationships between groups of problems that run within a certain amount of time or that use only a certain amount of memory. “We don’t even know if P equals NP,” Lin says, referring to the notoriously difficult theoretical question about the relationship between problems that can be answered quickly and problems whose answers can be verified quickly.
Lin instead studies query complexity—the number of times an algorithm uses a subroutine whose inner workings are unknown. Such “oracle” algorithms aren’t necessarily useful in practice, but they provide an easier way to prove statements about the power of quantum computers than do time or memory considerations, Lin says.
The quantum query complexity is a standard way of capturing the power of a quantum computer, and it is represented by the number of questions an algorithm must pose to an oracle to solve a problem. As a graduate student at the Massachusetts Institute of Technology, Lin studied the query complexity of an invented model: the bomb query model. That model, which was inspired by a quantum test that can determine if a bomb is live without touching it, has a restriction that ordinary quantum computers don’t have. If part of an algorithm produces a certain output, the computation fails, as if a bomb has exploded.
Lin and a colleague proved that this restricted model needs more queries to solve a problem than an ordinary quantum computer. In particular, the bomb query complexity is the square of the standard quantum query complexity. But, more importantly, their result provided a new theoretical tool for investigating the limits of quantum computers. “Once you restrict things, it’s much easier to prove statements about the different models,” Lin says.
As a postdoctoral fellow at QuICS, Lin has turned his focus to a group of problems known collectively by the name Quantum Merlin-Arthur (QMA). Problems in this collection have answers that can be checked quickly using a quantum computer. A common physics problem—finding the lowest energy configuration of a system of quantum particles—falls into QMA.
Lin and his QuICS colleague Bill Fefferman considered a variant of QMA, which amounts to finding the lowest energy of a system of particles when the next lowest energy is barely any bigger. Intuitively, this makes the problem much harder to solve, since figuring out which energy is lowest requires calculating it to a higher precision.
Lin and Fefferman found that this variant of QMA is equivalent to the collection of problems whose only restriction is that they be solvable using a reasonable amount of memory on everyday computers—a collection that contains many problems known to be hard. The result provides clear evidence that there is a jump in the difficulty of QMA problems when the spacing between energy levels gets very small, a fact that could interest many physicists.
“Cedric’s bomb complexity model makes a very clever connection between quantum measurement theory and quantum algorithms,” says Andrew Childs, professor of computer science and co-director of QuICS. “He has continued to innovate since joining QuICS and is making great progress on hard questions about the power of quantum computers.”
QuICS is a partnership between the University of Maryland and the National Institute of Standards and Technology. It is one of 16 centers and labs within the University of Maryland Institute for Advanced Computer Studies.
—Story by Chris Cesare