## AWS Quantum Technologies Blog

# Accelerating simulated quantum annealing on AWS Graviton processors

*This post was contributed by Kohji Nishimura, CTO, Jij, Yoshitaka Haribara, Senior Startup ML/Quantum Solutions Architect and Perminder Singh, Senior Partner Solutions Architect, Quantum, at AWS*

Numerical optimization is the process of minimizing or maximizing a given cost function, subject to any given constraints. Business needs across many industry verticals, like manufacturing, logistics, and telecommunication, require solving large-scale optimization problems. A scheduling plan that minimizes traffic congestion in logistics application, or a manufacturing plan that minimizes overall production costs are typical examples of combinatorial optimization – a class of some of the most computationally challenging problems.

Well-established techniques provide algorithmic performance guarantees for specific optimization problems, such as linear programming, where both the cost function and constraints are linear. However, for problems with nonlinear cost functions and constraints, these techniques aren’t suitable. In such cases, heuristics are commonly used to seek approximate solutions. Simulated Annealing (SA), Quantum Annealing (QA) — its quantum analog, and Simulated Quantum Annealing (SQA) — the classical version of QA, are heuristic algorithms designed to approximate solutions for nonlinear optimization problems.

In this post, we demonstrate how SQA can be accelerated by the Arm-based AWS Graviton processors, namely Graviton2 and Graviton3. SQA represents a good example of how we can leverage AWS-designed silicon to improve the implementation of quantum-inspired classical heuristics. We also show that the solution can be seamlessly integrated with JijZept — a cloud service for numerical optimization using quantum technology.

## Quadratic unconstrained binary optimization (QUBO) and Ising model

QUBO is an example of a combinatorial optimization problem. In QUBO, one is tasked with minimizing a cost function that is quadratic in binary decision variables *q _{i}* (each variable can be either 0 or 1). If

*Q*denotes a square matrixrepresenting a QUBO problem then solving the problem is equivalent to minimizing the cost function, which can be represented as:

_{ij}The QUBO model is equivalent to the popular Ising model in statistical physics, which is used to describe the behavior of spin systems:

with the transformation *s _{i}* = 2

*q*– 1.

_{i}## Annealing: simulated and quantum

Finding the optimal spin configuration of the Ising model that minimizes the given Hamiltonian *H* (which also optimizes the corresponding QUBO model) is typically an intractable NP-hard problem.

One of the most popular methods for finding an approximate solution to such problems is using the SA algorithm. This algorithm starts with an initial binary variable (spin) configuration and gradually changes it by selecting a new solution, and accepting or rejecting it based on a probabilistic criterion. This allows the algorithm to escape from local minima and explore the solution space more effectively.

QA is a quantum computing analogue of the SA algorithm. In QA, a system of qubits is time evolved using a Hamiltonian which consists of two parts: the cost function and the driver Hamiltonian, as follows:

The strengths of the driver Hamiltonian and the cost function are tuned by quantum devices so that at the initial point *s* = 0, the term *A*(*s*) is dominant, and at the final point *s* =* s _{f}* the term

*B*(

*s*) is dominant. Under the assumption of adiabaticity, the final state of the qubits reaches the ground (lowest energy) state of the cost function Hamiltonian that we want to minimize.

## Simulated quantum annealing (SQA)

Currently, applying the QA algorithm to real-world optimization problems using quantum devices is challenging due to limitations in device topology, and the intrinsic noise that affects the QA process. To evaluate the algorithm performance without encountering those challenges, developers created a classical method called SQA to simulate quantum annealing using conventional computers.

SQA algorithm uses the quantum Monte Carlo approach to sample the solution. Applying the Suzuki-Trotter decomposition technique [Trotter (1959), Suzuki (1976)], the original quantum Hamiltonian can be transformed into an equivalent classical Hamiltonian with Trotter slices that characterize the quantum fluctuation. It is important to note that the total number of spins required for the calculation increases by a factor of the number of Trotter slices, and the more Trotter slices are introduced, the more accurately the computation can be performed, especially in regions of low temperature.

## Parallelization technique on AWS Graviton processors

One of the main drawbacks of the SQA algorithm is that it requires redundant computational resources to express the Trotter slices. Although the calculation of each Trotter slice can be parallelized using a multi-core CPU, such processors often have a very high cost. However, Graviton processors provide an efficient parallelization solution using its multi-core feature (up to 64 cores in current configurations). Moreover, the latest processor generation, Graviton3, offers up to 2x faster computation than the previous generation, Graviton2. As such, customers can achieve faster computation for their SQA-based optimization problems by using Graviton3 processors.

## Jij’s JijZept service

Even with powerful computing devices, there remain many obstacles to real-world optimization applications. These include:

- Constructing a mathematical model that accurately represents the problem.
- Converting the mathematical model to the QUBO formulation.
- Transferring the QUBO model to the solver in a memory-efficient manner.
- Tuning the hyperparameters of the QUBO-solving algorithm.

Jij’s product, JijZept, helps overcome these bottlenecks.

For instance, consider the Traveling Salesman Problem (TSP), which aims to find the optimal traveling route given distances between each city to be visited. The problem can be formulated as follows:

With the constraints:

Here, the variable *x _{i,t}* ∈ {0, 1} indicates whether the salesman travels to the

*i*-th city on the

*t*-th route. The variable

*d*represents the distance between the

_{i,j}*i*-th city and the

*j*-th city.

We can implement the problem in Python with the JijZept library:

```
import jijmodeling as jm
# define variables
d = jm.Placeholder("d", ndim=2)
N = d.shape[0]
N.set_latex("N")
i = jm.Element("i", belong_to=(0, N))
j = jm.Element("j", belong_to=(0, N))
t = jm.Element("t", belong_to=(0, N))
x = jm.BinaryVar("x", shape=(N, N))
# set problem
problem = jm.Problem("Traveling Salesman Problem")
problem += jm.sum([i, j], d[i, j] * jm.sum(t, x[i, t] * x[j, (t + 1) % N]))
problem += jm.Constraint("one-city", jm.sum(i, x[i, t]) == 1, forall=t)
problem += jm.Constraint("one-time", jm.sum(t, x[i, t]) == 1, forall=i)
```

We can easily visualize the modeled object in a Jupyter notebook environment.

Once the model is constructed, we can send it to the server with only three simple lines:

```
import jijzept as jz
instance_data = {"d": distance} # distance object type: `np.ndarray` with two dimensions.
sampler = jz.JijSASampler()
sampler.sample_model(problem, instance_data)
```

This Python code automates:

- Transferring the mathematical model to the solver in a memory-efficient manner.
- Converting the mathematical model to the QUBO formulation.
- Tuning the hyperparameters in the QUBO model.

We can easily switch the solver without changing the mathematical model. Here is an example:

```
# Using Graviton2 processor
sampler = jz.JijAWSGraviton2Sampler()
# Using Graviton3 processor
#sampler = jz.JijAWSGraviton3Sampler()
sampler.sample_model(problem, instance_data)
```

The more detailed usage is described in the documentation.

Once the problem request is sent to the server, Graviton processors fetch the request and solve the problem, as shown in the architecture diagram.

## Benchmarking SQA with an instance of the TSP

To evaluate the performance of the SQA algorithm, we experimented using a specific QUBO model to solve TSP defined earlier.

The QUBO model used for benchmarking includes constraints to ensure that all cities are visited exactly once. The QUBO matrix is transformed into a form where the constraint term is converted to penalty terms, which prevents the solution from violating the constraints. The resulting form is given by:

Where λ_{t}^{1} and λ_{i}^{2} are the coefficients of the penalty terms. Note that the TSP in QUBO formulation are chosen as a benchmark purpose; there is room for designing more efficient algorithms for this type of optimization problems [Schuetz et al. (2022)].

Solving this problem (i.e., obtaining the minimum cost function) gives the solution shown in this figure:

The blue dots indicate cities to be visited, and the orange solid line shows the traveling route specified by the solution *x _{i,t}*. The total length of the orange solid line is the traveling distance that is to be minimized.

We compared the results of the total traveling route obtained by running the SQA algorithm on Graviton2 and Graviton3 processors with those obtained using a naive SA algorithm on a conventional CPU. The benchmark was performed on TSP instances with 40 cities, and 100 samples of annealing were taken.

To see the experiment code, please refer to the GitHub repository. The file `code_with_jijmodeling_graviton.py`

contains the code used for the benchmark.

The benchmark results appear in the figure that follows, where the horizontal axis represents the calculation time of each sample and the vertical axis indicates the total traveling route’s distance. The dashed lines, dark-shaded areas, and light-shaded areas represent the mean value, standard deviation, and minimum and maximum values of the samples, respectively. We can clearly see that the SQA algorithm produces a smaller traveling distance compared to the SA algorithm, which gets stuck at a distance of around 190. Additionally, we observed that the Graviton3 processor computes around 1.5x faster than the Graviton2 processor even if the experimental condition and parameters are the same.

## Conclusion

In this blog post, we have demonstrated the implementation of the SQA algorithm with TSP in QUBO formulation as a benchmark on Graviton processors. We have highlighted the benefits of using Graviton processors, which have a multicore architecture that allows efficient handling of the SQA algorithm. Specifically, we have shown that Graviton3 is 1.5 times faster than Graviton2 for our implementation of the algorithm. These findings highlight the potential of cloud platforms to harness quantum-inspired algorithms effectively. We have also showcased the cloud service JijZept, which enables customers to use the Ising solver without the need to consider the device-specific features of the underlying hardware.

Note that our approach can be applied not only to specific problems but also to various types of real-world applications such as flight scheduling, last-mile package delivery, or work scheduling of workers.

Overall, the combination of quantum-inspired heuristics, such as SQA, and powerful cloud-based platforms, such as Graviton and JijZept, holds great promise for approximating solutions of complex optimization problems in a more efficient and scalable manner. To learn more, please visit the JijZept web page or contact us through the AWS Partner page.

*The content and opinions in this blog are those of the third-party author and AWS is not responsible for the content or accuracy of this blog.*