Amplify 101¶

Introduction¶

Welcome to Fixstars Amplify tutorial. Amplify is a platform that makes it easy and efficient to use quantum annealing and ising machines. With Amplify, you can quickly create optimization applications for combinatorial optimization problems. In addition, because Amplify is compatible with a wide variety of Ising machines by making small changes, the effort of migrating between various Ising machines is greatly reduced.

In this tutorial, you will learn how to use Amplify to solve combinatorial optimization problems quickly and efficiently. This tutorial includes the following contents:

How to formulate a combinatorial optimization problem as a minimization problem of binary variable polynomials
How to solve a minimization problem for a binary variable polynomial using Amplify
How to handle constraints with Amplify
Tips for using Amplify
Real-world examples of solving various combinatorial optimization problems with Amplify

In this tutorial, you will learn how to use Amplify in an online environment. If you want Amplify to run on your computer, please follow the Quick Start to install it.

Quantum Annealing Machines and Ising Machines¶

A quantum annealing machine and Ising machine are systems that solve optimization problems represented by Ising models or QUBO models. If we can formulate a combinatorial optimization problem using a Ising model or QUBO model, we can use quantum annealing machines or Ising machines to solve the combinatorial optimization problem.

About Combinatorial Optimization Problem¶

A combinatorial optimization problem expresses a criterion for determining variables that represent discrete values such as integers and permutations. Most combinatorial optimization problems are expressed by the following three components: decision variables, objective function, and constraints.

Variables are elements that are subject to changes to improve objective functions or to satisfy constraints such as "list of products to buy", "travel routes", and so on.
An objective function quantitatively defines how good variables are, such as "buying as cheap a product as possible", "going as short a distance as possible", etc.
Constraints define the conditions that variables must meet, such as "a product can be purchased only once" or "a place can be visited only once".

The followings show a few examples of optimization problems.

Travelling Salesman Problem¶

The traveling salesman problem is to determine the order of the shortest travel route over cities by visiting them exactly only once. The expression for this combinatorial optimization problem is as follows.

Objective function: Sum of the distances traveled through all cities
Constraint: The salesman should not visit one city more than once
Variable: The order in which cities are visited

Graph Coloring Problem¶

The graph coloring problem is to paint regions in such a way that no adjacent regions have the same color. The expression for this combinatorial optimization problem is as follows.

Objective function: None
Constraint: Adjacent regions do not have the same color
Variable: Color of each region

The Ising Model and QUBO Model¶

The Ising model and the QUBO model are the types of problems that the quantum annealing machine and the Ising machine can handle. In order to solve various combinatorial optimization problems with quantum annealing machines and Ising machines, it is necessary to convert the combinatorial optimization problems into Ising and QUBO models.

The QUBO model is represented by the following equation:

$ \displaystyle H = \sum_{i<j} J_{ij} q_i q_j + \sum_i h_i q_i \quad q_i\in\{0, +1 \} $

The Ising model can also be expressed by the following equation:

$ \displaystyle H = \sum_{i<j} J_{ij} s_i s_j + \sum_i h_i s_i \quad s_i\in\{+1, -1 \} $

The only difference between the Ising model and the QUBO model is the values of the variables to be handled. These models can be transformed from one to the other by appropriate equation transformations.

The Roles of Amplify¶

In this way, Amplify plays two major roles in solving combinatorial optimization problems through Ising and QUBO models.

Formulation Support for the Ising Model and QUBO Model¶

For example, in general combinatorial optimization problems, equality constraints and inequality constraints appear as the types of constraints. However, the Ising model and QUBO model cannot directly describe such constraints, and users need to devise their own methods. Furthermore, it is difficult to flexibly handle constraints, such as checking whether the optimization result satisfies the constraints of the original problem, or treating some variables as constants. Amplify provides a number of features that make the formulation of problems in the Ising and QUBO models intuitive.

Absorbing Differences Between Machines¶

Currently, various quantum annealing and Ising machines are being researched and developed, and updates to the machines and associated performance improvements are being actively made. The cost of keeping up with such machines that are constantly being updated and using various machines with different specifications is high.

An example of differences in the specifications of machines is that problem formats that can be directly run by each machine may be different, so a problem needs to be converted to an appropriate format. Each quantum annealing machine or Ising machine does not necessarily solve the Ising model or the QUBO model directly. Some machines require further transformations of the models into the ones that they can directly handle, before solving problems. Separate transformation processes are thus needed for the machines that require this type of transformation of models. In addition, each machine has different forms of requests for sending problems to be solved, so it needs to be implemented according to the specifications of each machine.

Amplify absorbs these differences in machine specifications and makes it easy to run different machines with little code changes.

In the next section, we will learn how to use Amplify to solve combinatorial optimization problems.

Ising Model¶

This section describes the "Ising model", a kind of "binary variable quadratic polynomial", which is the input form of the annealing machine.

Definition of Ising Model¶

The Ising model is represented by a polynomial function of the Ising variables of the following form

$ \displaystyle H = \sum_{i<j} J_{ij} s_i s_j + \sum_i h_i s_i \quad s_i\in\{+1, -1 \} $

Solving the Ising Model with Amplify¶

As an example, we will take up the following minimization problem of a function (quadratic polynomial of binary variables) of the Ising variable {+1,-1}.

$ \displaystyle f(s_0, s_1) = 1 - s_0 s_1 $

Since $s_0,s_1 \in \{+1, -1\}$, $f(s_0=1,s_1=1)=0 $ is one of the optimal solutions.

Let's try to express this using Amplify.

Formulation using Amplify¶

Amplify uses the IsingPoly class to represent polynomials in the Ising model.

In [ ]:

                  from amplify import IsingPoly, gen_symbols
    
# Define the Ising variables s_0 and s_1
s = gen_symbols(IsingPoly, 2)
    
# Define the objective function f = 1 - s_0 * s_1
f = 1 - s[0] * s[1]
    
print(f"f = {f}")

Let's run the minimization problem of a quadratic polynomial of binary variables created in this way on an annealing machine to see if a solution can be obtained.

In [ ]:

                  from amplify import Solver
from amplify.client import FixstarsClient
    
# Set up the client
client = FixstarsClient()  # Fixstars Optigan
client.parameters.timeout = 1000  # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"  # If you are using it in a local environment, please enter the access token for Amplify AE
    
# Building a solver
solver = Solver(client)  # Set the client to be used for the solver
    
# Enter the problem and run the machine
result = solver.solve(f)  # Enter the problem and run the machine

                

Obtaining the Results¶

In the above example, result, obtained by executing the machine with solver.solve, is an object with the following attributes.

solutions: A list of execution results. Each element has the following attributes.
- energy: Energy value (evaluation value of input model)
- values: A dictionary of input variables corresponding to the above energy (key is the index of the variable, value is the value of the variable)
- frequency: Number of identical solutions

For example, the solution at the top of the list of results can be obtained with result.solutions[0].values. The same can be achieved with result[0].values. This is because the element access to result transparently becomes the access to the elements of result.solutions.

If you want to get the value of the solution for each element of the variable array, the decode_solution function is useful.

In [ ]:

                  from amplify import decode_solution
    
for sol in result:  # Iterate over multiple solutions
    # sol.values: Value of the decision variable (dictionary with key as index and value as variable value)
    # sol.energy: Value of the objective function (the value obtained by substituting the decision variable into the objective function)
    solution = decode_solution(
        s, sol.values
    )  #  Decode variable array s with sol.values
    
    print(f"result: {s} = {solution} (f = {sol.energy})")

                

$s_0=1,s_1=1$ was obtained as the optimal solution.

QUBO Model¶

We explain another input format of the annealing machine, the QUBO model.

Definition of QUBO Model¶

QUBO stands for Quadratic Unconstrained Binary Optimization, and it refers to an unconstrained 0-1 integer quadratic programming problem.

The QUBO model is represented by a polynomial function of binary variables of the following form:

$ \displaystyle H = \sum_{i<j} J_{ij} q_i q_j + \sum_i h_i q_i \quad q_i\in\{0, +1 \} $

Solving the QUBO model with Amplify¶

Let's look at an example of a two-variable problem in the QUBO model.

$ \displaystyle f(q_0, q_1) = 1 - q_0 q_1 $

$f(q_0=1,q_1=1)=0 $ is the optimal solution.

Let's try to express this using Amplify.

First, we define the objective function.

In [ ]:

                  from amplify import BinaryPoly, gen_symbols
    
# Define the Ising variables q_0 and q_1
q = gen_symbols(BinaryPoly, 2)
    
# Define the objective function 1 - q_0 * q_1
f = 1 - q[0] * q[1]
    
print(f"f = {f}")

As before, we will find the optimal solution for this objective function.

In [ ]:

                  from amplify import decode_solution, Solver
from amplify.client import FixstarsClient
    
# Set up the client
client = FixstarsClient()  # Fixstars Optigan
client.parameters.timeout = 1000  # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"  # If you are using it in a local environment, please enter the access token for Amplify AE
    
# Building a solver
solver = Solver(client)  # Set the client to be used for the solver
    
# Enter the problem and run the machine
result = solver.solve(f)  # Enter the problem and run the machine
    
for sol in result:  # Iterate over multiple solutions
    # sol.values: Value of the decision variable (dictionary with key as index and value as variable value)
    # sol.energy: Value of the objective function (the value obtained by substituting the decision variable into the objective function)
    solution = decode_solution(
        q, sol.values
    )  #  Decode variable array q with sol.values
    
    print(f"result: {q} = {solution} (f = {sol.energy})")

                

$q_0=1,q_1=1$ was obtained as the optimal solution.