Professor Shalev Ben-David completed his PhD at MIT in 2017 under the supervision of Scott Aaronson. He joined the David R. Cheriton School of Computer Science as a faculty member in the summer of 2018 after completing a postdoctoral fellowship at the University of Maryland.
Learn more about his research and where he sees it heading.
Your research interests are in classical and quantum complexity theory. Can you elaborate?
Computational complexity theory is concerned with what we can’t do quickly or efficiently with computers and, in particular, what we can prove that we can’t do quickly or efficiently.
This can be formalized in various ways. One famous problem is the P vs NP problem, which is equivalent to proving that there is no polynomial time algorithm for various problems that happen to be equivalent. We’re far away from proving this — in fact, we don’t know how to show that there’s no polynomial time for almost anything. It’s very hard to rule out the existence of fast algorithms.
A different formalization of efficiency is as follows: Say you had a black box that you could pose questions to. How many questions do you ask it before you can know some properties of the black box? Efficiency here is the number of questions you ask, not how much time is required to process the answers. In this black box model, everything is much easier.
Communication complexity is another area. Say I have my availability for a meeting next week and you have your availability and we want to find a slot where we can both meet to talk. We want to minimize the amount of communication to find such a slot. We could just exchange our entire schedules, but an interesting question is the minimum amount of communication we need to transmit to find an open slot for both of us. Is there a better protocol for finding a meeting slot than exchanging the complete schedules?
These kinds of questions are tractable. We can usually prove things about how much communication is necessary or how many queries to a black box we need to make. The interesting thing is that all these different models of complexity are related to each other, at least a bit. And because they’re related — well, it feels as though we’re climbing the same hill — working on these models might provide some insight into the P vs NP problem.
You also work on quantum computational models. Can you prove things about these models?
Yes, the models make sense mathematically. In other words, we can prove things about quantum computational models. And it looks like quantum algorithms can solve some problems faster than classical algorithms — exponentially faster in some cases.
The problem is, of course, that we can’t rule out fast classical algorithms. This means that we can’t prove that quantum computers are going to be better because maybe a classical algorithm is very fast. But we can prove that quantum algorithms give exponential speedups for some problems in the blackbox or communication models. Of course, to do so we need to define what it means to make a quantum query to a black box or to send quantum communication, but these turn out to have reasonable definitions.
What advantage could quantum computation bring?
The most famous example where quantum computing gives an advantage is factoring. This problem is important because it’s the basis for a lot of cryptography. If you can factor quickly, you can break many types of encryption.
There’s a quantum algorithm — known as Shor’s algorithm — that for a given integer N finds its prime factors. Once quantum computers are available, much of the cryptography we now use will be useless because on a quantum computer this algorithm runs in polynomial time.
Of course, from a complexity theory perspective we don’t know for sure that the cryptography we use now isn’t already useless. It’s possible that a classical algorithm could factor quickly, but we just haven’t found it.
What are your specific interests in quantum complexity?
One question that interests me is understanding the situations in which quantum algorithms help and the situations in which they don’t. In other words, can we characterize the kinds of problems for which a quantum computer would be better than a classical computer?
Breaking cryptography is one example where quantum computers appear to give exponential speed ups. And ironically, it’s the area where we wish quantum computers weren’t better. On the other hand, for other hard problems— like NP complete problems — quantum computers do not appear to give exponential speedups. A quantum computer is not just a faster version of a classical one: it is better at some tasks than others. That’s why it is interesting to try to characterize the kinds of problems that are quantum-friendly.
There are two sides to my research — a quantum side and a classical side. On the classical complexity side, my research is on understanding to what extent we can say there is no fast algorithm for something. On the quantum side, I’m interested in both upper bounds and lower bounds.
What recent work have you published?
We published a paper in which we used a quantum algorithm to argue that there’s no fast algorithm for another problem. It’s a neat result: we used a fast quantum algorithm to show there’s no fast classical algorithm.
Do you have any hobbies?
I play Hex, a strategy board game, but mostly online because the community of players is quite small.
