SQA computing

myQLM is equipped with a simulated annealer (SA), which can solve combinatorial problems encoded in an Ising or Quadratic Unconstrained Binary Optimization (QUBO) formalism - take a look at an Introductory notebook. It could also handle a general CombinatorialProblem with clauses and variables, as long as each of its Clause contains no more than two Var, such that it is translatable to Ising or QUBO.

Albeit not quantum, the simulated annealing solver is wrapped with a Quantum Processing Unit (QPU) interface which is made to resemble the rest of the QPUs on myQLM. It therefore consists of an implementation of the submit method of SimulatedAnnealing, which receives a Job and returns a Result. The Job is created via the to_job() method of the special purpose Ising or QUBO classes (or CombinatorialProblem, if applicable).

Note

The full Qaptiva appliance includes the even more powerful Simulated Quantum Annealing (SQA) solver which has been tested on a variety of benchmarks for the NP problems supported for annealing. The quality of the solutions is \(> 98 \%\) - see SQA benchmarking and performance for more details.

Inner workings

Simulated annealing (SA) is a well-known, historical heuristic for combinatorial optimization. It aims at finding low energy-states of a classical Ising system with a Markov Chain over spin configurations, with decreasing stochasticity.

Stochasticity is specified by a temperature. In practice, a decreasing temperature schedule is given to the algorithm. At the beginning of the execution, large temperature values allow to jump over energy barriers to escape local optima. When temperature settles to lower values, the Markov chain will hopefully settle to the global optimum of the cost function.

Mathematically, simulated annealing tries to find, given \(h\) and \(J\), the global minimum configuration of:

\[H(s_{1},...,s_{n}) = -\sum_{i,j=1}^{n} J_{ij}s_{i}s_{j}-\sum_{i=1} h_{i}s_{i}\]

It does so by first choosing a random configuration, which then evolves by applying updates. In the case of simulated annealing, an update consists in flipping the value \(s_{i}\) of a single spin.

An update is accepted with probability:

\[P_{flip} = min(1, e^{-\Delta H / T})\]

with \(\Delta H\) is the energy change incurred by switching from \(s_{i}\) to \(-s_{i}\). A change decreasing the energy of the system is always accepted, whereas a change which increases it needs a temperature high enough to have a non-negligible probability of being accepted.

The following picture explains in pseudo-code how simulated annealing works.

../../../images/simulated_annealing_algoritm_latex.png

A basic example of the use of SA - to solve the Antiferromagnetic Ising Model, is presented in the notebook Getting started with SA. Some more involved examples where SA solves some of the NP-hard problems have also been implemented in the following notebooks.