Problem stitching underconstrained CSP
Hello, I have encountered an issue building a BQM from a simple CSP. In the following code, the stitching hangs in a factory of the
penaltymodel. Is there a way to fix or avoid the problem? Thanks
import dwavebinarycsp
csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
def any(a, b, c, d, e):
return a or b or c or d or e
csp.add_constraint(any, ['a','b','c','d','e'])
bqm = dwavebinarycsp.stitch(csp)
Comments
Hi Igor,
There are a couple of complicating factors with this problem.
With the addition of each variable, the BQM becomes more complex.
Having 5 variables means that we are generating a 5-dimensional energy landscape model, which needs to be converted to a BQM.
In the stitch function, the problem is being translated from classical logic to a representation that the Quantum Processor (QPU) can recognize, namely an Ising model.
Building a BQM from a set of CSPs (Constraint Satisfaction Problems) is not a trivial task, so it can take time in cases with a larger number of variables per constraint.
I was able to run the stitch function on any(a,b,c,d,e), on a computer with 16GB of RAM, but it did take about 12 minutes.
Once this BQM has been generated, it will be cached, so it won't need to be recalculated.
This means that subsequent calls to the stitch function for this logical formula will be very quick.
Another issue is that the solution space of any(a,b,c,d,e) is quite large.
Looking at the following truth table, you can see that there is a large number of valid solutions. (There are 31 of them, 2 ** 5 minus the all-zero solution)
a
b
c
d
e
a or b or c or d or e
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
...
1
1
1
1
0
1
1
1
1
1
1
1
All of the rows that have a 1 in the last column are valid solutions that need to be incorporated in the Ising model that will be sent to the QPU.
Restricting the solution space to fewer target logical states will simplify the model generation.
The more complex that a given constraint is, the more time it will take to generate the BQM.
Replacing a complex constraint with several simpler constraints, with fewer variables each, will result in faster BQM generation.
This is because it reduces the overall complexity.
In addition, each of these constraints will be cached, so they will run faster when being used in generating other BQM models.
Here is a simple solution to the problem:
import dwavebinarycsp csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY) def four_or(a,b,c,d): return a or b or c or d def if_a_then_one_or_more_of_bc(a,b,c): return not(a and not(b) and not(c) or (not a and (b or c))) csp.add_constraint(four_or, ['a','b','c','de']) csp.add_constraint(if_a_then_one_or_more_of_bc, ['de','d','e']) b=csp.check({'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'de': 0}) print(b) bqm = dwavebinarycsp.stitch(csp)I hope this was helpful in understanding why an underconstrained CSP would cause the stitch function to take time to run.
When I run that code, it completes fine. What OS and Python version are you using?
Thanks for your answer. Possibly I wasn't patient enough, it indeed completes in about 2 hours, using Python 3.7.1 64-bit on Windows. Did you observe a more reasonable runtime?
I ran the code on a 2012 MacBook Pro laptop with 8GB of memory. Here is the result:
Edit:
Per Dave's comment, it seems very likely that this run time was a result of a cached result.
Thanks for the comparison. It still takes 17 min on my MacBook (16GB, 2015), but it's not that important, I'll try anyway to use less convoluted constraints for the sake of getting a solution from the QPU. With one less variable, it already takes just 2 seconds.
Sidenote: While manually compiling the SDK (as described here) to check if makes a difference (it does not), I got the error
Networkx may need to be added to the dependencies of the module.
David, wow, that's very instructive! Introducing an auxiliary variable is a smart idea, very inspiring. I wonder how the QPU reacts to this changes, I have just learned that less variables does not necessarily mean a simpler problem to solve.
So you bring up a few good points.
When formulating the problem there are some tradeoffs we need to consider.
The reason that more variables helps to facilitate this problem is that the BQM is being generated using classical computing resources.
Generating the penalty models for each constraint satisfaction problem then becomes the bottleneck, so making each CSP simpler will speed up this step.
Once all of the penalty models have been generated, combining them into a single model is a relatively quick step.
The model with auxiliary variables will have an affect on the QPU, as we are introducing some chaining variables to allow for the problem to be broken down into smaller pieces.
Increasing the chain length also has its limitations, as the influence of the first qubit on the last in a very long chain is weakened.
Please sign in to leave a comment.