QAOA MaxCut

The MaxCut problem and its QAOA implementation is discussed in plenty of detail in the MaxCut 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)

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:

cost_operatorfunction

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

Classical cost function

create_maxcut_cl_cost_function(G)

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:

cl_cost_functionfunction

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

MaxCut problem

maxcut_problem(G)

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=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,
        node_color=['#FFCCCB' if most_likely[node]=='0' else '#ADD8E6' for node in G.nodes()],
        edge_color='#D3D3D3',
        pos = nx.bipartite_layout(G, [node for node in G.nodes() if most_likely[node]=='0']))