Quadratic Model

This section describes the quadratic model (logical model) class and its related functions. The logical model class is responsible for modeling the objective function and the constraints as a “logical model” and reduce to a QUBO problem. The logical model class is used when executing the Ising machine using the solver class (Solver).

See also

Before reading this section, please review the Tutorial for basic Amplify SDK usage and the Polynomial for polynomial and Constraint for constraint objects.

Creating Logical Model Object

The correspondence between input model classes and logical model classes is as follows:

Logical model class	Input model class
BinaryQuadraticModel	BinaryPoly BinaryMatrix BinaryConstraint BinaryConstraints BinaryIntPolyBinaryIntMatrix BinaryIntConstraint BinaryIntConstraints
BinaryIntQuadraticModel	BinaryIntPolyBinaryIntMatrix BinaryIntConstraint BinaryIntConstraints
IsingQuadraticModel	IsingPoly IsingMatrix IsingConstraint IsingConstraints IsingIntPoly IsingIntMatrix IsingIntConstraint IsingIntConstraints
IsingIntQuadraticModel	IsingIntPoly IsingIntMatrix IsingIntConstraint IsingIntConstraints

The logical model class is constructed as below.

Construct from a Polynomial

A polynomial object can be converted to a logical model.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel

gen = BinarySymbolGenerator()
q = gen.array(2)  # Generate variable array of length 2
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
model = BinaryQuadraticModel(f)

You can get the input polynomial object with the input_poly property.

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> model.input_poly
2 q_0 q_1 + q_0 + q_1 - 1

Polynomials of degree three or higher can also be handled.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel

gen = BinarySymbolGenerator()
q = gen.array(3)  # Generate variable array of length 3
f = 3 * q[0] * q[1] * q[2] + 2 * q[0] * q[1] + q[0] - 1  # Cubic polynomial
model = BinaryQuadraticModel(f)

>>> f
3 q_0 q_1 q_2 + 2 q_0 q_1 + q_0 - 1
>>> model.input_poly
3 q_0 q_1 q_2 + 2 q_0 q_1 + q_0 - 1

The logical model can be obtained as follows:

>>> model.logical_poly
5 q_0 q_1 + 3 q_0 q_2 - 3 q_0 q_3 + 3 q_1 q_2 - 3 q_1 q_3 - 3 q_2 q_3 + q_0 + 3 q_3 - 1

In this case, a higher order polynomial is converted to a quadratic polynomial with auxiliary variables using a degree reduction algorithm. Note that the variable indices are mapped differently from the input variables.

See also

Please refer to Methods to Reduce the Degree of a Polynomial for more information on the degree reduction algorithms implemented in Amplify SDK and how to select one.

Construct from a Matrix

A matrix object can be converted to a logical model.

from amplify import BinaryMatrix, BinaryQuadraticModel

m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
model = BinaryQuadraticModel(m)

The input_matrix property allows you to see the input objective function in matrix form. Note that it is returned as a pair of a matrix and a constant.

>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]
>>> model.input_matrix
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.0)

The input_poly can also be used to get the input.

>>> model.input_poly
q_0 q_1 - q_1 q_2 - 2 q_0 + q_2

Construct from Constraints

From Single Constraint

A constraint object can be converted to a logical model.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel
from amplify.constraint import one_hot

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
c1 = one_hot(q[:3])   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(c1)

The constraints can be obtained by using the input_constraints property.

>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1, 1)]

From Multiple Constraints

Multiple constraint objects (or a constraints object) can be also converted into logical models.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel
from amplify.constraint import one_hot

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
c1 = one_hot(q[:3])   # q_0 + q_1 + q_2 == 1
c2 = one_hot(q[1:])   # q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(c1 + c2)

>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1, 1), (q_1 + q_2 + q_3 == 1, 1)]

Construct from a Polynomial and Constraints

A logical model object can be created from a polynomial and constraint objects (in that the polynomial is constrained by the constraints).

from amplify import BinarySymbolGenerator, BinaryQuadraticModel
from amplify.constraint import one_hot

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = one_hot(q[:3])   # q_0 + q_1 + q_2 == 1
c2 = one_hot(q[1:])   # q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(f, c1 + c2)

>>> model.input_poly
2 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1, 1), (q_1 + q_2 + q_3 == 1, 1)]

A logical model object can also be created by adding constraints to a polynomial object. Please see :ref:` Addition Operator <constraint-add-model>` of constraint class for details.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel
from amplify.constraint import one_hot

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = one_hot(q[:3])   # q_0 + q_1 + q_2 == 1
c2 = one_hot(q[1:])   # q_1 + q_2 + q_3 == 1
model = f + c1 + c2

>>> model.input_poly
2 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1, 1), (q_1 + q_2 + q_3 == 1, 1)]

Construct from a Matrix and Constraints

A logical model object can be created from a matrix and constraint objects. This model expresses that the quadratic polynomial represented by the matrix is constrained by the constraints.

from amplify import BinarySymbolGenerator, BinaryMatrix, BinaryQuadraticModel
from amplify.constraint import one_hot

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
c1 = one_hot(q[:3])   # q_0 + q_1 + q_2 == 1
c2 = one_hot(q[1:])   # q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(m, c1 + c2)

>>> model.input_matrix
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.0)
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1, 1), (q_1 + q_2 + q_3 == 1, 1)]

Methods to Reduce the Degree of a Polynomial

The following methods are implemented for reducing a higher degree polynomial to a quadratic polynomial. The method and parameters can be specified when constructing the logical model.

NTR-KZFD [1] [2]

A term of a polynomial over binary variables with a negative coefficient can be transformed to a quadratic polynomial using a binary auxiliary variable \(x\) as below. Only one auxiliary variable is needed for each term of any degree \(n\), but it can only be used if the coefficient \(p\) is negative.

\[p \prod_{i =1}^{n}{q_i} \rightarrow x p \left( S + 1 - n \right) \ \left( p < 0 \right)\]

\[\text{where} \quad S = \sum_{i =1}^{n}{q_i}\]

PTR-Ishikawa [3]

A term over binary variables with a positive coefficient \(p\) and degree \(n\) can be transformed using binary auxiliary variables \(x_i\) as below. The number of auxiliary variables required is \(\mathrm{floor} \left( \left(n - 1\right) / 2 \right)\).

\[p \prod_{i =1}^{n}{q_i} \rightarrow \left| p \right| \frac{1}{2} S \left( S - 1 \right) - \left| p \right| \sum_{k = 1}^{\mathrm{floor} \left( \left(n - 1\right) / 2 \right)}{x_k \left( c_{n,k} \left( S - 2 k \right) + 1 \right) }\]

\[\begin{split}\begin{align*} \text{where} \quad c_{n,k} &= \begin{cases} 1, & \text{if $n$ is odd and $k = \mathrm{floor} \left( \left(n - 1\right) / 2 \right)$} \\ 2, & \text{otherwise} \end{cases} , \\ S &= \sum_{i =1}^{n}{q_i} \end{align*}\end{split}\]

PTR-Ishikawa (Ising)

The Amplify SDK implements its own version of PTR-Ishikawa’s Ising version. An Ising term of degree \(n\) is transformed using auxiliary Ising variables \(y_i\). One of the following two cases is performed depending on the sign of the coefficient \(p\) and the parity of the degree \(n\).

• \(p > 0\) and \(n\) is odd, or \(p < 0\) and \(n\) is even

  \[p \prod_{i =1}^{n}{s_i} \rightarrow 2 \left| p \right| S^2 - 8 \left| p \right| \sum_{k = 1}^{\mathrm{floor} \left( n / 2 \right)}{x_k \left( S - 2 k + 1 \right) } - \left| p \right|\]
  \[\text{where} \quad S = \sum_{i =1}^{n}{\frac{s_i + 1}{2}}, \quad x_k = \frac{y_k + 1}{2}\]

• \(p > 0\) and \(n\) is even, or \(p < 0\) and \(n\) is odd

  \[p \prod_{i =1}^{n}{q_i} \rightarrow 2 \left| p \right| \left( S - 1 \right)^2 - 8 \left| p \right| \sum_{k = 1}^{\mathrm{floor} \left( \left(n - 1\right) / 2 \right)}{x_k \left( S - 2 k \right) } - \left| p \right|\]
  \[\text{where} \quad S = \sum_{i =1}^{n}{\frac{s_i + 1}{2}}, \quad x_k = \frac{y_k + 1}{2}\]

Substitution [4]

A product of two distinct binary variables can be substituted by a binary auxiliary variable \(x\), imposing an additional constraint with penalty function \(g\) to the model. Terms of degree 4 or higher can be also converted to a quadratic model by performing this substitution recursively. The number of auxiliary variables required for a binary term of degree \(n\) is \(n-2\), but it is sometimes possible to share an auxiliary variable by doing the substitution simultaneously for multiple terms which have the same variable pair in common. However, determining the appropriate weight of the penalty function \(g\) is generally non-trivial and must be adjusted.

\[q_1 q_2 \rightarrow x\]

\[g \left(q_1, q_2, x \right) = q_1 q_2 − 2 q_1 x − 2 q_2 x + 3 x\]

Specify a Reduction Method

When constructing a logical model from a polynomial object, QuadratizationMethod class can be given as the keyword argument method to select the degree reduction method.

from amplify import (
    BinarySymbolGenerator,
    BinaryQuadraticModel,
    QuadratizationMethod,
    pair_sum,
)

gen = BinarySymbolGenerator()
q = gen.array(8)  # Generate variable array of length 8
f = pair_sum(q) ** 4  # Example of creating a higher degree polynomial

# degree reduction using the Substitution method
BinaryQuadraticModel.substitution_multiplier = 2.0  # Specify the weight of the penalty functions used in the substitution method
model = BinaryQuadraticModel(f, method=QuadratizationMethod.SUBSTITUTION)

>>> model.num_input_vars   # Number of variables before lowering the degree
8
>>> model.num_logical_vars # Number of variables after lowering the degree
69

The following values can be selected:

QuadratizationMethod.ISHIKAWA

The Ishikawa’s method is used to perform the degree reduction. This method can be used in polynomials over Ising variables.

QuadratizationMethod.ISHIKAWA_KZFD [Default]

Hybrid method of the Ishikawa’s and the KZFD. The KZFD method is applied to binary terms with negative coefficients, and the Ishikawa’s method is applied to binary terms with positive coefficients. For polynomials over Ising variables, the Ishikawa’s method is used for all terms since the KZFD method cannot be applied to Ising terms.

QuadratizationMethod.SUBSTITUTION

The substitution method is used to perform the degree reduction. Ishikawa’s method is used for polynomials over Ising variables since the substitution method for Ising terms is not yet implemented.

QuadratizationMethod.SUBSTITUTION_KZFD

Hybrid method of the substitution and the KZFD. The KZFD is applied to binary terms with negative coefficients, and the substitution method is applied to binary terms with positive coefficients. For Ising terms, Ishikawa’s method is used since they are not yet implemented.

Each method has its advantages and disadvantages. The Ishikawa’s and KZFD methods use fewer auxiliary variables for a single term, but the substitution method may be more efficient when the same variable pair appears in multiple terms. On the other hand, the substitution method sets a penalty function as a constraint on substitution, and thus requires setting the strength of the penalty function, whereas the Ishikawa’s and KZFD methods do not. Amplify SDK estimates the appropriate strength and uses it as the initial value, but it may need to be adjusted to obtain an accurate solution. Also, the substitution target is determined by the greedy algorithm, so it is not always optimized for the determination of substitution variables.

from amplify import BinaryQuadraticModel

# Specifies the strength of the penalty function of Substitution
# Gives the ratio from the auto-estimate (default is 1.01)
BinaryQuadraticModel.substitution_multiplier = 2.0

We recommend using the default ISHIKAWA_KZFD for small problems; however, if the problem size greatly increases due to degree reduction, we recommend instead trying SUBSTITUTION or SUBSTITUTION_KZFD. Please note that the Substitution method may require adjustment of the weight of the penalty function.

See also

A review of various degree reduction methods is summarized in “Quadratization in discrete optimization and quantum mechanics” [5].

[1]

V. Kolmogorov and R. Zabih, “What energy functions can be minimized via graph cuts?” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 147–159 (2004).

[2]

D. Freedman and P. Drineas, “Energy Minimization via Graph Cuts: Settling What is Possible,” in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), Vol. 2 (IEEE, 2005) pp. 939–946.

[3]

H Ishikawa, “Transformation of General Binary MRF Minimization to the First-Order Case,” IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1234–1249 (2011).

[4]

I. G. Rosenberg, “Reduction of Bivalent Maximization to the Quadratic Case,” Cahiers du Centre d’Etudes de Recherche Operationnelle 17, 71–74 (1975).

[5]

Nike Dattani, “Quadratization in discrete optimization and quantum mechanics” http://arxiv.org/abs/1901.04405

Internal of the Logical Model Class

The logical model class performs a transformation of the input model object into a quadratic polynomial, the form the Ising machine can handle, and maps the indices of input variables to those of logical variables. This section describes how to get the transformation information and the transformation results from the internal information of the logical model.

Note

The interface for obtaining internal information may change in the future.

The following table shows read-only properties that return the internal representations of a logical model class.

	Input layer	Logical layer	Theoretical model
Polynomial object	input_poly	logical_poly	logical_model_poly
Matrix object	input_matrix	logical_matrix	logical_model_matrix
Constraint object	input_constraints	input_constraints/penalty	N/A

The input object is reduced to a quadratic polynomial and reassigned an index. The object before and after conversion can be obtained with the above properties. The mapping between the input index and the logical index can be obtained as a dictionary with the logical_mapping. This dictionary has the input indices as keys and logical indices as values.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
model = BinaryQuadraticModel(f)

>>> model.input_poly
2 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1
>>> model.logical_poly
3 q_0 q_1 + 2 q_0 q_2 - 2 q_0 q_3 + 2 q_1 q_2 - 2 q_1 q_3 - 2 q_2 q_3 + q_0 + q_1 + q_2 + 2 q_3 - 1
>>> model.logical_mapping
{0: 0, 1: 1, 2: 2}

Constraint objects can be added later to the logical model object.

from amplify.constraint import one_hot

c1 = one_hot(q[:3])
c2 = one_hot(q[1:])
model += c1 + c2

>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1, 1), (q_1 + q_2 + q_3 == 1, 1)]

The quadratic expression of the logical model is the sum of the converted objective function and the penalty function of the constraints.

>>> model.logical_model_poly
5 q_0 q_1 + 4 q_0 q_2 - 2 q_0 q_3 + 6 q_1 q_2 - 2 q_1 q_3 + 2 q_1 q_4 - 2 q_2 q_3 + 2 q_2 q_4 - q_1 - q_2 + 2 q_3 - q_4 + 1

In the above we obtained the quadratic expression in a polynomial form, but it can be obtained in matrix form as well using the logical_model_matrix.

Methods of the Logical Model Class

Obtain the Number of Input Variables

Obtain the number of variables in the input model.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel
from amplify.constraint import one_hot

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = one_hot(q)   # q_0 + q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(f, c)

The number of variables appearing in the polynomial f and the constraint c is returned.

>>> model.num_input_vars
4

Obtain the Number of Logical Variables

Obtain the number of variables contained in the quadratic polynomial, which is the internal representation of the logical model.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel
from amplify.constraint import one_hot

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = one_hot(q)   # q_0 + q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(f, c)

Note that this does not necessarily equal to the number of variables in the input model. In the above example, since the polynomial f is a higher degree polynomial, it is transformed to a quadratic polynomial with auxiliary variables. Therefore, the number of variables needed in the logic model is the number of variables in the input model plus the auxiliary variables. You can check the logical model and the number of its variables as follows:

>>> model.logical_model_poly
5 q_0 q_1 + 4 q_0 q_2 - 2 q_0 q_3 + 2 q_0 q_4 + 4 q_1 q_2 - 2 q_1 q_3 + 2 q_1 q_4 - 2 q_2 q_3 + 2 q_2 q_4 + 2 q_3 - q_4
>>> model.num_logical_vars
5

Obtain Constraints Objects

Obtain the container of the constraint object.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel
from amplify.constraint import one_hot

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = one_hot(q)   # q_0 + q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(f, c)

>>> model.input_constraints
[(q_0 + q_1 + q_2 + q_3 == 1, 1)]
>>> model.logical_model_poly
5 q_0 q_1 + 4 q_0 q_2 - 2 q_0 q_3 + 2 q_0 q_4 + 4 q_1 q_2 - 2 q_1 q_3 + 2 q_1 q_4 - 2 q_2 q_3 + 2 q_2 q_4 + 2 q_3 - q_4

The weights of the constraints can be changed after the logical model is constructed. After the change, the logical model will change.

>>> model.input_constraints[0][1] = 2
>>> model.input_constraints
[(q_0 + q_1 + q_2 + q_3 == 1, 2)]
>>> model.logical_model_poly
7 q_0 q_1 + 6 q_0 q_2 - 2 q_0 q_3 + 4 q_0 q_4 + 6 q_1 q_2 - 2 q_1 q_3 + 4 q_1 q_4 - 2 q_2 q_3 + 4 q_2 q_4 - q_0 - q_1 - q_2 + 2 q_3 - 2 q_4 + 1

Check If Constraints are Satisfied

The check_constraints() function can perform constraint satisfaction checks on all the constraint objects contained in the logical model. The arguments that can be given is the same as in is_satisfied(). Please refer to here for details.

This function is used to check which constraints are satisfied or not satisfied for the obtained output solution. The weight of the constraints in the logical model can also be retrieved and modified in the same way as Obtain Constraints Objects.

from amplify import BinarySymbolGenerator
from amplify.constraint import one_hot, less_equal

gen = BinarySymbolGenerator()
q = gen.array(3)  # Generate variable array of length 3
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = one_hot(q[0] + q[2])  # q_0 + q_2 == 1
c2 = less_equal(q[0] + q[1], 1)  # q_0 + q_1 <= 1
model = f + c1 + c2
checked = model.check_constraints({0: 1, 1: 1, 2: 0})  # q[0] = q[1] = 1, q[2] = 0

>>> checked
[((q_0 + q_2 == 1, 1), True), ((q_0 + q_1 <= 1, 1), False)]

The output is returned in a list of constraint objects and results in pairs. In the above, we check if q = [1, 1, 0] satisfies the constraints, to result in q_0 + q_2 == 1 but not q_0 + q_1 <= 1. Here the variable values are expressed in a dictionary form assuming that the output of the Solver class is given, but it is also possible to give a list.

As an example of using the check_constraints() function, we can change the weight of a constraint object only if the constraint is not satisfied.

for c, r in checked:
    if r is False:
        c[1] *= 2

>>> model.input_constraints
[(q_0 + q_2 == 1, 1), (q_0 + q_1 <= 1, 2)]

Logical Model Class Operators

Adding a constraint object or a constraint container to a logical model object adds a constraint. See Addition Operator of the constraint class for details.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel

gen = BinarySymbolGenerator()
q = gen.array(4)  # Generate variable array of length 4
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
model = BinaryQuadraticModel(f)

>>> model.input_poly
2 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1
>>> len(model.input_constraints)
0

from amplify.constraint import one_hot

c1 = one_hot(q[:3])
c2 = one_hot(q[1:])
model += c1 + c2

>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1, 1), (q_1 + q_2 + q_3 == 1, 1)]