Developing quantum algorithms for optimization problems

July 26, 2017 by Whitney Clavin
Designing Computer Software of the Future
Illustration of a quantum computer chip. Credit: iStock

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 . 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 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 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 computing," says Brandão. "We are still far from knowing all the applications of , 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.

Explore further: Five ways quantum computing will change the way we think about computing

More information: Quantum Speed-ups for Semidefinite Programming. arXiv. arxiv.org/abs/1609.05537

Related Stories

The mystery of quantum computers

May 26, 2017

Our computers, even the fastest ones, seem unable to withstand the needs of the enormous quantity of data produced in our technological society. That's why scientists are working on computers using quantum physics, or quantum ...

The exciting new age of quantum computing

October 25, 2016

What does the future hold for computing? Experts at the Networked Quantum Information Technologies Hub (NQIT), based at Oxford University, believe our next great technological leap lies in the development of quantum computing.

Solving systems of linear equations with quantum mechanics

June 9, 2017

(Phys.org)—Physicists have experimentally demonstrated a purely quantum method for solving systems of linear equations that has the potential to work exponentially faster than the best classical methods. The results show ...

Recommended for you

Using optical chaos to control the momentum of light

October 19, 2017

Integrated photonic circuits, which rely on light rather than electrons to move information, promise to revolutionize communications, sensing and data processing. But controlling and moving light poses serious challenges. ...

Black butterfly wings offer a model for better solar cells

October 19, 2017

(Phys.org)—A team of researchers with California Institute of Technology and the Karlsruh Institute of Technology has improved the efficiency of thin film solar cells by mimicking the architecture of rose butterfly wings. ...

Terahertz spectroscopy goes nano

October 19, 2017

Brown University researchers have demonstrated a way to bring a powerful form of spectroscopy—a technique used to study a wide variety of materials—into the nano-world.

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.