QPU finds valid solutions running logic circuit forwards but not backwards

Hi all.

I'm using the D-Wave quantum computer to explore a set of constraint satisfaction problems expressed in terms of combinational logic.  I'm finding that when I fix the logic circuit inputs, the QPU finds valid output solutions easily, but when I fix the outputs, the QPU doesn't find any valid solutions for the inputs, and the energies of the (invalid) solutions are higher.  I'm wondering why and what I can do about it.

Within the last 24 hours I updated Linux with the latest patches, created a fresh virtual environment, and installed the latest D-Wave Ocean SDK.

My program gets a sampler using DWaveSampler(), creates a CSP using dwavebinarycsp.ConstraintSatisfactionProblem('BINARY'), constructs logic gates using dwavebinarycsp.factories.constraint.gates.or_gate(), .xor_gate(), et al, adds the gates to the CSP using add_constraint(), gets a binary quadratic model (BQM) using dwavebinarycsp.stitch(), fixes the known inputs/outputs using fix_variable(), and searches for embeddings using minorminer.find_embedding().  I pick an embedding with low max chain length and average chain length.  A separate program gets a sampler using DWaveSampler(), applies the chosen embedding to the problem to map it to the sampler using dwave.embedding.embed_bqm(), and gets answers from the QPU.  A third program checks the results for validity.

I've tinkered a bit with min_classical_gap and annealing_time but haven't found a silver bullet.

I'm considering adding redundant constraints to see whether that makes it harder or easier for the QPU to find valid solutions.  For example, I could use De Morgan's laws to find two different ways to express the desired truth table of the circuit and add both sets of logic gates to the CSP.

Does the order in which gates are added to the CSP matter?

Can anyone offer any suggestions?

Happy Valentine's Day, everyone!  It's at least an excuse to eat chocolates.

Scott D.

0

Comments

2 comments
  • Hello,

    Are you saying that the invalid solutions have higher energy than the valid ones?

    Sometimes the optimal solution won't be found on the first few runs.

    It's definitely a good idea to try to formulate the problem in a different way, as some problems do better with the physical nature of the QPU.

    What did you set the min_classical_gap to?

    You might also want to try out some different logic gates.

    One type of problem that is hard to formulate on the QPU at present without some consideration and strategy is the choose one problem.
    Most problems are not restricted solely to a single choose one problem, so the problem formulation ends up being efficient.

    Here is one example post where a user ran into this problem:
    https://support.dwavesys.com/hc/en-us/community/posts/360020801573-Problem-stitching-underconstrained-CSP

    An example where someone had some problems formulating an equivalent logical problem and getting good outputs might also be informative:
    https://support.dwavesys.com/hc/en-us/community/posts/360020802573-Map-coloring-with-2-bits-

    Something else that might be good to keep in mind too is the idea of breaking logic down into smaller penalty models in order to stitch them into a single BQM faster:
    https://support.dwavesys.com/hc/en-us/community/posts/360034439773-Stitching-take-ages-even-for-small-problems-How-to-scale-

    I hope this was somewhat informative.
    Please feel free to ask more questions or give us updates so we can try to help guide you in this process.

    Eventually, getting a little lower level and working directly with the QPU's graph structure, understanding embeddings, etc. can be very useful.

    1
    Comment actions Permalink
  • Hi David,

    Thank you for your quick reply.  I'm looking into the things you suggested.  I'll follow up soon and let you know what I find out.

    Scott D.

    1
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post