Could you please point me to an implementation of Formulation A in the factoring example?

• 

  Luca W  (Report)

  December 07, 2018 18:37 (Edited December 07, 2018 18:38)

  Hello Sadhana,

  Formulation A is provided in the Factoring Jupyter Notebook is an intuitive way of solving the factoring problem P = ab. In the case of factoring integers, this approach becomes very complex and resource-heavy, so a better approach involving AND gates (Formulation B) is presented in more detail.

  If you're interested in trying out more general polynomial minimization problems, the general instructions provided in the Factoring Jupyter Notebook will work:

  1. state equation as a minimization
  2. represent integers as binary numbers
  3. reduce to quadratic

  For step (3), you can use the dimod function make_quadratic. If you are interested in seeing how this works, see the documentation on reducing polynomial order. 

  After this step, you can use a D-Wave sampler to embed the BQM and run on the QPU (or a classical solver). 

  0

  Comment actions Permalink
• 

  Sadhana S  (Report)

  December 11, 2018 13:35

  I am not able to understand how a polynomial is supposed to fed to the make_quadratic function. From what I saw in the tests, {(0,): .5, tuple(): 1.3} is basically 0.5*x +1.3. Is this correct?

  If the polynomial I am considering is

  

  what would the dictionary look like?

  Thank you so much for your help.

  0

  Comment actions Permalink
• 

  Luca W  (Report)

  December 11, 2018 22:32

  Hello Sadhana, 

  There are a few key points to consider if you want to minimize a polynomial with a Binary Quadratic Model (BQM):

  1. A BQM is Binary, so all your variables must evaluate to 1 or 0. The polynomial you provided above is alright as long as x and y are binary variables. Otherwise, you can expand integers to binary variables through the process described in Formulation A of the factoring notebook (e.g. x = x_0 + 2*x_1 + 4*x_2 + ...)
  2. Since we are only trying to determine the values of your variables for which the polynomial is minimized, we can ignore the constant (variable "e" in your polynomial example above). This is necessary because BQMs do not have zero-order terms. 
  3. As mentioned in the factoring notebook, you can simplify the polynomial using the property of binary variables that x^2 = x. 

  Once your polynomial is in this format, you can use the dimod tool make_quadratic to reduce your polynomial to quadratic. The syntax you wrote above is correct except (following point #2 about zero-order terms) you can leave out the constant "1.3" term.

  Following the steps above, the direct coding of your polynomial (assuming x and y are already binary variables) would be:

  poly = {(0,): (a+d), (1,): (c+d), (0,1): b}

  Note that this polynomial is already quadratic so there would be no need to pass it through make_quadratic. 

  0

  Comment actions Permalink
• 

  Sadhana S  (Report)

  December 12, 2018 10:15

  Thank you so much

  0

  Comment actions Permalink
• 

  Luca W  (Report)

  December 12, 2018 17:25

  No problem Sadhana, I realize there is a lot of background information to take in. Please do share your progress, I'm sure your project will be interesting and helpful to other users as well.

  0

  Comment actions Permalink

Please sign in to leave a comment.