How a Quantum Computer Solves Optimization Problems

In Search of the Shortest Route

A tangle of bright red cables encircles an unassuming chip in the center. This is the Advantage2 quantum annealer from D-Wave. This quantum computer specializes in optimization problems: tasks that require weighing countless possibilities against each other and quickly push even modern supercomputers to their limits.

The Advantage2 quantum annealer from D-Wave is designed to solve complex optimization problems. © D-Wave

A simple example of an optimization problem is finding the best route for a vehicle in a city. Only a few variables play a role, such as the distance or the current traffic situation. However, if this problem is applied to all traffic, it quickly becomes significantly more complex. Suddenly, the routes of hundreds or thousands of vehicles must be coordinated to minimize the overall travel time.

Somewhere Between a Mountain and a Valley

Such tasks can be described as a landscape with hills and valleys. Each possible solution corresponds to a point in this landscape. The height of the point indicates how good or bad that solution is. High hills represent unfavorable results with high costs, while deep valleys represent particularly good solutions. The goal is to find the lowest point.

Classical optimization methods often proceed stepwise downhill, starting from a randomly chosen starting point. This approach can lead to good results, but it carries a risk. The method can end in a valley that, while better than the surrounding terrain, is far from the best solution. Higher hills then block the way, even though significantly deeper valleys might lie beyond them.

Aid from quantum mechanics

A quantum annealer, in turn, uses the laws of quantum mechanics, the physics of the smallest particles. In this world, different rules apply than in everyday life. Particles can exist in multiple states simultaneously and "tunnel" through valleys. This means they can move through seemingly insurmountable barriers. Quantum computers take advantage of these special properties.

Instead of starting at a single point, the quantum annealer begins at many points in the landscape simultaneously. This allows it to pursue different solutions in parallel, gradually move toward better results, and tunnel through challenging sections. This reduces the risk of getting stuck early on an unfavorable solution.

Quantum annealers are used where many decisions need to be made simultaneously. Examples include modeling molecules in the development of new drugs or improving the planning of supply chains or power grids. Florida Atlantic University has now installed a large, publicly accessible quantum computer, the Advantage2 quantum annealer, directly on campus.

Source: Florida Atlantic University