Solving the Max-Cut Problem with QAOA
A reactive Guppy tutorial for Aqora Workspaces In this notebook tutorial we will be demonstrating how to solve the max-cut problem using the quantum approximate optimization algorithm (QAOA). This is a variational algorithm where we run a parameterised circuit to compute an expectation value. We will then try and maximize this expectation value by classically optimizing the circuit parameters. Original Quantinuum tutorial · QAOA paper · Guppy documentation
Source and attribution
This notebook is a marimo/Aqora port of Quantinuum's
Solving the Max-Cut Problem with QAOA
Jupyter tutorial. The original tutorial and code belong to Quantinuum
and their respective authors. This port preserves the tutorial's structure
while adapting the notebook format and Guppy execution path for
guppylang==0.21.16. It is not an official Quantinuum or Aqora publication.
The Max-Cut problem
The max-cut problem is a classic problem from graph theory. The problem consists of partitioning the nodes in a graph into two sets and such that the number of edges between and is maximized. In our statement of the problem, we will color the nodes red and blue. The objective for max-cut is then to color the nodes of the graph such that the number of edges connecting red nodes to blue nodes is maximized. Now consider the graph below with three nodes.
There are colorings of the graph. In general there are for an node graph. The Max-cut problem can then be stated as that of finding the color assignment which maximizes the number of edges between nodes of a different color.
We can define the following cost function for solving the max-cut problem for a graph
Here and are variables representing the "colors" of each node and is the edge set of the graph. We can solve max-cut by finding a coloring of the graph that maximizes
Quantum Approximate Optimization Algorithm (QAOA)
General theory
Introduced in "A Quantum Approximate Optimization Algorithm" (found at https://arxiv.org/abs/1411.4028). The idea is to prepare a quantum state which encodes a solution to the max-cut problem. Measuring such a state will give us computational basis states (or bitstrings) which correspond to colorings of the graph. QAOA is a variational algorithm, which is to say that a parameterized state is prepared, with the parameters varied to improve the solution. We will have parameters where is our number of layers. In particular, the state prepared has the form whereWe refer to as the problem Hamiltonian. This Hamiltonian essentially encodes the connectivity of the graph in the max-cut problem.
Here there is an implicit tensor product. We use the notation . Note also the resemblance between and our classical cost function .
The rule for constructing this problem Hamiltonian is that we include a term for every edge in the graph. The section below shows how this Hamiltonian looks for a specific graph.
The operator is called the mixer Hamiltonian. This operator is just a sum of Pauli operators with one non-identity term on each qubit.
Here we use the convention that means a Pauli operator will be applied to the th qubit and the identity operator will be applied to all other qubits in the circuit. Importantly, this mixer Hamiltonian does not commute with . This fact turns out to be important as it allows us to properly explore our solution space.
Example: cost and mixer Hamiltonian for a three node graph
Let us look again the three node graph we used in introducing the max-cut problem
For the simple three-node graph above the problem Hamiltonian is
Notice that there is a term acting between each pair of nodes connected by an edge.
The mixer Hamiltonian has the form
Here there is an operator acting on each node. The form of this operator is independent of the graph connectivity.
Building the program
To start off with, we will need to construct a QAOA circuit for a particular graph and number of layers (). Our circuit for QAOA is constructed by alternating the cost layer () and mixer layer () times for different parameters. The cost layer is defined by evolving the commuting Hamiltonian . We can realize this with a layer of ZZPhase gates. For the mixer layer we are evolving the -type Hamiltonian . We can realize the evolution with a layer of Rx gates.We will define a Python function which will construct a Guppy program implementing QAOA for an node graph. First we create the uniform superposition state and then alternate cost and mixer layers as described above.
Aqora compatibility note. The original Guppy v1.x tutorial fixes the graph topology and number of layers at compile time while passing the cost and mixer angles as runtime arguments. Inguppylang==0.21.16, the Selene emulator entrypoint used here must take no arguments. This port therefore embeds the angles withcomptimeand rebuilds the small program for each optimizer evaluation. The QAOA circuit and objective remain unchanged.
Calculating expectation values
We also need to extract our energy expectation values from a
QsysResult object after our circuit is processed by the Selene simulator. We do this with the energy_from_result function below. Note that the fact that the max-cut problem Hamiltonian contains only commuting terms means that we do not need to calculate our energy expectation using multiple measurement circuits.Now let's define helpers for executing and scoring QAOA parameter values.
In the original tutorial, the program is compiled once and re-run with different angle arguments. For the Aqora-compatible execution path described above,
build_qaoa_program instead defines a zero-argument main entrypoint with the supplied angles embedded as compile-time constants. run_qaoa_circuit builds and executes that program with Selene, and eval_qaoa_energy turns the result into the scalar energy needed by the classical optimizer.
The p_value argument defines the number of cost/mixer layers in the QAOA program.Setting up the variational loop
Now that we have the
eval_qaoa_energy function which does a single "forward pass" of our algorithm, we can use a classical optimizer to find a set of parameters which maximizes the energy expectation value.
To accomplish this, we define a SciPy objective function that accepts a single parameter vector, splits it into QAOA cost and mixer coefficients, builds and evaluates the Guppy program for those coefficients, and returns the negative energy. Minimizing the negative energy is equivalent to maximizing the max-cut energy.
Now we can put all of this machinery together in a solve_max_cut_instance function which, given a graph, attempts to solve the max-cut problem using this variational method. After the optimizer finishes, we run one final QAOA forward pass with the best parameters and use that QsysResult for validation and plotting.
Our function takes the following arguments:
graph: A networkx graph for which we want to solve the max-cut problem.max_optimizer_iterations: The maximum number of objective evaluations in the SciPy optimizer.p_value: The number of alternating cost/mixer layers in our QAOA program.n_shots: The number of Guppy program executions for each expectation value calculation.seed: A seed for the random number generator so the initial parameters and emulator executions are reproducible.
-cost_angle * pi / 2, and the mixer layer applies mixer_angle * pi. The optimizer works directly with these real-valued coefficients.
Aqora usability note. The helper accepts an optionalprogress_interval. The tutorial run below reports one line every five objective evaluations so a long-running remote calculation visibly remains active. Set it toNonefor the original silent behavior.
Solving max-cut for a graph with seven nodes
Now that we have all of the pieces ready, let's test our QAOA implementation for a very simple graph. We will use a graph where the correct answer for max-cut is very easy to verify manually.
The solution for this graph is a simple alternating coloring which we can represent with the following pair of bitstrings. See the two graphs drawn at the end of this notebook. The bitstrings are the binary complement of one another.
We have chosen a sparse graph where it is easy to check the max-cut solution by inspection. For this configuration, the solution is that nodes 1 and 4 are a different color to nodes 0, 2, 3, 5 and 6.
We can represent a coloring with a binary string where the th entry represents the color of node . Therefore the expected solutions can be represented by the following two strings.
Note that there are two colourings as all that matters is that we have partitioned the node indices into the sets and . If we have two colors e.g. red and blue, then we have the freedom to colour the nodes in blue and red or vice-versa.
Now we need a problem Hamiltonian which reflects the connectivity of our graph. Recall how the problem Hamiltonian is defined.
For our seven-vertex graph, the problem Hamiltonian is the following.
The form of the mixer Hamiltonian depends only on the number of nodes in our graph. The evolution operator can be implemented with a layer of
Rx gates. See the build_qaoa_instance function.Click Run the QAOA optimization above when you are ready. The full 100-evaluation run can take several minutes on the remote simulator.
Optimizer status note. COBYLA is a derivative-free trust-region optimizer. If it reports that the trust-region radius reached its lower bound, that is a normal termination condition: the local search radius has shrunk to the configured tolerance. If it reports that the maximum number of function evaluations was exceeded, the configured
maxiter budget was exhausted.
The optimizer objective above maximizes the expected max-cut energy. This is related to, but not identical to, maximizing the probability of sampling one of the two exact optimal colorings.Let's define a function that checks that the most frequent measurement outcomes correspond to the expected graph colorings.
The success ratio above counts only samples that land in the two optimal colorings. To compare it with the optimized energy objective, we can group all sampled bitstrings by their max-cut value.
Finally, we can plot the most common measurement outcomes. If we have done this correctly then the two most common measurement outcomes should correspond to the graph colorings which solve our instance of the max-cut problem
The two green bars correspond to the expected colorings of our seven vertex graph. These colorings are equivalent up to the swapping of blue and red nodes.
