Developing quantum algorithms for optimization problems

July 26, 2017 by Whitney Clavin, California Institute of Technology
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

New device for symmetry-breaking-induced optical nonlinearity

November 21, 2018

Second-order nonlinear optical processes play a pivotal role in both classical and quantum applications, ranging from extension of the accessible frequencies to generation of quantum entangled photon pairs and squeezed states. ...

Millimetre waves for the last mile

November 21, 2018

Reseachers at ETH Zurich have developed a modulator with which data transmitted via millimetre waves can be directly converted into light pulses for optical fibres. This could make covering the "last mile" up to the internet ...

Reducing the impact forces of water entry

November 20, 2018

When professional divers jump from a springboard, their hands are perpendicular to the water, with wrists pointed upward, as they continue toward their plunge at 30 mph.

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.