Source code for qrisp.qaoa.problems.maxClique

"""
\********************************************************************************
* Copyright (c) 2024 the Qrisp authors
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Public License 2.0 which is available at
* http://www.eclipse.org/legal/epl-2.0.
*
* This Source Code may also be made available under the following Secondary
* Licenses when the conditions for such availability set forth in the Eclipse
* Public License, v. 2.0 are satisfied: GNU General Public License, version 2
* with the GNU Classpath Exception which is
* available at https://www.gnu.org/software/classpath/license.html.
*
* SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0
********************************************************************************/
"""


from qrisp.algorithms.qaoa.problems.maxIndepSet import create_max_indep_set_cl_cost_function, create_max_indep_set_mixer, max_indep_set_init_function
import networkx as nx
import itertools



[docs]
def create_max_clique_cl_cost_function(G):
    """
    Creates the classical cost function for an instance of the maximum clique problem for a given graph $G$.

    Parameters
    ----------
    G : nx.Graph
        The Graph for the problem instance.

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

    """

    def cl_cost_function(res_dic):
        cost = 0
        for state, prob in res_dic.items():
            temp = True
            indices = [index for index, value in enumerate(state) if value == '1']
            combinations = list(itertools.combinations(indices, 2))
            for combination in combinations:
                if combination not in G.edges():
                    temp = False
                    break
            if temp: 
                cost += -len(indices)*prob

        return cost

    return cl_cost_function 




[docs]
def max_clique_problem(G):
    """
    Creates a QAOA problem instance with appropriate phase separator, mixer, and
    classical cost function.

    Parameters
    ----------
    G : nx.Graph
        The graph for the problem instance.

    Returns
    -------
    :ref:`QAOAProblem`
        A QAOA problem instance for MaxClique for a given graph ``G``.

    """        
    from qrisp.qaoa import QAOAProblem, RZ_mixer

    G_complement = nx.complement(G)

    return QAOAProblem(cost_operator=RZ_mixer,
                        mixer=create_max_indep_set_mixer(G_complement),
                        cl_cost_function=create_max_indep_set_cl_cost_function(G_complement),
                        init_function=max_indep_set_init_function)