QAOA MaxCut

The MaxCut problem and its QAOA implementation is discussed in plenty of detail in the QAOA tutorial. All the necessary ingredients and required steps to run QAOA are elaborated on in an easy to grasp manner.

Here, we provide a condensed implementation of QAOA for MaxCut using all of the predefined functions.

Problem description

Given a Graph \(G = (V,E)\) find a maximum cut, i.e., a bipartition \(S\), \(V\setminus S\) of the set of vertices \(V\) such that the number of edges between \(S\) and \(V\setminus S\) is maximal.

Cost operator

create_maxcut_cost_operator(G: nx.Graph) → Callable

Creates the cost operator for an instance of the maximum cut problem for a given graph G.

Parameters:

Gnx.Graph

The Graph for the problem instance.

Returns:

Callable[[QuantumVariable, float | sympy.Symbol], None]

A function receiving a QuantumVariable and a real parameter \(\gamma\) or a symbolic parameter. This function performs the application of the cost operator.

Classical cost function

create_maxcut_cl_cost_function(G: nx.Graph) → Callable[[dict], float]

Creates the classical cost function for an instance of the maximum cut problem for a given graph G.

Parameters:

Gnx.Graph

The Graph for the problem instance.

Returns:

Callable[[dict], float]

The classical cost function for the problem instance, which takes a dictionary of measurement results as input.

Sample array post processor (Jasp)

create_maxcut_sample_array_post_processor(G: nx.Graph) → Callable[[ArrayLike], Array]

Creates the sample array post processor for the MaxCut problem for a given graph G.

Note

This function is intended for use with dynamic (Jasp) QAOA only. In Jasp mode, quantum variables are decoded to integers rather than binary strings, so repeated sampling yields an array of integers encoding bipartitions of G. For standard (non-Jasp) QAOA, use create_maxcut_cl_cost_function() instead.

Parameters:

Gnx.Graph

The graph for the problem instance.

Returns:

Callable[[ArrayLike], jax.Array]

A JAX-traceable function that accepts an array of integer-encoded bitstrings (bipartitions of G) and returns the mean cut value as a 0-D jax.Array of float.

See also

How to use QAOA in Jasp

How to use QAOA in Jasp.

MaxCut problem

maxcut_problem(G: nx.Graph) → QAOAProblem

Creates a QAOA problem instance with appropriate phase separator, mixer, and classical cost function.

Parameters:

Gnx.Graph

The graph for the problem instance.

Returns:

QAOAProblem

A QAOA problem instance for MaxCut for a given graph G.

Example implementation

from qrisp import QuantumVariable
from qrisp.qaoa import QAOAProblem, RX_mixer, create_maxcut_cl_cost_function, create_maxcut_cost_operator
import networkx as nx

G = nx.erdos_renyi_graph(6, 0.7, seed = 133)
qarg = QuantumVariable(G.number_of_nodes())

qaoa_maxcut = QAOAProblem(cost_operator=create_maxcut_cost_operator(G),
                        mixer=RX_mixer,
                        cl_cost_function=create_maxcut_cl_cost_function(G))
results = qaoa_maxcut.run(qarg, depth=5, max_iter=50)

That’s it! Feel free to experiment with the init_type='tqa' option in the .run method for improved performance. In the following, we print the 5 most likely solutions together with their cost values.

cl_cost = create_maxcut_cl_cost_function(G)

print("5 most likely solutions")
max_five = sorted(results.items(), key=lambda item: item[1], reverse=True)[:5]
for res, prob in max_five:
    print(res, prob, cl_cost({res : 1}))

Finally, we visualize the most likely solution.

most_likely = max_five[0][0]
nx.draw(G, with_labels = True, font_color='white', node_size=1000, font_size=22,
        node_color=['#6929C4' if most_likely[node]=='0' else '#20306f' for node in G.nodes()],
        edge_color='#D3D3D3',
        pos = nx.bipartite_layout(G, [node for node in G.nodes() if most_likely[node]=='0']))