Creating MaxCut Qubots
This example shows how to create qubots for the Maximum Cut (MaxCut) problem - partitioning graph vertices to maximize edge weights crossing the partition. You’ll learn to build both problem and optimizer qubots, connect them, run locally, and upload to Rastion.
Problem Overview
MaxCut partitions graph vertices into two sets to maximize the total weight of edges between the sets.
Applications: Circuit design, machine learning clustering, network analysis, statistical physics.
Creating the MaxCut Problem Qubot
Step 1: Problem Implementation
Create qubot.py for the MaxCut problem:
# qubot.py
import numpy as np
import random
from qubots import BaseProblem, ProblemMetadata, ProblemType, ObjectiveType
class MaxCutProblem(BaseProblem):
def __init__(self, n_vertices=10, density=0.5, seed=42):
self.n_vertices = n_vertices
self.density = density
# Generate random graph
np.random.seed(seed)
random.seed(seed)
self.adjacency_matrix = self._generate_graph()
# Set metadata
metadata = ProblemMetadata(
name="MaxCut Problem",
description=f"Find maximum cut in {n_vertices}-vertex graph",
problem_type=ProblemType.COMBINATORIAL,
objective_type=ObjectiveType.MAXIMIZE,
dimension=n_vertices,
variable_bounds=[(0, 1)] * n_vertices
)
super().__init__(metadata)
def _generate_graph(self):
"""Generate random weighted graph."""
adj = np.zeros((self.n_vertices, self.n_vertices))
for i in range(self.n_vertices):
for j in range(i + 1, self.n_vertices):
if random.random() < self.density:
weight = random.uniform(1.0, 10.0)
adj[i][j] = weight
adj[j][i] = weight # Symmetric
return adj
def evaluate_solution(self, solution):
"""Calculate cut weight for given partition."""
if not self.is_valid_solution(solution):
return 0.0
cut_weight = 0.0
for i in range(self.n_vertices):
for j in range(i + 1, self.n_vertices):
if self.adjacency_matrix[i][j] > 0:
# Edge exists, check if it crosses the cut
if solution[i] != solution[j]:
cut_weight += self.adjacency_matrix[i][j]
return cut_weight
def is_valid_solution(self, solution):
"""Check if solution is valid binary partition."""
if len(solution) != self.n_vertices:
return False
if not all(x in [0, 1] for x in solution):
return False
# Ensure both partitions are non-empty
if sum(solution) == 0 or sum(solution) == len(solution):
return False
return True
def get_random_solution(self):
"""Generate random valid partition."""
solution = [random.randint(0, 1) for _ in range(self.n_vertices)]
# Ensure both partitions have at least one vertex
if sum(solution) == 0:
solution[0] = 1
elif sum(solution) == len(solution):
solution[0] = 0
return solution
def get_cut_edges(self, solution):
"""Get list of edges in the cut."""
cut_edges = []
for i in range(self.n_vertices):
for j in range(i + 1, self.n_vertices):
if (self.adjacency_matrix[i][j] > 0 and
solution[i] != solution[j]):
cut_edges.append((i, j, self.adjacency_matrix[i][j]))
return cut_edges
Step 2: Problem Configuration
Create config.json for the MaxCut problem:
{
"type": "problem",
"class_name": "MaxCutProblem",
"default_params": {
"n_vertices": 10,
"density": 0.5,
"seed": 42
},
"parameters": {
"n_vertices": {
"type": "integer",
"default": 10,
"min": 3,
"max": 100,
"description": "Number of vertices in the graph"
},
"density": {
"type": "number",
"default": 0.5,
"min": 0.1,
"max": 1.0,
"description": "Edge probability for random graph"
},
"seed": {
"type": "integer",
"default": 42,
"description": "Random seed for graph generation"
}
},
"metadata": {
"name": "MaxCut Problem",
"description": "Maximum cut problem on random graphs",
"domain": "graph_theory",
"tags": ["maxcut", "graph", "combinatorial"]
}
}
Creating the MaxCut Optimizer Qubot
Step 3: Optimizer Implementation
Create qubot.py for a simulated annealing optimizer:
# qubot.py
import numpy as np
import random
import math
from qubots import BaseOptimizer, OptimizationResult, OptimizerMetadata, OptimizerType
class SimulatedAnnealingMaxCut(BaseOptimizer):
def __init__(self, initial_temp=100.0, cooling_rate=0.95, min_temp=0.01, max_iterations=1000):
self.initial_temp = initial_temp
self.cooling_rate = cooling_rate
self.min_temp = min_temp
self.max_iterations = max_iterations
# Set metadata
metadata = OptimizerMetadata(
name="Simulated Annealing MaxCut",
description="Simulated annealing for maximum cut problems",
optimizer_type=OptimizerType.METAHEURISTIC,
required_parameters=["initial_temp", "cooling_rate"],
optional_parameters=["min_temp", "max_iterations"],
parameter_ranges={
"initial_temp": (1.0, 1000.0),
"cooling_rate": (0.8, 0.99),
"min_temp": (0.001, 1.0),
"max_iterations": (100, 10000)
}
)
super().__init__(metadata)
def optimize(self, problem, progress_callback=None, log_callback=None):
"""Solve MaxCut using simulated annealing."""
# Initialize with random solution
current_solution = problem.get_random_solution()
current_value = problem.evaluate_solution(current_solution)
best_solution = current_solution.copy()
best_value = current_value
temperature = self.initial_temp
iteration = 0
while temperature > self.min_temp and iteration < self.max_iterations:
# Generate neighbor by flipping a random bit
neighbor = current_solution.copy()
flip_idx = random.randint(0, len(neighbor) - 1)
neighbor[flip_idx] = 1 - neighbor[flip_idx]
# Ensure valid solution (both partitions non-empty)
if not problem.is_valid_solution(neighbor):
iteration += 1
continue
neighbor_value = problem.evaluate_solution(neighbor)
# Accept or reject the neighbor
delta = neighbor_value - current_value
if delta > 0 or random.random() < math.exp(delta / temperature):
current_solution = neighbor
current_value = neighbor_value
# Update best solution
if current_value > best_value:
best_solution = current_solution.copy()
best_value = current_value
# Cool down
temperature *= self.cooling_rate
iteration += 1
# Log progress
if log_callback and iteration % 100 == 0:
log_callback('info', f'Iteration {iteration}: Best = {best_value:.2f}, Temp = {temperature:.3f}', 'optimizer')
return OptimizationResult(
best_solution=best_solution,
best_value=best_value,
is_feasible=True,
iterations=iteration,
termination_reason="temperature_threshold" if temperature <= self.min_temp else "max_iterations"
)
Step 4: Optimizer Configuration
Create config.json for the simulated annealing optimizer:
{
"type": "optimizer",
"class_name": "SimulatedAnnealingMaxCut",
"default_params": {
"initial_temp": 100.0,
"cooling_rate": 0.95,
"min_temp": 0.01,
"max_iterations": 1000
},
"parameters": {
"initial_temp": {
"type": "number",
"default": 100.0,
"min": 1.0,
"max": 1000.0,
"description": "Initial temperature for annealing"
},
"cooling_rate": {
"type": "number",
"default": 0.95,
"min": 0.8,
"max": 0.99,
"description": "Temperature cooling rate"
},
"min_temp": {
"type": "number",
"default": 0.01,
"min": 0.001,
"max": 1.0,
"description": "Minimum temperature threshold"
},
"max_iterations": {
"type": "integer",
"default": 1000,
"min": 100,
"max": 10000,
"description": "Maximum number of iterations"
}
},
"metadata": {
"name": "Simulated Annealing MaxCut",
"description": "Simulated annealing for maximum cut optimization",
"optimizer_type": "metaheuristic",
"tags": ["simulated_annealing", "metaheuristic", "maxcut"]
}
}
Connecting Problem and Optimizer
Step 5: Local Testing
Test your qubots locally before uploading:
# test_local.py
from qubot import MaxCutProblem, SimulatedAnnealingMaxCut
# Create problem instance
problem = MaxCutProblem(n_vertices=12, density=0.4, seed=42)
print(f"Created MaxCut problem with {problem.n_vertices} vertices")
# Create optimizer instance
optimizer = SimulatedAnnealingMaxCut(
initial_temp=50.0,
cooling_rate=0.9,
max_iterations=500
)
print(f"Created simulated annealing optimizer")
# Solve the problem
print("Solving MaxCut...")
result = optimizer.optimize(problem)
print(f"Best cut weight: {result.best_value:.2f}")
print(f"Partition: {result.best_solution}")
print(f"Valid solution: {problem.is_valid_solution(result.best_solution)}")
print(f"Iterations: {result.iterations}")
# Analyze the cut
cut_edges = problem.get_cut_edges(result.best_solution)
print(f"Cut edges: {len(cut_edges)}")
for i, j, weight in cut_edges[:5]: # Show first 5 edges
print(f" Edge ({i}, {j}): weight {weight:.2f}")
Uploading to Rastion
Step 6: Upload Problem Qubot
Upload your MaxCut problem to Rastion:
# upload_problem.py
import qubots.rastion as rastion
# Authenticate with Rastion
rastion.authenticate("your_api_token")
# Upload the MaxCut problem
problem_result = rastion.upload_qubots_model(
model_path="./maxcut_problem", # Directory containing qubot.py and config.json
model_name="maxcut_problem",
description="MaxCut problem with configurable graph parameters",
tags=["maxcut", "graph", "combinatorial"],
public=True
)
print(f"Problem uploaded: {problem_result['repository_url']}")
Step 7: Upload Optimizer Qubot
Upload your simulated annealing optimizer:
# upload_optimizer.py
import qubots.rastion as rastion
# Upload the simulated annealing optimizer
optimizer_result = rastion.upload_qubots_model(
model_path="./sa_maxcut_optimizer", # Directory with qubot.py and config.json
model_name="sa_maxcut_optimizer",
description="Simulated annealing for MaxCut optimization",
tags=["simulated_annealing", "metaheuristic", "maxcut"],
public=True
)
print(f"Optimizer uploaded: {optimizer_result['repository_url']}")
Using AutoLoading Functions
Step 8: Load and Use Your Qubots
Once uploaded, use AutoProblem and AutoOptimizer to load your qubots:
from qubots import AutoProblem, AutoOptimizer
# Load your uploaded problem
problem = AutoProblem.from_repo("your_username/maxcut_problem", override_params={
"n_vertices": 15,
"density": 0.6,
"seed": 123
})
# Load your uploaded optimizer
optimizer = AutoOptimizer.from_repo("your_username/sa_maxcut_optimizer", override_params={
"initial_temp": 200.0,
"cooling_rate": 0.92,
"max_iterations": 2000
})
# Solve the problem
result = optimizer.optimize(problem)
print(f"Solution found!")
print(f"Cut weight: {result.best_value:.2f}")
print(f"Runtime: {result.runtime_seconds:.3f}s")
print(f"Valid partition: {problem.is_valid_solution(result.best_solution)}")
# Analyze the cut
cut_edges = problem.get_cut_edges(result.best_solution)
print(f"Number of cut edges: {len(cut_edges)}")
Step 9: Load Others’ Qubots
Use qubots created by the community:
# Load community MaxCut problems
random_graph = AutoProblem.from_repo("benchmarks/maxcut_random_20")
complete_graph = AutoProblem.from_repo("benchmarks/maxcut_complete_10")
# Load community optimizers
genetic_optimizer = AutoOptimizer.from_repo("algorithms/genetic_maxcut")
ortools_optimizer = AutoOptimizer.from_repo("algorithms/ortools_maxcut")
# Compare your optimizer against others
problems = [random_graph, complete_graph]
optimizers = [optimizer, genetic_optimizer, ortools_optimizer]
for prob in problems:
print(f"\nSolving {prob.metadata.name}:")
for opt in optimizers:
result = opt.optimize(prob)
print(f" {opt.metadata.name}: {result.best_value:.2f}")
Summary
You’ve learned how to create MaxCut qubots from scratch:
- Problem Qubot: Implemented
MaxCutProblem class with graph generation and cut evaluation
- Optimizer Qubot: Created
SimulatedAnnealingMaxCut with temperature-based search
- Configuration: Set up
config.json files for both qubots
- Local Testing: Connected problem and optimizer to verify functionality
- Upload to Rastion: Made qubots available to the community
- AutoLoading: Used
AutoProblem and AutoOptimizer to load and run qubots
Your qubots are now ready for benchmarking, cloud execution, and sharing with the community!
Next Steps
