Computer scientists love to ask simple questions. But those questions often end up being devilishly tough to answer.
For example, deciding whether a given computational problem is easy or hard—whether it can be solved quickly or not—seems straightforward, but for many problems this question remains stubbornly unanswered.
“It’s very hard to prove the non-existence of fast code,” says Shalev Ben-David, a recently arrived Hartree Postdoctoral Fellow at the Joint Center for Quantum Information and Computer Science (QuICS).
Not much about the situation changes if you’re solving a problem on a quantum computer, a device that may one day harness the rules of quantum physics to speed up the solution of certain problems. Figuring out exactly which problems will submit to a quantum computer’s speedy subroutines is a challenge—one that Ben-David has been puzzling over since he took a quantum computing class as a graduate student at the Massachusetts Institute of Technology.
After that class, Ben-David, who studied mathematics as an undergraduate at the University of Waterloo in Canada, began working with his instructor, Scott Aaronson, a computer scientist who specializes in quantum complexity theory. That discipline, which is heavily mathematical and theoretical, appealed to Ben-David, who soon got hooked on its methods and techniques for cataloguing the capabilities of quantum computers.
One way of describing what a quantum computer is up to—the query model—became of particular interest to Ben-David. Instead of counting the number of steps in an algorithm or the amount of time it takes to run some code, the query model just counts the number of times an algorithm needs to reference a description of the problem you want to solve—a piece of data that computer scientists call the input.
It sounds complicated, but the situation arises frequently. If you’re searching through a database for a particular entry, you’ve already got the database. But you might want to know how many entries you need to look through—that is, how many times you need to query the database—in order to find what you’re looking for. In the worst case, an ordinary computer would need to look through all of the entries, but a quantum computer offers a modest advantage for problems like this—something that’s easy to prove in the query model.
Ben-David says that describing algorithms in this way is a kind of sweet spot for proving things about their complexity. “The query model is sort of both rich enough to capture the quantum algorithms we know how to design, but also not so rich that we have no handle on bounding new algorithms,” he says.
The first project Ben-David worked on in grad school examined a restricted set of query model problems in which the inputs are a permutation—basically a reordering—of the numbers 1 through n. That restriction prompts many natural questions about the properties of the input, such as whether the permutation is even or odd or whether the particular permutation has any cycles. In the end, no major quantum advantage was found for answering any of these questions, but the problem had piqued Ben-David’s interest in the query model and got him thinking about what kinds of promises about the input might yield big quantum speedups.
“We know a few cases where quantum computing is useful,” he says, “but if we can hope for the moon then we can hope for a very clean characterization that tells you if your problem looks like this, you get an exponential quantum speedup, and if your problem looks like this, you don’t.”
Around this time, a major result was published that found a new a limit on how much better a quantum computer might do for generic query problems defined on all inputs. It showed quantum computers could offer faster speedups than the quadratic speedup present in the database-searching routine but in general not as good as the most dramatic quantum speedups—things like the exponentially faster period-finding in Shor’s algorithm.
Within 10 days of that result appearing online, Ben-David had improved on its findings by borrowing a key technique, showing a clear quantum advantage for solving a bizarre class of problems. Further refinements of the idea, published with Aaronson and the complexity theorist Robin Kothari, resulted in a new method for proving things about the complexity of problems in the quantum query model—work that earned Ben-David honors at a major quantum information conference and was presented at a top computer science theory conference. That technique, which Ben-David and his co-authors called the cheat-sheet method, boiled down to an elaborate conversion from a problem that has an exponential quantum speedup to a problem that doesn’t. The cheat sheet was a modification to a problem’s input that postulated a way to easily check that the original input had a certain structure.
“This was a really major breakthrough,” says Andrew Childs, a University of Maryland professor of computer science and co-director of QuICS. “It was an open question for more than 15 years whether there could be a superquadratic separation between the randomized and quantum query complexities of total functions. The conventional wisdom was that no such separation should be possible, but Shalev and his coauthors refuted that."
Since these forays into quantum query complexity, Ben-David has started to branch out into other areas of quantum information science, including applying the cheat-sheet method to some quantum communication tasks. He spoke about that work at the most recent Conference on Quantum Information Processing in the Netherlands.
Ben-David says he’s eager to expand his expertise into new areas of quantum complexity, and he looks forward to working more closely with his new colleagues at QuICS.
—Story by Chris Cesare
About the Hartree Fellowship
QuICS offers two-year Hartree Fellowships to exceptional candidates interested in quantum information science and quantum computing. The fellowship is named for Douglas Hartree, a scientist at the National Institute of Standards and Technology (NIST) in the mid-1900s who made substantial contributions to physics and computer science.
About QuICS
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.