Pair-wise reduction

Hello,

Does Dwave implement Bor 2002 algorithm to reducce high dimension polynomials to pair-wise interaction? What is the tool to do that?

Thank you

0

Comments

6 comments
  • I'm unfamiliar with the Bor 2002 algorithm, but Ocean does have tools for working with polynomials. 

    https://docs.ocean.dwavesys.com/en/stable/docs_dimod/reference/higherorder.html

    https://docs.ocean.dwavesys.com/en/stable/docs_dimod/reference/sampler_composites/higher_order_composites.html

    Feel free to post a link to the specific algorithm you're looking for and we can get back to you with more detail. 

    Hope this helps!

    0
    Comment actions Permalink
  • Thanks Alexandra,

    I've looked at the links you sent. I don't know how the methods can reduce k-body to 2-body. Did they introduce ancillary qubits and penalty function? 

    The Bor 2002 algorithm I mentioned is:

    Bor2002]

    E. Boros and P. L. Hammer. “Pseudo-boolean optimization.” Discrete Appl. Math., 123, 155-225 2002. http://rutcor.rutgers.edu/~boros/Papers/2002-DAM-BH.pdf.

    The algorithm is mentioned in the docs of Dwave:

    https://docs.dwavesys.com/docs/latest/handbook_reformulating.html

    0
    Comment actions Permalink
  • Thanks for linking the paper and document you were looking at. 

    The make_quadratic function in the Higher-Order Models tool can be used to reduce a polynomial of degree k to a quadratic model. The implementation uses ancillary variables and penalty models. It's a modification of the method outlined in the Bor 2002 algorithm.This is described in the last paragraph of https://docs.dwavesys.com/docs/latest/handbook_reformulating.html#non-quadratic-higher-degree-polynomials

    Here's an example of how it works.

    Let's say you have the following polynomial and call make_quadratic on it

    # pseudo code
    p = -a + b - ab - 2abc + bcd

    # This is how you would make the function call
    poly = {(0,): -1, (1,): 1, (2,): 1.5, (3,): 1, (0, 1): -1, (0, 1, 2): -2, (1, 2, 3): 1}

    bqm = make_quadratic(poly, strength=5.0, dimod.BINARY)

    To reduce the terms with degree 3 to quadratic terms the algorithm looks for variables common to both higher order terms and defines

    x = bc

    Then it uses the 'strength' input (also called the penalty weight) to craft a penalty function:

    P = 5(bc - 2(b + c)x + 3x)

    By replacing 'bc' products in the higher order terms with x and adding the penalty function we get the quadratic polynomial:

    BQM = -a + b + 15x - ab - 2ax + 5bc - 10bx - 10cx + dx

     

    0
    Comment actions Permalink
  • Dear Alexandra,

    Thank you very much for your reply. It solves my problem! Without you provide me the link, I even do not know about the existence of the links. But how can I find out all the sub-content of the website https://docs.ocean.dwavesys.com.. The link "make_quadratic" you sent me is not listed on the homepage.

    Thank you. Best regards,

    0
    Comment actions Permalink
  • I'm glad that helped!

    I will admit that it can be difficult to become familiar with the Ocean documentation. I would suggest using the search bar on the top left hand side. For example, to find information about your question I searched for 'higher order'. This was the first page that came up and if you scroll to the bottom you'll see the make_quadratic function. A big challenge can be knowing what to search for. 

    I also want to point out how to get to the source code. Whenever you're on the main page for a class or function you'll see the 'source' link in green, like the one shown below. 

    Feel free to reach out if you can't find what you're looking for. We're happy to help! 

    0
    Comment actions Permalink
  • I see. Thank you very much for sharing the tip to search for information! It is interesting to know that a user can get the source code also!

     

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post