intro.rst

Introduction

For quantum computing, as for classical, the first step in solving a problem is to express it in a mathematical formulation compatible with the underlying physical hardware.

Native Formulations for D-Wave Systems

D-Wave systems solve problems that can be mapped onto an Ising model or a quadratic unconstrained binary optimization (QUBO) problem.

$$\text{Ising:} \qquad E(\pmb{s}|\pmb{h},\pmb{J}) = \left\{ \sum_{i=1}^N h_i s_i + \sum_{i<j}^N J_{i,j} s_i s_j \right\} \qquad\qquad s_i\in\{-1,+1\}$$

is an objective function of N variables s = [s₁, ..., s_N] corresponding to physical Ising spins, where h_i are the biases and J_i, j the couplings between spins.

QUBO:  E(x|Q)

= sum{ile j}^N x_i Q{i,j} x_j qquadqquad x_iin {0,1}

is an objective function of N binary variables represented as an upper-diagonal matrix Q, where diagonal terms are the linear coefficients and the nonzero off-diagonal terms the quadratic coefficients.

Objective functions can be represented by graphs, a collection of nodes (representing variables) and the connections between them (edges).

D-Wave Architecture: Chimera

To solve a QUBO or Ising objective function on the D-Wave system, you must map it to a Chimera graph that represents architecture of the system's qubits.

The Chimera architecture comprises sets of connected unit cells, each with four horizontal qubits connected to four vertical qubits via couplers (bipartite connectivity). Unit cells are tiled vertically and horizontally with adjacent qubits connected, creating a lattice of sparsely connected qubits. A unit cell is typically rendered as either a cross or a column.

Chimera unit cell.

A $3 {\rm x} 3$ Chimera graph, denoted C3. Qubits are arranged in 9 unit cells.

D-Wave NetworkX

D-Wave NetworkX provides tools for working with Chimera graphs and implementations of graph-theory algorithms on the D-Wave system and other binary quadratic model samplers; for example, functions such as draw_chimera() provide easy visualization for Chimera graphs; functions such as maximum_cut() or min_vertex_cover() provide graph algorithms useful to optimization problems that fit well with the D-Wave system.

Like the D-Wave system, all other supported samplers (a process that samples from low energy states of the problem's objective function) must have sample_qubo and sample_ising methods for solving Ising and QUBO models and return an iterable of samples in order of increasing energy. You can set a default sampler using the set_default_sampler() function.

Below you can see how to create Chimera graphs implemented in the D-Wave 2X and D-Wave 2000Q systems:

import dwave_networkx as dnx

# D-Wave 2X
C = dnx.chimera_graph(12, 12, 4)

# D-Wave 2000Q
C = dnx.chimera_graph(16, 16, 4)