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.
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.
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 (lefthand side) and numeric (righthand 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 userfriendly 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 twodimensional 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 








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.
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
.
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 builtin 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 builtin 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:
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.
Either give a numerical range as the first argument, or give the same arguments as the builtin 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¶
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¶
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:
Operations on Indices¶
Simultaneously create variables q_i
and compute the following.
As with operations on functions, the first argument must be a range of numbers or the first three arguments must be identical to the builtin 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:
>>> 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 twodimensional 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 twodimensional array.
>>> sum_poly("ij>", q)
q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8
Return a onedimensional array \(p\) computed from the summation over the row direction.
>>> 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 twodimensional array \(p\) computed from the inner product of each row and column.
>>> 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)
butreplace
returns a constant but polynomial type poly.replace_all(list, default)
Same as
poly.decode(`list
, default)`` butreplace_all
cannot specifyNone
fordefault
 poly.replace_all(dict, default)
Same as
poly.decode(`dict`, `default`)
butreplace_all
cannot specifyNone
fordefault
.
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 
