MaxCutInstance

class iqm.applications.maxcut.MaxCutInstance(graph, break_z2=False)

Bases: QUBOInstance

The maxcut instance class.

This class is initialized with a graph whose maxcut we try to find. A maxcut is a division of the graph nodes into two groups, such that the number of edges connecting nodes from different groups is maximized. The optional break_z2 variable indicates whether the \(\mathbb{Z}_2\) symmetry of the problem is to be broken by pre-assigning one of the nodes to one of the groups.

Parameters:

• graph (Graph) – The Graph describing the maxcut problem.

• break_z2 (bool) – Boolean variable indicating whether the \(\mathbb{Z}_2\) symmetry of the problem should be artificially broken, reducing the number of problem variables by 1.

Raises:

ValueError – If the input graph’s nodes aren’t labelled by integers starting from 0.

Attributes

graph

The graph of the problem.

Methods

cut_size(bit_str)

Calculates the cut size of a solution represented by a bitstring.

property graph: Graph

The graph of the problem.

Equals the graph that was given on initialization of MaxCutInstance and shouldn’t be modified. Instead of modifying the graph, the user should instantiate a new object of MaxCutInstance.

cut_size(bit_str)

Calculates the cut size of a solution represented by a bitstring.

The calculation simply iterates over edges of the graph and adds +1 for each edge cut according to the bitstring. Since it uses the original graph, the input bitstring needs to have the same length as the graph has nodes.

Parameters:

bit_str (str) – A string of 0’s and 1’s (or any two distinct characters) representing the division of the graph into two sets.

Returns:

The number of edges cut.

Raises:

• ValueError – If the length of the input bitstring isn’t equal to the number of nodes of _graph.

• ValueError – If the bitstring contains more than 2 different characters (it doesn’t have to be 0’s and 1’s).

Return type:

int