# Embedding

In the context of optimization, embedding refers to the process of mapping a binary quadratic model (BQM) or an Ising model onto the physical qubits of a processor, such as those provided by D-Wave or Hitachi systems.

This is necessary because the structure of the problem graph (source graph) often does not directly match the hardware graph (target graph) of the quantum processing unit (QPU).

Embedding ensures that each variable in the problem is represented by a chain of qubits, which collectively act as a single logical variable.

## Solvers

The following solvers support embedding:

## Minor Miner

We use the MinorMiner algorithm to find embeddings for problems on the platform. This algorithm is a heuristic method that attempts to find an embedding that minimizes the number of chains and the chain lengths.

## Example

`import strangeworks as sw`

from strangeworks_optimization import StrangeworksOptimizer

from strangeworks_optimization_models.parameter_models import EmbeddingParameterModel, DwaveSamplerParameterModel

from dimod import BinaryQuadraticModel

sw.authenticate('your-api-key')

linear = {1: -2, 2: -2, 3: -3, 4: -3, 5: -2}

quadratic = {(1, 2): 2, (1, 3): 2, (2, 4): 2, (3, 4): 2, (3, 5): 2, (4, 5): 2}

model = BinaryQuadraticModel(linear, quadratic, "BINARY")

embedding = EmbeddingParameterModel(

max_no_improvement=10,

random_seed=42,

timeout=1000,

max_beta=1.5,

tries=10,

inner_rounds=100,

chainlength_patience=10,

max_fill=63,

threads=4,

return_overlap=False,

)

options = DwaveSamplerParameterModel(embedding_parameters=embedding)

solver = "dwave.Advantage2_prototype2.3"

so = StrangeworksOptimizer(model=model,

solver=solver,

options=options)

sw_job = so.run()

## EmbeddingParameterModel

Parameter | Type | Default | Description |
---|---|---|---|

max_no_improvement | int | None | Maximum number of failed iterations to improve the current solution. Each iteration attempts to find an embedding for each variable such that it is adjacent to all its neighbours. |

random_seed | int | None | Seed for the random number generator. If set to None, the seed is initialized using os.random(). |

timeout | int | None | Maximum time (in seconds) before the algorithm gives up. |

max_beta | float | None | Qubits are assigned weight based on a formula (beta^n) where n is the number of chains containing that qubit. This value should be greater than 1. If None, max_beta is effectively infinite. |

tries | int | None | Number of restart attempts before the algorithm stops. A typical restart takes between 1 and 60 seconds. |

inner_rounds | int | None | Maximum number of iterations between restart attempts. If None, inner_rounds is effectively infinite. |

chainlength_patience | int | None | Maximum number of failed iterations to improve chain lengths in the current solution. |

max_fill | int | None | Restricts the number of chains that can simultaneously incorporate the same qubit during the search. Values above 63 are treated as 63. If None, max_fill is effectively infinite. |

threads | int | None | Maximum number of threads to use. Parallelization is only advantageous where the expected degree of variables is significantly greater than the number of threads. |

return_overlap | bool | None | Determines the function’s return value. If True, a 2-tuple is returned with the embedding and a boolean representing the embedding validity. If False, only an embedding is returned. |

skip_initialization | bool | None | Skips the initialization pass if the chains passed through initial_chains and fixed_chains are semi-valid. |

verbose | int | None | Level of output verbosity. Ranges from 0 (quiet) to 4 (detailed debugging). |

interactive | bool | None | If True, the verbose output will be printed to stdout/stderr and keyboard interrupts will stop the embedding process, returning the current state to the user. |

initial_chains | dict | None | Initial chains to be inserted into an embedding before fixed_chains are placed. |

fixed_chains | dict | None | Fixed chains that are inserted into an embedding before the initialization pass and do not change during the algorithm. |

restrict_chains | dict | None | Ensures that each chain is a subset of restrict_chains throughout the algorithm. |

suspend_chains | dict | None | A metafeature implemented in the Python interface. Each entry is an iterable of iterables representing the target node labels. |