# Omnisolver: an extensible interface to Ising spin glass solvers

Konrad Jałowiecki  Łukasz Pawela  Institute of Theoretical and Applied
Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice, Poland
Institute of Physics, University of Silesia, Bankowa 12, 40-007 Katowice,
Poland

###### Abstract

We introduce a new framework for implementing Binary Quadratic Model (BQM)
solvers called omnisolver. The framework provides an out-of-the-box
dynamically built command-line interface as well as input/output system, thus
heavily reducing the effort required for implementing new algorithms for
solving BQMs. The proposed software should be of benefit for researchers
focusing on quantum annealers or discrete optimization algorithms as well as
groups utilizing discrete optimization as a part of their daily work. We
demonstrate the ease of use of the proposed software by presenting a step-by-
step, concise implementation of an example plugin.

###### keywords:

QUBO , spin-glass , discrete optimization , quantum annealing

††journal: SoftwareX

## Required Metadata

Nr. |  Code metadata description |  Please fill in this column
---|---|---
C1 |  Current code version |  v0.1.0
C2 |  Permanent link to code/repository used for this code version |  https://github.com/euro-hpc-pl/omnisolver
C4 |  Legal Code License |  Apache 2.0
C5 |  Code versioning system used |  git
C6 |  Software code languages, tools, and services used |  Python, YAML
C7 |  Compilation requirements, operating environments & dependencies |  Linux, Python >= 3.9, dimod, pluggy, plugins may require additional Python packages and build dependencies
C8 |  If available Link to developer documentation/manual |  https://omnisolver.readthedocs.io/
C9 |  Support email for questions |<EMAIL_ADDRESS>
Table 1: Code metadata (mandatory)

##  1 Motivation and significance

The rapidly developing field of quantum information brings us ever closer to
developing practical quantum computers. Currently, we are living in an era
marked by the so-called Noisy Intermediate-Scale Quantum (NISQ) [1] devices.
It comes as no surprise that these machines have attracted attention from both
the scientific and business communities. This attention results in a myriad of
proposed potential applications for NISQ devices. One of the potential
obstacles in developing quantum software, which this work aims to remedy, is
the cost of testing on actual NISQ devices.

The main way to cut quantum infrastructure access costs is to utilize
frameworks that simulate their behavior. Nonetheless, if we try this approach,
we quickly run into another problem: there are multiple frameworks available,
each of which can be based on different numerical algorithms. Here, we are
concerned with one particular NISQ architecture – the D-Wave annealer. The
behavior of this machine can be simulated using a tensor network approach [2,
3], dynamical system approach [4], neural networks [5] and, for sufficiently
small problem sizes, through a brute-force approach [6].

The downside of this multitude of options is that the implementations of each
of these approaches have incompatible input/output APIs. In this work, we
introduce the omnisolver package which, provides an extensible, unified API
for Ising spin-glass solvers and the actual D-Wave annealer.

##  2 Software description

Describe the software in as much as is necessary to establish a vocabulary
needed to explain its impact.

###  2.1 Software Architecture

Omnisolver is built in a modular fashion and comprises the following elements:

  * 1.

main Omnisolver framework,

  * 2.

plugins providing samplers built on top of dimod library [7].

The framework handles input/output operations, including parsing command line
arguments, reading an input problem file, and outputting solutions computed by
samplers. It can be extended via plugin system built using pluggy [8] library.
The plugins are responsible for implementing algorithms solving Binary
Quadratic Models and providing descriptions of available parameters. Figure 1
demonstrates the relationship between the main framework and plugins, as well
as the typical execution flow of the solver. The plugin definition comprises:

  * 1.

name of the plugin,

  * 2.

the create_sampler function used to construct new sampler instances,

  * 3.

the populate_parser callback used for defining command line arguments used for
creating sampler and running its sample method.

  * 4.

init_args and sample_args determining which command line arguments should be
passed respectively to sampler’s initializer and sample method.

Omnisolver extensions should provide one or more callables decorated with
omnisolver.plugin.plugin_impl returning an instance of Plugin class.

Figure 1: Omnisolver’s architecture diagram

###  2.2 Software Functionalities

The major functionality of the omnisolver project is providing a framework for
implementing arbitrary solvers of classical Ising spin–glasses. To this end,
the core omnisolver package provides:

  * 1.

plugin system for registering solvers inheriting from dimod.Sampler,

  * 2.

helper functions for implementing most typical plugins which remove the burden
of writing plugin boilerplate from the end–user,

  * 3.

input/output system automatically wired to the plugins. Currently, this allows
reading spin–glass instances from coordinate format and writing solutions as a
comma separated value (CSV) file,

  * 4.

dynamically generated command line interface (CLI). The CLI takes into account
information provided by the registered plugins, and hence is able to correctly
recognize parameters that need to be passed to each solver.

Apart from the core omnisolver package, we also implemented several plugins,
including:

  * 1.

omnisolver-pt providing implementation of parallel-tempering algorithm,
available at https://github.com/euro-hpc-pl/omnisolver-pt

  * 2.

omnisolver-bruteforce providing implementation of the exhaustive search which
can optionally be accelerated using CUDA–enabled GPU, available at
https://github.com/euro-hpc-pl/omnisolver-bruteforce.

###  2.3 Sample code snippets analysis

Code snippets in this section demonstrate an example implementation of an
omnisolver plugin, providing a dummy solver returning random solutions. While
this example is clearly artificial, it should be easy for the reader to extend
it to an implementation of an arbitrary nontrivial solver. The plugin is
implemented as a Python package called dummysolver. The layout of the package
is shown in the Listing 1, and the Fig. 2 summarizes relationship between
package’s essential components.

⬇

+-- dummysolver

| |-- dummy.yml

| |-- __init__.py

| +-- solver.py

|-- MANIFEST.in

|-- setup.cfg

+-- setup.py

Listing 1: Directory structure of dummy omnisolver plugin Figure 2:
Omnisolver’s plugin architecture diagram

The dummysolver/solver.py file, presented in Listing 2, contains the actual
implementation of the solver. The DummySolver class inherits from
dimod.Sampler and provides implementation of its abstract sample method. This
method accepts an instance of dimod.BinaryQuadraticModel (required by the base
class’ sample method) and an additional keyword parameter num_solutions
indicating how many solutions should be returned.

⬇

import dimod

import random

class DummySolver(dimod.Sampler):

"""A dummy sampler returning random solutions for given
BinaryQuadraticModel."""

@property

def parameters(self):

"""Parameters accepted by this sampler."""

return {"num_solutions": []}

@property

def properties(self):

"""Properties of this sampler."""

return {}

def sample(self, bqm, **parameters):

"""Uniformly sample given BQM."""

num_samples = parameters.pop("num_solutions", 1)

assert (

not parameters

), f"Unrecognized parameters: {parameters}"

possible_values = tuple(bqm.vartype.value)

solutions = [

[

random.choice(possible_values)

for _ in range(bqm.num_variables)

]

for _ in range(num_samples)

]

return dimod.SampleSet.from_samples_bqm(

solutions, bqm

).aggregate()

Listing 2: dummysolver/solver.py

To inform omnisolver’s plugin system about DummySolver, one needs to provide
information about solver’s class, displayed name, parameters accepted by the
solver and their command line counterparts. The easiest way to achieve this is
by providing the information in the YAML file, as exemplified by Listing 3.

⬇

schema_version: 1

name: "dummy"

sampler_class: "dummysolver.solver.DummySolver"

description: "Uniformly random dummy sampler"

init_args: []

sample_args:

- name: "num_solutions"

help: "number of sampled solutions"

type: int

default: 1

Listing 3: dummysolver/dummy.yml

One also needs to define the plugin’s entrypoint, which in this case is
located in the package’s initialization file (Listing 4). Here, we used
omnisolver’s convenience function plugin_from_specification for building the
plugin from the definition read from the YAML file. Finally, the entrypoint
has to be defined in the package’s setup file (Listing 5) to be picked up by
the plugin system.

⬇

from omnisolver.plugin import (

plugin_from_specification,

plugin_impl,

)

from pkg_resources import resource_stream

from yaml import safe_load

@plugin_impl

def get_plugin():

"""Construct plugin from given yaml file."""

specification = safe_load(

resource_stream("dummysolver", "dummy.yml")

)

return plugin_from_specification(specification)

Listing 4: dummysolver/__init__.py

⬇

[metadata]

name = dummysolver

description = Dummy solver plugin for omnisolver

[options]

packages = dummysolver

python_requires = >= 3.7

install_requires =

omnisolver >= 0.0.1

include_package_data = True

[options.package_data]

dummysolver = "dummysolver.yml"

[options.entry_points]

omnisolver =

dummy = dummysolver

Listing 5: setup.cfg

##  3 Illustrative Examples

Examples in this section assume that omnisolver, omnisolver-pt and dummysolver
(presented in Subsection 2.3) are installed in the current Python environment.

The available solvers can be displayed by running omnisolver -h, as
exemplified in Listing 6

⬇

usage: omnisolver [-h] {pt,dummy,random} ...

optional arguments:

-h, \--help show this help message and exit

Solvers:

{pt,dummy,random}

Listing 6: Example of running omnisolver -h

Help for the specific solver can be obtained by running omnisolver <solver-
name> -h. Listing 7 shows an example output of running command omnisolver pt
-h.

⬇

usage: omnisolver pt [-h] [--output OUTPUT] [--vartype {SPIN,BINARY}]
[--num_replicas NUM_REPLICAS] [--num_pt_steps NUM_PT_STEPS] [--num_sweeps
NUM_SWEEPS] [--beta_min BETA_MIN] [--beta_max BETA_MAX] input

Parallel tempering sampler

positional arguments:

input Path of the input BQM file in COO format. If not specified, stdin is
used.

optional arguments:

-h, \--help show this help message and exit

\--output OUTPUT Path of the output file. If not specified, stdout is used.

\--vartype {SPIN,BINARY}

Variable type

\--num_replicas NUM_REPLICAS

number of replicas to simulate (default 10)

\--num_pt_steps NUM_PT_STEPS

number of parallel tempering steps

\--num_sweeps NUM_SWEEPS

number of Monte Carlo sweeps per parallel tempering step

\--beta_min BETA_MIN inverse temperature of the hottest replica

\--beta_max BETA_MAX inverse temperature of the coldest replica

Listing 7: Specific help message for the omnisolver-pt plugin

Finally, let us demonstrate solving an instance of the Ising spin-glass using
a chosen solver. To this end, let us assume that the instance file
instance.txt as presented in Listing 8 is present in the current directory.
Running omnisolver pt instance.txt --vartype=SPIN yields result similar to the
one presented in Listing 9.

⬇

1 2 1.5

0 1 -1

0 2 -3

Listing 8: Example file with an instance of Ising spin-glass

⬇

0,1,2,energy,num_occurrences

1,-1,1,-3.5,1

Listing 9: Example output of running omnisolver on specific Ising spin-glass

##  4 Impact

This software has two main contributions. Firstly, it provides a unified
framework for implementing Ising or QUBO solvers. As such, it should
accelerate process of implementing new algorithms, saving the developers the
time needed for writing code handling CLI and input/output system. For the
researchers, common CLI and input/output interface should make it easier to
interchangeably use a variety of solvers, thus decreasing time needed for
preparing and running experiments. In particular, this will mainly benefit
entities that face combinatorial optimization problems in their daily routine,
such as railway companies. As an example of such application, we refer an
interested reader to the works [9, 10].

Secondly, Omnisolver provides new, faster implementation of the brute-force
algorithm utilizing Gray’s codes. As such, it allows us to find exact low-
energy spectrum for larger (up to 64 variables) problems, similar in size to
the largest cliques embeddable on present-day D-Wave hardware.

##  5 Conclusions

We provide the community interested in quantum computing with a tool which
provides an extensible framework allowing for communication with various
computational backends. These can include various numerical solvers to these
instances as well as actual quantum computing devices, such as the D-Wave
annealer.

During the development of our future solver backends, we will provide
accompanying plugins for omnisolver in order to provide a unified input/output
interface. The broader community is also encouraged to provide their own
implementations when coming up with interesting approaches to solving Ising
instances.

##  6 Conflict of Interest

No conflict of interest exists: We wish to confirm that there are no known
conflicts of interest associated with this publication and there has been no
significant financial support for this work that could have influenced its
outcome.

## Acknowledgements

This work was supported by the Foundation for Polish under the TEAM-NET
programme.

## References

  * [1] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2 (2018) 79.  doi:10.22331/q-2018-08-06-79.
URL https://doi.org/10.22331/q-2018-08-06-79

  * [2] U. Schollwöck, The density-matrix renormalization group in the age of matrix product states, Annals of physics 326 (1) (2011) 96–192.
  * [3] R. Orús, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics 349 (2014) 117–158.
  * [4] E. S. Tiunov, A. E. Ulanov, A. Lvovsky, Annealing by simulating the coherent ising machine, Optics express 27 (7) (2019) 10288–10295.
  * [5] D. Wu, L. Wang, P. Zhang, Solving statistical mechanics using variational autoregressive networks, Physical review letters 122 (8) (2019) 080602.
  * [6] K. Jałowiecki, M. M. Rams, B. Gardas, Brute-forcing spin-glass problems with cuda, Computer Physics Communications 260 (2021) 107728.
  * [7] D-Wave Systems Inc., dimod.
URL https://github.com/dwavesystems/dimod

  * [8] H. Krekel, pluggy - a minimalist production ready plugin system.
URL https://github.com/pytest-dev/pluggy

  * [9] K. Domino, M. Koniorczyk, K. Krawiec, K. Jałowiecki, B. Gardas, Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines, arXiv preprint arXiv:2010.08227 (2020).
  * [10] K. Domino, M. Koniorczyk, K. Krawiec, K. Jałowiecki, S. Deffner, B. Gardas, Quantum annealing in the nisq era: railway conflict management, arXiv preprint arXiv:2112.03674 (2021).