examples/fourcolor.py
def graph_coloring_qubo(graph, k):
    """
    the QUBO for k-coloring a graph A is as follows:

    variables:
    x_{v,c} = 1 if vertex v of A gets color c; x_{v,c} = 0 otherwise

    constraints:
    1)  each v in A gets exactly one color.
       This constraint is enforced by including the term (\sum_c x_{v,c} - 1)^2 in the QUBO,
       which is minimized when \sum_c x_{v,c} = 1.

    2) If u and v in A are adjacent, then they get different colors.
       This constraint is enforced by including terms x_{v,c} x_{u,c} in the QUBO,
       which is minimzed when at most one of u and v get color c.

    Total QUBO:
    Q(x) = \sum_v (\sum_c x_{v,c} - 1)^2  + \sum_{u ~ v} \sum_c x_{v,c} x_{u,c}

    The graph of interactions for this QUBO consists of cliques of size k (with vertices {x_{v,c} for c = 0,...,k-1})
    plus k disjoint copies of the graph A (one for each color).

    """

    K = nx.complete_graph(k)
    g1 = nx.cartesian_product(nx.create_empty_copy(graph), K)
    g2 = nx.cartesian_product(graph, nx.create_empty_copy(K))
    return nx.compose(g1, g2)
def graph_coloring_qubo(graph, k):
    """
    the QUBO for k-coloring a graph A is as follows:

    variables:
    x_{v,c} = 1 if vertex v of A gets color c; x_{v,c} = 0 otherwise

    constraints:
    1)  each v in A gets exactly one color.
       This constraint is enforced by including the term (\sum_c x_{v,c} - 1)^2 in the QUBO,
       which is minimized when \sum_c x_{v,c} = 1.

    2) If u and v in A are adjacent, then they get different colors.
       This constraint is enforced by including terms x_{v,c} x_{u,c} in the QUBO,
       which is minimzed when at most one of u and v get color c.

    Total QUBO:
    Q(x) = \sum_v (\sum_c x_{v,c} - 1)^2  + \sum_{u ~ v} \sum_c x_{v,c} x_{u,c}

    The graph of interactions for this QUBO consists of cliques of size k (with vertices {x_{v,c} for c = 0,...,k-1})
    plus k disjoint copies of the graph A (one for each color).

    """

    K = nx.complete_graph(k)
    g1 = nx.cartesian_product(nx.create_empty_copy(graph), K)
    g2 = nx.cartesian_product(graph, nx.create_empty_copy(K))
    return nx.compose(g1, g2)
the QUBO for k-coloring a graph A is as follows:

    variables:
    x_{v,c} = 1 if vertex v of A gets color c; x_{v,c} = 0 otherwise

    constraints:
    1)  each v in A gets exactly one color.
       This constraint is enforced by including the term (\sum_c x_{v,c} - 1)^2 in the QUBO,
       which is minimized when \sum_c x_{v,c} = 1.

    2) If u and v in A are adjacent, then they get different colors.
       This constraint is enforced by including terms x_{v,c} x_{u,c} in the QUBO,
       which is minimzed when at most one of u and v get color c.

    Total QUBO:
    Q(x) = \sum_v (\sum_c x_{v,c} - 1)^2  + \sum_{u ~ v} \sum_c x_{v,c} x_{u,c}

    The graph of interactions for this QUBO consists of cliques of size k (with vertices {x_{v,c} for c = 0,...,k-1})
    plus k disjoint copies of the graph A (one for each color).