Formulation: Objectives and Models#

For quantum computing, as for classical, solving a problem requires that it be formulated in a way the computer and its software understand.

For example, if you want your laptop to calculate the area of a $1 coin, you might express the problem as an equation, \(A=\pi r^2\), that you program as math.pi*13.245**2 in your Python terminal. For a laptop with Python software, this formulation—a particular string of alphanumeric symbols—causes the manipulation of bits in a CPU and memory chips that produces the correct result.

Objective Functions#

With quantum computing, you express your problem in a form that enables solution by minimization: an objective function, which is a mathematical expression of the energy of a system. If you are solving your problem on a D-Wave quantum computer, for example, the system is the qubits of a quantum processing unit (QPU) and your objective function represents the states of the qubits as binary variables, and the physical biases and couplings applied to these qubits as, respectively, linear and quadratic coefficients. By formulating an objective function such that lowest energy states represent good solutions to your problem, you can solve your problem by minimizing the objective function. In the case of a D-Wave quantum computer, the QPU uses quantum annealing to seek the minimum of the energy landscape for its qubits with the biases and couplings applied by your objective function; for hybrid quantum-classical algorithms, some parts of the objective function are minimized using classical heuristics and some by the QPU.

As an illustrative example, consider the equation \(x+1=2\). You can solve by minimization an equivalent objective function, \(\min_x[2-(x+1)]^2\), formulated by taking the square of the subtraction of one side from another. Minimization seeks the shortest distance between the sides, which occurs at equality (with the square eliminating negative distance).

There are many ways of mapping between a problem—chains of amino acids forming 3D structures of folded proteins, traffic in the streets of Beijing, circuits of binary gates—and an objective function to be solved (by sampling) with a D-Wave system, a hybrid solver, or locally on your CPU. The Getting Started examples given here show some simple objective functions to help you begin using Ocean tools.

For more detailed information on objective functions, how D-Wave quantum computers minimize objective functions, and techniques for reformulating problems as objective functions, see the System Documentation or the training content on the D-Wave website.

For code examples that formulate models for various problems, see D-Wave’s examples repo and many example customer applications on the D-Wave website.

Supported Models#

Ocean supports various models to express your problem as an objective function and submit to samplers for solution:

  • Binary Quadratic Models are unconstrained and have binary variables.

    BQMs are typically used for applications that optimize over decisions that could either be true (or yes) or false (no); for example, should an antenna transmit, or did a network node experience failure?

    Constraints for this model are typically represented by adding penalty models to the objective.

  • Constrained Quadratic Models can be constrained and have real, integer and binary variables.

    CQMs are typically used for applications that optimize problems that might include integer and/or binary variables and one or more constraints.

    Constraints for this model are represented natively.

  • Discrete Quadratic Models are unconstrained and have discrete variables.

    DQMs are typically used for applications that optimize over several distinct options; for example, which shift should employee X work, or should the state on a map be colored red, blue, green or yellow?

    Constraints for this model are typically represented by adding penalty models to the objective.

  • Nonlinear Models can be constrained and have different types of variables.

    Nonlinear (NL) models are typically used for applications that optimize over decision variables that represent a common logic, such as subsets of choices or permutations of ordering; for example, which of \(X\) available shifts should be assigned to each of \(Y`\) employees, or in which order should a traveling salesperson visit a list of cities?

    Constraints for this model are represented natively, both explicitly and implicitly through the variable types.

Example: CQM for Greatest Rectangle Area#

Consider the simple problem of finding the rectangle with the greatest area when the perimeter is limited.

In this example, the perimeter of the rectangle is set to 8 (meaning the largest area is for the \(2X2\) square). A CQM is created with two integer variables, \(i, j\), representing the lengths of the rectangle’s sides, an objective function \(-i*j\), representing the rectangle’s area (the multiplication of side \(i\) by side \(j\), with a minus sign because Ocean samplers minimize rather than maximize), and a constraint \(2i + 2j <= 8\), requiring that the sum of both sides must not exceed the perimeter .

>>> from dimod import ConstrainedQuadraticModel, Integer
>>> i = Integer('i', upper_bound=4)
>>> j = Integer('j', upper_bound=4)
>>> cqm = ConstrainedQuadraticModel()
>>> cqm.set_objective(-i*j)
>>> cqm.add_constraint(2*i+2*j <= 8, "Max perimeter")
'Max perimeter'

Example: BQM for a Boolean Circuit#

Consider the problem of determining outputs of a Boolean logic circuit. In its original context (in “problem space”), the circuit might be described with input and output voltages, equations of its component resistors, transistors, etc, an equation of logic symbols, multiple or an aggregated truth table, and so on. You can choose to use Ocean software to formulate BQMs for binary gates directly in your code or mathematically formulate a BQM, and both can be done in various ways; for example, a BQM for each gate or one BQM for all the circuit’s gates.

The following are two example formulations.

  1. The Penalty Models section shows that a NOT gate, represented symbolically as \(x_2 \Leftrightarrow \neg x_1\), is formulated mathematically as BQM,

    \[-x_1 -x_2 + 2x_1x_2\]

  2. Ocean’s dimod tool enables the following formulation of an AND gate as a BQM:

>>> from dimod.generators import and_gate
>>> bqm = and_gate('in1', 'in2', 'out')

The BQM for this AND gate may look like this:

>>> bqm     
BinaryQuadraticModel({'in1': 0.0, 'in2': 0.0, 'out': 3.0},
...                  {('in2', 'in1'): 1.0, ('out', 'in1'): -2.0, ('out', 'in2'): -2.0},
...                  0.0,
...                  'BINARY')

The members of the two dicts are linear and quadratic coefficients, respectively, the third term is a constant offset associated with the model, and the fourth shows the variable types in this model are binary.

For more detailed information on the parts of Ocean programming model and how they work together, see Ocean Software Stack.

Once you have a model that represents your problem, you sample it for solutions. Sampling: Minimizing the Objective explains how to submit your problem for solution.