small example requires many many samples for valid solution #57

The attached program solves the max-cut graph problem by creating a circuit of 14 variables (3 full adders and 1 half adder) to see if a cut of size k exists. For cutSize=2, it takes anywhere from 817K samples to 17M samples to find a valid answer. Given that solving it randomly would require on average only 2^14 ~= 16K samples, this seems excessive.

Expected Behavior
When run as
$ python maxCut_csp.py
you will see output like
cutSize=0
cutSize=1
cutSize=2
nSamples=0, gathering 10000 more
nSamples=10000, gathering 10000 more
nSamples=20000, gathering 10000 more
[...]
nSamples=16990000, gathering 10000 more
nSamples=17000000, gathering 10000 more
valid sample=[('A', 0), ('AB', 1), ('AC', 1), ('B', 1), ('BC', 0), ('BD', 0), ('C', 1), ('C0', 1), ('C1', 0), ('C2', 0), ('CE', 0), ('D', 1), ('DE', 0), ('E', 1), ('S0', 0), ('S1', 0), ('aux0', 1), ('aux1', 1), ('aux10', 1), ('aux11', 1), ('aux12', 1), ('aux13', 1), ('aux2', 0), ('aux3', 0), ('aux4', 1), ('aux5', 1), ('aux6', 1), ('aux7', 1), ('aux8', 1), ('aux9', 0)]
result=[('A', 0), ('AB', 1), ('AC', 1), ('B', 1), ('BC', 0), ('BD', 0), ('C', 1), ('C0', 1), ('C1', 0), ('C2', 0), ('CE', 0), ('D', 1), ('DE', 0), ('E', 1), ('S0', 0), ('S1', 0), ('aux0', 1), ('aux1', 1), ('aux10', 1), ('aux11', 1), ('aux12', 1), ('aux13', 1), ('aux2', 0), ('aux3', 0), ('aux4', 1), ('aux5', 1), ('aux6', 1), ('aux7', 1), ('aux8', 1), ('aux9', 0)]
cutSize=3
nSamples=0, gathering 10000 more
nSamples=10000, gathering 10000 more

Source file
maxCut_csp.py.gz

Environment

• OS: [macOS HighSierra / Darwin Kernel 17.7.0]
• Python version: [Anaconda 2.7.14]