Quantum computers of the future hold promise for solving complex problems more quickly than ordinary computers. For example, they can factor large numbers exponentially faster than classical computers, which would allow them to break codes in the most commonly used cryptography system. There are other potential applications for quantum computers, too, such as solving complicated chemistry problems involving the mechanics of molecules. But exactly what types of applications will be best for quantum computers, which still may be a decade or more away from becoming a reality, is still an open question.
In a new Caltech study, accepted by the Institute of Electrical and Electronics Engineers (IEEE) 2017 Symposium on Foundations of Computer Science, researchers have demonstrated that quantum computing could be useful for speeding up the solutions to “semidefinite programs,” a widely used class of optimization problems. These programs include so-called linear programs, which are used, for example, when a company wants to minimize the risk of its investment portfolio or when an airline wants to efficiently assign crews to its flights.
The study presents a new quantum algorithm that could speed up solutions to semidefinite problems, sometimes exponentially. Quantum algorithms are sets of instructions that tell quantum computers what to do to solve problems.
“One of the goals of quantum computing is to speed up computations to levels that far exceed what classical computers can do,” says Fernando Brandão, the Bren Professor of Theoretical Physics at Caltech. Brandão’s co-author is Krysta Svore of Microsoft, which partially funded the study.
The new quantum algorithm would, in particular, greatly speed up semidefinite programs that are…