There is no doubt that the future of computing belongs to quantum computers. They are ultra-fast, better at solving complex problems and at multitasking than ordinary computers. But what types of applications will be best for quantum computers remains an open question.
Recently, a team of researchers has demonstrated that quantum computers could be useful for speeding up the solutions to what is called “semidefinite programs.” These are simply a widely used class of optimization programs, which include linear programs. The researchers also presented a new quantum algorithm that could speed up the solutions to semidefinite problems.
“One of the goals of quantum computing is to speed up computations to levels that far exceed what classical computers can do,” said Fernando Brandão, the Bren Professor of Theoretical Physics at Caltech and of the researchers. And this is where the quantum algorithms come in.
The new algorithm could greatly speed up semidefinite programs that are used to learn unknown quantum states. This could help researchers better understand the strange and still largely unexplored states of the subatomic world.
The new study is titled “Quantum Speed-ups for Semidefinite Programming” and was funded by Microsoft, Caltech, and National Science Foundation.