How to define a QAOA cost function
Defining the input cost function for Fire Opal's QAOA Solver
Fire Opal's QAOA Solver's flexible input definition offers flexibility to enable you to solve any type of QAOA problem.
One possible input is a NetworkX Graph object, which is automatically converted by Fire Opal to a cost function and mapped to qubits.
Alternatively, the solver accepts a user-defined cost function as input, which makes it possible to define and solve both constrained and unconstrained optimization problems. This guide only covers the use of a cost function as an input. For an example on using an input graph with the QAOA Solver, check out the tutorial on Solving max-cut using Fire Opal.
This guide provides examples of a few types of optimization problems that can be solved using the QAOA Solver and demonstrates how to construct the cost function as an input. The following problem types are covered:
- An unconstrained graph problem: max-cut.
- A constrained problem, using penalty terms to formulate the constraints: Minimum Vertex Cover (MVC).
- A generalized unconstrained problem formulation: Quadratic Unconstrained Binary Optimization (QUBO).
The problems explained in ths guide are just a few examples; the QAOA Solver can be used to solve all sorts of optimization problems. For more information on building cost functions for optimization problems, this article provides detailed explanation.
Summary workflow
The following steps describe the general workflow for defining the QAOA problem and solving it using Fire Opal's solve_qaoa function.
1. Define the cost function to minimize
Start by building a graph with a given list of nodes and edges. Using binary variables
2. Add penalty terms to the cost function (optional)
If there are constraints to the problem, they can be included as a penalty terms in the cost function.
3. Solve the problem with Fire Opal's QAOA Solver
Solve the problem using Fire Opal's QAOA Solver. The problem (represented by the SymPy cost function or NetworkX graph) and problem type (String) are passed as parameters, and the output Dict is stored in the result variable.
job = fireopal.solve_qaoa(problem, problem_type, ...)
result = job.result()
Example: The max-cut problem
Given some undirected graph
To encode this problem on a quantum computer, a qubit is assigned to each graph node. The following code defines an example problem setup by created a random graph.
import numpy as np
# Given a graph with randomly weighted edges.
# To change the weights, change the seed to any integer.
_rng = np.random.default_rng(seed=99)
node_count = 7
edges = [(0, 1), (1, 3), (1, 2), (3, 4), (4, 5), (4, 6)]
weighted_edges = [(*edge, _rng.random()) for edge in edges]To model this problem, binary variables can be used such that
Therefore, the objective is to maximize the sum of the weights of edges in the cut, which can be formulated as follows:
where
However, since the Fire Opal's QAOA Solver takes the input cost function as a minimization problem, we can rewrite the objective as follows:
This is the standard unconstrained binary optimization model for the max-cut problem.
from sympy import symbols
# Construct the cost function.
variables = symbols([f"n[{i}]" for i in range(node_count)])
cost_function = 0
for i, j, weight in weighted_edges:
cost_function -= (
variables[i] + variables[j] - variables[i] * variables[j]
) * weight
# Display the cost function.
cost_functionExample: The Minimum Vertex Cover (MVC) problem
Given an undirected graph
The following code defines and sets up a random MVC problem.
# Given a graph with randomly weighted nodes.
# To change the weights, change the seed to any integer.
_rng = np.random.default_rng(seed=99)
node_count = 7
edges = [(0, 3), (0, 4), (1, 3), (2, 3), (2, 4), (2, 5), (4, 5), (4, 6), (5, 6)]
weighted_nodes = [(node, _rng.random()) for node in range(node_count)]A standard optimization model for weighted MVC can be formulated as follows. First, a penalty must be added for any case where an edge is not connected to a vertex in the subset. Therefore, let
# Construct the cost function.
variables = symbols([f"n[{i}]" for i in range(node_count)])
cost_function = 0
for i, weight in weighted_nodes:
cost_function += variables[i] * weight
# Display the cost function.
cost_functionNow every edge in the graph should include at least one end point from the cover, which can be expressed as the inequality:
Any case where an edge is not connected to the vertex of cover must be penalized. This can be represented in the cost function by adding a penalty of the form
# Add penalty term.
penalty_constant = 2
for i, j in edges:
cost_function += penalty_constant * (
1 - variables[i] - variables[j] + variables[i] * variables[j]
)
# Display the cost function.
cost_functionExample: The Quadratic Unconstrained Binary Optimization (QUBO)
All the cost functions constructed prior have a common feature: they all contain weighted sums on linear (
where
# Given any real matrix Q, we can formulate the cost function as the input of QAOA solver.
Q = np.array(
[
[2, 1, -1, 0, 0],
[1, 2, 0, -1, 0],
[-1, 0, 3, -1, -1],
[0, -1, -1, 3, -1],
[0, 0, -1, -1, 2],
]
)
# Construct the cost function.
node_count, _ = Q.shape
variables = symbols([f"n[{i}]" for i in range(node_count)])
cost_function = 0
for i in range(node_count):
for j in range(node_count):
if i == j:
cost_function += variables[i] * Q[i, j]
if i < j:
cost_function += variables[i] * variables[j] * (Q[i, j] + Q[j, i])
# Display the cost function.
cost_functionfrom fireopal import print_package_versions
print_package_versions()| Package | Version |
| --------------------- | ------- |
| Python | 3.11.3 |
| networkx | 3.5 |
| numpy | 2.3.1 |
| sympy | 1.12 |
| fire-opal | 9.0.4 |
| qctrl-workflow-client | 7.1.0 |
