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

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

../_images/NOT.png

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.