The "Factoring" Jupyter example for bigger numbers

• 

  Tanvi M  (Report)

  November 11, 2020 02:05 (Edited November 11, 2020 02:10)

  Hello,

  Here is a paper that goes over the exact same problem: Factoring the integer 143:
  https://www.dwavesys.com/media/l0tjzis2/14-1002a_b_tr_boosting_integer_factorization_via_quantum_annealing_offsets.pdf

  I was able to achieve the results(a =11 and b = 13) by following this paper: using 4 bits for a, b and 8 bits for p.

  csp = dbc.factories.multiplication_circuit(4)

  p_vars = ['p0', 'p1', 'p2', 'p3', 'p4', 'p5','p6','p7']
  
  # Convert P from decimal to binary
  fixed_variables = dict(zip(reversed(p_vars), "{:08b}".format(P)))

  Good eye on catching the to_base_ten() function changes. One thing that I noticed is you might have forgot to change the embedding. The given demo uses FixedEmbeddingComposite() by defining the embedding in helpers.embedding. You can either define the embedding manually or use EmbeddingComposite() as follows:

  from dwave.system import EmbeddingComposite
  
  sampler_embedding = EmbeddingComposite(sampler)
  

  Also, here is a notebook that you might find useful:
  https://cloud.dwavesys.com/learning/user/tmittal_40dwavesys_2ecom/notebooks/leap/demos/factoring/01-factoring-overview.ipynb

  Please let us know if you have any further questions or concerns.

  0

  Comment actions Permalink
• 

  Develop D  (Report)

  November 19, 2020 03:01

  Thanks for the information. But, I am afraid it does not help my case. Let me clarify what I want to achieve.

   

  I am evaluating the capabilities of the D-Wave API and I want to know how much I can achieve by using the D-Wave API alone. I can easily accomplish factoring 143 into 11 and 13 by using an 8-bit circuit, thanks to the D-Wave API find_embedding function. I am not using helpers.embedding and I don't need to follow the paper because the find_embedding function is smart enough to give me all I need. (I suspect your API may have already captured the wisdom in that paper.)

   

  Here is the code based on an 8-bit circuit and a 16-bit circuit. I know the 8-bit circuit works perfectly, but that is not the only goal I want to achieve. The 16-bit circuit does not work at all. I want you to tell me what goes wrong. My goal is to understand the correct approach to reach a very large circuit, say, 2048 bits.

   

  # 8-bit circuit
  # Perfect. Thank you.
  
  from dwave.system import FixedEmbeddingComposite
  from minorminer import find_embedding
  from dwavebinarycsp import dwavebinarycsp
  from dwave.system.samplers import DWaveSampler
  
  csp = dwavebinarycsp.factories.multiplication_circuit(4)
  bqm = dwavebinarycsp.stitch(csp, min_classical_gap=1)
  
  p_vars = ['p0', 'p1', 'p2', 'p3', 'p4', 'p5', 'p6', 'p7']
  
  P = 11*13
  fixed_variables = dict(zip(reversed(p_vars), "{:08b}".format(P)))
  fixed_variables = {var: int(x) for(var, x) in fixed_variables.items()}
  
  for var, value in fixed_variables.items():
      bqm.fix_variable(var, value)
  
  sampler = DWaveSampler(solver={'qpu': True})  
  sampler_fixed_embedding = FixedEmbeddingComposite(sampler, find_embedding(bqm.quadratic, sampler.edgelist))
  sampleset = sampler_fixed_embedding.sample(bqm, num_reads=1000)
  s = sampleset.first.sample
  
  print('a in binary =', s['a3'], s['a2'], s['a1'], s['a0'])
  print('b in binary =', s['b3'], s['b2'], s['b1'], s['b0'])

   

  # 16-bit circuit
  # It does not work at all. Please help!
  
  from dwave.system import FixedEmbeddingComposite
  from minorminer import find_embedding
  from dwavebinarycsp import dwavebinarycsp
  from dwave.system.samplers import DWaveSampler
  
  csp = dwavebinarycsp.factories.multiplication_circuit(8)
  bqm = dwavebinarycsp.stitch(csp, min_classical_gap=1)
  
  p_vars = ['p0', 'p1', 'p2', 'p3', 'p4', 'p5', 'p6', 'p7', 'p8', 'p9', 'p10', 'p11', 'p12', 'p13', 'p14', 'p15']
  
  P = 11*13
  fixed_variables = dict(zip(reversed(p_vars), "{:016b}".format(P)))
  fixed_variables = {var: int(x) for(var, x) in fixed_variables.items()}
  
  for var, value in fixed_variables.items():
  bqm.fix_variable(var, value)
  
  sampler = DWaveSampler(solver={'qpu': True}) 
  sampler_fixed_embedding = FixedEmbeddingComposite(sampler, find_embedding(bqm.quadratic, sampler.edgelist))
  sampleset = sampler_fixed_embedding.sample(bqm, num_reads=1000)
  s = sampleset.first.sample
  
  print('a in binary =', s['a7'], s['a6'], s['a5'], s['a4'], s['a3'], s['a2'], s['a1'], s['a0'])
  print('b in binary =', s['b7'], s['b6'], s['b5'], s['b4'], s['b3'], s['b2'], s['b1'], s['b0'])
  
  

  0

  Comment actions Permalink
• 

  Joel G  (Report)

  November 20, 2020 14:51

  Hello Develop D, I did some exploring of running factoring problems on the D-Wave QPU, a few years ago, so I have a few thoughts which may help.

  We do not expect the D-Wave QPU to do very well beyond about 16 bits. I have factored numbers up to 2**16. Beyond that, the algebra becomes onerous (as you found), and it becomes hard for the D-Wave QPU to find the one solution amidst many others. Tanvi M alluded to one of the reasons for that: there is a huge range in the QUBO entries. Problems with huge range in QUBO entries (many orders of magnitude) tend not to do well.

  Please note that Shor's algorithm, showing the dramatic time performance, is for gate model quantum computers, which D-Wave isn't.

  Another note is to explore the use of hybrid solvers, instead of the QPU. I'll look at your example code to see how it does on LeapHybridSampler, for example. 

  If you're wanting to explore the power of the D-Wave QPU, I would suggest finding a different problem. I'll report back after I explore the code a little more, and of course Tanvi M may have more thoughts.

  0

  Comment actions Permalink
• 

  Develop D  (Report)

  November 25, 2020 06:57

  Thanks, Joel.

  Your information has improved my understanding of the subject. I have explored some other problems. It is amazing the D-Wave computers are able to solve a 128 variable problem in 0.03 seconds!

  Keep up with the good work!

  0

  Comment actions Permalink

Please sign in to leave a comment.