Advanced D-Wave: Hybrid Solvers and Leap
Use D-Wave's Leap hybrid solver service to solve large optimization problems that are too big for the QPU alone: LeapHybridSampler, problem formulation, and interpreting solutions.
Circuit diagrams
Why Hybrid Solvers?
D-Wave’s QPU (quantum processing unit) is an analog quantum annealer with around 5000 qubits. The limitation is not qubit count alone: the Pegasus hardware graph is sparse, meaning each qubit is physically connected to at most 15 others. Embedding a dense problem onto the QPU requires minor embedding, which maps logical variables to chains of physical qubits. For large, densely connected problems, chains consume most of the qubit budget and leave few resources for the actual problem variables.
Practical QPU runs are therefore limited to roughly 100 to 500 logical variables for dense problems and a few thousand for sparse ones.
Hybrid solvers bypass this constraint. They partition the problem: the classical component handles large-scale decomposition, variable reduction, and preprocessing, while the QPU handles the hard subproblems it is best suited for. The result is a solver that handles millions of variables while still leveraging quantum hardware.
D-Wave Leap
Leap is D-Wave’s cloud service that provides access to both QPU hardware and hybrid solvers via a REST API. It offers:
- Direct QPU access (for small, well-embedded problems)
- LeapHybridSampler (for BQM problems up to 1 million variables)
- LeapHybridCQMSampler (for constrained problems with explicit constraint objects)
- Free developer access at cloud.dwavesys.com
Developer accounts include a limited monthly quota of QPU time and hybrid solver time, which is sufficient for experimentation and learning.
Setup
Install the Ocean SDK and configure your API token:
pip install dwave-ocean-sdk
dwave config create
The dwave config create command walks you through entering your API token (obtained from cloud.dwavesys.com after creating a free account) and selecting a default solver. It writes a configuration file to ~/.config/dwave/dwave.conf.
Verify the setup:
dwave ping --client qpu # test QPU connection
The Binary Quadratic Model
Both the QPU and hybrid solvers accept problems formulated as Binary Quadratic Models (BQM). A BQM over binary variables x_i in {0, 1} has the form:
E(x) = sum_i h_i * x_i + sum_{i<j} J_{ij} * x_i * x_j + offset
h_i values are linear biases and J_{ij} values are quadratic interactions. The solver searches for the assignment of x_i values that minimizes E(x).
In practice, you build BQMs using the dimod library:
import dimod
bqm = dimod.BinaryQuadraticModel(vartype='BINARY')
bqm.add_variable('x0', -1.0) # linear bias for x0
bqm.add_variable('x1', -1.0) # linear bias for x1
bqm.add_interaction('x0', 'x1', 2.0) # quadratic interaction
Problem Formulation: Graph Coloring as QUBO
Graph coloring assigns colors to vertices so that no two adjacent vertices share the same color. We will formulate 3-coloring as a QUBO (Quadratic Unconstrained Binary Optimization) problem.
Variables: For each vertex i and color c in {0, 1, 2}, define a binary variable x_{i,c}. The variable equals 1 if vertex i receives color c.
Constraint 1: Each vertex gets exactly one color.
For each vertex i: sum_c x_{i,c} = 1. This is equivalent to (sum_c x_{i,c} - 1)^2 = 0. Expand and add to the QUBO with a penalty coefficient A.
Constraint 2: Adjacent vertices must have different colors.
For each edge (i, j) and each color c: x_{i,c} + x_{j,c} <= 1, meaning both cannot receive color c. Add penalty term A * x_{i,c} * x_{j,c} for each edge and color.
import dimod
import networkx as nx
def graph_coloring_bqm(graph, n_colors=3, penalty=10.0):
bqm = dimod.BinaryQuadraticModel(vartype='BINARY')
nodes = list(graph.nodes())
colors = list(range(n_colors))
# Constraint 1: each vertex gets exactly one color
# Expand (sum_c x_{i,c} - 1)^2 = sum_c x_{i,c} - 2 * sum_{c} x_{i,c} + sum_{c<d} 2 x_{i,c} x_{i,d} + const
for i in nodes:
for c in colors:
var = f"x_{i}_{c}"
bqm.add_variable(var, penalty * (1 - 2)) # linear term: -penalty
for ci in colors:
for cj in colors:
if ci < cj:
bqm.add_interaction(f"x_{i}_{ci}", f"x_{i}_{cj}", 2 * penalty)
# Constraint 2: adjacent vertices must have different colors
for u, v in graph.edges():
for c in colors:
bqm.add_interaction(f"x_{u}_{c}", f"x_{v}_{c}", penalty)
return bqm
# Define a small graph
G = nx.petersen_graph() # 10 nodes, 15 edges, chromatic number 3
bqm = graph_coloring_bqm(G, n_colors=3, penalty=10.0)
print(f"BQM variables: {len(bqm.variables)}")
print(f"BQM interactions: {len(bqm.quadratic)}")
# BQM variables: 30 (10 nodes x 3 colors)
# BQM interactions: 75 (one-hot) + 45 (edge constraints) = 120
Running LeapHybridSampler
# Production: use LeapHybridSampler with a Leap API token (requires dwave-system)
# sampler = LeapHybridSampler() -- requires account
# Local testing: use SimulatedAnnealingSampler
from dimod import SimulatedAnnealingSampler
sampler = SimulatedAnnealingSampler()
sampleset = sampler.sample(bqm, num_reads=200)
print(sampleset.first.sample) # best solution found
print(f"Energy: {sampleset.first.energy:.2f}")
The time_limit parameter defaults to the minimum allowed by the hybrid solver (usually 3 seconds). For large problems, increasing it improves solution quality.
sampleset.first returns the lowest-energy sample found. The energy corresponds to the QUBO objective value: a valid coloring that satisfies all constraints has energy close to zero (the penalty terms evaluate to 0 for satisfied constraints).
Reading and Validating the Solution
def decode_coloring(sample, nodes, n_colors=3):
coloring = {}
for i in nodes:
assigned_colors = [c for c in range(n_colors) if sample.get(f"x_{i}_{c}", 0) == 1]
if len(assigned_colors) == 1:
coloring[i] = assigned_colors[0]
else:
coloring[i] = None # constraint violated: 0 or 2+ colors assigned
return coloring
def validate_coloring(coloring, graph):
violations = 0
for u, v in graph.edges():
if coloring.get(u) == coloring.get(v) and coloring.get(u) is not None:
violations += 1
uncolored = [v for v, c in coloring.items() if c is None]
return violations, uncolored
sample = sampleset.first.sample
coloring = decode_coloring(sample, list(G.nodes()), n_colors=3)
violations, uncolored = validate_coloring(coloring, G)
print(f"Coloring: {coloring}")
print(f"Edge violations: {violations}")
print(f"Uncolored vertices: {uncolored}")
# Good result: violations=0, uncolored=[]
If violations remain, the penalty coefficient was too low relative to the problem’s interaction strengths. Try increasing penalty to 20 or 50 and rerunning.
LeapHybridCQMSampler: Constrained Quadratic Models
Manually converting constraints to penalty terms is error-prone. The LeapHybridCQMSampler accepts explicit constraint objects and handles the penalty formulation internally:
import dimod
from dwave.system import LeapHybridCQMSampler
# Build a CQM directly with named constraints
cqm = dimod.ConstrainedQuadraticModel()
nodes = list(G.nodes())
colors = list(range(3))
# Add binary variables
x = {(i, c): dimod.Binary(f"x_{i}_{c}") for i in nodes for c in colors}
# Objective: minimize violations (here we minimize 0 since feasibility is the goal)
cqm.set_objective(sum(0 * x[i, c] for i in nodes for c in colors))
# Constraint 1: each vertex gets exactly one color
for i in nodes:
cqm.add_constraint(
sum(x[i, c] for c in colors) == 1,
label=f"one_color_{i}"
)
# Constraint 2: adjacent vertices have different colors
for u, v in G.edges():
for c in colors:
cqm.add_constraint(
x[u, c] + x[v, c] <= 1,
label=f"diff_color_{u}_{v}_{c}"
)
sampler_cqm = LeapHybridCQMSampler()
sampleset_cqm = sampler_cqm.sample_cqm(cqm, time_limit=5)
# Filter for feasible solutions
feasible = sampleset_cqm.filter(lambda s: s.is_feasible)
if feasible:
best = feasible.first
print(f"Feasible solution found, energy={best.energy:.2f}")
else:
print("No feasible solution found; increase time_limit or check formulation.")
CQM is the preferred interface for most optimization problems. It requires no manual penalty tuning and makes constraint satisfaction explicit and checkable.
QPU Direct vs. Hybrid: When to Use Each
| Factor | QPU Direct | Hybrid Solver |
|---|---|---|
| Problem size | Up to ~500 dense variables | Up to ~1 million variables |
| Connectivity | Must fit Pegasus graph | No restriction |
| Speed | Microseconds (annealing) | Seconds to minutes |
| Solution quality | Good for small problems | Better for large problems |
| Best for | Research, well-structured small problems | Production optimization |
Use QPU direct access when you need to study the annealing process itself, when your problem is small and sparse, or when you want to benchmark raw QPU performance. Use hybrid solvers for real-world optimization where problem size exceeds a few hundred variables.
Problem Types That Map Well to D-Wave
D-Wave and hybrid solvers are well-suited for combinatorial optimization problems with natural binary or integer structure:
Scheduling: Assign jobs to time slots or machines. Variables represent job-slot assignments; constraints enforce no overlapping and resource limits.
Vehicle routing: Assign deliveries to routes. Binary variables encode which vehicle serves which stop; constraints enforce route feasibility and capacity.
Portfolio optimization: Select a subset of assets to maximize return subject to risk constraints. Binary variables encode asset inclusion.
Bin packing: Assign items to containers without exceeding capacity. Natural binary encoding with linear capacity constraints.
Network design: Select which edges to include in a network to minimize cost while maintaining connectivity. Graph structure maps directly to QUBO interactions.
For all of these, the CQM interface is usually the most practical starting point. Define variables and constraints naturally, submit to LeapHybridCQMSampler, and filter for feasible solutions.
Was this tutorial helpful?