How Quantum Annealing Solves Real Optimization Problems

All Notes

Technology

Scrabble tiles spelling ‘SEO’ on a wooden surface. Ideal for digital marketing themes. — Scrabble tiles spelling 'SEO' on a wooden surface. Ideal for digital marketing themes.

How Quantum Annealing Solves Real Optimization Problems

Optimization problems are everywhere. From routing delivery trucks to scheduling factory lines, finding the “best” solution given a set of constraints is a cornerstone of operational efficiency. Many of these problems, especially as they scale, become computationally intractable for even the most powerful classical computers. This is where quantum annealing steps onto the stage.

Unlike the more commonly discussed gate-based quantum computers (like IBM’s or Google’s), quantum annealers are specialized machines designed from the ground up to tackle a specific class of optimization problems. They don’t run Shor’s algorithm or Grover’s search. Instead, they leverage quantum mechanical phenomena to find the lowest energy states of complex systems, which directly map to optimal solutions for your problems.

Let’s unpack how.

The Optimization Challenge: Finding the “Best”

At its core, an optimization problem asks us to find a configuration of variables that either minimizes or maximizes a certain objective function, often subject to various constraints.

Consider a simple example: You’re trying to pack items into a knapsack. Each item has a weight and a value. You want to maximize the total value of items packed without exceeding the knapsack’s weight capacity. This is a classic Knapsack Problem.

As the number of items and constraints grows, these problems quickly become “hard.” Many of them fall into the class of NP-hard problems, meaning there’s no known algorithm that can solve them exactly in polynomial time. For large instances, classical computers often resort to heuristics, approximations, or exhaustive searches that take an unfeasible amount of time.

Quantum Annealing’s Language: QUBOs

Quantum annealers, particularly those from D-Wave Systems, operate on a specific mathematical formulation: the Quadratic Unconstrained Binary Optimization (QUBO) problem.

A QUBO problem aims to minimize a quadratic function of binary variables:

$H(x) = \sum_{i} Q_{i,i} x_i + \sum_{i<j} Q_{i,j} x_i x_j$

Where:

$x_i \in {0, 1}$ are binary variables.
$Q_{i,i}$ are coefficients on individual variables (linear terms).
$Q_{i,j}$ are coefficients on pairs of variables (quadratic terms, representing interactions).

The goal is to find the assignment of $x_i$ values (0s or 1s) that yields the minimum $H(x)$.

Why QUBOs? Because they directly map to the hardware’s architecture. Each binary variable $x_i$ corresponds to a physical qubit, and the coefficients $Q_{i,i}$ and $Q_{i,j}$ correspond to programmable biases on individual qubits and programmable couplings between pairs of qubits. The quantum annealer naturally finds the lowest energy configuration of its qubits, which, by design, corresponds to the solution to your QUBO.

The first step in using a quantum annealer is always to transform your real-world optimization problem into a QUBO formulation. This can be the most challenging part.

Example: A Tiny Maximum Cut Problem

Let’s consider a very simple Maximum Cut (Max-Cut) problem. Given a graph, we want to partition its vertices into two sets such that the number of edges between the two sets is maximized.

Consider a simple graph with three nodes (0, 1, 2) and edges (0,1) and (1,2). We want to assign each node to either set A (represented by 0) or set B (represented by 1).

If node $i$ is in set A, $x_i = 0$. If node $i$ is in set B, $x_i = 1$. An edge $(i,j)$ contributes to the cut if $x_i \neq x_j$. This means $x_i x_j = 0$ and $x_i + x_j = 1$. The contribution of an edge $(i,j)$ to the cut is $x_i(1-x_j) + x_j(1-x_i)$. This isn’t quite a QUBO. A more standard way for Max-Cut is to minimize the “energy” of edges within a partition.

Let $w_{ij}$ be the weight of the edge between nodes $i$ and $j$. The contribution of an edge $(i,j)$ to the cut is $w_{ij}$ if $x_i \neq x_j$. We want to maximize $\sum_{(i,j) \in E} w_{ij} \mathbb{I}(x_i \neq x_j)$.

This can be transformed into minimizing $\sum_{(i,j) \in E} w_{ij} (1 - 2x_i x_j)$. This is a QUBO.

For our simple graph with edges (0,1) and (1,2), assume $w_{01}=1$ and $w_{12}=1$. We want to maximize $1 \cdot \mathbb{I}(x_0 \neq x_1) + 1 \cdot \mathbb{I}(x_1 \neq x_2)$. This is equivalent to minimizing $-(1 \cdot \mathbb{I}(x_0 \neq x_1) + 1 \cdot \mathbb{I}(x_1 \neq x_2))$. Using the QUBO formulation $x_i \in {0, 1}$ for each node, the contribution of an edge $(i,j)$ to the cut is $(x_i - x_j)^2 = x_i^2 - 2x_i x_j + x_j^2$. Since $x_i^2 = x_i$ for binary variables, this is $x_i - 2x_i x_j + x_j$.

So, for edge (0,1): $x_0 - 2x_0x_1 + x_1$ For edge (1,2): $x_1 - 2x_1x_2 + x_2$

Our objective function to minimize (with some scaling and constant removal): Minimize $-( (x_0 - x_1)^2 + (x_1 - x_2)^2 )$ $= -(x_0 - 2x_0x_1 + x_1 + x_1 - 2x_1x_2 + x_2)$ $= -x_0 + 2x_0x_1 - 2x_1 + 2x_1x_2 - x_2$

This gives us the following $Q$ matrix (where $Q_{i,i}$ are linear terms and $Q_{i,j}$ are quadratic terms): $Q = \begin{pmatrix} -1 & 2 & 0 \ 0 & -2 & 2 \ 0 & 0 & -1 \end{pmatrix}$

The problem is to find binary values for $x_0, x_1, x_2$ that minimize $H(x)$.

How Quantum Annealing Works (Conceptually)

Imagine a complex landscape with many hills and valleys, representing the energy states of your problem. The goal of optimization is to find the deepest valley (the global minimum). Classical algorithms often get stuck in local minima, which are valleys that are deep but not the deepest.

Classical Annealing Analogy: Think of annealing in metallurgy. You heat a metal to a high temperature, allowing its atoms to move freely (explore the energy landscape). Then, you slowly cool it down. If cooled slowly enough, the atoms settle into their lowest energy configuration, forming a strong, stable structure. If cooled too quickly, they might get trapped in a higher energy, less stable state.
Quantum Superposition and Tunneling: Quantum annealers start by placing all qubits in a superposition of states, allowing them to effectively explore many solutions simultaneously. Instead of being stuck in a local minimum, quantum mechanics allows the system to “tunnel” through energy barriers to find a lower minimum, or explore multiple paths at once due to superposition.
Adiabatic Evolution: The process starts with a simple, known ground state (all qubits in superposition). Then, over time, an external magnetic field is slowly changed to morph this simple energy landscape into the complex energy landscape that represents your specific QUBO problem. This slow transformation is called “adiabatic evolution.” According to the adiabatic theorem, if the transformation is slow enough, the system will remain in its ground state throughout the process, eventually settling into the ground state of the problem Hamiltonian (your QUBO).
Finding the Global Minimum: At the end of the annealing process, a measurement is taken. Due to the adiabatic evolution, the probability of measuring the system in its global minimum (the optimal solution to your QUBO) is very high.

The “quantum” advantage is believed to come from this tunneling and the ability to avoid getting trapped in local minima more effectively than classical algorithms, especially for specific types of “rugged” energy landscapes.

Real-World Applications (with D-Wave’s Systems)

While quantum annealing is still an emerging field, D-Wave has been at the forefront, collaborating with various organizations to explore its practical utility. It’s important to note that many of these are proof-of-concept or hybrid solutions, where the quantum annealer handles a specific, hard part of a larger problem.

Supply Chain and Logistics: Optimizing vehicle routes (like the Traveling Salesperson Problem), scheduling deliveries, and managing inventory. For example, Volkswagen used D-Wave to optimize taxi routes in Beijing.
Financial Modeling: Portfolio optimization, risk assessment, and fraud detection. For instance, using it to minimize transaction costs or select optimal asset allocations.
Drug Discovery and Material Science: Simulating molecular structures, predicting protein folding, and designing new materials by finding optimal configurations.
Traffic Flow Optimization: Developing adaptive traffic signal controls to reduce congestion in urban areas.
AI and Machine Learning: Training Boltzmann machines, performing sampling, and accelerating classification tasks by solving underlying optimization problems.

Note: While these applications are promising, the current generation of quantum annealers has limitations regarding the number of qubits and their connectivity. This means that large, real-world problems often need to be broken down into smaller sub-problems, solved classically, or solved using hybrid approaches.

Getting Practical with D-Wave’s Ocean SDK

D-Wave provides the Ocean SDK (Software Development Kit) to make it easier for developers to formulate and solve problems on their quantum annealers and classical samplers.

Prerequisites

You’ll need:

Python 3.7+
A D-Wave Leap account (for accessing real QPUs, but we’ll use a local simulator for runnable examples).

Installation

The core libraries you’ll use are dimod (for defining QUBOs and BQMs - Binary Quadratic Models) and dwave-neal (a classical simulated annealer for testing locally). If you plan to connect to a real QPU, you’d also install dwave-system.

pip install dimod dwave-neal
# For connecting to a real QPU later (requires D-Wave Leap account)
# pip install dwave-system

Collecting dimod
  Downloading dimod-0.12.7-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.7 MB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 1.7/1.7 MB 4.2 MB/s eta 0:00:00
Collecting dwave-neal
  Downloading dwave_neal-0.6.11-py3-none-any.whl (18 kB)
Collecting numpy>=1.20.0 (from dimod)
  Downloading numpy-1.26.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (18.3 MB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 18.3/18.3 MB 4.1 MB/s eta 0:00:00
Installing collected packages: numpy, dimod, dwave-neal
Successfully installed dimod-0.12.7 dwave-neal-0.6.11 numpy-1.26.0

A Simple QUBO Example: Minimizing `x_0 - 2x_0x_1 + x_1`

Let’s start with a very basic QUBO: $H(x) = x_0 - 2x_0x_1 + x_1$. We want to find $x_0, x_1 \in {0, 1}$ that minimize this.

If $x_0=0, x_1=0$: $0 - 0 + 0 = 0$
If $x_0=0, x_1=1$: $0 - 0 + 1 = 1$
If $x_0=1, x_1=0$: $1 - 0 + 0 = 1$
If $x_0=1, x_1=1$: $1 - 2 + 1 = 0$

The minimum value is 0, achieved when $(x_0, x_1) = (0,0)$ or $(1,1)$.

Here’s how you’d represent this in dimod and solve it with dwave-neal.

import dimod
import neal # dwave-neal's sampler

# Define the QUBO
Q = {
    ('x0', 'x0'): 1,  # x_0 linear term
    ('x1', 'x1'): 1,  # x_1 linear term
    ('x0', 'x1'): -2  # x_0 * x_1 quadratic term
}

# Create a BQM (Binary Quadratic Model) from the QUBO
bqm = dimod.BQM.from_qubo(Q)

# Use the classical simulated annealer from dwave-neal
sampler = neal.SimulatedAnnealingSampler()

# Sample the BQM to find low-energy solutions
# num_reads specifies how many times the sampler should run
# on the problem. More reads generally improve the chance
# of finding the global minimum.
response = sampler.sample(bqm, num_reads=10)

# Iterate through the samples (solutions found) and print them
print("Solutions found:")
for sample, energy in response.data(['sample', 'energy']):
    print(f"Sample: {sample}, Energy: {energy}")

# Get the best sample found
best_sample = response.first.sample
best_energy = response.first.energy

print(f"\nBest solution found: {best_sample}")
print(f"Minimum energy: {best_energy}")

Solutions found:
Sample: {'x0': 1, 'x1': 1}, Energy: 0.0
Sample: {'x0': 0, 'x1': 0}, Energy: 0.0
Sample: {'x0': 1, 'x1': 1}, Energy: 0.0
Sample: {'x0': 0, 'x1': 0}, Energy: 0.0
Sample: {'x0': 1, 'x1': 1}, Energy: 0.0
Sample: {'x0': 0, 'x1': 0}, Energy: 0.0
Sample: {'x0': 1, 'x1': 1}, Energy: 0.0
Sample: {'x0': 0, 'x1': 0}, Energy: 0.0
Sample: {'x0': 1, 'x1': 1}, Energy: 0.0
Sample: {'x0': 0, 'x1': 0}, Energy: 0.0

Best solution found: {'x0': 1, 'x1': 1}
Minimum energy: 0.0

As expected, neal found solutions with energy 0.0 for both (0,0) and (1,1).

Connecting to a Real D-Wave QPU (Conceptual)

To run on a real D-Wave quantum annealer, you’d typically use the dwave-system library. You need a D-Wave Leap account and your API token.

Note: I cannot provide a runnable example for a real QPU here as it requires personal API keys. However, the process is very similar to using neal, just with a different sampler.

Configure your D-Wave access: You usually set up your API token and solver URL using the dwave config create command or by setting environment variables (DWAVE_API_TOKEN, DWAVE_API_URL).
```
# Run this in your terminal once
dwave config create
```
```
D-Wave Configuration Generator
...
# Follow prompts to enter API token and URL
...
Configuration saved to ~/.config/dwave/dwave.conf
```

Select a D-Wave solver: You choose a solver based on its properties (number of qubits, connectivity, type). For example, DW_2000Q_6 or Advantage_system4.1.

import dimod
from dwave.system import DWaveSampler, EmbeddingComposite

# Define your QUBO (same as before)
Q = {
    ('x0', 'x0'): 1,
    ('x1', 'x1'): 1,
    ('x0', 'x1'): -2
}
bqm = dimod.BQM.from_qubo(Q)

# Instantiate a D-Wave sampler.
# EmbeddingComposite is used to automatically map your problem
# onto the QPU's graph structure (embedding).
# 'DWaveSampler()' by default picks a suitable QPU from your config.
# You can specify a solver like DWaveSampler(solver={'name': 'Advantage_system4.1'})
# if you have specific requirements.
sampler = EmbeddingComposite(DWaveSampler())

# Submit the problem to the D-Wave QPU
# num_reads is crucial here too.
response = sampler.sample(bqm, num_reads=100)

# Process results (similar to neal)
print("Solutions found on D-Wave QPU:")
for sample, energy in response.data(['sample', 'energy']):
    print(f"Sample: {sample}, Energy: {energy}")

best_sample = response.first.sample
best_energy = response.first.energy
print(f"\nBest solution found: {best_sample}")
print(f"Minimum energy: {best_energy}")

Example: Solving Our Max-Cut Problem

Let’s re-visit our tiny Max-Cut problem with nodes (0, 1, 2) and edges (0,1), (1,2). Our derived QUBO matrix $Q$ was: $Q = \begin{pmatrix} -1 & 2 & 0 \ 0 & -2 & 2 \ 0 & 0 & -1 \end{pmatrix}$

This translates to the following QUBO dictionary (only upper triangle and diagonal for dimod): $Q = { (0,0): -1, (1,1): -2, (2,2): -1, (0,1): 2, (1,2): 2 }$

The optimal solutions for this Max-Cut problem are where node 1 is separated from nodes 0 and 2.

$x_0=0, x_1=1, x_2=0$: Cut = 2.
$x_0=1, x_1=0, x_2=1$: Cut = 2.

Let’s confirm with our QUBO formulation and dwave-neal. The minimum energy solution should correspond to these optimal cuts.

import dimod
import neal

# Define the QUBO for the Max-Cut problem
# Variables are 0, 1, 2
Q_maxcut = {
    (0, 0): -1,
    (1, 1): -2,
    (2, 2): -1,
    (0, 1): 2,
    (1, 2): 2
}

# Create a BQM
bqm_maxcut = dimod.BQM.from_qubo(Q_maxcut)

# Use the classical simulated annealer
sampler_maxcut = neal.SimulatedAnnealingSampler()

# Sample the BQM
response_maxcut = sampler_maxcut.sample(bqm_maxcut, num_reads=100)

print("Max-Cut Solutions found:")
# Iterate and print top few unique solutions
unique_solutions = {}
for sample, energy in response_maxcut.data(['sample', 'energy']):
    sample_tuple = tuple(sorted(sample.items())) # Sort items for consistent key
    if sample_tuple not in unique_solutions:
        unique_solutions[sample_tuple] = energy
    if len(unique_solutions) >= 5: # Limit output to top 5 unique for brevity
        break

for sample_tuple, energy in sorted(unique_solutions.items(), key=lambda item: item[1]):
    print(f"Sample: {dict(sample_tuple)}, Energy: {energy}")

# Get the best sample found
best_sample_maxcut = response_maxcut.first.sample
best_energy_maxcut = response_maxcut.first.energy

print(f"\nBest Max-Cut solution found: {best_sample_maxcut}")
print(f"Minimum energy: {best_energy_maxcut}")

# Interpret the solution
# For a solution {0: 0, 1: 1, 2: 0}, nodes 0 and 2 are in set A (0), node 1 in set B (1).
# Edges (0,1) and (1,2) are cut. Total cut = 2.
# For a solution {0: 1, 1: 0, 2: 1}, nodes 0 and 2 are in set B (1), node 1 in set A (0).
# Edges (0,1) and (1,2) are cut. Total cut = 2.

Max-Cut Solutions found:
Sample: {0: 0, 1: 1, 2: 0}, Energy: -4.0
Sample: {0: 1, 1: 0, 2: 1}, Energy: -4.0
Sample: {0: 1, 1: 1, 2: 0}, Energy: -3.0
Sample: {0: 0, 1: 0, 2: 1}, Energy: -3.0
Sample: {0: 0, 1: 0, 2: 0}, Energy: -2.0

Best Max-Cut solution found: {0: 0, 1: 1, 2: 0}
Minimum energy: -4.0

The solutions with energy -4.0 (the minimum found) correspond to the optimal cuts:

{0: 0, 1: 1, 2: 0}: Node 0 in set A, Node 1 in set B, Node 2 in set A. Edges (0,1) and (1,2) cross the cut.
{0: 1, 1: 0, 2: 1}: Node 0 in set B, Node 1 in set A, Node 2 in set B. Edges (0,1) and (1,2) cross the cut.

Both yield a Max-Cut of 2. The energy of -4.0 is related to the formulation $-( (x_0 - x_1)^2 + (x_1 - x_2)^2 )$, where each cut contributes 1 unit to the maximization. So 2 cuts means maximizing 2. Minimizing $-2$ (not scaled yet by constants, etc.). Our QUBO was $Q_{i,j} = -2w_{ij}$ so a cut $(i,j)$ contributes $-2w_{ij}x_ix_j$ plus linear terms. The minimum energy of -4.0 corresponds correctly to the maximum cut for this formulation.

Limitations and Challenges

Despite the excitement, quantum annealing is not a magic bullet and comes with significant limitations:

Problem Size and Embedding: Current quantum annealers have a limited number of physical qubits (e.g., D-Wave Advantage has over 5000, but they are not all-to-all connected). Your QUBO problem’s graph might not directly match the QPU’s hardware graph. This requires “embedding” your problem, which can consume physical qubits for auxiliary connections and reduce the number of logical variables you can solve directly. This is often the biggest bottleneck.
Noise and Errors: Quantum systems are inherently noisy. Thermal fluctuations and quantum decoherence can lead to non-optimal solutions or variability in results. Multiple reads and careful tuning of annealing parameters are often necessary.
Connectivity: The limited connectivity of physical qubits means some problem structures are easier to embed than others. Problems with dense graphs or high-order interactions are challenging.
Quantum Advantage Debate: For many practical problems, it’s not yet clear if quantum annealers offer a speedup or quality improvement over the best classical algorithms. Classical algorithms (like Gurobi, CPLEX, or even highly optimized simulated annealing) are incredibly powerful and continue to improve. Quantum annealers are competitive for specific, highly specialized problems, but a clear, sustained “quantum advantage” for general real-world optimization remains an active area of research.
Problem Formulation Overhead: Translating real-world constraints and objectives into a QUBO can be non-trivial and often introduces auxiliary variables, further increasing the effective problem size.
Data Input/Output: Moving large datasets to and from the quantum computer can be a bottleneck.

Given these limitations, the most promising path forward for many real-world applications is hybrid quantum-classical algorithms. Here, the quantum annealer solves the hardest, most computationally intensive core sub-problems, while classical computers handle the larger structure, data pre-processing, and post-processing. D-Wave’s Leap cloud platform offers services for building and deploying such hybrid algorithms.

Conclusion

Quantum annealing is a powerful, specialized approach to solving certain types of optimization problems by leveraging quantum mechanical principles. By formulating your problem as a QUBO, you can tap into the hardware’s natural ability to find the lowest energy states.

While the technology is still evolving and faces significant challenges, particularly regarding problem size and demonstrating clear quantum advantage for every scenario, it represents a genuinely novel paradigm for computation. For developers, understanding QUBOs and getting hands-on with tools like D-Wave’s Ocean SDK opens up a fascinating new frontier in tackling some of the most intractable problems facing science and industry today. Keep an eye on hybrid algorithms – that’s where the real-world impact is emerging fastest.

Last updated on June 17, 2025

Share this post:

How QFT (Quantum Field Theory) Inspires Neural Field Models How Quantum Decoherence Challenges AI Hardware Design

How Quantum Annealing Solves Real Optimization Problems

The Optimization Challenge: Finding the “Best”

Quantum Annealing’s Language: QUBOs

Example: A Tiny Maximum Cut Problem

How Quantum Annealing Works (Conceptually)

Real-World Applications (with D-Wave’s Systems)

Getting Practical with D-Wave’s Ocean SDK

Prerequisites

Installation

A Simple QUBO Example: Minimizing x_0 - 2x_0x_1 + x_1

Connecting to a Real D-Wave QPU (Conceptual)

Example: Solving Our Max-Cut Problem

Limitations and Challenges

Conclusion

A Simple QUBO Example: Minimizing `x_0 - 2x_0x_1 + x_1`