Tutorial

Introduction

The Amplify SDK is a middleware library that makes it easy to work with Ising machines. Ising machines are dedicated hardware for minimizing polynomial of binary variables, called Ising models or QUBO models. The following is an expression of 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 optimization problem to be solved needs to be converted to the input format supported by the Ising machine. This is because many Ising machines only accept quadratic polynomials in the binary variables \(\left\{0, 1\right\}\) or Ising variables \(\left\{-1, 1\right\}\) as input (logical model). For some Ising machines, quadratic polynomials must follow a specific form 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, the input model need to be transformed to a logical model, and then the logical model need to be transformed 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 need to be applied to each step. “pre-processing”, such as handling the constraints associated with the transformation, and “post-processing”, such as checking the constraint satisfaction of the output values related to the inverse transformation, are also crucial in this transformation and inverse transformation processes.

The Amplify SDK provides an integrated interface for running optimization problems on Ising machines. This interface can hide the transformations, inverse transformations, pre-processing, and post-processing that depend on the input models and the specification of each Ising machine. 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.

[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 the Amplify SDK to support each layer are summarized below.

Input Layer

This is the layer where users operate directly by handling input models to Ising machines. The followings are the available expressions:

Polynomial:

BinaryPoly, IsingPoly, BinaryIntPoly, IsingIntPoly

polynomial array:

BinaryPolyArray, IsingPolyArray, BinaryIntPolyArray, IsingIntPolyArray

Matrix:

BinaryMatrix, IsingMatrix, BinaryIntMatrix, IsingIntMatrix

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:

DWaveSamplerClient, LeapHybridSamplerClient

Fujitsu:

FujitsuDASolverClient, FujitsuDASolverExpertClient, FujitsuDAPTSolverClient, FujitsuDAMixedModeSolverClient, FujitsuDA2SolverClient, FujitsuDA2SolverExpertClient, FujitsuDA2PTSolverClient, FujitsuDA2MixedModeSolverClient, FujitsuDA3SolverClient

Toshiba:

ToshibaClient

Hitachi:

HitachiClient

Hiroshima Univ. / NTT DATA:

ABSClient

Gurobi:

GurobiClient

Programming Flow with the Amplify SDK

The flow for using Ising machines with the 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 use and set the parameters (Physical machine layer).

4. Feed the logical model to the optimization solver and obtain the results by 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 optimization problem of minimizing a polynomial on binary variables \(\left\{0, 1\right\}\).

\[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 \(f \left( q_0 = 1, q_1 = 1 \right) = 0\) can be immediately obtained. 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 SymbolGenerator() function.

from amplify import BinaryPoly, SymbolGenerator

gen = SymbolGenerator(BinaryPoly)  # Define Variable Variable Generator
q = gen.array(2)  # Generate a Binary array of length 2

>>> q
[q_0, q_1]

A one-dimensional array of length \(2\) is created. Using this, we construct a polynomial as follows:

f = 1 - q[0] * q[1]

>>> f
- q_0 q_1 + 1

Using the generator of variable arrays, it is possible to systematically construct polynomials using array names and their indices in the program code. For more advanced problems, you will need to deal with multiple variables together, so declaring an array of the variables and proceeding with formulation eliminates the need to manage individual variables and gives you a better outlook. Multiple arrays and scalar variables can also be managed. Please see Construction using variable arrays for details.

Note

Not limited to quadratic polynomials, higher-order polynomials of the third degree or higher can also be constructed.

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 BinaryQuadraticModel

model = BinaryQuadraticModel(f)

In addition to polynomials, matrices and constraints can be used to construct a logical model. Combinations of a polynomial and constraints, or a matrix and constraints can be also given. 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 Creating Logical Model Object.

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.client import FixstarsClient

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 one from the top as below. In this case, we used a simple polynomial with binary variables as the input model, but if constraints are given, the solutions are filtered so that only the ones that satisfy the constraints will be output.

from amplify import Solver

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 is the value of the input model \(f\), and values is a dictionary with the input indices as keys and variable values as 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.

It is convenient to use the decode() method to relate input variables to output variables. This function reshapes the output values into the same shape as the variable array used in the input model.

for solution in result:
    print(f"q = {q.decode(solution.values)}")

q = [1. 1.]

The dictionary values with the input indices as keys and the variable values as values has been applied to the variable array q. This makes it possible to efficiently interpret the solution in the same format as the variable array of the input model.

In summary, the following is the code template for the Ising machine execution using the Amplify SDK.

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

# Generate Variable Arrays
gen = SymbolGenerator(BinaryPoly)
q = gen.array(2)

# Construct Binary Polynomial
f = 1 - q[0] * q[1]
model = BinaryQuadraticModel(f)

# Set Ising Machine Client Settings
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second

# Run Solver
solver = Solver(client)
result = solver.solve(model)

# Analysis of result
for solution in result:
    print(f"q = {q.decode(solution.values)}")

Next Step

This is the basic flow of programming with the Amplify SDK.

Please see the Demo Tutorial Page for sample code for specific problems.

If you wish to continue reading the tutorial, or for more advanced usage, please continue reading in the next section and beyond. The later sections introduce detailed explanations of how to construct various forms of optimization problems and the functionality of each of the classes. A formal reference to the classes and functions is available at Reference.