# Factoring program / embedding metrics

Starting with code from the factoring Jupyter notebook, I cobbled together a command-line Python + Ocean SDK factoring program.  It takes three command-line parameters -- product to be factored, number of bits in each multiplication circuit input, and number of QPU reads.  I ran 116 experiments on the D-Wave.  See table summarizing results below.

I tried factoring four products -- 12, 20, 36, and 81.  For each product I tried two multiplication circuit input bit sizes.  For each combination of product and bit size, I ran several experiments with 100, 200, 500, 1000, or 2000 QPU reads.  I wanted to get a feel for how results might vary with different embeddings found by minorminer and with different numbers of reads.

All expected valid factors of 12 were found easily using multiplication circuit inputs of 3 or 4 bits.

All expected valid factors of 20 were found using 4 or 5 bits.  It took thousands of QPU reads to find the factors using 5 bits.

All expected valid factors of 36 were found using 5 bits.  It took thousands of QPU reads.  No valid factors of 36 were found using 6 bits.

No valid factors of 81 were found using 6 or 7 bits.  One experiment failed because minorminer could not find an embedding.

Valid factors did not always have the lowest energies of the answers returned by the QPU.

Here is the table.

`prod:    product to be factoredbits:    number of bits in each input of           multiplication circuitreads:   number of reads from QPUexpno:   ordinal experiment number           (1st, 2nd, ... nth run with           given parameters)factors: valid factors foundenergy:  reported energy of solutionprod bits reads expno                    factors  energy12   3    100   1                     2,  6   -25.5                     4,  3   -25.5                     3,  4   -25.5                     6,  2   -25.512   3    100   2                     4,  3   -25.5                     3,  4   -25.5                     2,  6   -25.5                     6,  2   -25.512   3    200   1                     4,  3   -25.5                     6,  2   -25.5                     2,  6   -25.5                     3,  4   -25.512   3    200   2                     3,  4   -25.5                     2,  6   -25.5                     4,  3   -25.5                     6,  2   -25.512   3    500   1                     3,  4   -25.5                     4,  3   -25.5                     6,  2   -25.5                     2,  6   -25.512   3    500   2                     4,  3   -25.5                     6,  2   -25.5                     3,  4   -25.5                     2,  6   -25.512   3   1000   1                     3,  4   -25.5                     4,  3   -25.5                     2,  6   -25.5                     6,  2   -25.512   3   1000   2                     4,  3   -25.5                     6,  2   -25.5                     3,  4   -25.5                     2,  6   -25.512   3   1000   3                     2,  6   -25.5                     4,  3   -25.5                     6,  2   -25.5                     3,  4   -25.512   3   1000   4                     3,  4   -25.5                     4,  3   -25.5                     2,  6   -25.5                     6,  2   -25.512   4    100   112   4    100   2                     1, 12   -45.012   4    200   1                     4,  3   -48.0                    12,  1   -42.012   4    200   212   4    500   1                     3,  4   -45.0                     4,  3   -42.0                     6,  2   -39.012   4    500   2                     6,  2   -42.0                    12,  1   -40.012   4   1000   1                     2,  6   -48.0                     3,  4   -45.0                     6,  2   -41.012   4   1000   2                     6,  2   -44.012   4   1000   3                     2,  6   -43.012   4   1000   4                     2,  6   -45.0                     4,  3   -45.0                     3,  4   -43.0                     1, 12   -41.020   4    100   1                    10,  2   -45.0                     5,  4   -42.020   4    100   220   4    200   120   4    200   2                     5,  4   -45.020   4    500   1                     4,  5   -39.0                     2, 10   -37.020   4    500   220   4   1000   1                     5,  4   -40.020   4   1000   2                     4,  5   -46.0                     2, 10   -42.0                     5,  4   -41.0                    10,  2   -40.020   4   1000   3                     2, 10   -45.020   4   1000   4                     2, 10   -45.020   5    100   120   5    100   220   5    200   120   5    200   220   5    500   120   5    500   220   5   1000   120   5   1000   220   5   1000   320   5   1000   420   5   2000   120   5   2000   2                     5,  4   -61.520   5   2000   3                    10,  2   -69.520   5   2000   436   5    100   136   5    100   236   5    200   136   5    200   236   5    500   136   5    500   236   5   1000   136   5   1000   236   5   1000   336   5   1000   436   5   2000   136   5   2000   2                     3, 12   -58.5                    18,  2   -51.536   5   2000   336   5   2000   436   5   2000   536   5   2000   6                     6,  6   -68.5                     4,  9   -65.536   5   2000   736   5   2000   8                     3, 12   -57.5                     9,  4   -53.536   6    100   136   6    100   236   6    200   136   6    200   236   6    500   136   6    500   236   6   1000   136   6   1000   236   6   1000   336   6   1000   436   6   2000   136   6   2000   236   6   2000   336   6   2000   436   6   2000   536   6   2000   636   6   2000   736   6   2000   881   6    100   181   6    100   281   6    200   181   6    200   281   6    500   181   6    500   281   6   1000   181   6   1000   281   6   1000   381   6   1000   481   6   2000   181   6   2000   281   6   2000   381   6   2000   481   6   2000   581   6   2000   681   6   2000   781   6   2000   881   7    100   181   7    100   281   7    200   181   7    200   281   7    500   181   7    500   281   7   1000   181   7   1000   281   7   1000   381   7   1000   4                    No embedding found81   7   2000   181   7   2000   281   7   2000   381   7   2000   481   7   2000   581   7   2000   681   7   2000   781   7   2000   8`

• Thanks for posting this, Scott. Note even excited states may be "correct" answers as only a subset of the variables represent the factors sought.

• The factoring Jupyter notebook says:

"This example uses a pre-calculated minor-embedding. ... ... ... The stored embedding we used was selected for its good performance from many candidate embeddings generated by a heuristic algorithm from dwave-ocean-sdk called minorminer (GitHub repo). Alternatively, we can use this tool here to generate a new embedding that may or may not have as good performance. Here we will ask for more samples from the QPU by raising the num_reads parameter from 50 to 1000 to increase our chances of getting a correct answer."

I'm glad that the notebook didn't go too far down this rabbit hole, but now I want to know more.

How do you assess the quality of an embedding obtained from minorminer?  Is there any way to check its fitness by examining it?  Or do you just have to try it and see how well it works compared with other embeddings?

In the little experiment I reported on above, I called minorminer to obtain an embedding every time I submitted a factoring problem to the QPU.  I regret now that I didn't save the embeddings -- but I was just getting my feet wet.  I'm wondering whether I got a different embedding every time.

As a follow-up experiment, I think I'll do the following.  Obtain several embeddings from minorminer and store them or record their details.  For each embedding, submit the same set of factoring experiments to the QPU and record the results.  Tabulate and graph the results to attempt to discern which embedding works best.

Is this a good idea?

• The first two metrics I would use for embedding quality are maximum chain length and average chain length.

`max(len(chain) for chain in embedding.values())sum(len(chain) for chain in embedding.values()) / len(embedding)`

We care about maximum chain length because long chains 'break' more easily so it makes sense to minimize the longest chain.

Beyond that, assessing embedding quality is more than an art than a science. It is worth noting that chains do not necessarily behave like ideal qubits and their idiosyncrasies can affect the quality of the returned solutions. See

https://www.dwavesys.com/media/22zdsrbs/14-1020a-a_virtual_graphs_for_high_performance_embedded_topologies.pdf

https://www.dwavesys.com/media/l0tjzis2/14-1002a_b_tr_boosting_integer_factorization_via_quantum_annealing_offsets.pdf

for some examples/strategies.

In practice, one can obtain good results by simply trying a large number of embeddings and seeing which gives the best answer!

• Hi Alex,

Thank you very much!

In the little project I'm working on, I build 8 copies of a circuit, each with 16 inputs and 8 outputs, and chain them together.  I specify some or all of the 16 inputs to the first circuit, some or all of the 8 outputs from the last circuit, and leave some unfixed, then run the circuit forward, backward, or in both directions at once.

It's hard for minorminer to find an embedding for this circuit.  When minorminer succeeds in finding an embedding, sometimes the QPU finds valid solutions.

I'll try calling minorminer many times till I have a large collection of embeddings.  I'll rank the embeddings by their metrics, try the most promising ones, and see how well they do.

Scott

• Alex,

Thank you again for your guidance on metrics of embeddings.  Very helpful!

To others who may read this, I suggest using float() to calculate a double-precision value for average chain length.  Otherwise integer division is performed.

`float(sum(len(chain) for chain in embedding.values())) / float(len(embedding))`

Scott