Planning a vacation with a group of people can quickly turn into a nightmare. One traveler may really want to catch some rays at the beach, while another might want to hit the slopes. All the while, everyone needs to match schedules and stick to a budget.
This kind of problem—trying to juggle many demands and come up with an agreeable plan—is called constraint satisfaction, and it impacts everything from family vacations to airline staff scheduling. In general, it can be time-consuming to solve, and there are even versions where the constraints are partially or fully unknown.
Aarthi Sundaram, a recently arrived Hartree Postdoctoral Fellow at the Joint Center for Quantum Information and Computer Science (QuICS), studied these problems in graduate school and plans to investigate them further at QuICS. Instead of always considering concrete scenarios like a vacation, Sundaram phrases the problems in the language of math, allowing abstract constraints to stand in for everyday concerns. Her goal has been to understand the limits of using computers to solve these problems—including whether future quantum computers will offer any advantages.
Such problems don’t just catch the eye of computer scientists. Physicists, too, use the language of constraint satisfaction problems to categorize and classify some states of matter, a connection that drew Sundaram in when she was first introduced to it as a computer science undergraduate at the Birla Institute of Technology and Sciences in India. It’s what ultimately attracted her to quantum information, a field that mixes computer science with physics. “A lot of innovation happens at the intersection of different fields,” she says. “There's a fascinating push and pull of ideas and techniques.”
After earning a master’s degree in math, Sundaram received a Ph.D. in computer science at the Centre for Quantum Technologies (CQT) in Singapore. It was there that she became fascinated by constraint satisfaction problems and the differences between ordinary versions of the problem and their quantum analogs.
One of the simplest examples of constraint satisfaction is 2-SAT, in which each constraint affects only two variables. It’s like planning a road trip with a bunch of couples and trying to agree on a weekend that everyone has free. Each variable signifies a yes or a no, which can be represented by a bit that’s 0 or 1.
The 2-SAT problem is easy to solve with a regular computer, but it was unclear if the quantum version of the problem was just as simple. There were reasons to suspect it wasn’t. For example, in the quantum case, the constraints affect pairs of qubits instead of bits. Unlike ordinary bits, qubits can be a 0, a 1 or any combination of the two. Additionally, while constraints for the ordinary problem are either satisfied or unsatisfied, quantum constraints can be partially satisfied. But although this quantum nature seems to present new challenges, Sundaram and several colleagues showed that it was possible to solve quantum 2-SAT just as fast as ordinary 2-SAT.
At CQT, Sundaram also studied conventional constraint satisfaction problems with a twist: hidden constraints. When even the constraints aren’t known, “suddenly, because you're not getting enough information, an easy problem can become very hard,” she says. Computer scientists attack this kind of problem by imagining that there’s a powerful black box—the inner workings of which are unknown—that knows the constraints and provides feedback on guesses. In addition to saying whether a guess is right or wrong, the black box will reveal a small amount of information to guide future guesses. It wasn’t known how much hiding constraints in this way affected the difficulty of a given problem. Sundaram, together with collaborators, proved that every black box problem with hidden constraints corresponds to a problem with known constraints that is just as difficult, allowing researchers to study these black box problems through the lens of ordinary constraint satisfaction.
Sundaram has already begun to expand this work into a quantum black box model. She also hopes to understand more about the structure of quantum constraint satisfaction problems in general, especially whether there is a smooth or sharp transition between easy and hard problems.
Sundaram says she is excited to work with the many experts at QuICS. “As an early stage researcher, you want to be exposed to as many new ideas as you can,” she says. “You gain more exposure, more knowledge and maybe you get better ideas for your own problems.”
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.
QuICS is a partnership between the University of Maryland and NIST. It is one of 14 centers and labs in the University of Maryland Institute for Advanced Computer Studies.
—Story by Nina Beier