A computer that harnesses the strange properties of the quantum realm could accelerate artificial intelligence, speed up drug discovery, and allow us to model the impacts of climate change with greater accuracy.
But quantum computing, a dream that is increasingly close to realization, could impact our lives in more everyday ways, too.
“Let’s say a delivery company wants to route packages to a few different cities,” says Rebekah Herrman, an assistant professor in the Department of Industrial and Systems Engineering. The company, she explains, will need to decide on the most efficient way to visit all the locations in the shortest possible time.
Known as the traveling salesman problem, it is “very difficult to solve” without the help of quantum computing, says Herrman, whose research focuses on quantum algorithms, essentially the instructions that are given to quantum computers.
What makes the problem so complicated? One reason is that the number of possible solutions balloons exponentially as the number of cities grows. With just ten destinations on the schedule, that’s already 3,628,800 possible different routes. Ordinary computers struggle to find the quickest journey among this rapidly expanding number of possibilities. And there is no known single algorithm that can be applied to solve every example of the problem, an example of what mathematicians and computer scientists call “combinatorial optimization problems.”
“There’s hope that we can use quantum computing to solve these problems more efficiently,” says Herrman. So what’s stopping us? The main reason is that quantum computers aren’t yet sufficiently powerful. “Right now,” she says, “quantum hardware hasn’t caught up.” Researchers, including those at UT and the Oak Ridge National Laboratory (ORNL), are busy attempting to scale up the technology. In the meantime, though, Herrman and her colleagues are working on mathematical proofs that demonstrate how combinatorial optimization problems can, in theory, be solved by quantum computers.
But why work on the algorithms before we can use them? “The proofs are important for two reasons,” says Herrman, who works in close collaboration with Jim Ostrowski, a professor in ISE. Demonstrating exactly how much faster a quantum computer could solve a problem compared to an ordinary machine tells us a lot about how, exactly, quantum computing could change the world.
Plus, having mathematical proofs in hand helps researchers who are working on hardware. It shows them exactly which physical capabilities will be needed to solve specific problems. “We try to figure out what type of hardware we might want in the future,” says Herrman.
Laying the theoretical groundwork for the quantum computers of the future is vital, and Herrman’s work has been funded by several recent grants, including from the National Science Foundation (NSF), the Department of Energy, and the Department of Defense. The Pentagon, Herrman says, recognizes the importance of quantum algorithms for military logistics. “They are interested in finding efficient ways to perform large-scale computations to advance scientific research,” she says.
The NSF is investing in the next generation of quantum computing researchers, too. Currently, the Foundation is funding an educational project which has allowed UT to welcome undergraduates from across the country for a summer program on quantum algorithms.
Students work in teams to solve an optimization problem, or to mathematically prove or disprove whether optimization problems could be solved by quantum computers. The program, called Quantum Algorithms and Optimization Research Experience for Undergraduates, will run for two more summers.
“We have a great group here at UT studying quantum algorithms,” says Herrman, who is passionate about “the opportunity to get more students interested in quantum.”
Contact
Tomas Weber (tce@utk.edu)