Polynomial

This section describes the polynomial class and their related functions.

See also

Before reading this page, please review the Tutorial for basic Amplify SDK usage.

Binary Multivariate Polynomial

With the Amplify SDK, you can formulate using multivariate polynomials of binary (or Ising) variables. A polynomial \(f\) over \(n\) binary (or Ising) variables is expressed as follows.

\[ \begin{align}\begin{aligned}f \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\) is a binary (or Ising) variable, and \(a_{k_1, k_2, \cdots, k_n}\) is a real number. Thereafter, \(q\) will be used 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 nature of binary and Ising variables, no more than a quadratic order can appear in the polynomial.

\[ \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 representing polynomials of binary or Ising variables.

BinaryPoly and IsingPoly represent the polynomials in terms of binary variables \(\left\{0, 1\right\}\) and Ising variables \(\left\{-1, 1\right\}\), respectively. The polynomial class can represent any degree (including cubic or higher) and includes constant terms. If the degree is fixed to \(2\), BinaryPoly and IsingPoly correspond to the QUBO model and the Ising model, respectively.

Note

If the coefficients of a polynomial needs to be restricted to integer values, BinaryIntPoly and IsingIntPoly can be used. However, this may lead to unintended results since the coefficients are restricted to integers in the intermediate calculations. For this reason, we usually recommend BinaryPoly and IsingPoly, which can handle real numbers.

Construct Polynomial Class

The polynomial class is constructed as follows. The BinaryPoly is used as an example hereafter, but the same applies to other polynomial classes including Ising classes.

from amplify import BinaryPoly

f = BinaryPoly()

>>> f
0

A set of terms can be given to the constructor argument to initialize the polynomial object. Here, a term is represented by a key/value pair of the following form:

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

Multiple terms are represented as 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\) is given as follows:

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1, (1): 1, (): -1})

>>> f
2 q_0 q_1 + q_0 + q_1 - 1

The constant part can be treated specially, where a number is treated as a single term of the constant.

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

It is also possible to give more than one of the above notations to the constructor.

The previous \(f = 2 q_0 q_1 + q_0 + q_1 - 1\) can be also written as below:

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1}, {(1): 1}, -1)

>>> f
2 q_0 q_1 + q_0 + q_1 - 1

If an object of the same polynomial class is given to the constructor, it is copied.

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1}, {(1): 1}, -1)
g = BinaryPoly(f)

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> g
2 q_0 q_1 + q_0 + q_1 - 1

Polynomial Operators

The polynomial class defines equality, addition, subtraction, multiplication, division, and exponentiation, which can be applied to polynomial objects themselves and their terms and constants. For exponentiation and division, only polynomial (left-hand side) and numeric (right-hand side) are supported. Compound assignment operators are also supported, although they are omitted below.

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1}, {(1): 1}, -1)

>>> f + f
4 q_0 q_1 + 2 q_0 + 2 q_1 - 2
>>> f + {(0, 1, 2): 1}
q_0 q_1 q_2 + 2 q_0 q_1 + q_0 + q_1 - 1
>>> f + 1
1 q_0 q_1 + q_0 + q_1

>>> f - f
0
>>> f - {(0, 1): 1}
q_0 q_1 + q_0 + q_1 - 1
>>> f - 2
2 q_0 q_1 + q_0 + q_1 - 3

>>> f * f
10 q_0 q_1 - q_0 - q_1 + 1
>>> f * {(2): 1}
2 q_0 q_1 q_2 + q_0 q_2 + q_1 q_2 - q_2
>>> 2 * f
4 q_0 q_1 + 2 q_0 + 2 q_1 - 2

>>> f / 2
q_0 q_1 + 0.5 q_0 + 0.5 q_1 - 0.5

>>> f ** 2
10 q_0 q_1 - q_0 - q_1 + 1

>>> f + f == 2 * f
True

Construction using Variable Arrays

In the above polynomial construction, the indices of the variables had to be given explicitly as integer values. However, when formulating complex problems, you may want to manage variables with indices in two or more dimensions or handle multiple variable sets together.

To handle variable indices conveniently, the Amplify SDK provides a polynomial array class. The polynomial array class acts like a polynomial version of NumPy ndarray. By utilizing the polynomial array classes, advanced formulations can be processed at high speed.

See also

Please see Polynomial Array for more information on polynomial array classes.

A SymbolGenerator() is provided to dynamically generate an array of variables to be used in the formulation. SymbolGenerator() has the ability to issue variables starting from index 0, and return them as a polynomial array of arbitrary dimensionality. This allows hiding polynomial variable indices and naming them as user-friendly variables in the program code.

You can generate a variable array of the specified length as follows:

from amplify import BinaryPoly, SymbolGenerator

gen = SymbolGenerator(BinaryPoly)   # Declare BinaryPoly variable generators
q = gen.array(10) # Generate variable array of 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 constructing a polynomial expression using terms, you can construct the same polynomial \(f = 2 q_0 q_1 + q_0 + q_1 - 1\) using the variable array q.

from amplify import BinaryPoly, SymbolGenerator

gen = SymbolGenerator(BinaryPoly)
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1

To create a variable array of any dimension, specify the array shape. The array shape is given as an argument or tuple. For example, if you want to manage variables using a two-dimensional index of shape \(4 \times 4\), you can create a variable array as follows:

from amplify import BinaryPoly, SymbolGenerator

# Define variable generator for BinaryPoly
gen = SymbolGenerator(BinaryPoly)   # Equivalent to BinarySymbolGenerator
# Generate 4 x 4 variable array
q1 = gen.array(shape=(4, 4))  # Equivalent to gen.array(4, 4)

>>> q1
[[ q_0,  q_1,  q_2,  q_3],
 [ q_4,  q_5,  q_6,  q_7],
 [ q_8,  q_9, q_10, q_11],
 [q_12, q_13, q_14, q_15]]

The actual content of the variable array q consists of 16 variables from q_0 to q_15. By using the variable array, you can directly access each variable by specifying the array index, for example q[2,3], without referring the actual variable index.

Multiple arrays can also be generated. You can call the array() method any number of times using the variable generator gen described previously.

from amplify import BinaryPoly, SymbolGenerator

# Define variable generator for BinaryPoly
gen = SymbolGenerator(BinaryPoly)  # Equivalent to BinarySymbolGenerator
q1 = gen.array(4, 4)  # Generate 4 x 4 variable array
q2 = gen.array(shape=(2, 3)) # Generate 2 x 3 variable array

>>> q1
[[ q_0,  q_1,  q_2,  q_3],
 [ q_4,  q_5,  q_6,  q_7],
 [ q_8,  q_9, q_10, q_11],
 [q_12, q_13, q_14, q_15]]
>>> q2
[[q_16, q_17, q_18],
 [q_19, q_20, q_21]]

Please note that the actual variables in the arrays q1 and q2 have different indices. Each time a variable array is created, the indices of the corresponding variables are incremented accordingly. In other words, different variable arrays are treated as different sets of variables.

If you want to generate scalar variables from a variable generator, use the scalar() method.

from amplify import BinaryPoly, SymbolGenerator

# Define variable generator for BinaryPoly
gen = SymbolGenerator(BinaryPoly)  # Same with BinarySymbolGenerator
q = gen.array(shape=(4, 4))  # Generate 4 x 4 variable array
r = gen.scalar()

>>> r
q_16

A variable generator can be created by specifying the starting number of the variable’s index. This feature is provided for compatibility, so it is not usually necessary to use it.

from amplify import BinaryPoly, SymbolGenerator

# Define variable generator for BinaryPoly with start index 4
gen = SymbolGenerator(BinaryPoly, 4)  # Same with BinarySymbolGenerator
q = gen.array(shape=(2, 3)) # Generate 2 x 3 variable array

>>> q
[[q_4, q_5, q_6],
 [q_7, q_8, q_9]]

Note

For compatibility with previous versions, the gen_symbols() function is provided. This has the following effect:

gen_symbols(PolyType, *args):: SymbolGenerator(PolyType).array(*args)
gen_symbols(PolyType, start, shape):: SymbolGenerator(PolyType, start).array(shape)

When using the gen_symbols() function to generate multiple variable arrays, the user must calculate and specify the starting number start for the variable indices. Since an incorrect start number will result in unintended polynomial construction, it is recommended to use SymbolGenerator().

The SymbolGenerator() is a function to generate the class objects below. The variable generator classes, such as the BinarySymbolGenerator class, may be also used directly.

Variable generator class	Alias
`BinarySymbolGenerator`	`SymbolGenerator(BinaryPoly)`
`IsingSymbolGenerator`	`SymbolGenerator(IsingPoly)`
`BinaryIntSymbolGenerator`	`SymbolGenerator(BinaryIntPoly)`
`IsingIntSymbolGenerator`	`SymbolGenerator(IsingIntPoly)`

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)

>>> q
[q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7, q_8, q_9]

Substitution of Values to Variable Arrays

If you want to fix a part of a variable array to any value, or if you know the solution in advance, you can set the values by specifying the array element.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
q[0] = 1    # Fix q[0] to 1
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
3 q_1

Substituting one variable for another makes them the same variable.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
q[1] = q[0] # Fix q[1] to q[0]
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
4 q_0 - 1

In the above examples, constants or unary were set to array variables, but any polynomial object can also be set.

Note

If you want to set values to a polynomial array, the substitution needs to be done before constructing the polynomial (f in the above example). Since a polynomial array holds the actual variables themselves, not a reference to the array variables, setting values to the array elements after constructing the polynomial will not be reflected.

Obtain a Solution using an Array of Variables

To make a correspondence between a polynomial array to the output of the solver class Solver, it is convenient to use the decode() method. By giving a solution in dictionary form to \(~amplify.BinaryPolyArray.decode\), it assigns the values in the solution to the corresponding elements of the variable array and returns a numpy array of numerical type of the same shape.

Below is an example of using the decode() method.

from amplify import BinarySymbolGenerator, Solver
from amplify.client import FixstarsClient

# Generating Variable Arrays
gen = BinarySymbolGenerator()
q = gen.array(shape=(2, 2))
print(f"q = {q}")

# Polynomial Construction
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]
)
print(f"f = {f}")

# Set ising machine client
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000

# Run machine
solver = Solver(client)
result = solver.solve(f)
values = result[0].values

# Decode solution
print(f"solution = {q.decode(values)}")

q = [[q_0, q_1], [q_2, q_3]]
f = q_0 q_1 + q_0 q_2 - q_0 q_3 + q_1 q_3 + q_2 q_3
solution = [[1. 0.], [0. 1.]]

By applying the solver’s output values to the variable array q, each value of the solution is substituted for the corresponding element of q. and a \(2 \times 2\) array of the same shape as q is returned.

Let us look at the contents of the variable array and the output value of the solver to make sure of this point.

>>> q
[[q_0, q_1], [q_2, q_3]]
>>> values
{0: 1, 1: 0, 2: 0, 3: 1}
>>> q.decode(values)
array([[1., 0.],
       [0., 1.]])

We can see that the substitution is correct for each array element.

In the above, all variable array elements were substituted. However, there can be cases where only some elements of the variable array are used in the formulation.

from amplify import BinarySymbolGenerator, Solver
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(shape=(4, 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]
)

>>> q
[[q_0, q_1],
 [q_2, q_3],
 [q_4, q_5],
 [q_6, q_7]]

The q has been extended to \(4 \times 2\). The polynomial itself is unchanged, so the solution is the same as the previous result.

>>> f
q_0 q_1 + q_0 q_3 - q_0 q_4 + q_1 q_4 + q_3 q_4
>>> values
{0: 1, 1: 0, 2: 0, 3: 1}

In such a case, the solutions for the unused variables q_4, q_5, q_6, and q_7 are undefined; namely, they can be either of the binary values. The same can happen if some variables are eliminated during the calculation. The decode() method replaces variables with the default value 1 in such cases.

>>> q.decode(values)
array([[1., 0.],
       [0., 1.],
       [1., 1.],
       [1., 1.]])

It is also possible to explicitly specify a different default value. Specify the default value as the keyword argument default of the decode() method as below:

>>> q.decode(values, default=0)
array([[1., 0.],
       [0., 1.],
       [0., 0.],
       [0., 0.]])

If you specify None as the default value, no variable substitution is performed and undefined variables are left as they are.

>>> q.decode(values, default=None)
[[  1,   0],
 [  0,   1],
 [q_4, q_5],
 [q_6, q_7]]

Note

Please note that if you specify None as the default value, the decode() method will return an object of Python list, not a NumPy array.

Note

For compatibility with previous versions, the decode_solution() function is provided. This has the following effect.

decode_solution(poly_array, *args):: poly_array.decode(*args)

Construction of Logical Expressions

You can perform logical operations on the binary variable \(\left\{0, 1\right\}\), where \(0\) is considered False and \(1\) is considered True. For example, the binary variable polynomial representing the logical OR \(x_0 \lor x_1\) for the Boolean variables \(x_0, x_1\) can be obtained as follows:

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
x = gen.array(2)

>>> x[0] | x[1]
- q_0 q_1 + q_0 + q_1

Comparing this polynomial - q_0 q_1 + q_0 + q_1 with the truth table below, we can see that the polynomial has the same value as the truth table for all possible states.

\(x_0\)	\(x_1\)	\(x_0 \lor x_1\)	\(-x_0 x_1 + x_0 + x_1\)
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	1

Binary polynomials provide logical operators, namely, logical conjunction &, logical disjunction |, exclusive disjunction ^ and their compound assignment operators &=, |=, ^= and logical negation ~. Using these operators, combinatorial optimization problems expressed in terms of logical expressions or satisfiability problems can be formulated in terms of binary polynomials.

The effect of each operator is as below, where the polynomials \(f_0\) and \(f_1\) are assumed to satisfy \(0\) or \(1\) for all possible cases of the variables. The behavior for other possible values is undefined.

Logic operation	Output
\(f_0 \lor f_1\)	\(-f_0 f_1 + f_0 + f_1\)
\(f_0 \land f_1\)	\(f_0 f_1\)
\(f_0 \oplus f_1\)	\(-2 f_0 f_1 + f_0 + f_1\)
\(\lnot f_0\)	\(- f_0 + 1\)

As an example of a formulation, the Maximum SAT problem can be represented by a binary variable polynomial. The Maximum SAT problem is the problem of finding the combination of boolean variables that maximizes the number of clauses satisfying the given logical expression. An example of Maximum SAT problem is maximizing the number of clauses that are True for all possible values of the boolean variables \(x_0, x_1, x_2\), given the following boolean expression.

\[\left( \lnot x_0 \lor x_1 \right) \land \left(\lnot x_0 \lor x_2 \right) \land \left(x_1 \lor x_2 \right) \land \left(x_0 \lor \lnot x_2 \right)\]

In this case, a solution value of 4 means that all clauses are satisfied and the logical expression as a whole is True.

This problem is represented by a minimization problem of a polynomial over binary variables as follows:

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
x = gen.array(3)
f = - (~x[0] | x[1]) - (~x[0] | x[2]) - (x[1] | x[2]) - (x[0] | ~x[2])

All clauses are expressed as polynomials over binary variables and summed. The negative sign is due to the fact that the problem of maximizing the number of satisfactions is converted to a minimization problem. You can see how the objective function is expressed in the following way:

>>> f
- q_0 q_1 - 2 q_0 q_2 + q_1 q_2 + 2 q_0 - q_1 - 3

The solution is obtained by solving this as a binary optimization problem.

from amplify import Solver
from amplify.client import FixstarsClient

# Set ising machine client
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000

# Run machine
solver = Solver(client)
result = solver.solve(f)

>>> print(f"number of satisfied clauses: {int(-result[0].energy)}")
number of satisfied clauses: 4
>>> print(f"x = {x.decode(result[0].values).astype(bool)}")
x = [ True  True  True]

Now we were able to find a solution for the variable \(x_0, x_1, x_2\) that satisfies all four clauses.

Formulation Auxiliary Function

The following functions are provided to assist in processing equations in the polynomial class:

sum_poly() function represents a sum (Equivalent to \(\sum_i\))
pair_sum() function represents a combinatorial sum (Equivalent to \(\sum_{i \ne j}\))
product() function represents a product (Equivalent to \(\prod_i\))

With binary variable polynomials, functions to assist with the following logical expressions are also provided:

intersection() function is equivalent to all logical products \(\land_i\)
union() function is equivalent to all disjunctions \(\lor_i\)
symmetric_difference() function is equivalent to all exclusive ors \(\oplus_i\)

These functions have the following three functions.

Operations on Variable Arrays

Perform the following operations on a variable array 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 BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3)

>>> q
[q_0, q_1, q_2]
>>> 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

For sums over polynomial arrays, it is recommended to use the sum_poly() function rather than the built-in sum() function for speed.

Note

For the operation of sum on polynomial arrays, it is recommended to use the sum_poly() function rather than the built-in function sum(), because of execution speed consideration.

Applying the sum_poly() function to a multidimensional polynomial array yields the same result as the sum() method with no axes specified. To compute the sum for an arbitrary axis, use the sum() method.

from amplify import BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3, 3)

>>> q
[[q_0, q_1, q_2],
 [q_3, q_4, q_5],
 [q_6, q_7, q_8]]
>>> sum_poly(q)
q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8
>>> q.sum()
q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8
>>> q.sum(axis=0)
[q_0 + q_3 + q_6, q_1 + q_4 + q_7, q_2 + q_5 + q_8]

The following logical operations can be performed with binary variable polynomials:

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} x_\left[ i \right]\\l &= \bigvee_{i = 0}^{n - 1} x_\left[ i \right]\\l &= \bigoplus_{i = 0}^{n - 1} x_\left[ i \right]\end{aligned}\end{align} \]

from amplify import BinarySymbolGenerator, intersection, union, symmetric_difference

gen = BinarySymbolGenerator()
x = gen.array(3)

>>> intersection(x)
q_0 q_1 q_2
>>> union(x)
q_0 q_1 q_2 - q_0 q_1 - q_0 q_2 - q_1 q_2 + q_0 + q_1 + q_2
>>> symmetric_difference(x)
4 q_0 q_1 q_2 - 2 q_0 q_1 - 2 q_0 q_2 - 2 q_1 q_2 + q_0 + q_1 + q_2

Operation on Functions

Perform the following operations on a function \(g(i)\), which takes a polynomial value.

\[\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}\]

Either give a numerical range as the first argument, or give the same arguments as the built-in function range for the first through third arguments to specify a numerical range, and give the function to be applied as the last argument. That is, sum_poly(start[, stop, step], func) is equivalent to sum_poly(range(start[, stop, step]), func).

The pair_sum() function can also be given a function with two arguments.

Example: Operations on Functions

\[f = \prod_{i = 0}^{n - 1} { \left( 2 q_i - 1 \right) }\]

from amplify import BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3)

>>> q
[q_0, q_1, q_2]
>>> product(3, lambda i: 2 * q[i] - 1)
8 q_0 q_1 q_2 - 4 q_0 q_1 - 4 q_0 q_2 - 4 q_1 q_2 + 2 q_0 + 2 q_1 + 2 q_2 - 1

Example: Nested Operations

\[f = \sum_{i = 0}^{n - 1} { \left( \sum_{j = 0}^{n - 1}{ q_{i,j} - 1} \right)^2 }\]

from amplify import BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3, 3)

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

The following logical operations are possible on binary variable polynomials:

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} g\left( i \right)\\l &= \bigvee_{i = 0}^{n - 1} g\left( i \right)\\l &= \bigoplus_{i = 0}^{n - 1} g\left( i \right)\end{aligned}\end{align} \]

Operations on Indices

Simultaneously create variables q_i and compute the following.

\[\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}\]

As with operations on functions, the first argument must be a range of numbers or the first three arguments must be identical to the built-in function range. The final argument is the type of the polynomial class.

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

The following logical operations are possible on polynomial classes of binary variables:

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} x_i\\l &= \bigvee_{i = 0}^{n - 1} x_i\\l &= \bigoplus_{i = 0}^{n - 1} x_i\end{aligned}\end{align} \]

>>> intersection(3, BinaryPoly)
q_0 q_1 q_2
>>> intersection(1, 4, BinaryPoly)
q_1 q_2 q_3
>>> intersection(1, 6, 2, BinaryPoly)
q_1 q_3 q_5
>>> intersection(range(2, 7, 2), BinaryPoly)
q_2 q_4 q_6

>>> union(3, BinaryPoly)
q_0 q_1 q_2 - q_0 q_1 - q_0 q_2 - q_1 q_2 + q_0 + q_1 + q_2
>>> union(1, 4, BinaryPoly)
q_1 q_2 q_3 - q_1 q_2 - q_1 q_3 - q_2 q_3 + q_1 + q_2 + q_3
>>> union(1, 6, 2, BinaryPoly)
q_1 q_3 q_5 - q_1 q_3 - q_1 q_5 - q_3 q_5 + q_1 + q_3 + q_5
>>> union(range(2, 7, 2), BinaryPoly)
q_2 q_4 q_6 - q_2 q_4 - q_2 q_6 - q_4 q_6 + q_2 + q_4 + q_6

>>> symmetric_difference(3, BinaryPoly)
4 q_0 q_1 q_2 - 2 q_0 q_1 - 2 q_0 q_2 - 2 q_1 q_2 + q_0 + q_1 + q_2
>>> symmetric_difference(1, 4, BinaryPoly)
4 q_1 q_2 q_3 - 2 q_1 q_2 - 2 q_1 q_3 - 2 q_2 q_3 + q_1 + q_2 + q_3
>>> symmetric_difference(1, 6, 2, BinaryPoly)
4 q_1 q_3 q_5 - 2 q_1 q_3 - 2 q_1 q_5 - 2 q_3 q_5 + q_1 + q_3 + q_5
>>> symmetric_difference(range(2, 7, 2), BinaryPoly)
4 q_2 q_4 q_6 - 2 q_2 q_4 - 2 q_2 q_6 - 2 q_4 q_6 + q_2 + q_4 + q_6

Einstein Summation Convention

You can calculate the sum of multiple polynomial arrays according to the subscript string representing the Einstein summation convention. It is an alias for the einsum() function. Please see Formulation by Polynomial Array for details on the function.

See also

It functions as numpy.einsum() for polynomial arrays. Please see also numpy.einsum() for the argument notations and functionalities.

The followings are examples of the Einstein summation convention for the two-dimensional array \(q\).

from amplify import BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3, 3)

>>> q
[[q_0, q_1, q_2],
 [q_3, q_4, q_5],
 [q_6, q_7, q_8]]

Compute the element sum \(s\) of a two-dimensional array.

\[s = \sum_i \sum_j {q_{ij}}\]

>>> sum_poly("ij->", q)
q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8

Return a one-dimensional array \(p\) computed from the summation over the row direction.

\[p_i = \sum_j {q_{ij}}\]

>>> sum_poly("ij->i", q)
[q_0 + q_1 + q_2, q_3 + q_4 + q_5, q_6 + q_7 + q_8]

Return a two-dimensional array \(p\) computed from the inner product of each row and column.

\[p_{ik} = \sum_j {q_{ij} q_{jk}}\]

>>> sum_poly("ij,jk->ik", q, q)
[[q_1 q_3 + q_2 q_6 + q_0, q_0 q_1 + q_1 q_4 + q_2 q_7, q_0 q_2 + q_1 q_5 + q_2 q_8],
 [q_0 q_3 + q_3 q_4 + q_5 q_6, q_1 q_3 + q_5 q_7 + q_4, q_2 q_3 + q_4 q_5 + q_5 q_8],
 [q_0 q_6 + q_3 q_7 + q_6 q_8, q_1 q_6 + q_4 q_7 + q_7 q_8, q_2 q_6 + q_5 q_7 + q_8]]

Polynomial Class Methods

Change Variables

The change_variables() method converts indices of variables in a polynomial object to another indices.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

Replace the variable q_0 with q_3 by giving a dictionary.

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

When given a list as the argument, the indices of the conversion source is the indices of the list, and the indices of the conversion destination is the corresponding elements of the list. Here q_0 is converted to q_3 and q_1 to q_4.

>>> f.change_variables([3, 4])
2 q_3 q_4 + q_3 + q_4 - 1

A function can be given to perform an arbitrary index conversion.

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

Number of Terms

The count() method returns how many terms a polynomial object contains.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.count()
4

Obtain Constant Term

The constant term of a polynomial object can be obtained using constant().

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.constant()
-1.0

Convertibility to Constant Value

is_number() returns whether the polynomial object consists only of constants. If it is True, an implicit conversion to a number is possible.

from amplify import BinarySymbolGenerator
import math

gen = BinarySymbolGenerator()
q = gen.array(10)
f = q[0] + 1
g = f - q[0]

>>> f
q_0 + 1
>>> g
1
>>> f.is_number()
False
>>> g.is_number()
True
>>> math.exp(g)
2.718281828459045

Obtain the Degree

The degree of a polynomial object can be obtained by the degree() method. If the polynomial object is equal to \(0\), \(-1\) will be returned.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.degree()
2

Whether the Polynomial is Linear

The is_linear() method returns whether the polynomial is at most linear.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.is_linear()
False

Whether the Polynomial is Quadratic

The is_quadratic() method returns whether the polynomial is at most quadratic.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.is_quadratic()
True

Maximum Index Value

The max_index() method returns the largest index of a variable that appears in a term of a polynomial object.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.max_index()
1

Assign values to Polynomials and Evaluate

Use the decode() method to assign values to variables of a polynomial object.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

In the following, \(1\) is assigned to the variable q_0, giving the variable index and value in dictionary form. If the variable index is not found in the dictionary key, it is replaced by 1 as the default value.

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.decode({0: 1})    # q_0 = 1, assign 1 implicitly to q_1
3.0

To explicitly specify a different default value, use the default argument.

>>> f.decode({0: 1}, default=0)    # q_0 = 1, assign 0 implicitly to q_1
0.0

If None is specified as the default value, variables that are not given a value are not substituted and remain as variables.

>>> f.decode({0: 1}, default=None)    # q_0 = 1, leave q_1 as is
3 q_1

You can also give the values of the variables as a list. The index of the list corresponds to the index of the variable, and the element in the list of that index is to be substituted for the variable.

>>> f.decode([1, 0])   # substitute q_0 = 1, q_1 = 0
0.0

You can also give a function that takes an index and returns a value.

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

Note

For compatibility with previous versions, the replace() and replace_all() methods are provided. They perform variable substitution in the same way as the decode() method, with the following differences:

poly.replace(dict):: Same as poly.decode(`dict`, default=None) but replace returns a constant but polynomial type
poly.replace_all(list, default):: Same as poly.decode(`list, default)`` but replace_all cannot specify None for default
poly.replace_all(dict, default):: Same as poly.decode(`dict`, `default`) but replace_all cannot specify None for default.

Change Variable Symbols

The property symbol is used to get and change the character representing the variables when a polynomial object is output as a string, such as with the print() function. The initial value is \(q\) for binary variable polynomials and \(s\) for Ising variable polynomials.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f.symbol
q
>>> f
2 q_0 q_1 + q_0 + q_1 - 1

f.symbol = "x"

>>> f
2 x_0 x_1 + x_0 + x_1 - 1

Convert to Dictionary Format

asdict() converts a polynomial 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 q_0 q_1 + q_1 q_2 + q_0 + q_2 - 2
>>> f.asdict()
{(1, 2, 3): -1.0, (0, 1): 2.0, (1, 2): 1.0, (0,): 1.0, (2,): 1.0, (): -2.0}

Convert to a Polynomial on Binary Variables

The to_Binary() method converts an Ising variable polynomial to a binary variable polynomial. Variables are converted by the correspondence \(s = 2 q - 1\) between the binary variable \(q\) and the Ising variable \(s\) by default.

from amplify import IsingSymbolGenerator

gen = IsingSymbolGenerator()
s = gen.array(10)
f = -1 * s[0] * s[1] + s[0] + s[1] + 1

>>> f
- s_0 s_1 + s_0 + s_1 + 1
>>> f.to_Binary()
- 4 q_0 q_1 + 4 q_0 + 4 q_1 - 2

By default, the binary variables \(0, 1\) correspond to the Ising variables \(-1, 1\), respectively. You can flip this correspondence by giving False to the keyword argument ascending. In this case, variables are converted by the correspondence \(s = -2 q + 1\).

>>> f
- s_0 s_1 + s_0 + s_1 + 1
>>> f.to_Binary(ascending=False)
- 4 q_0 q_1 + 2

Convert to a Polynomial on Ising Variables

The to_Ising() method converts a binary variable polynomial to an Ising variable polynomial. By default, variables are converted by the correspondence \(q = \left(s + 1\right) / 2\) between the binary variable \(q\) and the Ising variable \(s\). If False was given to the keyword argument ascending, the conversion will be made by the correspondence \(q = \left(-s + 1\right) / 2\).

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.to_Ising()
0.5 s_0 s_1 + s_0 + s_1 + 0.5
>>> f.to_Binary(ascending=False)
0.5 s_0 s_1 - s_0 - s_1 + 0.5

Convert to a Matrix

The to_Matrix() method converts a polynomial into matrix form. The degree of the polynomial must be less than or equal to \(2\).

After conversion, a tuple of a matrix object and a constant term is returned.

See also

Please see Matrix for matrix classes.

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.to_Matrix()
([[1, 2],
 [0, 1]], -1.0)

from amplify import IsingSymbolGenerator

gen = IsingSymbolGenerator()
s = gen.array(10)
f = -1 * s[0] * s[1] + s[0] + s[1] + 1

>>> f
- s_0 s_1 + s_0 + s_1 + 1
>>> f.to_Matrix()
([[1, -1],
 [0, 1]], 1.0)

The following polynomial classes are converted to the corresponding matrix classes:

Polynomial class	Matrix class
`BinaryPoly`	`BinaryMatrix`
`IsingPoly`	`IsingMatrix`
`BinaryIntPoly`	`BinaryIntMatrix`
`IsingIntPoly`	`IsingIntMatrix`