Introduction

About this Document

This guide steps users through the process of developing a model suitable for the D-Wave quantum processing unit (QPU) or hybrid solvers. By reading through this guide and working through the provided exercises, a new user with little to no prior experience with D-Wave technology will able to model small problems using the binary quadratic model (BQM).

Example Problems

When working with the D-Wave systems and software, we need to formulate our problem as a binary quadratic model, or BQM. We can formulate many classes of problems as BQMs, such as optimization problems. We can view an optimization problem in terms of objectives and constraints. An objective is something that we want to minimize or maximize, while constraints are rules about which solutions are acceptable. As we explore how to formulate our problems as binary quadratic models, we will use this terminology frequently.

Below are two examples of optimization problems that can be formulated as BQMs and run using the D-Wave QPU or our hybrid solvers. These examples provided demonstrate how real world problems can be broken down into objectives and constraints. While these examples are more complex than those that we will develop in this guide, the same strategy and techniques can help to build a BQM for each of them. For the interested reader we provide links to where more information on the BQM formulation for each example can be found.

Example 1: Traveling Salesman Problem

A well-known problem in computer science is the traveling salesman problem (TSP). In this problem, we have a list of cities that must be visited (exactly once) on a sales person’s route. The sales person would like to take the shortest route possible. We can phrase this problem in terms of objectives and constraints.

Objective:
Minimize the total distance for the route.
Constraint:
Visit each city exactly once.

For more information on how to formulate this problem as a BQM, check out Andrew Lucas’s paper on Ising formulations [1] .

Example 2: Antenna Placement Problem

We have a set of 10 antennas that we can place anywhere in a list of 100 locations. We want to cover as much geographic area as possible. However, some locations interfere with each other. Where should we build our antennas?

Objective:
Maximize coverage.
Constraints:
  • Build at most 10 antennas.
  • Choose locations that do not cause interference.

For more information on how to formulate this problem as a BQM, take a look at the antenna selection example in the Collection of Code Examples [2] .

Exercise

How can we split the following problem up into an objective and constraints?

A business is trying to figure out the best way to pack a box full of items. There are five items, with values 1, 5, 3, 4, and 2 dollars. These items have weights 2, 4, 4, 1, and 3 lbs, respectively. The contents of the box must weigh exactly 6 lbs. What is the best way to pack the box so that the box has the highest total value?

Other Resources

Many other resources are available for new users getting with D-Wave. Below is a selection of some that may be especially useful.

Ocean SDK Documentation: https://docs.ocean.dwavesys.com/

Collection of Code Examples: https://github.com/dwave-examples

D-Wave on YouTube: https://www.youtube.com/dwavesystems

[1]Lucas, Andrew. “Ising formulations of many NP problems.” Frontiers in Physics 2 (2014): 5.
[2]https://github.com/dwave-examples/antenna-selection