dwavesystems
small example requires many many samples for valid solution
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]
I agree; this is an insane number of samples. I tried running Steve's code on NASA's DW2000Q system and never even managed to run it to completion. The occasional brief network glitch between my site and NASA would cause Python to abort long before I made it through the millions of samples required.
— Scott
P.S. Being more robust to network glitches is probably another issue worth raising, but I'm not sure which dwavesystems repo is the right one to post it to. dwave-cloud-client perhaps?
