Source code for qrisp.qiro.qiroproblems.qiroMaxSat

"""
\********************************************************************************
* 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
********************************************************************************/
"""

# just write a replacement_routine and throw out not relevant sets

from qrisp import rz, x, cx
from qrisp import app_sb_phase_polynomial

import numpy as np
import math
import copy
from qrisp.algorithms.qiro.qiroproblems.qiro_utils import * 

from itertools import combinations



[docs]
def create_maxsat_replacement_routine(res, problem_updated):
    """
    Creates a replacement routine for the problem structure, i.e., defines the replacement rules. 
    See the `original paper <https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.5.020327>`_ for a description of the update rules.

    Parameters
    ----------
    res : dict
        Result dictionary of QAOA optimization procedure.
    problem_updated : List
        Updates that happened during the QIRO routine. Consits of the updated problem, a list of Qubits which were found to be positively correlated, i.e. part of the problem solution, 
        and a list Qubits which were found to be negatively correlated, i.e. they contradict solution qubits in accordance with the update rules.  

    Returns
    -------
    new_problem: list
        Updated clauses of the problem instance.
    solutions : list
        Updated set of solutions to the problem.
    sign : int
        The sign of the correlation.
    exclusions : list
        Updated set of exclusions to the problem.

    """

    problem = problem_updated[0]
    solutions = problem_updated[1]
    exclusions =  problem_updated[2]
    
    numVars = problem[0]
    clauses = copy.deepcopy(problem[1])

    # FOR SINGLE QUBIT CORRELATIONS
    # make -1 here for consistency in the find max
    orig_nodes = [i - 1 for i in list(range(1,numVars + 1)) if not i in exclusions]
    combinations_list = list(combinations(orig_nodes, 2))

    max_item, sign = find_max(orig_nodes, combinations_list, res, solutions)
    if max_item == None:
        return problem, solutions, 0 ,exclusions

    # we just directly remove clauses from the problem, or literals from the clause. 
    if isinstance(max_item, int):
        
        max_item += 1

        for sgl_clause in clauses:
            if sign < 0:
                #clause evaluates to TRUE, can empty the clause 
                if max_item in sgl_clause:
                    sgl_clause.clear()
                #clause evaluates to FALSE, can remove the literal
                # if its last literal remaining in the clause, we just remove the clause
                elif -1*max_item in sgl_clause: 
                    if len(sgl_clause) == 1:
                        clauses.remove(sgl_clause)
                    else:
                        val = -1* max_item
                        sgl_clause.remove(val)
                solutions.append(max_item)
                exclusions.append(max_item)

            #same as above
            elif sign > 0:
                if -1* max_item in sgl_clause:
                    sgl_clause.clear()
                elif max_item in sgl_clause: 
                    if len(sgl_clause) == 1:
                        clauses.remove(sgl_clause)
                    else:
                        val =  max_item
                        sgl_clause.remove(val)
                exclusions.append(max_item)


    else:
        max_item = [max_item[0] +1 , max_item[1] + 1 ]

        if sign > 0:
            for sgl_clause in clauses:
                # replace with pos. correlated number if its in an item
                if max_item[1] in sgl_clause:
                    temp = sgl_clause.index(max_item[1])
                    sgl_clause[temp] = max_item[0]
                if -1* max_item[1] in sgl_clause:
                    temp = sgl_clause.index(-1* max_item[1])
                    sgl_clause[temp] = -1* max_item[0]
                exclusions.append(max_item[1])
                    
        elif sign < 0:
            for sgl_clause in clauses:
                # replace with neg. correlated number if its in an item
                if max_item[1] in sgl_clause:
                    temp = sgl_clause.index(max_item[1])
                    sgl_clause[temp] = -1 * max_item[0]
                if -1* max_item[1] in sgl_clause:
                    temp = sgl_clause.index(-1  * max_item[1])
                    sgl_clause[temp] = max_item[0]
                exclusions.append(max_item[1])

    # create sign list somewhere?
    return [numVars, clauses], solutions, sign, exclusions




[docs]
def create_maxsat_cost_operator_reduced(problem_updated):

    """
    Creates the ``cost_operator`` for the problem instance.
    This operator is adjusted to consider qubits that were found to be a part of the problem solution.
    
    Parameters
    ----------
    problem_updated : List
        Updates that happened during the QIRO routine. Consits of the updated problem, a list of Qubits which were found to be positively correlated, i.e. part of the problem solution, 
        and a list Qubits which were found to be negatively correlated, i.e. they contradict solution qubits in accordance with the update rules.  

    Returns
    -------
    cost_operator : function
        A function receiving a :ref:`QuantumVariable` and a real parameter $\gamma$. This function performs the application of the cost operator.

    """
    
    from qrisp.algorithms.qaoa import create_maxsat_cost_polynomials

    problem = problem_updated[0]
    
    cost_polynomials, symbols = create_maxsat_cost_polynomials(problem)

    def cost_operator(qv, gamma):
        for P in cost_polynomials:
            if not isinstance(P, int):
                app_sb_phase_polynomial([qv], -P, symbols, t=gamma)

    return cost_operator