# Embedding Equality Constraints of Optimization Problems into a Quantum Annealer +
## 5 Ising Program Design and Correctness Analysis
### Cost of Tiles and Tile Configurations  
Consider a region \(R=R_{k,n}\) of the Chimera graph consisting of a \((k+2)\times(n+2)\) array of gadgets, an assignment \(\mathcal{A}\) of values on the variables in \(R\), and the resulting set \(\mathcal{T}\) of tiles. The value of \(Is(R)\) for \(\mathcal{A}\) is a sum of the values of all tiles in \(\mathcal{T}\) plus the sum of the values of all interactions between the tiles. Next, we set the desirable properties for the values of the tiles, depending on their type, and for their interactions.  
Figure 3: The set of the good tiles.  
For each tile \(\tau\) in \(R\), denote by \(\text{cost}(\tau)\) the value \(Is(\tau)\) minimized over all hidden variables. Then our requirements for the cost of \(\tau\) are  
\[\text{cost}(\tau) =s\text{, if }\tau\text{ is good,} \tag{6}\] \[\text{cost}(\tau) \geq s+\gamma\text{, if }\tau\text{ is bad,}\]  
for some constants \(s\) and \(\gamma\), where \(\gamma\) is the gap from (C3).  
To show that such tiles do exist, we will formulate and solve an optimization problem for each of the three gadget types, which will have variables the coefficients \(\mathbf{a}\), \(\mathbf{b}\), and \(\mathbf{c}\) restricted to a single unit cell of the Chimera graph. We will give details on the optimization problem in Section 6.  
Next, we estimate the contribution of the tile interaction to \(Is(R)\). Consider a pair \((\tau_{1},\tau_{2})\) of adjacent tiles. Denote by \((t_{1},t_{2})\) the pair of the corresponding adjacent interface variables (i.e., \(t_{1}\in\tau_{1}\), \(t_{2}\in\tau_{2}\)), by \(\alpha\) the coefficient of the corresponding quadratic term (i.e., that quadratic term is \(\alpha t_{1}t_{2}\)), and by \(\text{cost}(\tau_{1},\tau_{2})\) the value of that quadratic term. Please note that there are in total 4 edges joining \(\tau_{1}\) and \(\tau_{2}\), but we allow only one to take a nonzero value, by setting the weights of the other 3 to zero. For any variable \(v\), let \(\mathcal{A}(v)\) denote the value assigned to \(v\). Then, if we set \(\alpha\) to the maximum value of \(+1\) allowed by the D-Wave hardware, we have  
\[\text{cost}(\tau_{1},\tau_{2})=\alpha\,\mathcal{A}(t_{1})\mathcal{A}(t_{2})= \mathcal{A}(t_{1})\mathcal{A}(t_{2}).\]  
Hence  
\[\text{cost}(\tau_{1},\tau_{2})=\begin{cases}1,&\text{if }\mathcal{A}(t_{1})= \mathcal{A}(t_{2}),\\ -1,&\text{if }\mathcal{A}(t_{1})\
eq\mathcal{A}(t_{2}).\end{cases} \tag{7}\]  
Let us call the pair \((\tau_{1},\tau_{2})\)_good_, if \(\mathcal{A}(t_{1})\
eq\mathcal{A}(t_{2})\), and call it _bad_, otherwise. Then (7) can be reformulated as  
\[\text{cost}(\tau_{1},\tau_{2})=\begin{cases}1,&\text{if }(\tau_{1},\tau_{2}) \text{ is bad,}\\ -1,&\text{if }(\tau_{1},\tau_{2})\text{ is good.}\end{cases} \tag{8}\]  
Finally, for the cost of \(Is(R)\) for \(\mathcal{A}\), denoted by \(\text{cost}(R)\), we have  
\[\text{cost}(R)=\sum_{\tau\in\mathcal{T}}\text{cost}(\tau)+\sum_{(\tau_{1}, \tau_{2})\in Adj}\text{cost}(\tau_{1},\tau_{2}), \tag{9}\]  
where \(Adj\) is the set of all pairs of adjacent tiles. If all tiles in \(\mathcal{T}\) are good and all pairs in \(Adj\) are good, we call \(\mathcal{T}\) an _optimal_ tiling, as \(\text{cost}(R)\) gets a minimum value in that case.  
If \(\mathcal{T}\) is not optimal, then it will have at least one bad tile or at least one bad pair. From (6), any tiling containing a bad tile will have a value at least \(\gamma\) greater than the optimal one. Since, by (8), the difference of the values between the cases of a bad and good pair is 2, any tiling containing a bad pair will have a value by at least 2 greater than the optimal one. Hence, if \(\mathcal{T}\) is not optimal, \(\text{cost}(R)\) gets a value by at least \(\min\{\gamma,2\}\) larger than the optimum.