Skip to content

Latest commit

 

History

History
executable file
·
134 lines (101 loc) · 6.19 KB

solving_problems.rst

File metadata and controls

executable file
·
134 lines (101 loc) · 6.19 KB
Raw

How a D-Wave System Solves Problems

This section explains some of the basics of how you can use D-Wave quantum computers to solve problems and how Ocean tools can help.

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 = πr2, that you program as math.pi*13.245**2 in your Python CLI. 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.

The D-Wave system uses a quantum processing unit (QPU) to solve a binary quadratic model (BQM)1: given N variables x1, ..., xN, where each variable xi can have binary values 0 or 1, the system finds assignments of values that minimize

$$\sum_i^N q_ix_i + \sum_{i<j}^N q_{i,j}x_i x_j$$

where qi and qi, j are configurable (linear and quadratic) coefficients. To formulate a problem for the D-Wave system is to program qi and qi, j so that assignments of x1, ..., xN also represent solutions to the problem.

Ocean software can abstract away much of the mathematics and programming for some types of problems. At its heart is a binary quadratic model (BQM) class that together with other Ocean tools helps formulate various optimization problems. It provides an API to binary quadratic samplers (the component used to minimize a BQM and therefore solve the original problem), such as the D-Wave system, Leap's hybrid quantum-classical solvers,and classical algorithms you can run on your computer2.

The following sections describe this problem-solving procedure in two steps (plus a third that may benefit some problems); see the gs Examples section and :stdSystem Documentation <sysdocs_gettingstarted:index> for further description.

  1. formulating_bqm.
  2. submitting.
  3. improving, if needed, using advanced features.

Solution steps: (1) a problem known in "problem space" (a circuit of Boolean gates, a graph, a network, etc) is formulated as a BQM, mathematically or using Ocean functionality and (2) the BQM is sampled for solutions.

Solution steps: (1) a problem known in "problem space" (a circuit of Boolean gates, a graph, a network, etc) is formulated as a BQM, mathematically or using Ocean functionality and (2) the BQM is sampled for solutions.

Formulate Your Problem for a Quantum Computer

There are different 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 a BQM (or DQM) to be solved (by sampling) with a D-Wave system, a hybrid solver, or locally on your CPU.

For example, 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 different ways too; for example, a BQM for each gate or one BQM for all the circuit's gates.

The following are two example formulations.

  1. The not example, takes a NOT gate represented symbolically as x2 ⇔ ¬x1 and formulates it mathematically as the following BQM:


     − x1 − x2 + 2x1x2

    The table below shows that this BQM has lower values for valid states of the NOT gate (e.g., x1 = 0, x2 = 1) and higher for invalid states (e.g., x1 = 0, x2 = 0).

    Boolean NOT Operation Formulated as a BQM.
    x1 x2 Valid? BQM Value
    0 1 Yes 0
    1 0 Yes 0
    0 0 No 1
    1 1 No 1
  2. Ocean's dwavebinarycsp </docs_binarycsp/sdk_index> tool enables the following formulation of an AND gate as a BQM:

>>> import dwavebinarycsp >>> import dwavebinarycsp.factories.constraint.gates as gates >>> csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY) >>> csp.add_constraint(gates.and_gate(['x1', 'x2', 'y1'])) # add an AND gate >>> bqm = dwavebinarycsp.stitch(csp)

The resultant BQM of this AND gate may look like this:

>>> bqm # doctest: +SKIP BinaryQuadraticModel({'x1': 0.0, 'x2': 0.0, 'y1': 6.0}, ... {('x2', 'x1'): 2.0, ('y1', 'x1'): -4.0, ('y1', 'x2'): -4.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 oceanstack.

Once you have a BQM (or DQM) that represents your problem, you sample it for solutions. samplers_and_solvers explains how to submit your problem for solution.

  1. The "native" forms of BQM programmed into a D-Wave system are the Ising model traditionally used in statistical mechanics and its computer-science equivalent, shown here, the QUBO.↩

  2. At a higher level of abstraction, it also provides a discrete quadratic model (DQM) class that can be used, for example, by the hybrid DQM samplers offered by Leap.↩