D-Wave Instance Generator (D-WIG)

The D-WIG toolset is used to generate binary quadratic programs based on a specific D-Wave QPU. A key motivation for generating problems on a specific QPU is that these problems do not require an embedding step to test them on the hardware. The D-WIG problem generator assumes that the QPU has a chimera topology.

dwig.py is the primary entry point and generats B-QP instances in the bqpjson format.

The remainder of this documentation assumes that,

1. You have access to a D-Wave QPU and the SAPI binaries
2. You are familiar with the D-Wave Qubist interface
3. You are using a bash terminal

Installation

The D-WIG toolset requires dwave-sapi2 and bqpjson to run and pytest for testing. To install these requirements first make sure that the dwave-sapi2 library is installed by running,

python <path to sapi>/install.py

Then the remaining dependencies can be installed via,

pip install -r requirements.txt

The installation can be tested by running,

./test.it

Introduction

Basic Usage

The primary entry point of the D-WIG toolset is dwig.py this script is used to generate a variety of B-QP problems, which have been studied in the literature. For example, the following command will generate a RAN1 problem for a full yield QPU of chimera degree 12 and send it to standard output,

./dwig.py ran

Bash stream redirection can be used to save the standard output to a file, for example,

./dwig.py ran > ran1.json

The ran1.json file is a json document in the bqpjson format. A detailed description of this format can be found in the bqpjson python package.

A helpful feature of D-WIG is to reduce the size of the QPU that you are working with. The chimera degree argument -cd n can be used to reduce D-WIG's view of the full QPU to a smaller n-by-n QPU. For example try,

./dwig.py -cd 2 ran

A detailed list of all command line options can be viewed via,

./dwig.py --help

Problem Types

The D-Wig toolset currently supports three types of problem generation,

1. const - fields are couplers are set to a given constant value
2. ran - fields are couplers are set uniformly at random
3. fl - frustrated loops
4. wscn - weak-strong cluster networks

A detailed list of command line options for each problem type can be viewed via,

./dwig.py <problem type> --help

See the doc strings inside of generator.py for additional documentation on each of these problem types.

Connecting to a QPU

Without any connection details, D-WIG will assume a full yield QPU of chimera degree 12. Connection details are required to build B-QPs from a specific QPU. The simplest way to add connection details is via the following command line arguments,

./dwig.py 
    -url <d-wave endpoint url>
    -token <sapi token>
    -solver <solver name>
    ran

Alternatively, a _config file can be placed in the D-WIG directory of the following form,

{
    "dw_url":"<d-wave endpoint url>",
    "dw_token":"<sapi token>",
    "dw_solver_name":"<solver name>"
}

The configuration file is a json document that can be use to set default values for all command line parameters.

Viewing a B-QP

The Qubist Solver Visualization tool is helpful in understanding complex B-QP datasets. To that end, the bqp2qh.py script converts a B-QP problem into the Qubist Hamiltonian format so that it can be viewed in the Solver Visualization tool. For example, the following command will generate a 2-by-2 RAN1 problem in the qubist format and then print it to standard output,

./dwig.py -cd 2 ran | bqp2qh

To view this problem paste the terminal output into the Data tab of the Qubist Solver Visualization tool.

Spin vs Boolean Variables

The B-QP format supports problems with spin variables (i.e. {-1,1}) and boolean variables (i.e. {0,1}). However, the D-WIG toolset generates problems only using spin variables. The spin2bool.py tool can be used to make the transformation after the problem is generated. For example, the following command will generate 2-by-2 RAN1 problem and convert it to a boolean variable space,

./dwig.py -cd 1 ran | spin2bool -pp

The QUBO Format

The QUBO format is supported by a variety of the tools provided by D-Wave, such as qbsolv, aqc, and toq. The bqp2qubo.py tool can be combined with the spin2bool.py tool to convert D-WIG cases into the qubo format. For example, the following command will generate 2-by-2 RAN1 problem and convert it to the QUBO format,

./dwig.py -cd 1 ran | spin2bool | bqp2qubo

Acknowledgments

This code has been developed as part of the Advanced Network Science Initiative at Los Alamos National Laboratory. The primary developer is Carleton Coffrin.

The D-WIG development team would like to thank Denny Dahl for suggesting the D-WIG name. Special thanks are given to these works, which provided significant inspiration for the D-WIG toolset.

For the RAN-pr formulation,

@article{Zdeborova2016statistical,
  author = {Lenka Zdeborova and Florent Krzakala},
  title = {Statistical physics of inference: thresholds and algorithms},
  journal = {Advances in Physics},
  volume = {65},
  number = {5},
  pages = {453-552},
  year = {2016},
  doi = {10.1080/00018732.2016.1211393},
  URL = {http://dx.doi.org/10.1080/00018732.2016.1211393}
}

For the RAN-k formulation,

@article{king2015benchmarking,
  title={Benchmarking a quantum annealing processor with the time-to-target metric},
  author={King, James and Yarkoni, Sheir and Nevisi, Mayssam M and Hilton, Jeremy P and McGeoch, Catherine C},
  journal={arXiv preprint arXiv:1508.05087},
  year={2015}
}

For the FL-k formulation,

@article{king2015performance,
  title={Performance of a quantum annealer on range-limited constraint satisfaction problems},
  author={King, Andrew D and Lanting, Trevor and Harris, Richard},
  journal={arXiv preprint arXiv:1502.02098},
  year={2015}
}

For the FCL-k formulation,

@article{king2017quantum,
  title={Quantum Annealing amid Local Ruggedness and Global Frustration},
  author={King, James and Yarkoni, Sheir and Raymond, Jack and Ozfidan, Isil and King, Andrew D and Nevisi, Mayssam Mohammadi and Hilton, Jeremy P, and McGeoch, Catherine C},
  journal={arXiv preprint arXiv:1701.04579},
  year={2017}
}

For the weak-strong cluster network formulation,

@article{denchev2016computational,
  title={What is the Computational Value of Finite-Range Tunneling?},
  author={Denchev, Vasil S and Boixo, Sergio and Isakov, Sergei V and Ding, Nan and Babbush, Ryan and Smelyanskiy, Vadim and Martinis, John and Neven, Hartmut},
  journal={Physical Review X},
  volume={6},
  number={3},
  pages={031015},
  year={2016},
  publisher={APS}
}

License

D-WIG is provided under a BSD-ish license with a "modifications must be indicated" clause. See the LICENSE.md file for the full text. This package is part of the Hybrid Quantum-Classical Computing suite, known internally as LA-CC-16-032.