Someday, quantum computers may be able to solve complex optimization problems, quickly mine huge data sets, simulate the kind of physics experiments that currently require billion-dollar particle accelerators, and accomplish many other tasks beyond the scope of present-day computers. That is, if they are ever built. But even as daunting technical challenges keep the dream at bay, theorists are increasingly putting the ideas and techniques of quantum computing to work solving deep, long-standing problems in classical computer science, mathematics and cryptography.
“There are quite vigorous debates about whether quantum computers will ever actually be built,” said Chris Peikert, a cryptographer and computer scientist at Georgia Institute of Technology. “But that’s a separate question from whether quantum techniques or quantum algorithms can help you solve problems in new ways.”
In recent years, quantum ideas have helped researchers prove the security of promising data encryption schemes called lattice-based cryptosystems, some applications of which can shroud users’ sensitive information, such as DNA, even from the companies that process it. A quantum computing proof also led to a formula for the minimum length of error-correcting codes, which are safeguards against data corruption.
Quantum ideas have also inspired a number of important theoretical results, such as a refutation of an old, erroneous algorithm that claimed to efficiently solve the famously difficult traveling salesman problem, which asks how to find the fastest route through multiple cities.
“If it only happened once it would be a coincidence, but there are so many instances when we ‘think quantumly’ and come up with a proof,” said Oded Regev, a computer scientist at New York University.
This recurring theme has led some researchers to argue that quantum computing is not an esoteric subfield of computer science, but rather a generalization of classical computing, in much the same way that polygons are a generalization of triangles. Just as polygons can have any number of sides while triangles only have three, quantum computers can perform operations represented by any numbers (positive or negative, real or imaginary), while operations on classical computers use only nonnegative real numbers.
As the more general case, quantum ideas are a powerful tool in developing more specific classical computing proofs. “There are a number of classical problems that have nothing to do with quantum, but that are most easily analyzed by generalizing to the quantum level, proving something using quantum information theory, and scaling back the result to the classical level,” said Ronald de Wolf, a theoretical computer scientist at the Dutch Centre for Mathematics and Computer Science.
Currently, it is estimated that fewer than 5 percent of theoretical computer scientists study quantum computing. But researchers say that recent success from “thinking quantumly” has led a growing number of theorists to brush up on their physics. “These very striking spinoffs of quantum computing have actually drawn classical computer scientists into learning something about quantum computing,” said Scott Aaronson, a theoretical computer scientist at the Massachusetts Institute of Technology.