QAOA MaxIndepSet#

Problem description#

Given a Graph \(G = (V,E)\) find a maximal independent set, i.e., a subset of vertices \(V' \subset V\) such that all pairs of vertices are mutually non-adjacent in the graph \(G\). The QAOA implementation is based on the work of Hadfield et al.

Mixer#

create_max_indep_set_mixer(G)[source]#

Creates the controlled_RX_mixer for an instance of the maximal independet set problem for a given graph \(G\) following Hadfield et al.

The belonging predicate function indicates if a set can be swapped into the solution.

Parameters:

Gnx.Graph: The graph for the problem instance.

Returns:

function: A Python function receiving a QuantumVariable and real parameter \(\beta\). This function performs the application of the mixer associated to the graph \(G\).

Classical cost function#

create_max_indep_set_cl_cost_function(G)[source]#

Creates the classical cost function for an instance of the maximal independet set 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.

Initial state function#

max_indep_set_init_function(qv)[source]#

Prepares the initial state \(\ket{0}^{\otimes n}\).

Parameters:

qvQuantumVariable: The quantum argument.

MaxIndepSet problem#

max_indep_set_problem(G)[source]#

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 MaxIndepSet for a given graph G.

Example implementation#

from qrisp import QuantumVariable
from qrisp.qaoa import QAOAProblem, RZ_mixer, create_max_indep_set_cl_cost_function, create_max_indep_set_mixer, max_indep_set_init_function
import networkx as nx

G = nx.erdos_renyi_graph(9, 0.5, seed =  133)
qarg = QuantumVariable(G.number_of_nodes())

qaoa_max_indep_set = QAOAProblem(cost_operator=RZ_mixer,
                                mixer=create_max_indep_set_mixer(G),
                                cl_cost_function=create_max_indep_set_cl_cost_function(G),
                                init_function=max_indep_set_init_function)
results = qaoa_max_indep_set.run(qarg=qarg, depth=5)

That’s it! In the following, we print the 5 most likely solutions together with their cost values.

cl_cost = create_max_indep_set_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([index for index, value in enumerate(res) if value == '1'], prob, cl_cost({res : 1}))

Finally, we visualize the most likely solution.

most_likely = [index for index, value in enumerate(max_five[0][0]) if value == '1']
nx.draw(G, with_labels = True,
        node_color=['#FFCCCB' if node in most_likely else '#ADD8E6' for node in G.nodes()],
        edge_color='#D3D3D3')