# Embedding Equality Constraints of Optimization Problems into a Quantum Annealer +
## 1 Introduction  
Quantum annealing (QA) computers such as the commercially available D-Wave 2X and D-Wave 2000Q are designed to seek solutions to problems that are hard for the conventional computers, such as many NP-hard problems [1]. The type of problems such computers can solve _directly_ in their quantum hardware is minimizing a quadratic form of the type  
\[Q(x_{1},\ldots,x_{n})=\sum_{1\leq i<j\leq n}J_{ij}x_{i}x_{j}+\sum_{i=1}^{n}h_{ i}x_{i}\,, \tag{1}\]  
where variables \(x_{i}\) are either in the set \(\{-1,1\}\), in which case the problem is called an _Ising problem_, or in the set \(\{0,1\}\), in which case it is called a _Quadratic Unconstrained Binary Optimization_ (QUBO) problem. Both versions are NP-hard [1,2] and they can easily be converted into each other by a linear variable transformation. To minimize \(Q\), QA computers are trying to find a low-energy state of the quantum system whose Hamiltonian corresponds to \(Q\)[3,4]. Solving an optimization problem using a quantum annealer involves the following several steps. (i) Represent the optimization problem of interest as a QUBO or Ising problem. Many well-known NP-hard problems such as Maximum Clique, Maximum Independent Set, Maximum Cut, and GraphColoring have simple formulations as quadratic constrained binary optimization problems, i.e., problems with objective function of type (1) plus constraints [5]. A typical such constraint is of the form \(\sum_{i=1}^{n}x_{i}=k\), for a QUBO, or \(\sum_{i=1}^{n}x_{i}=2k-n\) for an Ising problem, where \(0<k<n\), meaning that exactly \(k\) of the decision variables should be set to 1 (true). To have the same representation valid both for the QUBO and the Ising formulations of the constraint, we rewrite it as  
\[\sum_{ \begin{subarray}{c}1\leq i\leq n\\ x_{i}>0\end{subarray} }x_{i}=k. \tag{2}\]  
As an example, the graph partitioning problem [6], asking to divide the vertices of an \(n\)-vertex graph into two equal (with difference in sizes at most one) parts so that the number of edges with endpoints in different parts is minimized, can be formulated as the Ising problem:  
\[\text{Maximize }\sum_{i,j}x_{i}x_{j}\text{ subject to }\sum_{i}x_{i}=n\mod 2,\ x_{i}\in\{-1,1\}\]  
we will later discuss approaches for dealing with such constraints. (ii) Map the Ising problem onto the annealer's hardware. To define the mapping, we consider two graphs, the graph \(P\) describing the structure of the Ising (the program graph), and the graph \(H\), describing the interconnections between the qubits in the hardware (the hardware graph). Specifically, \(P\) has a vertex \(i\) for each variable \(x_{i}\) and an edge \((i,j)\) if \(I_{ij}\
eq 0\), while \(H\) describes the connections between the qubits in the quantum processing unit. In the current D-Wave architecture, \(H\) has the structure of a _Chimera graph_, which consists of an array of _unit cells_, where each unit cell is a complete \(4\times 4\) bipartite graph, and the cells are connected as illustrated on Figure 1. Please note that with the current technology, due to errors during manufacturing and/or calibration, some qubits and couplers are defective and therefore disabled. We assume for now that the Chimera graph is complete, but in Section 8.1.1 we describe a method for dealing with incomplete Chimera graphs. Figure 1: The Chimera interconnection graph for the D-Wave 2X system is a \(12\times 12\) array of _unit cells_, where each cell is a \(4\times 4\) bipartite graph. Since \(P\) is almost never a subgraph of \(H\), \(P\) has to be _minor-embedded_ into \(H\), which means that each vertex of \(P\) is mapped onto a connected set of vertices (qubits) of \(H\) called _chain_, and the parameters of the edges (couplers) connecting the qubits in a chain are chosen so that all such qubits are getting the same value in an optimal solution, with a high probability. While this approach allows any graph \(P\) to be embedded into a sufficiently large Chimera graph \(H\), it comes at a cost.