Polynomial
==========

This section describes the polynomial class and their related functions.

.. seealso::
    Before reading this page, please review the :doc:`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 :math:`f` over :math:`n` binary (or Ising) variables is expressed as follows.

.. math::

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

Here, :math:`x_i` is a binary (or Ising) variable, and :math:`a_{k_1, k_2, \cdots, k_n}` is a real number. Thereafter, :math:`q` will be used instead of :math:`x` when the variable is a binary variable :math:`\left\{0, 1\right\}` and :math:`s` instead of :math:`x` when the variable is an Ising variable :math:`\left\{-1, 1\right\}`. Due to the nature of binary and Ising variables, no more than a quadratic order can appear in the polynomial.

.. math::

   q ^ 2 &= q \quad \left( q \in \left\{ 0, 1 \right\} \right)

   s ^ 2 &= 1 \quad \left( s \in \left\{ -1, + 1 \right\} \right)

Amplify SDK provides the following classes representing polynomials of binary or Ising variables.

* :class:`~amplify.BinaryPoly`
* :class:`~amplify.IsingPoly`
* :class:`~amplify.BinaryIntPoly`
* :class:`~amplify.IsingIntPoly`

:class:`~amplify.BinaryPoly` and :class:`~amplify.IsingPoly` represent the polynomials in terms of binary variables :math:`\left\{0, 1\right\}` and Ising variables :math:`\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 :math:`2`, :class:`~amplify.BinaryPoly` and :class:`~amplify.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, :class:`~amplify.BinaryIntPoly` and :class:`~amplify.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 :class:`~amplify.BinaryPoly` and :class:`~amplify.IsingPoly`, which can handle real numbers.


Construct Polynomial Class
--------------------------

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

.. code-block:: python

    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:

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

Multiple terms are represented as a dictionary.

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

For example, the construction of :math:`f = 2 q_0 q_1 + q_0 + q_1 - 1` is given as follows:

.. code-block:: python

    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.

* :math:`c` :math:`\to` ``c``

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

The previous :math:`f = 2 q_0 q_1 + q_0 + q_1 - 1` can be also written as below:

.. code-block:: python

    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.

.. code-block:: python

    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.

.. code-block:: python

    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

.. _polynomial-symbol_generator:

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 <https://numpy.org/doc/stable/reference/generated/numpy.ndarray.html>`_. By utilizing the polynomial array classes, advanced formulations can be processed at high speed.

.. seealso::

    Please see :doc:`array` for more information on polynomial array classes.

A :func:`~amplify.SymbolGenerator` is provided to dynamically generate an array of variables to be used in the formulation. :func:`~amplify.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:

.. code-block:: python

    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 :math:`f = 2 q_0 q_1 + q_0 + q_1 - 1` using the variable array ``q``.

.. code-block:: python

    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 :math:`4 \times 4`, you can create a variable array as follows:

.. code-block:: python

    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 :meth:`~amplify.BinarySymbolGenerator.array` method any number of times using the variable generator ``gen`` described previously.

.. code-block:: python

    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 :meth:`~amplify.BinarySymbolGenerator.scalar` method.

.. code-block:: python

    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.

.. code-block:: python

    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 :func:`~amplify.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 :func:`~amplify.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 :func:`~amplify.SymbolGenerator`.

The :func:`~amplify.SymbolGenerator` is a function to generate the class objects below. The variable generator classes, such as the :class:`~amplify.BinarySymbolGenerator` class, may be also used directly.

+--------------------------------------------+------------------------------------+
|           Variable generator class         |             Alias                  |
+============================================+====================================+
| :class:`~amplify.BinarySymbolGenerator`    | ``SymbolGenerator(BinaryPoly)``    |
+--------------------------------------------+------------------------------------+
| :class:`~amplify.IsingSymbolGenerator`     | ``SymbolGenerator(IsingPoly)``     |
+--------------------------------------------+------------------------------------+
| :class:`~amplify.BinaryIntSymbolGenerator` | ``SymbolGenerator(BinaryIntPoly)`` |
+--------------------------------------------+------------------------------------+
| :class:`~amplify.IsingIntSymbolGenerator`  | ``SymbolGenerator(IsingIntPoly)``  |
+--------------------------------------------+------------------------------------+

.. code-block:: python

    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]

.. _polynomial-substitute:

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.

.. code-block:: python

    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.

.. code-block:: python

    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.

.. _polynomial-decode_solution:

Obtain a Solution using an Array of Variables
---------------------------------------------

To make a correspondence between a polynomial array to the output of the solver class :class:`~amplify.Solver`, it is convenient to use the :meth:`~amplify.BinaryPolyArray.decode` method. By giving a solution in dictionary form to :math:`~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 :meth:`~amplify.BinaryPolyArray.decode` method.

.. code-block:: python

    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)}")

.. code-block:: none

    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 :math:`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.

.. code-block:: python

    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 :math:`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 :meth:`~amplify.BinaryPolyArray.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 :meth:`~amplify.BinaryPolyArray.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 :meth:`~amplify.BinaryPolyArray.decode` method will return an object of Python list, not a NumPy array.


.. note::
    For compatibility with previous versions, the :func:`~amplify.decode_solution` function is provided. This has the following effect.

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

.. _polynomial-logic_operations:

Construction of Logical Expressions
-----------------------------------

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

.. code-block:: python

    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.

+-------------+-------------+----------------------+------------------------------+
| :math:`x_0` | :math:`x_1` | :math:`x_0 \lor x_1` | :math:`-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 :math:`f_0` and :math:`f_1` are assumed to satisfy :math:`0` or :math:`1` for all possible cases of the variables. The behavior for other possible values is undefined.

+-----------------------+--------------------------------+
| Logic operation       | Output                         |
+=======================+================================+
| :math:`f_0 \lor f_1`  | :math:`-f_0 f_1 + f_0 + f_1`   |
+-----------------------+--------------------------------+
| :math:`f_0 \land f_1` | :math:`f_0 f_1`                |
+-----------------------+--------------------------------+
| :math:`f_0 \oplus f_1`| :math:`-2 f_0 f_1 + f_0 + f_1` |
+-----------------------+--------------------------------+
| :math:`\lnot f_0`     | :math:`- f_0 + 1`              |
+-----------------------+--------------------------------+


As an example of a formulation, the `Maximum SAT problem <https://en.wikipedia.org/wiki/Maximum_satisfiability_problem>`_ can be represented by a binary variable polynomial. The `Maximum SAT problem <https://en.wikipedia.org/wiki/Maximum_satisfiability_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 :math:`x_0, x_1, x_2`, given the following boolean expression.

.. math::

    \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:

.. code-block:: python

    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.

.. code-block:: python

    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 :math:`x_0, x_1, x_2` that satisfies all four clauses.

.. _polynomial-numeric_funcs:

Formulation Auxiliary Function
------------------------------

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

* :func:`~amplify.sum_poly` function represents a sum (Equivalent to :math:`\sum_i`)
* :func:`~amplify.pair_sum` function represents a combinatorial sum (Equivalent to :math:`\sum_{i \ne j}`)
* :func:`~amplify.product` function represents a product (Equivalent to :math:`\prod_i`)

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

* :func:`~amplify.intersection` function is equivalent to all logical products :math:`\land_i`
* :func:`~amplify.union` function is equivalent to all disjunctions :math:`\lor_i`
* :func:`~amplify.symmetric_difference` function is equivalent to all exclusive ors :math:`\oplus_i`

These functions have the following three functions.

Operations on Variable Arrays
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Perform the following operations on a variable array ``q``.

.. math::

    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]


.. code-block:: python

    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 :func:`~amplify.sum_poly` function rather than the built-in :func:`sum` function for speed.

.. note::
    For the operation of sum on polynomial arrays, it is recommended to use the :func:`~amplify.sum_poly` function rather than the built-in function :func:`sum`, because of execution speed consideration.

Applying the :func:`~amplify.sum_poly` function to a multidimensional polynomial array yields the same result as the :meth:`~amplify.BinaryPolyArray.sum` method with no axes specified. To compute the sum for an arbitrary axis, use the :meth:`~amplify.BinaryPolyArray.sum` method.

.. code-block:: python

    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:

.. math::

    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]

.. code-block:: python

    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 :math:`g(i)`, which takes a polynomial value.

.. math::

    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)


Either give a numerical range as the first argument, or give the same arguments as the built-in function :class:`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 :func:`~amplify.pair_sum` function can also be given a function with two arguments.

Example: Operations on Functions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. math::

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

.. code-block:: python

    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
~~~~~~~~~~~~~~~~~~~~~~~~~~

.. math::

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

.. code-block:: python

    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:

.. math::

    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)

Operations on Indices
^^^^^^^^^^^^^^^^^^^^^

Simultaneously create variables ``q_i`` and compute the following.

.. math::

    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


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 :class:`range`. The final argument is the type of the polynomial class.

.. code-block:: python

    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:

.. math::

    l &= \bigwedge_{i = 0}^{n - 1} x_i

    l &= \bigvee_{i = 0}^{n - 1} x_i

    l &= \bigoplus_{i = 0}^{n - 1} x_i

>>> 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

.. _polynomial-einsum:

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 :func:`~amplify.einsum` function. Please see :ref:`Formulation by Polynomial Array <polynomial_array-einsum>` for details on the function.

.. seealso::

    It functions as :func:`numpy.einsum` for polynomial arrays. Please see also :func:`numpy.einsum` for the argument notations and functionalities.

The followings are examples of the Einstein summation convention for the two-dimensional array :math:`q`.

.. code-block:: python

    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 :math:`s` of a two-dimensional array.

.. math::
    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 :math:`p` computed from the summation over the row direction.

.. math::
    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 :math:`p` computed from the inner product of each row and column.

.. math::
    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-method:

Polynomial Class Methods
------------------------

Change Variables
^^^^^^^^^^^^^^^^

The :meth:`~amplify.change_variables` method converts indices of variables in a polynomial object to another indices.

.. code-block:: python

    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 :meth:`~amplify.BinaryPoly.count` method returns how many terms a polynomial object contains.

.. code-block:: python

    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

.. _poly-constant:

Obtain Constant Term
^^^^^^^^^^^^^^^^^^^^

The constant term of a polynomial object can be obtained using :meth:`~amplify.BinaryPoly.constant`.

.. code-block:: python

    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
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

:meth:`~amplify.BinaryPoly.is_number` returns whether the polynomial object consists only of constants. If it is ``True``, an implicit conversion to a number is possible.

.. code-block:: python

    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

.. _poly-degree:

Obtain the Degree
^^^^^^^^^^^^^^^^^^

The degree of a polynomial object can be obtained by the :meth:`~amplify.BinaryPoly.degree` method. If the polynomial object is equal to :math:`0`, :math:`-1` will be returned.

.. code-block:: python

    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 :meth:`~amplify.BinaryPoly.is_linear` method returns whether the polynomial is at most linear.

.. code-block:: python

    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 :meth:`~amplify.BinaryPoly.is_quadratic` method returns whether the polynomial is at most quadratic.

.. code-block:: python

    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 :meth:`~amplify.BinaryPoly.max_index` method returns the largest index of a variable that appears in a term of a polynomial object.

.. code-block:: python

    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 :meth:`~amplify.BinaryPoly.decode` method to assign values to variables of a polynomial object.

.. code-block:: python

    from amplify import BinarySymbolGenerator

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

In the following, :math:`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 :meth:`~amplify.replace` and :meth:`~amplify.replace_all` methods are provided. They perform variable substitution in the same way as the :meth:`~amplify.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 :attr:`~amplify.BinaryPoly.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 :func:`print` function. The initial value is :math:`q` for binary variable polynomials and :math:`s` for Ising variable polynomials.

.. code-block:: python

    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

.. code-block:: python

    f.symbol = "x"

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

.. _poly-asdict:

Convert to Dictionary Format
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

:meth:`~amplify.BinaryPoly.asdict` converts a polynomial to a Python dictionary type.

.. code-block:: python

    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}

.. _to-binary:

Convert to a Polynomial on Binary Variables
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The :meth:`~amplify.IsingPoly.to_Binary` method converts an Ising variable polynomial to a binary variable polynomial. Variables are converted by the correspondence :math:`s = 2 q - 1` between the binary variable :math:`q` and the Ising variable :math:`s` by default.

.. code-block:: python

    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 :math:`0, 1` correspond to the Ising variables :math:`-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 :math:`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 :meth:`~amplify.BinaryPoly.to_Ising` method converts a binary variable polynomial to an Ising variable polynomial. By default, variables are converted by the correspondence :math:`q = \left(s + 1\right) / 2` between the binary variable :math:`q` and the Ising variable :math:`s`.
If ``False`` was given to the keyword argument ``ascending``, the conversion will be made by the correspondence :math:`q = \left(-s + 1\right) / 2`.

.. code-block:: python

    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 :meth:`~amplify.BinaryPoly.to_Matrix` method converts a polynomial into matrix form. The degree of the polynomial must be less than or equal to :math:`2`.

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

.. seealso::
    Please see :doc:`matrix` for matrix classes.

.. code-block:: python

    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)

.. code-block:: python

    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            |
+=================================+=====================================+
|   :class:`~amplify.BinaryPoly`  |   :class:`~amplify.BinaryMatrix`    |
+---------------------------------+-------------------------------------+
|   :class:`~amplify.IsingPoly`   |   :class:`~amplify.IsingMatrix`     |
+---------------------------------+-------------------------------------+
| :class:`~amplify.BinaryIntPoly` | :class:`~amplify.BinaryIntMatrix`   |
+---------------------------------+-------------------------------------+
|  :class:`~amplify.IsingIntPoly` |   :class:`~amplify.IsingIntMatrix`  |
+---------------------------------+-------------------------------------+