Using quantum computing to speed up optimization problems

How quantum computers are being used to speed up optimization problems using a recent breakthrough from D-Wave.
Tejasri Gururaj
A 3D render of a futuristic glowing quantum computer.
A 3D render of a quantum computer.


  • Quantum computers promise mind-boggling capabilities.
  • They are particularly well-suited for tackling optimization problems, thanks to the increased computing speed they offer.
  • D-Wave has recently demonstrated that their quantum annealing system offers enough speed to take on these problems.

With its seemingly limitless potential to solve complex problems much faster than classical computers, quantum computing holds a great deal of promise.

One area where quantum computing has already made advances is in its ability to rapidly find solutions for optimization problems.

D-Wave is a leader in quantum computing equipment, software, and services, and is the world's first commercial supplier of quantum computers. Recently, D-Wave achieved a milestone by demonstrating coherent quantum spin-glass dynamics on an astounding 5,000+ qubits.

This achievement not only validates the power of quantum computing but also opens the door to a new era of possibilities in solving optimization problems.

Interesting Engineering (IE) spoke to Murray Thom, Vice President of Quantum Business Innovation at D-Wave, about their achievement, which we will discuss later in the article.

But first, let's start at the beginning.

What are optimization problems?

We have all actually heard of or worked on an optimization problem — even if we don't realize it. Whether it's planning the most efficient route for a road trip, maximizing profits in business operations, or designing an energy-efficient building, optimization problems are all around us.

Using quantum computing to speed up optimization problems
Planning the most efficient route for a road trip is an example of an optimization problem.

These challenges involve finding the best possible solution within certain limitations or constraints. Typically, there is an objective function that represents the quantity to be optimized. This may represent a value that needs to be maximized (profit, efficiency, or utility) or minimized (cost, time, or error). There are also decision variables that define the possible choices or solutions.

For instance, imagine you are planning a cross-country adventure with multiple destinations. The goal is to visit as many places as possible on your list while minimizing the overall distance traveled and the time spent on the road. This classic 'traveling salesman problem' is a prime example of an optimization challenge.

Optimization problems arise in a variety of fields and industries, from engineering and finance to logistics and artificial intelligence.

Quantum-assisted optimization

The challenge with optimization problems is that, as the number of variables and constraints increases, finding the optimal solution becomes increasingly complex.

Using quantum computing to speed up optimization problems
Quantum computing could speed up algorithms for solving the traveling salesman problem.

Classical computers have been used to tackle optimization problems. But some of these problems become computationally difficult as their size grows. This is where quantum computing holds promise.

"A quantum computer is a device that accelerates calculations by using quantum mechanical effects. So how does it make use of quantum effects to accelerate calculations? In this model of a quantum computer, it leverages these effects to explore solutions more quickly than a classical computer can," explained Thom.

Quantum computers can solve optimization problems at an exponentially faster rate than classical computers. One of the ways they achieve this is by using quantum parallelism, which allows quantum computers to perform multiple calculations simultaneously.

While quantum computers excel at solving certain specific mathematical problems exponentially faster than classical computers, they also currently face challenges, such as susceptibility to errors, limited qubit connectivity, and hardware constraints.

As a result, fully utilizing the power of quantum computing for complex optimization problems is not always straightforward.

Using quantum computing to speed up optimization problems
A quantum computer.

Hybrid quantum-classical algorithms leverage the capabilities of quantum computers to speed up specific optimization components while employing classical methods for complementary tasks. They are used either because the quantum resources are not currently sufficient to address the entire problem or because classical methods are better suited for certain parts of the optimization process.

This approach allows researchers to exploit the advantages of quantum computers while at the same time gaining a significant advantage over classical algorithms. This quantum-assisted optimization could open up new avenues for tackling real-world challenges across industries.

Quantum annealing

All natural systems 'want' to remain in a minimum energy state; this is a fundamental law of physics. Nature tends to optimize the energy of a system so that it is at a minimum.

Using quantum computing to speed up optimization problems
An object will always tend to move towards 1, as it is the lowest energy state.

Similarly, quantum annealing is an optimization process which uses quantum mechanics to find the lowest energy of any given system. By doing so, we can identify the optimal or nearly optimal combination of variables that results in the lowest possible energy configuration. 

The term annealing is borrowed from metallurgy, where a material is annealed, which is to say, heated and then slowly cooled, to achieve a highly ordered crystal structure (the low-energy state) while minimizing defects. 

In quantum annealing, a quantum system is evolved to reach its lowest energy state, corresponding to the solution of the optimization problem.

D-Wave's quantum annealers have been at the forefront of this field, with the company announcing its first commercial quantum annealer in 2011, the D-Wave One™. More recently, the company announced that it had successfully demonstrated coherent quantum spin-glass dynamics on a 5,000+ qubit system, using quantum annealing.

Using quantum computing to speed up optimization problems
D-Wave has been at the helm of developing quantum computers based on annealing.

"D-Wave's quantum annealing system has demonstrated a significant speedup over classical computing for complex problems. The observed speedup matches the theory of coherent quantum annealing, showcasing a direct connection between coherence and quantum annealing's computational power," said Thom, explaining the significance of their research. 

The research was a collaboration between scientists at D-wave and Boston University, with the study being published in Nature.

However, it's essential to note that quantum annealing, while adept at tackling specific optimization problems, may not speed up all of them. The efficiency of quantum annealing heavily depends on the structure of the problem and its compatibility with the annealing process.

Quantum annealing's true power emerges when dealing with optimization challenges that exhibit rugged landscapes or involve finding the ground state of a complex energy landscape. These are precisely the types of problems where classical optimization methods often face limitations and quantum annealing can shine.

Using quantum computing to speed up optimization problems
Quantum annealing (blue line) explores energy landscapes effectively by utilizing quantum tunneling to find the global minimum.

A coherence milestone

Coherence is fundamental in quantum computing to ensure that a quantum system remains uninterrupted and stable throughout its calculations. This is especially important when dealing with large-scale quantum systems, as interference can degrade the quantum state. 

Thom shed light on the importance of coherence in quantum computing, saying, "For a quantum system to be coherent, its quantum state must remain uninterrupted and free from interference. Even the smallest factors, such as individual photons of light interacting with the quantum processor, can degrade coherence. Demonstrating coherence at a 5,000 qubit level without any interference is a significant milestone for large-scale engineered quantum systems."

"Coherent quantum dynamics, in contrast to classical algorithms, can be illustrated with a metaphor. In an optimization problem, you encode penalties and incentives to guide your search for the best solution."

"Imagine yourself navigating the peaks and valleys of the Sahara Desert, searching for the lowest valley. A classical computer would need to individually check each grain of sand, which is a time-consuming process."

"In contrast, a quantum computer acts like a storm cloud raining over the entire desert, swiftly measuring all valleys at once and collecting in the lowest ones. Quantum dynamics determine the rate at which the water collects and permeates, ultimately leading to the lowest valleys."

Using quantum computing to speed up optimization problems
The Advantage™ system by D-Wave was used to conduct the experiment.

The experiment

The researchers conducted an experiment using a material called spin glasses. Spin glasses are materials with disordered magnetic moments (or spins). Their aim was to understand how D-Wave's quantum annealer can find the lowest-energy state of these materials.

The researchers first validated the quantum annealing technique on small spin glasses and found it matched the theoretical predictions. Then, they scaled up their experiment to study spin glasses using thousands of quantum bits (qubits).

Their findings showed that quantum annealing can outperform classical algorithms in finding the lowest-energy state of these complex materials. This demonstrates the potential power of quantum annealing for solving large-scale optimization problems and performing complex simulations that are difficult for classical computers.

Looking to the future

As we delve deeper into quantum computing and quantum annealing, the research conducted by D-Wave could mark a significant milestone for the quantum industry. 

This research may also provide evidence that quantum computing can provide an advantage in optimization, validating a previously theoretical concept. Thom noted, "It has never previously been proven that you can provide an advantage with quantum computing and optimization; it's only ever been a theory."

The applications of quantum annealing also extend to the real-world. From optimizing supply chains and employee scheduling to e-commerce delivery, missile defense, designing new proteins, fraud detection, and industrial manufacturing, quantum annealing presents a potentially transformative technology with broad applications.

However, as with any emerging technology, quantum computing still faces significant challenges that need to be addressed. 

Using quantum computing to speed up optimization problems
Quantum error correction codes are being built to manage the noise that quantum computers pick up.

One of the most significant challenges is the problem of error correction. Quantum systems are highly susceptible to noise and disturbances, which can introduce errors in calculations. Developing robust error correction techniques is crucial for building reliable and practical quantum computers.

Another challenge lies in scalability. While D-Wave's 5,000+ qubit system is an impressive feat, scaling quantum annealing to even larger systems will require overcoming significant engineering and technical hurdles. Ensuring coherence and stability in such large-scale quantum systems remains a complex task.

Despite these challenges, the potential of quantum annealing for optimization problems looks very promising.

Add Interesting Engineering to your Google News feed.
Add Interesting Engineering to your Google News feed.
message circleSHOW COMMENT (1)chevron
Job Board