# The "Factoring" Jupyter example for bigger numbers

I refer to this example

I change the circuit to 8 in order to factor a bigger number such as 143.

csp = dbc.factories.multiplication_circuit(8)

Of course, I change the other lines accordingly.

p_vars = ['p0', 'p1', 'p2', 'p3', 'p4', 'p5','p6','p7','p8','p9','p10','p11','p12','p13','p14','p15']

fixed_variables = dict(zip(reversed(p_vars), "{:016b}".format(P)))

Also, I change the to_base_ten function.

It runs without any exceptions and it does give some results, but it never gives the correct result 11 * 13.

Could you please show me how to achieve big number factoring?

Since the D-Wave quantum computers have thousands of qubits already, I assume they should be able to factor much bigger numbers than 15, 21, etc.

What is the biggest number that has been factored?

• Hello,

Here is a paper that goes over the exact same problem: Factoring the integer 143:
https://www.dwavesys.com/sites/default/files/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.

• 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})
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

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})
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'])

• 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.

• 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!