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

The code in this example requires that your development environment have Ocean software and be configured to access SAPI, as described in the Initial Set Up section.

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 model and (2) Solve your model 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.

A NOT gate.

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

See the D-Wave Problem-Solving Handbook for more information about formulating problems as QUBOs.

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:

• The sampler API is a QUBO formulation of the problem.

• The sampler is DWaveSampler.

• The compute resource is a D-Wave system.

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