# Solve Max-Cut using Fire Opal

Solve weighted and unweighted Max-Cut instances using Fire Opal's built-in QAOA solver

The Max-Cut problem is a classic problem in combinatorial optimization and graph theory. It involves partitioning the vertices of a graph into two distinct subsets such that the number of edges between the two subsets is maximized. The Max-Cut problem can be applied to many real-world applications across various domains, such as communications network design, image segmentation in computer vision, and financial risk management.

Fire Opal's built-in Quantum Approximate Optimization Algorithm (QAOA) solver can deliver solutions to nontrivial unweighted and weighted graph Max-Cut problems instances using quantum hardware.

In a recent paper, Q-CTRL published results benchmarking Fire Opal's QAOA Solver on several classically nontrivial unconstrained binary optimization problems and demonstrated the ability to correctly solve Max-Cut instances that represent the largest quantum optimizations successfully performed on hardware to date.

This application note provides the following information and examples to produce similar results as those shown in the published manuscript:

- Defining the Max-Cut problem
- Introducing QAOA
- Solving a sparse, 100-node, 3-regular unweighted graph Max-Cut problem with Fire Opal
- Solving a dense, 50-node, 7-regular weighted graph Max-Cut problem with Fire Opal

## 1. Introduction

### 1.1 Defining the Max-Cut problem

The aim of Max-Cut is to separate the nodes of a graph into two groups by intersecting as many edges between nodes as possible with a single partition, or "cut". For non-planar graphs, those with edges that cross one another, it has been mathematically proven that a polynomial-time solution does not exist, making this problem an excellent candidate for approximate optimization.

Quantum optimization algorithms are an attractive near-term opportunity to deliver efficient solutions to key high-impact applications that are classically nontrivial.

### 1.2 Introducing QAOA

QAOA is an algorithm often applied to combinatorial optimization problems, which involve finding an optimal object out of a finite set of objects. Such problems are relevant in many fields, such as portfolio optimization, supply chain optimization, optimal networking and scheduling, transportation routing, and more. Many combinatorial optimizations of interest fall under the NP-hard complexity class, meaning that there are no known polynomial-time solutions.

QAOA is one algorithm within the broader class of variational quantum algorithms (VQAs), which use classical optimization techniques to train a parameterized quantum circuit. Combining the power of both classical and quantum computation, VQAs are a promising method to achieve quantum advantage on NISQ devices and will likely remain relevant even in the age of fault-tolerant quantum computing.

Typically when implementing the QAOA, one must:

- Define cost and mixer Hamiltonians
- Construct circuits for the cost and mixer layers
- Choose parameters
- Prepare the initial state
- Implement a classical parameter optimizer

Adding to the challenge, most implementations of QAOA fail when executed on real hardware, either converging on the wrong solution or never converging at all.

Fire Opal’s QAOA solver alleviates the complexity of running QAOA algorithms by providing an easy-to-use function that consistently returns the correct answer. It converges quickly and enables the full QAOA implementation on problem sizes greater than achievable with other commercial QAOA methods.

## 2. Imports and initialization

The following section sets up the necessary imports and helper functions.

```
import fireopal as fo
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
from pyscipopt import Model
import qctrlvisualizer as qv
```

### 2.1 Set up your account and choose a backend

To run this tutorial, you will need an IBM Quantum account. Set up your IBM account information to choose a backend.

```
# These are the properties for the publicly available provider for IBM backends.
# If you have access to a private provider and wish to use it, replace these values.
hub = "ibm-q"
group = "open"
project = "main"
token = "YOUR_IBM_TOKEN"
credentials = fo.credentials.make_credentials_for_ibmq(
token=token, hub=hub, group=group, project=project
)
```

```
# Enter your desired IBM backend here.
backend_name = "desired_backend"
```

### 2.2 Define helper functions

The following functions are used to set up the Max-Cut problem instances and analyze results.

```
def maxcut_obj(bitstring: str, graph: nx.Graph) -> float:
"""
Given a bitstring, this function returns the number of edges
shared between the two partitions of the graph.
"""
obj = 0
# Iterate through each edge in the graph
for i, j, data in graph.edges(data=True):
# Calculate the contribution of the edge to the Max-Cut objective
# If the nodes are in different partitions, the term (int(bitstring[i]) - int(bitstring[j]))**2 will be 1
# Otherwise, it will be 0
obj -= data.get("weight", 1) * (int(bitstring[i]) - int(bitstring[j])) ** 2
return obj
def get_cost_distribution(
distribution: dict[str, int], graph: nx.Graph
) -> tuple[np.ndarray, np.ndarray]:
"""
Given a bitstring count distribution and a graph, returns the
costs and relative probabilities as numpy arrays.
"""
# Total number of bitstrings (shots)
shot_count = sum(distribution.values())
costs = []
probabilities = []
# Calculate the cost and probability for each bitstring
for bitstring, count in distribution.items():
# Reverse the bitstring to match graph node indices
cost = maxcut_obj(bitstring[::-1], graph)
costs.append(cost)
probabilities.append(count / shot_count)
return np.array(costs), np.array(probabilities)
def generate_random_bitstrings(length, num_bitstrings, rng_seed=0) -> list[str]:
"""
Generate a random sampling of bitstrings.
"""
# Initialize the random number generator with a seed for reproducibility
rng = np.random.default_rng(seed=rng_seed)
# Generate random bitstrings
random_array = rng.integers(0, 2, size=(num_bitstrings, length))
bitstrings = ["".join(row.astype(str)) for row in random_array]
return bitstrings
def calculate_percent_gap_to_optimal(
costs: np.ndarray, optimal_cut_value: float
) -> None:
"""
Determine the percent gap between the optimal cut value and the best cut value
found from Fire Opal.
"""
# Find the best cut value found (most negative cost)
best_cut_value_found = max(-costs)
# Calculate the percentage difference from the optimal value
percent_optimality = np.round(
100 - (abs(optimal_cut_value - best_cut_value_found) / optimal_cut_value * 100),
2,
)
# Print the results
print(
f"The best cut value found by Fire Opal is {best_cut_value_found}. \n"
f"This solution is {percent_optimality}% optimized relative to the classically determined solution, {optimal_cut_value}."
)
def analyze_maxcut_results(
distribution: dict[str, int], graph: nx.Graph, optimal_cut_value: float
) -> None:
"""
Analyze results from Max-Cut execution.
"""
# Number of nodes in the graph
qubit_count = graph.number_of_nodes()
# Total number of bitstrings (shots)
shot_count = sum(distribution.values())
# Get cost distribution from the results
costs, probs = get_cost_distribution(distribution, graph)
# Generate random bitstrings and get their cost distribution
random_bitstrings = generate_random_bitstrings(qubit_count, shot_count)
random_probs = np.ones(shot_count) / shot_count
random_costs = np.asarray(
[maxcut_obj(bitstring[::-1], graph) for bitstring in random_bitstrings]
)
# Plot histograms of cut values
plt.style.use(qv.get_qctrl_style())
fig, ax = plt.subplots(1, 1)
n, bin_edges, _ = ax.hist(
[-costs, -random_costs],
np.arange(-max(random_costs), -min(costs) + 1, 1),
weights=[probs, random_probs],
label=["Fire Opal QAOA solver", "Random Sampling"],
color=[qv.QCTRL_STYLE_COLORS[0], qv.QCTRL_STYLE_COLORS[1]],
)
ax.set_xlabel("Cut Value")
ax.set_ylabel("Probability")
ax.legend()
# Calculate and print the percent gap to optimal
calculate_percent_gap_to_optimal(costs=costs, optimal_cut_value=optimal_cut_value)
def solve_maxcut_classically(graph):
"""
Solve the Max-Cut problem classically using linear programming.
"""
model = Model("MaxCut")
# Add binary variables for edges
e = {(u, v): model.addVar(vtype="B", name=f"e({u, v})") for u, v in graph.edges()}
# Add binary variables for nodes
x = {u: model.addVar(vtype="B", name=f"x({u})") for u in graph.nodes()}
# Define the objective function to maximize the cut value
objective = sum(
data.get("weight", 1) * e[(u, v)] for u, v, data in graph.edges(data=True)
)
model.setObjective(objective, "maximize")
# Add constraints to ensure valid cuts
for u, v in graph.edges():
model.addCons(e[(u, v)] <= x[u] + x[v])
model.addCons(e[(u, v)] <= 2 - (x[u] + x[v]))
model.hideOutput(True)
model.optimize()
# Ensure the solution is optimal
assert model.getStatus() == "optimal"
# Return the solution indicating which partition each node belongs to
return {u: model.getVal(x[u]) for u in graph.nodes()}
def cut_value(graph, cut):
"""
Calculate the cut value of a given partition.
"""
value = 0
# Calculate the total weight of the cut edges
for i, j, data in graph.edges(data=True):
value += data.get("weight", 1) * np.round(cut[i] - cut[j]) ** 2
return value
```

## 3. Solving an unweighted 3-regular graph Max-Cut problem with Fire Opal

Max-Cut on random 3-regular graphs is a standard benchmark problem used to test the efficacy of quantum algorithms against classical counterparts by being both a simple and nontrivial example of a QUBO problem. The following section demonstrates Fire Opal's QAOA Solver's capability to achieve highly satisfactory solutions to an unweighted 100-node 3-regular graph Max-Cut instance.

### 3.1 Generate a random unweighted 100-node 3-regular graph

An unweighted 3-regular graph is a graph where every vertex is connected to exactly three other vertices, and all edges have the same weight.

The seed here is set to 12 to reproduce the results of the notebook, but the seed can be changed to generate a new random graph, which may correspond to a different optimal cut value.

`unweighted_graph = nx.random_regular_graph(d=3, n=100, seed=12)`

### 3.2 Solve the graph problem using Fire Opal's QAOA Solver

```
unweighted_job = fo.solve_qaoa(
problem=unweighted_graph,
credentials=credentials,
problem_type="maxcut",
backend_name=backend_name,
)
```

`unweighted_result = unweighted_job.result()`

### 3.3 Solve the graph problem using classical methods

Because this problem is still within the bounds of what can be solved by classical methods, it's possible to check the accuracy of Fire Opal's obtained solution.

```
solution = solve_maxcut_classically(unweighted_graph)
optimal_cut_value = cut_value(unweighted_graph, solution)
print(f"Classically derived cut value: {optimal_cut_value}")
```

```
Classically derived cut value: 135.0
```

### 3.4 Plot and analyze the solutions generated by Fire Opal

The performance baseline is set by sampling bitstrings uniformly at random (red histogram bars), akin to a random brute-force scan through the solution set. In all cases, the number of samples is taken to be the same as the samples of the optimal QAOA circuit. This baseline is chosen because a naive QAOA implementation using standard Qiskit compilers returns results indistinguishable from random selection when solving problems at this scale.

```
analyze_maxcut_results(
distribution=unweighted_result["final_bitstring_distribution"],
graph=unweighted_graph,
optimal_cut_value=optimal_cut_value,
)
```

```
The best cut value found by Fire Opal is 135.
This solution is 100.0% optimized relative to the classically determined solution, 135.0.
```

In this scenario, the solutions produced by Fire Opal's QAOA solver significantly outperform the cut values obtained via random sampling, a benchmark akin to naive QAOA implementations at this scale. Fire Opal's best cut value closely approximates the true optimal solution.

## 4. Solving a weighted 7-regular graph Max-Cut problem with Fire Opal

In this next scenario, the Max-Cut problem becomes more challenging due to denser connectivity, with each node linked to seven others, and the inclusion of weighted edges. To handle this complexity, the graph size is scaled down to 50 nodes. Notably, Fire Opal reliably achieves the correct solution when tackling this weighted 7-regular graph Max-Cut challenge.

### 4.1 Generate a random weighted 7-regular graph

A weighted 7-regular graph is a type of graph in which every vertex is connected to exactly seven other vertices (degree of 7), and each edge has an associated weight that represents the cost, length, or some other metric.

The seed here is set to 27 to reproduce the results of the notebook, but the seed can be changed to generate a new random graph, which may correspond to a different optimal cut value.

```
rng_seed = 27
rng = np.random.default_rng(rng_seed)
weighted_graph = nx.random_regular_graph(d=7, n=50, seed=rng_seed)
quantized_edge_weight_count = 4
max_edge_weight = 1.0
allowed_edge_weights = (
1 / quantized_edge_weight_count * np.arange(1, quantized_edge_weight_count + 1)
)
weighted_graph.add_weighted_edges_from(
[
(i, j, rng.choice(allowed_edge_weights) * max_edge_weight)
for i, j in weighted_graph.edges()
]
)
```

### 4.2 Solve the graph problem using Fire Opal's QAOA Solver

```
weighted_job = fo.solve_qaoa(
problem=weighted_graph,
credentials=credentials,
problem_type="maxcut",
backend_name=backend_name,
)
```

`weighted_result = weighted_job.result()`

### 4.3 Solve the graph problem using classical methods

Once again, it's possible to check the accuracy of Fire Opal's obtained solution using classical methods.

```
weighted_solution = solve_maxcut_classically(weighted_graph)
optimal_weighted_cut_value = cut_value(weighted_graph, weighted_solution)
print(f"Classically derived cut value: {optimal_weighted_cut_value}")
```

```
Classically derived cut value: 86.25
```

### 4.4 Plot and analyze the solutions generated by Fire Opal

Performance is again compared to randomly sampled bitstrings (red histogram bars), which are akin to a random brute-force scan through the solution set. In all cases, the number of samples is taken to be the same as the samples of the optimal QAOA circuit. This baseline is chosen because a naive QAOA implementation using standard Qiskit compilers returns results indistinguishable from random selection when solving problems at this scale.

```
analyze_maxcut_results(
distribution=weighted_result["final_bitstring_distribution"],
graph=weighted_graph,
optimal_cut_value=optimal_weighted_cut_value,
)
```

```
The best cut value found by Fire Opal is 86.25.
This solution is 100.0% optimized relative to the classically determined solution, 86.25.
```

Even in the harder problem instance, Fire Opal's QAOA solver still outperform the cut values obtained via random sampling, a benchmark akin to naive QAOA implementations at this scale. In this case, Fire Opal successfully found the optimal cut solution.

Congratulations on successfully leveraging Fire Opal's QAOA Solver to tackle two challenging Max-Cut problems with quantum hardware. For a deeper dive into what sets Fire Opal's QAOA Solver apart and its efficacy in finding accurate solutions at utility scales, explore the topic on Fire Opal's QAOA Solver.

The following package versions were used to produce this notebook.

```
from fireopal import print_package_versions
print_package_versions()
```

```
| Package | Version |
| --------------------- | ------- |
| Python | 3.11.8 |
| matplotlib | 3.8.3 |
| networkx | 2.8.8 |
| numpy | 1.26.4 |
| sympy | 1.12 |
| fire-opal | 7.3.1 |
| qctrl-visualizer | 7.0.0 |
| qctrl-workflow-client | 3.0.0 |
```