Developing quantum algorithms for optimization problems

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 used to learn unknown quantum states. Brandão says that this type of "quantum learning" problem is faced by researchers who study large quantum systems in a variety of different systems such as superconducting qubits, which are quantum information units similar to computer bits that would operate based on superconducting technology. The semidefinite programs are used to give a description of how the quantum matter is behaving, and this, in turn, allows the researchers to better understand the bizarre states of the subatomic world.

"This type of application is a good candidate for use in quantum computing," says Brandão. "We are still far from knowing all the applications of quantum computing, and that's part of the excitement—there are possibilities we haven't even dreamed of yet."

The study, titled, "Quantum Speed-ups for Semidefinite Programming," was funded by Microsoft, the National Science Foundation, and Caltech.