Brute Force Minimization

Types

The brute-force minimization functions in Forge rely on custom types for problem specification, constraints, and results.

class qcware.types.optimization.PolynomialObjective(polynomial: Dict[Tuple[int, ], int], num_variables: int, domain: Union[qcware.types.optimization.variable_types.Domain, str] = Domain.BOOLEAN, variable_name_mapping: Optional[Dict[int, str]] = None, validate_types: bool = True)

Integer-valued polynomial of binary variables with int coefficients.

Objects of this class specify polynomials of some number of binary variables with integer coefficients. “Binary variables” can either mean variables taking on the values 0 and 1 or variables taking on the values 1 and -1. The former a referred to as boolean variables and the latter are referred to as spin variables

Objects of this class are meant to be treated as objective functions for optimization. They do not know about constraints. Constraints can be specified separately using a Constraints object.

Polynomials are specified with a dict that specifies the coefficients for the polynomial. For example, suppose that we are interested in the polynomial of three boolean variables defined by:

p(x, y, z) = 12 x - 2 y z + x y z - 50

The three variables should be associated with the integers 0, 1, and 2. We choose the association x ~ 0, y ~ 1, and z ~ 2.

There are four terms in p. Consider the term -2yz. We can specify this term by matching the tuple (1, 2), which represents yz, with the coefficient -2. This can be encoded with an entry in a dict (1, 2): -2. Overall, p can be defined by:

{
    (): -50,
    (0,): 12,
    (1, 2): -2,
    (0, 1, 2): -50
}

The number of variables must be specified explicitly, even if it seems obvious how many variables there are. The reason for this is to allow for the possibility that there are more variables than appear explicitly in the polynomial. For example, the polynomial p(a, b) = 12 b might be mistaken for q(b) = 12 b.

polynomial

The polynomial is specified by a dict as described above. We only use tuples of int as keys and the range of ints must be from 0 to num_variables - 1. Values for the dict must be type int. This is because we are only treating integer-coefficient polynomials.

Type

Dict[Tuple[int, ..], int]

variables

Set of ints representing the variables.

Type

Set[int]

num_variables

The number of variables for the polynomial. This number can be larger than the actual number of variables that appear in polynomial but it cannot be smaller.

Type

int

degree

The degree of the polynomial. This is not the mathematically correct degree. It is instead the length of the longest key in the polynomial dict or -inf in the case when the dict is {}. For example, the boolean PolynomialObjective {(1,): 12, (0, 1): 0} has mathematical degree 1 but the attribute degree is 2.

Type

Union[int, float]

domain

Specifies if variables take on boolean (0, 1) or spin (1, -1) values.

Type

qcware.types.optimization.variable_types.Domain

clone()

Make a copy of this PolynomialObjective.

pretty_str()

Make a string that presents the polynomial algebraically.

The names of variables can be controlled with the attribute variable_name_mapping.

Adapted from qubovert–thanks to Joseph T. Iosue.

qubovert(use_variable_names: bool = False)

Get a qubovert model describing this polynomial.

This method will return a qubovert PUBO or PUSO depending on the domain of the variables.

Parameters

use_variable_names – When True, the variables in the qubovert object will use the same string names as appear in the attribute variable_name_mapping.

qubovert_boolean()

Get a boolean qubovert model equivalent to this polynomial.

This produces a PUBOMatrix which is qubovert’s enumerated form of a PUBO (polynomial unconstrained boolean optimization). This transformation may change the variable ordering and for that reason we also return a mapping that can be used to recover the original variable identifiers.

qubovert_spin()

Get a spin qubovert model equivalent to this polynomial.

This produces a PUSOMatrix which is qubovert’s enumerated form of a PUSO (polynomial unconstrained spin optimization). This transformation may change the variable ordering and for that reason we also return a mapping that can be used to recover the original variable identifiers.

reduce_variables()

Return a PolynomialObjective with trivial variables removed.

As an example, suppose that we have a PolynomialObjective defined by

PolynomialObjective(

polynomial={(1,): 1}, num_variables=3

)

which essentially means p(x, y, z) = y. This has two variables that the polynomial doesn’t actually depend on. In this case, this function will return a polynomial of one variable along with a mapping to identify variables appropriately. Specifically, the return would be

{
‘polynomial’: PolynomialObjective(polynomial={(0,): 1},

num_variables=1 )

‘mapping’: {1: 0}

}.

classmethod validate_type(v)

This validator only confirms that we are dealing with an object of the expected type. This does not validate internal consistency of attributes for the Objective function because that is done by __init__.

class qcware.types.optimization.Constraints(constraints: Dict[qcware.types.optimization.predicate.Predicate, List[qcware.types.optimization.problem_spec.objective.PolynomialObjective]], num_variables: int, validate_types: bool = True)

Specification of constraints on binary variables.

An object of class Constraints does not have information about the objective function on which the constraints are applied. It is simply a collection of constraints which can then be imposed on something.

To specify constraints, we use a “constraint dict”. The format of this dict is:

{type of constraint: list of constraints of that type}.

The “type of constraint” means a Predicate object. The list of constraints of a given Predicate are a list of PolynomialObjective s.

This can be understood fairly easily by example. Suppose that f is an PolynomialObjective with 3 boolean variables. We take:

f(x, y, z) = (x + y + z - 1)^2

which is minimized when exactly one of the three variables is 1.

If we want to impose the condition that either x or z is zero, we can roughly use the constraint dict:

{Predicate.ZERO: [p]}

where p is the PolynomialObjective representing the function:

p(x, y, z) = OR(x, z) = x + z - x z

(To build this, see the documentation for PolynomialObjective.) If we additionally want to add the constraint that the sum of the three variables is at least 2, we can make our dict:

{Predicate.ZERO: [p], Predicate.POSITIVE: [q]}

where q is a PolynomialObjective representing q(x, y, z) = x + y + z - 1. The reason that we are using [p] and [q] instead of just p and q is that we can add additional constraints of those types in this fashion by adding more entries to the lists.

constraint_exists(order: Optional[Union[int, Iterable[int]]] = None, predicate: Optional[qcware.types.optimization.predicate.Predicate] = None)

Return True iff a constraint exists with given order or predicate.

order can be an int or an iterable of ints. predicate is a Predicate object.

If order and predicate are both None, this function returns True iff any constraint exists.

get_constraint_group(predicate: qcware.types.optimization.predicate.Predicate, order: Optional[Union[int, Iterable[int]]] = None)

Iterate over constraints with specified predicate and order.

If order is not specified, all orders are generated.

num_constraints(predicate: Optional[qcware.types.optimization.predicate.Predicate] = None)

Return the number of constraints.

If a predicate is specified, only return the number of constraints for that predicate.

class qcware.types.optimization.BruteOptimizeResult(*, domain: qcware.types.optimization.variable_types.Domain, value: int = None, arguments: List[str] = [], solution_exists: bool = True)

Return type for brute force maximization and minimization.

When solution_exists == False, we must have value is None and arguments == [].

Arguments are specified with a list of strings that describe solutions. For the boolean case, this means something like [‘00101’, ‘11100’] and for the spin case, this means something like [‘++-+-‘, ‘—++’].

int_argument()List[List[int]]

Convert arguments to a list of list of ints.

Functions

qcware.optimization.brute_force_minimize(objective: qcware.types.optimization.problem_spec.objective.PolynomialObjective, constraints: Optional[qcware.types.optimization.problem_spec.constraints.Constraints] = None, backend: str = 'qcware/cpu')

Minimize given objective polynomial subject to constraints.

Arguments:

Parameters
  • objective (types.PolynomialObjective) – The integer-coefficient polynomial to be evaluated should be specified by a PolynomialObjective. See documentation for PolynomialObjective for more information. Note that variables are boolean in the sense that their values are 0 and 1.

  • constraints (Optional[types.Constraints]) – Optional constraints are specified with an object of class Constraints. See its documentation for further information., defaults to None

  • backend (str) – String specifying the backend. Currently only [qcware/cpu] available, defaults to qcware/cpu

Returns

BruteOptimizeResult object specifying the minimum value of the objective function (that does not violate a constraint) as well as the variables that attain this value.

Return type

types.BruteOptimizeResult