Source code for qiskit.optimization.converters.quadratic_program_to_qubo

# -*- coding: utf-8 -*-

# This code is part of Qiskit.
# (C) Copyright IBM 2020.
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.

"""A converter from quadratic program to a QUBO."""

from typing import Optional

from ..algorithms.optimization_algorithm import OptimizationResult
from ..problems.quadratic_program import QuadraticProgram
from ..problems.constraint import Constraint
from ..converters.linear_equality_to_penalty import LinearEqualityToPenalty
from ..exceptions import QiskitOptimizationError

[docs]class QuadraticProgramToQubo: """Convert a given optimization problem to a new problem that is a QUBO. Examples: >>> from qiskit.optimization.problems import QuadraticProgram >>> from qiskit.optimization.converters import QuadraticProgramToQubo >>> problem = QuadraticProgram() >>> # define a problem >>> conv = QuadraticProgramToQubo() >>> problem2 = conv.encode(problem) """ def __init__(self, penalty: Optional[float] = None) -> None: """ Args: penalty: Penalty factor to scale equality constraints that are added to objective. """ from ..converters.integer_to_binary import IntegerToBinary self._int_to_bin = IntegerToBinary() self._penalize_lin_eq_constraints = LinearEqualityToPenalty() self._penalty = penalty
[docs] def encode(self, problem: QuadraticProgram) -> QuadraticProgram: """Convert a problem with linear equality constraints into new one with a QUBO form. Args: problem: The problem with linear equality constraints to be solved. Returns: The problem converted in QUBO format. Raises: QiskitOptimizationError: In case of an incompatible problem. """ # analyze compatibility of problem msg = self.get_compatibility_msg(problem) if len(msg) > 0: raise QiskitOptimizationError('Incompatible problem: {}'.format(msg)) # map integer variables to binary variables problem_ = self._int_to_bin.encode(problem) # penalize linear equality constraints with only binary variables if self._penalty is None: # TODO: should be derived from problem penalty = 1e5 else: penalty = self._penalty problem_ = self._penalize_lin_eq_constraints.encode(problem_, penalty_factor=penalty) # return QUBO return problem_
[docs] def decode(self, result: OptimizationResult) -> OptimizationResult: """ Convert a result of a converted problem into that of the original problem. Args: result: The result of the converted problem. Returns: The result of the original problem. """ return self._int_to_bin.decode(result)
[docs] @staticmethod def get_compatibility_msg(problem: QuadraticProgram) -> str: """Checks whether a given problem can be solved with this optimizer. Checks whether the given problem is compatible, i.e., whether the problem can be converted to a QUBO, and otherwise, returns a message explaining the incompatibility. Args: problem: The optimization problem to check compatibility. Returns: A message describing the incompatibility. """ # initialize message msg = '' # check whether there are incompatible variable types if problem.get_num_continuous_vars() > 0: msg += 'Continuous variables are not supported! ' # check whether there are incompatible constraint types if not all([constraint.sense == Constraint.Sense.EQ for constraint in problem.linear_constraints]): msg += 'Only linear equality constraints are supported.' if len(problem.quadratic_constraints) > 0: msg += 'Quadratic constraints are not supported. ' # if an error occurred, return error message, otherwise, return None return msg
[docs] def is_compatible(self, problem: QuadraticProgram) -> bool: """Checks whether a given problem can be solved with the optimizer implementing this method. Args: problem: The optimization problem to check compatibility. Returns: Returns True if the problem is compatible, False otherwise. """ return len(self.get_compatibility_msg(problem)) == 0