# Embedding Equality Constraints of Optimization Problems into a Quantum Annealer +
## 8 Experiments
### Multi-Row Algorithm
#### 8.1.2 Analysis  
We performed two experiments. In the first experiment, we analyze whether and how the accuracy of the solution is affected by the value of the gap parameter \(\gamma\). While the constraint (10) should be satisfied for any values of \(x\) and \(t\) minimizing the quadratic Ising program (5), for a solution returned by the D-Wave machine that may not be necessarily true due to the annealer's stochastic behavior. The reason is that, because of incoherence, flux noise, background susceptibility, etc. [29], the D-Wave machine might not be able to find the global minimum of the Ising program implementing the constraint, and hence the constraint may not be satisfied. Because of such inherent inaccuracy, when solving NP-hard optimization problems one usually performs thousands of anneals on the same  
Figure 14: Embedding of the Ising constraint \(\sum_{i=1}^{n}x_{i}=-n+2\) (corresponding to QUBO constraint \(\sum_{i=1}^{n}x_{i}=1\)) for \(n=94\). Colors encode vertex and edge values as in Figure 13.  
Figure 13: Figure illustrating a connection between two perfect cells by a chain of bad-cell vertices and edges. Colors on the vertices and edges encode the values of the corresponding coefficients, where blue is for negative, red for positive, and gray is for near-zero, and the intensities of colors encode the magnitudes. The couplers of cell \(\sigma_{f}\) are all set to \(-1\) forcing \(t_{12}\) and \(t^{*}\) to take the same values in an optimal solution. input and chooses the best result as a solution. This is justified as annealing and comparing the results is relatively fast, while coming with good candidate solutions in the case of NP-hard problems is very difficult. Therefore, one would expect that for greater \(\gamma\), i.e., when the difference between the global minimum and the best suboptimal solutions is greater, it would be easier for the D-Wave machine to distinguish between optimal and suboptimal solutions, and therefore the accuracy would also be better. To produce embeddings with different values for \(\gamma\), we modify the solution \(\mathcal{I}(n)\) described above. Recall the value of the gap of \(\mathcal{I}(n)\) is determined as the minimum of the gap between the good and bad tiles, which is four, and the gap between good and bad pairs of tiles, which is two. Recall also that the second type of gap is equal to twice the absolute value of the bias (weight) on the coupler (edge) between the adjacent cells, which absolute value is \(1=|-1|\). Hence, if we change in \(\mathcal{I}(n)\) the weight of each interface edge between cells, currently set at \(-1\), to a weight \(-w\in[-1,0]\), this will result in an embedding with \(\gamma=2w\). In this way, one can generate a set of embeddings with arbitrary values for \(\gamma\) between 0 and 2. Figure 15 shows results based on the embedding illustrated on Figure 14 modified with respect to \(\gamma\) as discussed above. In all experiments in this section, the results are for 10,000 anneals averaged over 10 trials. Each curve, shown in a different color, corresponds to an embedding with a given value of the parameter \(\gamma\), ranging from 0.2 to 2. The quantity we measure is the number of problem variables \(x_{i}\) with value \(+1\). As we can expect, the larger the gap \(\gamma\), the better the embedding (curves that are to the left correspond to better embeddings). However, even the best embedding, for \(\gamma=2\), is still of insufficient quality. That raises the question whether other parameters such as the number of problem variables \(x_{i}\) can also affect the quality of the embedding. In the second experiment, we study how the accuracy of the solution depends on the size of the problem vector \(x\) (the value of the size parameters \(n\)). For this purpose, for each number of variables  
Figure 15: Dependence of the quality of the constraint embedding measured as the value of the sum of all \(x_{i}\) (horizontal axis) on the value of the _gap_ parameter, shown as curves of different colors.