.. _not:
================
Boolean NOT Gate
================
This example solves a simple problem of a Boolean NOT gate to demonstrate the mathematical formulation
of a problem as a :term:`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
====================
.. include:: hybrid_solver_service.rst
:start-after: example-requirements-start-marker
:end-before: example-requirements-end-marker
Solution Steps
==============
.. include:: hybrid_solver_service.rst
:start-after: example-steps-start-marker
:end-before: example-steps-end-marker
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 :term:`sampler` like the D-Wave system to solve binary quadratic models (BQM)\ [#]_\:
given :math:`M` variables :math:`x_1,...,x_N`, where each variable :math:`x_i` can
have binary values :math:`0` or :math:`1`, the system tries to find assignments of values
that minimize
.. math::
\sum_i^N q_ix_i + \sum_{i`
for more information about formulating problems as QUBOs.
Solve the Problem by Sampling
=============================
Now solve on a D-Wave system using sampler :class:`~dwave.system.samplers.DWaveSampler`
from Ocean software's :doc:`dwave-system `. Also use
its :class:`~dwave.system.composites.EmbeddingComposite` composite to map the
unstructured problem (variables such as :math:`x_2` etc.) to the sampler's graph structure
(the QPU's numerically indexed qubits) in a process known as :term:`minor-embedding`.
The next code sets up a D-Wave system as the sampler.
.. include:: min_vertex.rst
:start-after: default-config-start-marker
:end-before: default-config-end-marker
>>> 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) # 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 :ref:`oceanstack`\ , Ocean tools moved the original problem through the
following layers:
* The sampler API is a :term:`QUBO` formulation of the problem.
* The sampler is :class:`~dwave.system.samplers.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 :math:`\mathbf{z}` is the corresponding
output values; column **Valid?** shows whether the variables represent a valid state
for a NOT gate; column :math:`\mathbf{P}` shows the value of the penalty for all
possible assignments of variables.
.. table:: Boolean NOT Operation Represented by a Penalty Function.
:name: BooleanNOTAsPenalty
=========== =================== ========== ===================
**x** :math:`\mathbf{z}` **Valid?** :math:`\mathbf{P}`
=========== =================== ========== ===================
:math:`0` :math:`1` Yes :math:`0`
:math:`1` :math:`0` Yes :math:`0`
:math:`0` :math:`0` No :math:`1`
:math:`1` :math:`1` No :math:`1`
=========== =================== ========== ===================
For example, the state :math:`x, z=0,1` of the first row represents
valid assignments, and the value of :math:`P` is
.. math::
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 :math:`x,
z=0,0` of the third row represents an invalid assignment, and the
value of :math:`P` is
.. math::
2xz-x-z+1 = 2 \times 0 \times 0 -0 -0 +1 =1,
adding a value of :math:`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.