Using quantum computing to speed up 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.

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.

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.

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.

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.

"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.

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."

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. 

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.