# Embedding Equality Constraints of Optimization Problems into a Quantum Annealer +
## 7 Improved Embeddings for the Case \(k=1\)
### Reducing the Number of Cells  
While, for the case \(k=1\), we can use the embedding described in the previous sections, that embedding is going to use \(3(n+2)\) Chimera graph cells and the maximum \(n\) is restricted by the number of cells in one row of the Chimera graph, which for the case of D-Wave 2X is 12 and for D-Wave 2000Q is 16. In this section, we describe an embedding for the case of \(k=1\), i.e., of the constraint  
\[\sum_{ \begin{subarray}{c}1\leq i\leq n\\ x_{i}>0\end{subarray} }x_{i}=1. \tag{10}\]  
using just \(n+2\) (one row of) cells. We will later show how we can extend the embedding to cover all the cells of the Chimera graph. The type of the variables are the same as in the general case, i.e., problem, interface, and hidden variables. However, now we have only the following two types of gadgets:  
* _An internal gadget_--for cells in the interior of the row, and will be denoted by \(\yng(1)\). Each internal gadget contains one problem, two interface, and five hidden variables (Figure 6(a),b). * _A boundary gadget_--for cells on the two ends of the row. They are similar to the boundary gadgets in the general case, but come in only two orientations, which will be denoted by \(\yng(1)\) and \(\yng(2)\). As in the previous case, _tiles_ are gadgets with assignments of values in \(\{-1,1\}\) to their variables and have the same type as their corresponding gadgets. The values of the interface variables are used to assign colors to the corresponding halves of the tile in our notation, where green corresponds to value \(-1\) and red corresponds to value \(+1\). An internal tile corresponding to the gadget on Figure 6(b) is shown on Figure 6(c). The set of all _good_ tiles is illustrated on Figure 8. Recall that in order for a tile to be good, it should have a combination of program and interface variables as shown on Figure 8 and values of the hidden variables that minimizes the corresponding cell Ising program. Note also that (only) the \(\yng(1)\) tile has value of the \(x\) variable set to \(1\) and the other two good tiles hold an \(x\) variable set to \(-1\). Figure 7: Illustration of the internal type gadgets and tile for the case \(k=1\). (**a**) A cell of the Chimera graph. Short lines indicate the couplers connecting to the neighboring cells (some may be missing for boundary cells). (**b**) The logical structure of the the corresponding internal gadget. There are two edges (couplers) shown in red (thicker line in b&w) in (**a**) with weights (in he example) \(-1\) and \(1\) connecting it to the neighboring cells in the row. The coupler shown in blue, in combination with the red coupler on top, is used in the gadget discussed in Section 7.2. (**c**) The corresponding tile as used in our embedding illustrations, with red color for \(+1\) and green for \(-1\) type variables. The cost of the tiles and configurations of tiles is defined in the same way as in the previous sections, i.e., using (6), (8) and (9). Similarly, we define a good tiling as a tiling all of whose tiles and tile pairs are good. We next define an Ising program \(\mathcal{I}(n)\) for implementing the constraint (10) corresponding to the gadget configuration shown on Figure 9a, i.e., such that it covers a row or a sub-row of cells, and has \(n\) internal gadgets plus two boundary gadgets on the ends. We want to show that the minimum cost of a tiling of \(\mathcal{I}(n)\) (Figure 9b) corresponds to an assignment to the \(x\) variables that has exactly one \(x\) variable, which is equivalent to an optimal tiling containing exactly one tile. To estimate the value of \(\mathcal{I}(n)\), we state the following analogues of Propositions 1 and 2. **Proposition 3**. : _Any good internal tile except has left and right sides in different colors._  
**Proposition 4**. : _Since the end tiles of \(\mathcal{I}(n)\) are in red, in any good tiling of \(\mathcal{I}(n)\) there is at least one tile._  
From Proposition 4, any good tiling corresponds to an assignment to the \(x\) variables with at least one \(+1\) value.