# Multiple-Gate Circuit¶

This example solves a logic circuit problem to demonstrate using Ocean tools to solve a problem on a D-Wave system. It builds on the discussion in the Boolean AND Gate example about the effect of minor-embedding on performance.

## 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 dwavebinarycsp and dwave-system. For the optional graphics, you will also need Matplotlib.

If you installed dwave-ocean-sdk
and ran `dwave config create`

, your installation should meet these requirements.

## Formulating the Problem as a CSP¶

This example demonstrates two formulations of constraints from the problem’s logic gates:

Single comprehensive constraint:

import dwavebinarycsp def logic_circuit(a, b, c, d, z): not1 = not b or2 = b or c and3 = a and not1 or4 = or2 or d and5 = and3 and or4 not6 = not or4 or7 = and5 or not6 return (z == or7) csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY) csp.add_constraint(logic_circuit, ['a', 'b', 'c', 'd', 'z'])

Multiple small constraints:

import dwavebinarycsp import dwavebinarycsp.factories.constraint.gates as gates import operator csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY) csp.add_constraint(operator.ne, ['b', 'not1']) # add NOT 1 gate csp.add_constraint(gates.or_gate(['b', 'c', 'or2'])) # add OR 2 gate csp.add_constraint(gates.and_gate(['a', 'not1', 'and3'])) # add AND 3 gate csp.add_constraint(gates.or_gate(['d', 'or2', 'or4'])) # add OR 4 gate csp.add_constraint(gates.and_gate(['and3', 'or4', 'and5'])) # add AND 5 gate csp.add_constraint(operator.ne, ['or4', 'not6']) # add NOT 6 gate csp.add_constraint(gates.or_gate(['and5', 'not6', 'z'])) # add OR 7 gate

Note

dwavebinarycsp works best for constraints of up to 4 variables; it may not function as expected for constraints of over 8 variables.

The next line of code converts the constraints into a BQM that we solve by sampling.

```
# Convert the binary constraint satisfaction problem to a binary quadratic model
bqm = dwavebinarycsp.stitch(csp)
```

The first approach, which consolidates the circuit as a single constraint, yields a binary quadratic model with 7 variables: 4 inputs, 1, output, and 2 ancillary variables. The second approach, which creates a constraint satisfaction problem from multiple small constraints, yields a binary quadratic model with 11 variables: 4 inputs, 1 output, and 6 intermediate outputs of the logic gates.

You can see the binary quadratic models here: Multiple-Gate Circuit: Further Details.

## Minor-Embedding and Sampling¶

Algorithmic minor-embedding is heuristic—solution results vary significantly based on the minor-embedding found.

The next code sets up a D-Wave system as the sampler.

Note

In the code below, replace sampler parameters as needed. 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
# Set up a D-Wave system as the sampler
sampler = EmbeddingComposite(DWaveSampler(endpoint='https://URL_to_my_D-Wave_system/', token='ABC-123456789012345678901234567890', solver='My_D-Wave_Solver'))
```

Next, we ask for 1000 samples and separate those that satisfy the CSP from those that fail to do so.

```
response = sampler.sample(bqm, num_reads=1000)
# Check how many solutions meet the constraints (are valid)
valid, invalid, data = 0, 0, []
for datum in response.data(['sample', 'energy', 'num_occurrences']):
if (csp.check(datum.sample)):
valid = valid+datum.num_occurrences
for i in range(datum.num_occurrences):
data.append((datum.sample, datum.energy, '1'))
else:
invalid = invalid+datum.num_occurrences
for i in range(datum.num_occurrences):
data.append((datum.sample, datum.energy, '0'))
print(valid, invalid)
```

For the single constraint approach, 4 runs with their different minor-embeddings yield significantly varied results, as shown in the following table:

Embedding | (valid, invalid) |
---|---|

1 | (39, 961) |

2 | (1000, 0) |

3 | (998, 2) |

4 | (316, 684) |

You can see the minor-embeddings found here: Multiple-Gate Circuit: Further Details; below those embeddings are visualized graphically.

For the second approach, which creates a constraint satisfaction problem based on multiple small constraints, a larger number of variables (11 versus 7) need to be minor-embedded, resulting in worse performance. However, performance can be greatly improved in this case by increasing the chain strength (to 2 instead of the default of 1).

Embedding | Chain Strength | (valid, invalid) |
---|---|---|

1 | 1 | (7, 993) |

2 | 1 | (417, 583) |

3 | 2 | (941, 59) |

4 | 2 | (923, 77) |

You can see the minor-embeddings used here: Multiple-Gate Circuit: Further Details; below those embeddings are visualized graphically.

## Looking at the Results¶

You can verify the solution to the circuit problem by checking an arbitrary valid or invalid sample:

```
>>> print(next(response.samples()))
{'a': 1, 'c': 0, 'b': 0, 'not1': 1, 'd': 1, 'or4': 1, 'or2': 0, 'not6': 0,
'and5': 1, 'z': 1, 'and3': 1}
```

For the lowest-energy sample of the last run, found above, the inputs are \(a, b, c, d = 1, 0, 0, 1\) and the output is \(z=1\), which indeed matches the analytical solution for the circuit,

You can also plot the energies for valid and invalid samples. The example code above converted the constraint satisfaction problem to a binary quadratic model using the default minimum energy gap of 2. Therefore, each constraint violated by the solution increases the energy level of the binary quadratic model by at least 2 relative to ground energy.

```
>>> import matplotlib.pyplot as plt
>>> plt.ion()
>>> plt.scatter(range(len(data)), [x[1] for x in data], c=['y' if (x[2] == '1')
... else 'r' for x in data],marker='.')
>>> plt.xlabel('Sample')
>>> plt.ylabel('Energy')
```

You can see in the graph that valid solutions have energy -9.5 and invalid solutions energies of -7.5, -5.5, and -3.5.

```
>>> for datum in response.data(['sample', 'energy', 'num_occurrences', 'chain_break_fraction']):
... print(datum)
...
Sample(sample={'a': 1, 'c': 0, 'b': 1, 'not1': 0, 'd': 1, 'or4': 1, 'or2': 1, 'not6': 0, 'and5': 0, 'z': 0, 'and3': 0}, energy=-9.5, num_occurrences=13, chain_break_fraction=0.0)
Sample(sample={'a': 1, 'c': 1, 'b': 1, 'not1': 0, 'd': 0, 'or4': 1, 'or2': 1, 'not6': 0, 'and5': 0, 'z': 0, 'and3': 0}, energy=-9.5, num_occurrences=14, chain_break_fraction=0.0)
# Snipped this section for brevity
Sample(sample={'a': 1, 'c': 0, 'b': 0, 'not1': 1, 'd': 1, 'or4': 1, 'or2': 0, 'not6': 1, 'and5': 1, 'z': 1, 'and3': 1}, energy=-7.5, num_occurrences=3, chain_break_fraction=0.09090909090909091)
Sample(sample={'a': 1, 'c': 1, 'b': 0, 'not1': 1, 'd': 1, 'or4': 1, 'or2': 1, 'not6': 1, 'and5': 1, 'z': 1, 'and3': 1}, energy=-7.5, num_occurrences=1, chain_break_fraction=0.18181818181818182)
Sample(sample={'a': 1, 'c': 1, 'b': 1, 'not1': 1, 'd': 0, 'or4': 1, 'or2': 1, 'not6': 1, 'and5': 1, 'z': 1, 'and3': 1}, energy=-5.5, num_occurrences=4, chain_break_fraction=0.18181818181818182)
# Snipped this section for brevity
Sample(sample={'a': 1, 'c': 1, 'b': 1, 'not1': 1, 'd': 0, 'or4': 1, 'or2': 1, 'not6': 1, 'and5': 0, 'z': 1, 'and3': 1}, energy=-3.5, num_occurrences=1, chain_break_fraction=0.2727272727272727)
```

You can see, for example, that sample

```
Sample(sample={'a': 1, 'c': 1, 'b': 0, 'not1': 1, 'd': 1, 'or4': 1, 'or2': 1, 'not6': 1, 'and5': 1, 'z': 1, 'and3': 1}, energy=-7.5, num_occurrences=1, chain_break_fraction=0.18181818181818182)
```

has a higher energy by 2 than the ground energy. It is expected that this solution violates a single constraint, and you can see that it violates constraint

```
Constraint.from_configurations(frozenset([(1, 0, 0), (0, 1, 0), (0, 0, 0), (1, 1, 1)]), ('a', 'not1', 'and3'), Vartype.BINARY, name='AND')
```

on AND gate 3.

Note also that for samples with higher energy there tends to be an increasing fraction of broken chains: zero for the valid solutions but rising to almost 30% for solutions that have three broken constraints.