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:
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 <constraintaddmodel>` 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.
NTRKZFD [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.
PTRIshikawa [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)\).
PTRIshikawa (Ising)
The Amplify SDK implements its own version of PTRIshikawa’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 \(n2\), 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 nontrivial and must be adjusted.
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 autoestimate (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].
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 readonly properties that return the internal representations of a logical model class.
Input layer 
Logical layer 
Theoretical model 


Polynomial object 

Matrix object 

Constraint object 
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)]