# Boolean NOT Gate¶

This example solves a simple problem of a Boolean NOT gate to demonstrate the mathematical formulation of a problem as a binary quadratic model (BQM) and using Ocean tools to solve such problems on a D-Wave system. Other examples demonstrate the more advanced steps that are typically needed for solving actual problems.

## Example Requirements¶

To run the code in this example, the following is required.

- The requisite information for problem submission through SAPI, as described in Configuring Access to D-Wave Solvers
- Ocean tools dwave-system and dimod.

If you installed dwave-ocean-sdk
and ran `dwave setup`

, your installation should meet these requirements.
In D-Wave’s Leap IDE, the default workspace
meets these requirements.

## Solution Steps¶

Section How a D-Wave System Solves Problems describes the process of solving problems on the quantum computer in two steps: (1) Formulate the problem as a binary quadratic model (BQM) and (2) Solve the BQM with a D-wave system or classical sampler. In this example, we mathematically formulate the BQM and use Ocean tools to solve it on a D-Wave system.

## Formulate the NOT Gate as a BQM¶

We use a sampler like the D-Wave systems to solve binary quadratic models (BQM)[1]: given \(M\) variables \(x_1,...,x_N\), where each variable \(x_i\) can have binary values \(0\) or \(1\), the system tries to find assignments of values that minimize

where \(q_i\) and \(q_{i,j}\) are configurable (linear and quadratic) coefficients. To formulate a problem for the D-Wave system is to program \(q_i\) and \(q_{i,j}\) so that assignments of \(x_1,...,x_N\) also represent solutions to the problem.

[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. |

Ocean tools can automate the representation of logic gates as a BQM, as demonstrated in the Multiple-Gate Circuit example.

### Representing the Problem With a Penalty Function¶

This example demonstrates a mathematical formulation of the BQM. We can represent a NOT gate, \(z \Leftrightarrow \neg x\), where \(x\) is the gate’s input and \(z\) its output, using a penalty function:

This penalty function represents the NOT gate in that for assignments of variables that match valid states of the gate, the function evaluates at a lower value than assignments that would be invalid for the gate. Therefore, when the D-Wave minimizes a BQM based on this penalty function, it finds those assignments of variables that match valid gate states.

The table below shows that this function penalizes states
that are not valid for the gate while no penalty is applied to assignments of
variables that correctly represent a NOT gate. In this table, column **x** is all
possible states of the gate’s input; column \(\mathbf{z}\) is the corresponding
output values; column **Valid?** shows whether the variables represent a valid state
for a NOT gate; column \(\mathbf{P}\) shows the value of the penalty for all
possible assignments of variables.

x |
\(\mathbf{z}\) | Valid? |
\(\mathbf{P}\) |
---|---|---|---|

\(0\) | \(1\) | Yes | \(0\) |

\(1\) | \(0\) | Yes | \(0\) |

\(0\) | \(0\) | No | \(1\) |

\(1\) | \(1\) | No | \(1\) |

For example, the state \(x, z=0,1\) of the first row represents valid assignments, and the value of \(P\) is

not penalizing the valid assignment of variables. In contrast, the state \(x, z=0,0\) of the third row represents an invalid assignment, and the value of \(P\) is

adding a value of \(1\) to the BQM being minimized. By penalizing both possible assignments of variables that represent invalid states of a NOT gate, the BQM based on this penalty function has minimal values (lowest energy states) for variable values that also represent a NOT gate.

See the system documentation for more information about penalty functions in general, and penalty functions for representing Boolean operations.

### Formulating the Problem as a QUBO¶

Sometimes penalty functions are of cubic or higher degree and must be reformulated as quadratic to be mapped to a binary quadratic model. For this penalty function we just need to drop the freestanding constant: the function’s values are simply shifted by \(-1\) but still those representing valid states of the NOT gate are lower than those representing invalid states. The remaining terms of the penalty function,

are easily reordered in standard QUBO formulation:

where \(z=x_2\) is the NOT gate’s output, \(x=x_1\) the input, linear coefficients are \(q_1=q_2=-1\), and quadratic coefficient is \(q_{1,2}=2\). These are the coefficients used to program a D-Wave system.

Often it is convenient to format the coefficients as an upper-triangular matrix:

See the system documentation for more information about formulating problems as QUBOs.

## Solve the Problem by Sampling¶

We now solve on a D-Wave system using sampler *DWaveSampler()* from Ocean software’s
dwave-system. We also use
its *EmbeddingComposite()* composite to map our unstructured problem (variables
such as `time`

etc.) to the sampler’s graph structure (the QPU’s numerically
indexed qubits) in a process known as minor-embedding.

The next code sets up a D-Wave system as the sampler.

Note

The code below sets a sampler without specifying SAPI parameters. Configure a default solver as described in Configuring Access to D-Wave Solvers to run the code as is, or see dwave-cloud-client to access a particular solver by setting explicit parameters in your code or environment variables.

```
>>> from dwave.system import DWaveSampler, EmbeddingComposite
>>> sampler = EmbeddingComposite(DWaveSampler())
```

Because the sampled solution is probabilistic, returned solutions may differ between runs. Typically, when submitting a problem to the system, we ask for many samples, not just one. This way, we see multiple “best” answers and reduce the probability of settling on a suboptimal answer. Below, we ask for 5000 samples.

```
>>> Q = {('x', 'x'): -1, ('x', 'z'): 2, ('z', 'x'): 0, ('z', 'z'): -1}
>>> sampleset = sampler.sample_qubo(Q, num_reads=5000)
>>> print(sampleset) # doctest: +SKIP
x z energy num_oc. chain_.
0 0 1 -1.0 2266 0.0
1 1 0 -1.0 2732 0.0
2 0 0 0.0 1 0.0
3 1 1 0.0 1 0.0
['BINARY', 4 rows, 5000 samples, 2 variables]
```

Almost all the returned samples represent valid value assignments for a NOT gate, and minima (low-energy states) of the BQM, and with high likelihood the best (lowest- energy) samples satisfy the NOT gate formulation:

```
>>> sampleset.first.sample["x"] != sampleset.first.sample["z"]
True
```

## Summary¶

In the terminology of Ocean Software Stack, Ocean tools moved the original problem through the following layers:

- The sampler API is a QUBO formulation of the problem.
- The sampler is
*DWaveSampler()*. - The compute resource is a D-Wave system.