1. D-Wave Quantum Inc
  2. Community
  3. APIs

Handling Linear Constraints in Quantum and Hybrid Optimization Methods

Avatar
Jia-Cheng H
Follow

I have a long linear constraint in my optimization problem, expressed as a0x0+a1x1+⋯=c.

I am considering two approaches:

  1. A purely quantum method.
  2. A hybrid method.

If I use Binary Quadratic Models (BQM), I must adopt a quadratic penalty (… )^ to enforce the constraint. This leads to a large, fully connected graph, which hinders embedding and increases chain length. Consequently, this may result in poor performance.

  • Is there any other advanced method for handling linear constraints in BQM?

Alternatively, if I use the Constrained Quadratic Model (CQM) with the LeapHybridSampler method, how does CQM handle linear constraints?

  • Are the constraints handled during embedding, or does it use classical methods to enforce them?

On the other hand, if I customize my hybrid workflow using dwave-hybrid, is it possible to achieve better results compared to LeapHybridSampler?
Are there detailed documents or resources available for learning more about dwave-hybrid?

Thanks a lot!

0

Comments

2 comments
Sort by Date Votes
  • Avatar
    David J  (Report)

    Hello,

    To answer your questions:

    1. For specific constraints, better ways of enforcing them do exist, but in general the penalty model is the main method.
    2. Unfortunately all of our Hybrid samplers are proprietary so we can't comment on the way the CQMs are handled by the LeapHybridCQMSampler.
    3. In some cases it is possible to get better results with dwave-bydrid but in general HSS performs better.
    4. See our dwave-hybrid documentation for detailed information about the framework and how to use it. The Overview section has a nice introduction, the Using the Framework section gets into the use of the code, and the Developing New Components section describes how to create your own custom pieces of the pipeline.

    Hopefully this was helpful. Please let us know if you have any questions.

    0
    Comment actions Permalink
  • Avatar
    Jia-Cheng H  (Report)

    Indeed, the LeapHybridCQMSampler demonstrates good performance for most cases. However, I have the following additional questions about it:

    1. Does reweighting the coefficients in the constraint equation affect the performance of the results?

    For example:

    ( c_1x_1 + c_2x_2 + c_3x_3 = k
    ==>
    a(c_1x_1 + c_2x_2 + c_3x_3) = a(k) 

    2. Are there any guidelines for formulating problems to make them easier to solve using LeapHybridCQMSampler?

    For instance, if I have a constraint like:

    ( c_1x_1 + c_2x_2 + c_3x_3 = k ,

    I could reformulate the constraint by shifting terms, as follows:

    (c_1x_1 + c_2x_2 + c_3x_3) - a(x_1 + x_2 + x_3) = k - a .

    What value of  a  would lead to a better formulation for LeaphybridCQMSampler? 

     

    3. For large problems, the LeapHybridCQMSampler takes significant time to run. If the results are not satisfactory, is it possible to reload the problem or continue the calculation using `hybrid.state` or another method?

     

    4. I want to track how the energy changes over iterations, QPU time, or real time. How can I obtain energy changes as a time-dependent variable?

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post