# Embedding Equality Constraints of Optimization Problems into a Quantum Annealer +
## 5 Ising Program Design and Correctness Analysis
### Defining the Ising Program  
To define \(Is(R)\), we assign gadgets to \(R\) as follows (see Figure 4). To all inner cells, i.e., the ones that do not share an edge on the boundary of \(R\) we assign inner gadgets. To all leftmost cells we assign positive left boundary gadgets, to all rightmost cells we assign positive right boundary gadgets, and to all cells in the top row we assign positive top boundary gadgets. To the rest (the bottom row), we assign problem gadgets, specifically, the \(i\)-th gadget is red, if \(x_{i}=1\), and green, if \(x_{i}=-1\). The four corner cells are ignored (assigned zero coefficients). Coefficients corresponding to edges joining interface variables we set to 1, and the other coefficients we set to 0. We can prove the following property characterizing feasible tilings of \(Is(R)\). If it is clear from the context, we will use \(R\) instead of \(Is(R)\) to simplify notation. **Lemma 1**. : _There exists an optimal tiling of \(R\) and any such tiling has exactly \(k\) red problem regions._  
The lemma implies that if we place the problem \((x_{i})\) variables in the problem tiles (bottom row of \(R\)), then there is a tiling of \(R\) (i.e., an assignment of the \(t_{i}\) variables) that minimizes \(R\) if and only if (2) is satisfied. An example of such an optimal tiling is shown in Figure 5.  
Lemma 1 directly follows from the following property, which we prove below. **Lemma 2**. : _If the number of red problem tiles of \(R\) is \(k\), then \(R\) has an optimal tiling, else \(R\) has no optimal tiling._  
To prove Lemma 2, we state some properties of optimal tilings. **Proposition 1**. : _Any good internal tile except has opposite sides in different colors._  
Then, in any optimal sequence of internal tiles not containing the leftmost and the rightmost sides are of different colors. This implies that since each row of \(R\) except the first and the last one has two red boundary tiles at its ends, i.e., tiles of the same color, we have the following. Figure 4: Ising program construction for the case \(n=6\), \(k=3\). Figure 5: Optimal tiling of \(Is(R)\). **Proposition 2**. : _In any good tiling of \(R\), each row with internal tiles has at least one internal tile of type_  
We next prove an auxiliary lemma. Consider any row except the bottom and top ones of any optimal tiling of \(R\) and denote the corresponding Ising program as \(R_{i}\). Assume we know the colors \(b_{1},\ldots b_{n}\) of the top triangles of the tiles below that row (Figure 6), but we do not know the colors of the internal tiles in \(R_{i}\). Nevertheless, we will show that we can characterize the colors \(b_{1}^{\prime},\ldots b_{n}^{\prime}\) of the top triangles of the internal tiles of \(R_{i}\), shaded in gray in Figure 6.  
**Lemma 3**. : _The number of red colors in \(b_{1}^{\prime},\ldots,b_{n}^{\prime}\) is exactly one less than the number of red colors in \(b_{1},\ldots,b_{n}\)._  
Proof. : By Proposition 2, there is at least one internal tile of type in \(R_{i}\). Let \(i_{i}\) be the first such tile. Hence, there is no tile in \(i_{1},\ldots,i_{l-1}\) and, by Proposition 1, \(b_{j}^{\prime}=b_{j}\) for \(j=1,\ldots,l-1\). Since \(i_{l}\) is, \(b_{l}^{\prime}\) is green and \(b_{l}\) is red. For the remaining tiles \(i_{l+1},\ldots,i_{n}\) we can see that if tile \(p_{j}\) is red for \(l+1\leq j\leq n\), then \(i_{j}\) is, otherwise \(i_{j}\) is. In both cases, \(b_{j}^{\prime}=b_{j}\). In summary, \(b_{j}^{\prime}=b_{j}\) for \(j\
eq l\) and \(b_{l}\) is red, while \(b_{l}^{\prime}\) is green, which proves the lemma. Lemma 3 states that the number of red colors decreases by one after each row of internal tiles in an optimal tiling, and there are \(k\) such rows, so that would prove the lemma if there is an optimal tiling. However, we do not know if such optimal tiling always exists. The next lemma helps answer when a tiling can be extended to the next row. **Lemma 4**.