Tutorial

Introduction

Amplify SDK is a middleware library that makes it easy to work with Ising machines. Ising machines are dedicated hardware for minimizing polynomial problems of binary variables, called Ising models or QUBO models. The following is an example of an expression by QUBO.

\[f = \sum_{i < j}{Q_{i,j} q_i q_j} + \sum_{i}{Q_{i,i} q_i} \quad \left(q_i \in \left\{ 0, 1\right\} \right)\]

Normally, to run an Ising machine, the “target optimization problem” needs to be converted to the input format supported by the Ising machine to be run. This is because many Ising machines only accept quadratic polynomials in the binary variable \(\left\{0, 1\right\}\) or Ising variable \(\left\{-1, 1\right\}\) as input (logical model). For some Ising machines, quadratic polynomials must follow a certain form that is consistent with the graph structure between variables originating from the hardware specification (physical model).

When an optimization problem (input model) is run on an Ising machine, we first need to transform the input model to a logical model, and then we further need to transform the logical model to a physical model specific to the Ising machine. On the other hand, in order to interpret the output values of the Ising machine, the inverse transformation of this procedure is applied to each step. In this transformation and inverse transformation processes, it is also important to process “pre-processing” such as the constraints associated with the transformation and “post-processing” such as the constraint satisfaction check of the output value associated with the inverse transformation.

The Amplify SDK provides an integrated interface for running optimization problems on Ising machines. This interface can hide the transformations, inverse transformations, preprocessing, and postprocessing that depend on the input models and the specifications of each Ising machine, and it also provides support for creating input models and interpreting results. See reference 1 for the Amplify SDK architecture. The following diagram illustrates the flow of the Amplify SDK from input to the Ising machine to execution and interpretation of results.

_images/architecture.png
1

Yoshiki Matsuda “Research and Development of Common Software Platform for Ising Machines” 2020 IEICE General Conference

The layers of the flow and the classes provided by Amplify SDK to support each layer are summarized in the following.

Input Layer

This is the layer where users operate directly by handling “input models” to Ising machines. The following expressions can be handled:

Polynomial

BinaryPoly, IsingPoly, BinaryIntPoly, IsingIntPoly

Matrix

BinaryMatrix, IsingMatrix, BinaryIntMatrix, IsingIntMatrix

Logical expression

LogicPoly

Constraint equation

BinaryConstraint, IsingConstraint, BinaryIntConstraint, IsingIntConstraint

Logical Layer

This layer abstracts the constructed input models to “logical models” that can be handled by Ising machines.

Quadratic polynomial model

BinaryQuadraticModel, IsingQuadraticModel, BinaryIntQuadraticModel, IsingIntQuadraticModel

Physical Machine Layer

This layer provides the optimization solver that converts logical models into “physical models” based on each hardware specification. Users only need to adjust the execution parameters of each machine, so there is no need for writing conversion codes directly.

Optimization solver

Solver

Machine client
Fixstars

FixstarsClient

D-Wave

DWaveClient (will be deprecated), DWaveSamplerClient, LeapHybridSamplerClient

Fujitsu

FujitsuDASolverClient, FujitsuDAPTSolverClient, FujitsuDAMixedModeSolverClient, FujitsuDA2SolverClient, FujitsuDA2PTSolverClient, FujitsuDA2MixedModeSolverClient

Toshiba

ToshibaClient

Programming Flow with Amplify SDK

The flow for using Ising machines with Amplify SDK is as follows:

  1. Formulate a target optimization problem and create the input model (Input layer).

  2. Transform the input model into a quadratic polynomial model (Logical layer).

  3. Declare the machine to be used and set the parameters (Physical machine layer).

  4. Feed the logical model to the optimization solver and obtain the results of the inverse transformation to the input layer.

The actual procedure for using Amplify in each layer described above is as follows.

First, we explain how to handle the “input model”. As a simplest example, we treat the following minimization problem of a function of the binary variables \(\left\{0, 1\right\}\) (a polynomial of binary variables).

\[f\left( q_0, q_1 \right) = 1 - q_0 q_1\]

Since \(q_0, q_1 \in \left\{ 0, 1 \right\}\), the optimal value can be immediately obtained as \(f \left( q_0 = 1, q_1 = 1 \right) = 0\). Here, we will actually input this problem into an Ising machine to see if it outputs the optimal solution.

BinaryPoly class is provided to represent polynomials of binary variables in program code.

There are several ways to construct BinaryPoly. One of the easiest ways is to prepare a set of variables as an array \(\mathbf{q} = \left\{q_0, q_1, ... \right\}\) and then construct the polynomial.

First, an array of variables can be created with gen_symbols() function.

from amplify import BinaryPoly, gen_symbols

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

gen_symbols(BinaryPoly, 2) creates a one-dimensional array of the binary variables (BinaryPoly) whose length is \(2\) and the variable index starting from \(0\). Using this, we can construct a polynomial as follows:

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols

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

In this way, you can systematically construct polynomials in your program code. You can also construct arrays of two or more dimensions, and start indexing from a specified value. Please see Construction using variable arrays for details.

Exercise

Change the degree and terms of the polynomial to make sure it is constructed as intended (tertiary and higher degrees are also possible).

Conversion to Logical Model

The next step is to build a logical model from the input model. Since we have BinaryPoly as an input, we convert it to BinaryQuadraticModel as a logical model. This conversion can be done implicitly with the optimization solver class Solver described below, but here we make it explicit with the model variable as shown below.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols

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

In addition to polynomials, matrices and constraint equations can be used to construct this logical model. It can be also given as a combination of polynomials and constraint equations, or matrices and constraint equations. The internal representation and internal state of a logical model can be obtained by several methods, but we will not discuss them in this tutorial.

Note

For polynomials and matrices in combination with constraints,, please see Constructing a Logical Model Object.

Note

For an example of using constraint expressions, please see EXAMPLES.

Settings for the Ising Machine to Run

Here, we declare the Ising machine to use and set the machine parameters. We use Amplify Annealing Engine (FixstarsClient) as an example.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols
from amplify.client import FixstarsClient

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

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # Timeout is 1 second

Note

Please enter your Amplify Annealing Engine access token in the xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx field. You can get an access token by registering as a free user.

Note

Please see the respective client references in Client for parameters when using other clients.

Performing Combinatorial Optimization

The preparation has been completed now. By setting the client to the optimization solver Solver and calling the solve() method, we can run an Ising machine. Since the Ising machine may output multiple solutions, we will extract them from the top as follows. In this case, we used a simple polynomial equation with binary variables as the input model, but if a constraint equation is given, the solutions are filtered so that only the ones that satisfy the constraint will be output.

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

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

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # Timeout is 1 second

solver = Solver(client)
result = solver.solve(model)
for solution in result:
    print(f"energy = {solution.energy}\nvalues = {solution.values}")
energy = 0.0
values = {0: 1, 1: 1}

In the displayed values, energy represents the value of of the input model \(f\), and values represents a dictionary of the input indices and variable values. So the solution shown here means \(f\left( q_0 = 1, q_1 = 1 \right) = 0\). This is consistent with the optimal solution and the optimal value we initially expected.

To relate input variables to output variables, it is useful to use the decode_solution() function. This function decodes the array of variables used in the construction of the input model and converts it to the array evaluated with output values.

from amplify import (
    BinaryPoly,
    BinaryQuadraticModel,
    gen_symbols,
    Solver,
    decode_solution,
)
from amplify.client import FixstarsClient

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

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # Timeout is 1 second

solver = Solver(client)
result = solver.solve(model)
values = result[0].values
print(f"q = {decode_solution(q, values)}")
q = [1.000000, 1.000000]

decode_solution(q, values) applies a dictionary of input indices and variable values values to an array of variables q. This allows the solution to be interpreted efficiently just as building the input models.

Note

If the variable values do not exist for some of the indices of a variable array, no value will be applied to the array elements (variables) of those indices. If the third argument of decode_solution() is set to a default value, the default value will be applied in such elements. Please see Obtaining the solution using an array of variables for details.

Next Step

This is the basic flow of programming with the Amplify SDK. Please see the next section for more advanced methods of use, EXAMPLES for examples for specific problems, and Reference for class and function references.