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 Using a D-Wave System
Ocean tools dwave-system and dimod.

If you installed dwave-ocean-sdk and ran dwave config create, your installation should meet these requirements.

Solution Steps¶

Section Solving Problems on a D-Wave System 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

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

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

A NOT gate.

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:

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

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.

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,

\[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}\]

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

In the code below, replace sampler parameters in the third line. If you configured a default solver, as described in Using a D-Wave System, you should be able to set the sampler without parameters as sampler = EmbeddingComposite(DWaveSampler()). You can see this information by running dwave config inspect in your terminal.

>>> from dwave.system.samplers import DWaveSampler
>>> from dwave.system.composites import EmbeddingComposite
>>> sampler = EmbeddingComposite(DWaveSampler(endpoint='https://URL_to_my_D-Wave_system/', token='ABC-123456789012345678901234567890', solver='My_D-Wave_Solver'))

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}
>>> response = sampler.sample_qubo(Q, num_reads=5000)
>>> for datum in response.data(['sample', 'energy', 'num_occurrences']):   
...    print(datum.sample, "Energy: ", datum.energy, "Occurrences: ", datum.num_occurrences)
...
{'x': 0, 'z': 1} Energy:  -1.0 Occurrences:  2062
{'x': 1, 'z': 0} Energy:  -1.0 Occurrences:  2937
{'x': 1, 'z': 1} Energy:  0.0 Occurrences:  1

Almost all the returned samples represent valid value assignments for a NOT gate, and minimize (are low-energy states of) the BQM.

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.