Polynomial

This section describes the polynomial class of binary variables and Ising variables and their peripheral functions.

Binary Multivariable Polynomial

A \(n\)-th order polynomial \(f_n\) with binary or Ising variables is generally expressed as below:

\[ \begin{align}\begin{aligned}f_n \left( x_1, x_2, \cdots, x_n \right) = \sum_{ \left\{ k_1, k_2, \cdots, k_n \right\} } { a_{k_1, k_2, \cdots, k_n} x_1^{k_1} x_2^{k_2} \cdots x_n^{k_n} }\\k_i \in \left\{ 0, 1 \right\}\end{aligned}\end{align} \]

Here, \(x_i\) represents a binary or Ising variable. From this point on, we will use \(q\) instead of \(x\) when the variable is a binary variable \(\left\{0, 1\right\}\), and \(s\) instead of \(x\) when the variable is an Ising variable \(\left\{-1, 1\right\}\). Due to the following properties of binary and Ising variables, the highest order term appearing in a polynomial is quadratic.

\[ \begin{align}\begin{aligned}q ^ 2 &= q \quad \left( q \in \left\{ 0, 1 \right\} \right)\\s ^ 2 &= 1 \quad \left( s \in \left\{ -1, + 1 \right\} \right)\end{aligned}\end{align} \]

Amplify SDK provides the following classes to represent polynomials that follow the algebraic rules for binary and Ising variables.

BinaryPoly and IsingPoly are polynomials whose variables are the binary variable \(\left\{0, 1\right\}\) and the Ising variable \(\left\{-1, 1\right\}\), respectively. They can represent any degree (e.g., cubic or higher) and also include a constant term. When the degree is fixed to \(2\), the QUBO model and the Ising model are obtained, respectively.

Note

BinaryIntPoly and IsingIntPoly are used to restrict the coefficients to integer values. Even in the middle of a calculation, unintended results may occur due to the limitation to integers. So BinaryPoly and IsingPoly, which can handle real numbers, are usually recommended.

Building Polynomial Classes

A polynomial class is constructed by default as follows (henceforth BinaryPoly is used as an example, but the same is true for other polynomial classes including Ising class):

from amplify import BinaryPoly

f = BinaryPoly()
>>> f
0

To set the initial value, we give a set of terms to the constructor argument. A key/value pair of the following form is interpreted as a term.

  • \(k x_i x_j \cdots x_m\) \(\to\) (i, j, ..., m): k

Multiple terms can be combined into a dictionary.

  • \(k_2 x_i x_j + k_1 x_i + c\) \(\to\) {(i, j): k2, (i): k1, (): c}

For example, the construction of \(f = 2 q_0 q_1 + q_0 + q_1 - 1\) can be written as:

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1, (1): 1, (): -1})
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

Only the constant term has an alternative expression, simply numerical values can represent constant terms.

  • \(c\) \(\to\) c

You can also give more than one of the above notations as arguments to the constructor.

For example, \(f = 2 q_0 q_1 + q_0 + q_1 - 1\) above can be alternatively expressed as follows:

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1}, {(1): 1}, -1)
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

If an object of the same polynomial class is given as the constructor argument, it will be copied.

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1}, {(1): 1}, -1)
g = BinaryPoly(f)
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> g
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

Polynomial Operators

In the polynomial class, equivalence, addition, subtraction, multiplication, division, and exponentiation are defined between polynomial objects themselves, as well as between them and terms and constants. For exponentiation and division, only polynomial (left hand side) and numeric (right hand side) are supported. Although omitted in the following, compound assignment operators are also supported.

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1}, {(1): 1}, -1)
>>> f + f
4.000000 q_0 q_1 + 2.000000 q_0 + 2.000000 q_1 - 2.000000
>>> f + {(0, 1, 2): 1}
q_0 q_1 q_2 + 2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f + 1
2.000000 q_0 q_1 + q_0 + q_1
>>> f - f
0
>>> f - {(0, 1): 1}
q_0 q_1 + q_0 + q_1 - 1.000000
>>> f - 2
2.000000 q_0 q_1 + q_0 + q_1 - 3.000000
>>> f * f
10.000000 q_0 q_1 - q_0 - q_1 + 1.000000
>>> f * {(2): 1}
2.000000 q_0 q_1 q_2 + q_0 q_2 + q_1 q_2 - q_2
>>> 2 * f
4.000000 q_0 q_1 + 2.000000 q_0 + 2.000000 q_1 - 2.000000
>>> f / 2
q_0 q_1 + 0.500000 q_0 + 0.500000 q_1 - 0.500000
>>> f ** 2
10.000000 q_0 q_1 - q_0 - q_1 + 1.000000
>>> f + f == 2 * f
True

Building Polynomials with Variable Arrays

The index of a variable is usually an integer value greater than or equal to \(0\). However, we sometimes need to manage variables whose indices are two or more dimensions, or to prepare necessary variables in advance to manage them by groups. In such cases, the gen_symbols() function is useful. By specifying a polynomial class, starting number for array index (0 by default if omitted), and array length, it generates the corresponding array of variables.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10) # Create a variable array with starting number 0 and length 10
>>> q
[q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7, q_8, q_9]

Instead of building a polynomial equation using terms, we can also build the same equation using a variable array q .

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

Note

If you call gen_symbols() more than once, you may need to specify the starting number explicitly. If the starting number is not specified, variables with the same index will appear in separately defined variable arrays.

from amplify import BinaryPoly, gen_symbols

qs1 = gen_symbols(BinaryPoly, 4)    # Starting number 0, length 4
qs2 = gen_symbols(BinaryPoly, 4)    # Starting number 0, length 4 (identical to qs1)
qs3 = gen_symbols(BinaryPoly, len(qs1), (4, ))  # Shift the starting number by the length of qs1
>>> qs1
[q_0, q_1, q_2, q_3]
>>> qs2
[q_0, q_1, q_2, q_3]
>>> qs3
[q_4, q_5, q_6, q_7]

To create a variable array of an arbitrary dimension, we specify an additional size corresponding to the shape of the array.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 2, 2)
>>> q
[[q_0, q_1], [q_2, q_3]]

It is also possible to specify a starting number, but note that the array form shape must be given as a tuple.

from amplify import BinaryPoly, gen_symbols

q_a = gen_symbols(BinaryPoly, 0, (2, 2))
q_b = gen_symbols(BinaryPoly, 4, (2, 2))
>>> q_a
[[q_0, q_1], [q_2, q_3]]
>>> q_b
[[q_4, q_5], [q_6, q_7]]

Note

The method using variable arrays is simple and intuitive for handling equations. In addition, it is usually recommended to use this method since it hides the raw variable indices and allows the user to handle variables with convenient indices.

Assigning Values to a Variable Array

There may be cases where you want to assign a value to a part of the variable array created by the gen_symbols() function. In such a case, it is possible to access the elements of the variable array and assign values to them.

The following is an example where the value of the variable to be solved is already known.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
q[0] = 1
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f
3.000000 q_1

It is possible to use the same variable across different variables, by assigning one variable to others.

q = gen_symbols(BinaryPoly, 10)
q[1] = q[0]
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f
4.000000 q_0 - 1.000000

Obtaining a Solution Using a Variable Array

The decode_solution() function is useful for substituting the output values of the solver class Solver to the variable arrays from the gen_symbols() function. Giving a variable array and values to the decode_solution() function, it returns the variable array in the same form as the input array by making substitution with the given values. Users thus do not need to directly handle the indices hidden by gen_symbols() for making a substitution.

The following is an example of using the decode_solution() function.

from amplify import BinaryPoly, gen_symbols, Solver, decode_solution
from amplify.client import FixstarsClient

q = gen_symbols(BinaryPoly, 0, (2, 2))
f = (
    -q[0][0] * q[1][1]
    + q[0][0] * q[0][1]
    + q[0][1] * q[1][1]
    + q[0][0] * q[1][0]
    + q[1][0] * q[1][1]
)

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000

solver = Solver(client)
result = solver.solve(f)
values = result[0].values
d = decode_solution(q, values)
>>> d[0][0]
1.000000
>>> d[0][1]
0
>>> d[1][0]
0
>>> d[1][1]
1.000000

Here, q is a \(2\times2\) array of variables. By using the output of the solver values and the variable array q, we can use decode_solution(q, values) to get the \(2 \times 2\) variable array d of the same shape as q. This makes it possible to access the elements of d by the same form of indices as the variable array, such as d[0][0], without referring to the \(2\times 2\) array q.

We can check the internal index of the variable array and the output values of the solver.

>>> q
[[q_0, q_1], [q_2, q_3]]
>>> values
{0: 1, 1: 0, 2: 0, 3: 1}
>>> d
[[1.000000, 0], [0, 1.000000]]

We have verified that the decode_solution() function correctly replaces q with values.

In the above, all the elements of the variable array have been replaced. However, there are cases that not all variables can be replaced as seen in the following example.

from amplify import BinaryPoly, gen_symbols, Solver, decode_solution
from amplify.client import FixstarsClient

q = gen_symbols(BinaryPoly, 0, (3, 3))
f = (
    -q[0][0] * q[1][1]
    + q[0][0] * q[0][1]
    + q[0][1] * q[1][1]
    + q[0][0] * q[1][0]
    + q[1][0] * q[1][1]
)

As a change from the previous example, q has been extended to \(3 \times 3\). As before, we give the polynomial to the solver and obtain the solution with the decode_solution() function.

solver = Solver(client)
result = solver.solve(f)
values = result[0].values
d = decode_solution(q, values)
>>> d
[[1.000000, 0, q_2], [0, 1.000000, q_5], [q_6, q_7, q_8]]

Unlike before, the variable q_x remains for some elements, because not all q array elements appear in the polynomial f.

If you don’t want some variables to be left unreplaced, you should be careful. Even if a variable array of the right size is used, this type of unreplaced variable could occur unintentionally. For example, it is possible for some variables to be erased as a consequence of intermediate addition or subtraction while equations are constructed.

To prepare for such cases, the 3rd argument of the decode_solution() function sets the default value for the unreplaced variables.

solver = Solver(client)
result = solver.solve(f)
values = result[0].values
d = decode_solution(q, values, 1)
>>> d
[[1.0, 0.0, 1.0], [0.0, 1.0, 1.0], [1.0, 1.0, 1.0]]

This successfully replaced all the variables.

It is recommended to provide a 3rd argument if it is possible to define the default value for variables. This will prevent unintended results when interpreting the output values.

Note

The variable values given to the decode_solution() function support not only the dictionary types described above, but also list types and more flexible function objects. Please see Reference for details.

Auxiliary Functions for Formulation

The following functions are provided as formulation aids for the polynomial classes:

  • sum_poly() function equivalent to sum of all \(\sum_i\)

  • pair_sum() function equivalent to sum of all combinations \(\sum_{i \ne j}\)

  • product() function equivalent to all products \(\prod_i\)

These functions have the following three functions:

Operations on Lists

The following operations can be performed on a list q.

\[\begin{split}f &= \sum_{i = 0}^{n - 1} q_\left[ i \right] \\ f &= \sum_{i \ne j} q_\left[ i \right] q_\left[ j \right] \\ f &= \prod_{i = 0}^{n - 1} q_\left[ i \right]\end{split}\]
from amplify import BinaryPoly, sum_poly, pair_sum, product

q = gen_symbols(BinaryPoly, 3)
>>> sum_poly(q)
q_0 + q_1 + q_2
>>> pair_sum(q)
q_0 q_1 + q_0 q_2 + q_1 q_2
>>> product(q)
q_0 q_1 q_2

Operations on Indices

The following operations can be performed on variables q_i.

\[\begin{split}f &= \sum_{i = 0}^{n - 1} q_i \\ f &= \sum_{i \ne j} q_i q_j \\ f &= \prod_{i = 0}^{n - 1} q_i\end{split}\]

The 1st through 3rd arguments can be the same as the built-in class range, or the 1st argument can be an enumerated type. Note that the final argument must be of the polynomial class type.

from amplify import BinaryPoly, sum_poly, pair_sum, product
>>> sum_poly(3, BinaryPoly)
q_0 + q_1 + q_2
>>> sum_poly(1, 4, BinaryPoly)
q_1 + q_2 + q_3
>>> sum_poly(1, 6, 2, BinaryPoly)
q_1 + q_3 + q_5
>>> sum_poly(range(2, 7, 2), BinaryPoly)
q_2 + q_4 + q_6
>>> pair_sum(3, BinaryPoly)
q_0 q_1 + q_0 q_2 + q_1 q_2
>>> pair_sum(1, 4, BinaryPoly)
q_1 q_2 + q_1 q_3 + q_2 q_3
>>> pair_sum(1, 6, 2, BinaryPoly)
q_1 q_3 + q_1 q_5 + q_3 q_5
>>> pair_sum(range(2, 7, 2), BinaryPoly)
q_2 q_4 + q_2 q_6 + q_4 q_6
>>> product(3, BinaryPoly)
q_0 q_1 q_2
>>> product(1, 4, BinaryPoly)
q_1 q_2 q_3
>>> product(1, 6, 2, BinaryPoly)
q_1 q_3 q_5
>>> product(range(2, 7, 2), BinaryPoly)
q_2 q_4 q_6

Operations on Functions

The following operations can be performed on functions \(g(i)\).

\[\begin{split}f &= \sum_{i = 0}^{n - 1} g\left(i\right) \\ f &= \sum_{i \ne j} g\left(i\right) g\left(j\right) \\ f &= \sum_{i \ne j} g\left(i, j\right) \quad \left(i < j \right)\\ f &= \prod_{i = 0}^{n - 1} g\left(i\right)\end{split}\]

Operations on Expressions

\[f = \prod_{i = 0}^{n - 1} { \left( 2 x_i - 1 \right) }\]
from amplify import BinaryPoly, sum_poly, pair_sum, product

q = gen_symbols(BinaryPoly, 3)
>>> product(3, lambda i: 2 * q[i] - 1)
8.000000 q_0 q_1 q_2 - 4.000000 q_0 q_1 - 4.000000 q_0 q_2 - 4.000000 q_1 q_2 + 2.000000 q_0 + 2.000000 q_1 + 2.000000 q_2 - 1.000000

Nested Operations

\[f = \sum_{i = 0}^{n - 1} { \left( \sum_{j = 0}^{n - 1}{ q_{i,j} - 1} \right)^2 }\]
from amplify import BinaryPoly, sum_poly, pair_sum, product

q = gen_symbols(BinaryPoly, 3, 3)
>>> sum_poly(3, lambda i: (sum_poly(3, lambda j: q[i][j]) - 1) ** 2)
2.000000 q_0 q_1 + 2.000000 q_0 q_2 + 2.000000 q_1 q_2 + 2.000000 q_3 q_4 + 2.000000 q_3 q_5 + 2.000000 q_4 q_5 + 2.000000 q_6 q_7 + 2.000000 q_6 q_8 + 2.000000 q_7 q_8 - q_0 - q_1 - q_2 - q_3 - q_4 - q_5 - q_6 - q_7 - q_8 + 3.000000

Methods of the Polynomial Class

Variable Transformation

An index contained in a polynomial object can be converted to another index.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

Using a dictionary, the variable q_0 can be replaced with q_3.

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.change_variables({0: 3})
2.000000 q_1 q_3 + q_1 + q_3 - 1.000000

When indices are replaced using a list, the indices of the original variables before conversion coincide with the indices of the list, and the indices of the converted variables are assigned to the list elements having the indices which they are converted from. For example, we can convert q_0 to q_3 and q_1 to q_4 in the following way.

>>> f.change_variables([3, 4])
2.000000 q_3 q_4 + q_3 + q_4 - 1.000000

It is also possible to perform an arbitrary index conversion by giving a function.

>>> f.change_variables(lambda i: 2 * i + 2)
2.000000 q_2 q_4 + q_2 + q_4 - 1.000000

Number of Terms

The number of terms contained in a polynomial object can be found as follows.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.count()
4

Obtaining the Constant Term

A constant term from a polynomial object can be obtained.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.constant()
-1.0

Convertibility to Constant Values

We can check whether a polynomial object consists only of constants. If it is True, implicit conversion to numeric values is possible.

from amplify import BinaryPoly, gen_symbols
import math

q = gen_symbols(BinaryPoly, 10)
f = q[0] + 1
g = f - q[0]
>>> f
q_0 + 1.000000
>>> g
1.000000
>>> f.is_number()
False
>>> g.is_number()
True
>>> math.exp(g)
2.718281828459045

Maximum Index Value

It returns the largest index of the variables that appear in a polynomial object.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.max_index()
1

Assigning Values to a Polynomial

Values can be assigned to the variables of a polynomial object.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

\(1\) is assigned to the variable q_0 by a dictionary. The variables that are not assigned will remain unsubstituted.

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.replace({0: 1})
3.000000 q_1

Evaluating the Value of a Polynomial

Values can be assigned to all variables of a polynomial object.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

We give a dictionary for assigning \(1\) to the variable q_0 and \(-1\) to q_1. Please note that it is necessary to have a correspondence for all variables.

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.replace_all({0: 1, 1: -1})
-3.0

When using a list, the indices of the variables are the same as the indices of the list, and the values to be assigned are set to the elements with the corresponding indices.

>>> f.replace_all([1, -1])
-3.0

If using a function, it should relate indices to their corresponding values as follows.

>>> f.replace_all(lambda i: 2 * i + 1)
9.0

Change Variable Symbols

This property is used to get or change the character that represents a variable when a polynomial object is output as a string using the print() function. The default value is \(q\) for binary variable polynomials, and \(s\) for Ising variable polynomials.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f.symbol
q
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
f.symbol = "x"
>>> f
2.000000 x_0 x_1 + x_0 + x_1 - 1.000000

Conversion to a Dictionary Format

A polynomial can be converted to a Python dictionary type.

from amplify import BinaryPoly

f = BinaryPoly(
    {(1, 2, 3): -1, (0, 1): 2, (1, 2): 1, (0): 1, 2: 1, (): -2}
)
>>> f
- q_1 q_2 q_3 + 2.000000 q_0 q_1 + q_1 q_2 + q_0 + q_2 - 2.000000
>>> f.asdict()
{(1, 2, 3): -1.0, (0, 1): 2.0, (1, 2): 1.0, (0,): 1.0, (2,): 1.0, (): -2.0}

Conversion to a Polynomial of Binary Variables

A polynomial of Ising variables can be converted to a polynomial of binary variables. A variable transformation based on the correspondence \(s = 2 q - 1\) between the binary variable \(q\) and the Ising variable \(s\) is performed.

from amplify import IsingPoly, gen_symbols

s = gen_symbols(IsingPoly, 10)
f = -1 * s[0] * s[1] + s[0] + s[1] + 1
>>> f
- s_0 s_1 + s_0 + s_1 + 1.000000
>>> f.to_Binary()
- 4.000000 q_0 q_1 + 4.000000 q_0 + 4.000000 q_1 - 2.000000

Conversion to a Polynomial of Ising Variables

A polynomial of binary variables can be converted to a polynomial of Ising variables. A variable transformation based on the correspondence between the binary variable \(q\) and the Ising variable \(s\) \(q = \left(s + 1\right) / 2\) is performed.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.to_Ising()
0.500000 s_0 s_1 + s_0 + s_1 + 0.500000

Conversion to a Matrix Format

A polynomial can be converted to a matrix form. However, the degree of the polynomial must be less than or equal to \(2\).

After the conversion, a tuple consisting of a matrix class and a constant term is returned. Please see Matrix for the matrix class.

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.to_Matrix()
([[1, 2],
 [0, 1]], -1.0)
from amplify import IsingPoly, gen_symbols

s = gen_symbols(IsingPoly, 10)
f = -1 * s[0] * s[1] + s[0] + s[1] + 1
>>> f
- s_0 s_1 + s_0 + s_1 + 1.000000
>>> f.to_Matrix()
([[1, -1],
 [0, 1]], 1.0)

The following table summarizes the correspondence between the polynomial classes before the conversion and the matrix classes after the conversion.

Polynomial class

Matrix class

BinaryPoly

BinaryMatrix

IsingPoly

IsingMatrix

BinaryIntPoly

BinaryIntMatrix

IsingIntPoly

IsingIntPoly