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

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 Workflow Steps: Formulation and Sampling describes the problem-solving workflow as consisting of two main steps: (1) Formulate the problem as an objective function in a supported form of quadratic model (QM) and (2) Solve your QM with a D-Wave solver.

This example mathematically formulates the BQM and uses Ocean tools to solve it on a D-Wave quantum computer.

## Formulate the NOT Gate as a BQM¶

You use a sampler like the D-Wave system to solve binary quadratic models (BQM)2: 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

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

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.

2

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. As shown in Penalty Models, you can represent a NOT gate, $$z \Leftrightarrow \neg x$$, where $$x$$ is the gate’s input and $$z$$ its output, using a penalty function:

$2xz-x-z+1.$

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.1 Therefore, when the D-Wave system minimizes a BQM based on this penalty function, it finds those assignments of variables that match valid gate states.

### 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 you 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,

$2xz-x-z,$

are easily reordered in standard QUBO formulation:

$-x_1 -x_2 + 2x_1x_2$

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:

$\begin{split}Q = \begin{bmatrix} -1 & 2 \\ 0 & -1 \end{bmatrix}\end{split}$

## Solve the Problem by Sampling¶

Now solve on a D-Wave system using sampler DWaveSampler from Ocean software’s dwave-system. Also use its EmbeddingComposite composite to map the unstructured problem (variables such as $$x_2$$ 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 Leap’s 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, you ask for many samples, not just one. This way, you see multiple “best” answers and reduce the probability of settling on a suboptimal answer. Below, 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, label='SDK Examples - NOT Gate')
>>> print(sampleset)
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:

1

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.

Boolean NOT Operation Represented by a Penalty Function.

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

$2xz-x-z+1 = 2 \times 0 \times 1 - 0 - 1 + 1 = -1+1=0,$

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

$2xz-x-z+1 = 2 \times 0 \times 0 -0 -0 +1 =1,$

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.