Incorrect QUBOs from large combinations of And, Or, and Not

[spakin]

Describe the bug

I'm trying to represent a truth table as a QUBO by penalizing all combinations of variables that do not correspond to a truth-table row. For example, I represent the row

1 1 0

as

And(x0, And(x1, Not(x2)))

and the row

0 1 0

as

And(Not(x0), And(x1, Not(x2)))

I then penalize all rows that are Not the first row Or the second row:

Not(Or(And(x0, And(x1, Not(x2))),
       And(Not(x0), And(x1, Not(x2)))))

When I pass PyQUBO-compiled versions of such expressions to dimod.ExactSolver I expect to see the original truth table in the lowest-valued energy states. I usually do, especially for smaller truth tables, but I don't always.

To Reproduce

The following code—let's call it bad-pyqubo.py—reproduces the problem:

#! /usr/bin/env python

import pyqubo
import dimod

# This example works.
good = [[0, 0, 0, 0, 0],
        [0, 0, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [0, 1, 1, 1, 1],
        [1, 0, 0, 0, 0],
        [1, 0, 1, 1, 0],
        [1, 1, 0, 0, 1],
        [1, 1, 1, 1, 1]]

# This example doesn't work.
bad = [[0, 0, 0, 0, 1, 1],
       [0, 0, 0, 1, 0, 1],
       [0, 0, 0, 1, 1, 0],
       [0, 0, 1, 0, 0, 1],
       [0, 0, 1, 0, 1, 0],
       [0, 0, 1, 1, 0, 0],
       [0, 1, 0, 0, 0, 1],
       [0, 1, 0, 0, 1, 0],
       [0, 1, 0, 1, 0, 0],
       [0, 1, 1, 0, 0, 0],
       [1, 0, 0, 0, 0, 1],
       [1, 0, 0, 0, 1, 0],
       [1, 0, 0, 1, 0, 0],
       [1, 0, 1, 0, 0, 0],
       [1, 1, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1]]

# Construct a PyQUBO expression.
pattern = bad   # Edit this line to contrast "good" and "bad".
nc = len(pattern[0])
vars = [pyqubo.Binary('x%d' % c) for c in range(nc)]
rows = []
for row in pattern:
    cexps = []
    for c, bit in enumerate(row):
        if bit == 1:
            cexps.append(vars[c])
        else:
            cexps.append(pyqubo.Not(vars[c]))
    rows.append(pyqubo.reduce(pyqubo.And, cexps[1:], cexps[0]))
expr = pyqubo.Not(pyqubo.reduce(pyqubo.Or, rows[1:], rows[0]))

# Minimize the QUBO and output the result.
model = expr.compile()
qubo = model.to_qubo()[0]
sampleset = dimod.ExactSolver().sample_qubo(qubo)
for d in sampleset.data():
    bits = [str(d.sample[v]) for v in model.variables]
    print('%s  %s  -->  %.1f' % \
          (' '.join(bits[:nc]),
           ' '.join(bits[nc:]),
           d.energy))

First, change pattern = bad to pattern = good in line 35 and run bad-pyqubo.py | head -16. You should see the rows of the good truth table, possibly permuted, in the lowest eight energy states:

$ ./bad-pyqubo.py | head -16
0 0 0 0 0  0 0 0 0 0  -->  0.0
0 1 0 1 0  0 0 0 0 0  -->  0.0
1 1 0 0 1  1 0 1 1 1  -->  0.0
1 1 1 1 1  1 1 1 1 1  -->  0.0
0 1 1 1 1  0 1 0 1 0  -->  0.0
0 0 1 0 1  0 0 0 0 0  -->  0.0
1 0 1 1 0  0 1 0 0 0  -->  0.0
1 0 0 0 0  0 0 0 0 0  -->  0.0
1 0 1 0 0  0 0 0 0 0  -->  1.0
0 0 1 0 0  0 0 0 0 0  -->  1.0
0 1 0 0 0  0 0 0 0 0  -->  1.0
0 0 1 1 0  0 1 0 0 0  -->  1.0
1 1 1 0 1  1 0 1 1 1  -->  1.0
0 1 1 0 0  0 0 0 0 0  -->  1.0
1 0 1 1 1  0 1 1 0 0  -->  1.0
0 1 0 0 1  0 0 0 1 0  -->  1.0

(The first set of columns represent the truth table. The second set of columns are ancillary product terms introduced by PyQUBO.)

This is correct output. But now revert pattern = good to pattern = bad and run the script again:

$ ./bad-pyqubo.py | head -16
1 1 1 1 0 0  1 1 1 1 1 0 1 1 0 0 0 1  -->  -18.0
0 1 1 1 0 0  0 1 1 1 1 0 1 1 0 0 0 1  -->  -14.0
1 1 1 0 0 0  1 0 1 1 1 0 1 1 0 0 0 1  -->  -14.0
1 0 1 1 0 0  0 1 1 1 1 0 1 1 0 0 0 1  -->  -14.0
1 1 0 1 0 0  1 0 1 1 1 0 1 1 0 0 0 1  -->  -14.0
1 0 1 1 0 0  0 1 1 1 1 0 1 0 0 0 0 1  -->  -12.0
1 0 1 1 0 0  0 1 1 1 1 0 0 1 0 0 0 1  -->  -12.0
0 1 1 1 0 0  0 1 1 0 1 0 1 1 0 0 0 1  -->  -12.0
1 1 0 1 0 0  1 0 1 1 1 0 0 1 0 0 0 1  -->  -12.0
1 1 0 0 0 0  1 0 1 1 1 0 1 1 0 0 0 1  -->  -12.0
0 1 1 1 0 0  0 1 1 1 0 0 1 1 0 0 0 1  -->  -12.0
1 1 0 1 0 0  1 0 1 0 1 0 1 1 0 0 0 1  -->  -12.0
0 0 1 1 0 0  0 1 1 1 1 0 1 1 0 0 0 1  -->  -12.0
1 1 1 0 0 0  1 0 1 1 0 0 1 1 0 0 0 1  -->  -12.0
1 1 1 0 0 0  1 0 1 1 1 0 1 0 0 0 0 1  -->  -12.0
1 0 1 1 0 0  1 1 1 1 1 0 1 1 0 0 0 1  -->  -11.0

Only one row lies at minimum energy, and it is not even a row that appears in the bad truth table. In fact, the output from this run of bad-pyqubo.py bears little resemblance at all to the truth table.

Expected behavior

I would expect bad-pyqubo.py to reproduce any truth table it is given, not just smaller/simpler truth tables.

I suspect that the program is related to #113, but I don't know for sure.