# Embedding Equality Constraints of Optimization Problems into a Quantum Annealer +
## 1 Introduction
If the Ising/QUBO problem is dense, embedding a problem of \(n\) variables requires number of qubits proportional to \(n^{2}\). (iii) Run the annealer in order to find values of the variables producing a low energy of the quantum system modeling the Ising, which corresponds to a low value of the objective function. Due to errors caused by hardware imperfections, thermal noise, decoherence, and the short anneal times (in the order of microseconds), usually this operation is being performed many thousands of times and the best of the proposed solutions is chosen as an answer. Since a QUBO problem cannot, by definition, contain constraints, any constraints have to be added to the objective as penalties. For instance, constraint (2) can be transformed into a penalty term \(M(\sum_{i=1}^{n}x_{i}-k)^{2}\) that is added to the objective of a QUBO. If \(M\) is chosen large enough, then for any optimal solution the constraint (2) should be satisfied, assuming the problem is a minimization one. A drawback of such an approach is that such squared penalty will result in a QUBO or Ising with \(O(n^{2})\) quadratic terms (nonzero coefficients \(J_{ij}\)) and a complete graph \(P\) even if the original objective was sparse (with \(O(n)\) quadratic terms). Hence, our goal is to design more efficient ways to represent constraints for optimization with quantum annealers such as D-Wave. Previous work on this problem includes [7], where the constraint embedding problem is formulated as a mixed integer optimization problem, which is solved by using MathSat solver [8], a Satisfiability Modulo Theory (SMT) [9] type solver, in a combination with using dynamic programming and exploiting the special structure of the Chimera graph. They use their algorithm to find an embedding of the Ising constraint \(\sum_{i=1,x_{i}>0}^{8}x_{i}=1\), \(x_{i}\in\{-1,1\}\), producing an embedding with 8 qubits, compared to the 12 qubits required by the squared constraint penalty. However, their approach is not scalable and is restricted to problems where \(n\) is no more than 10-20 [7]. There also has been a lot of work on solving constrained optimization problems on classical computers. The approach adopted in this paper and commonly used for solving constrained problems on the D-Wave annealer belongs to the class of penalty methods, which includes barrier methods [10; 11]. Another approach is the Augmented Lagrangian Method [12], which combines the penalty function with Lagrange multipliers in a single objective function. However, since the Lagrange multipliers are real numbers, the resulting problem cannot be directly solved on the D-Wave annealer, which only accepts binary variables. For further discussion of constrained methods, see [10; 13; 14]. For minor-embedding a general graph into the Chimera graph, [PERSON] [15; 16] show that a Chimera graph consisting of \(m\times m\) array of unit cells allows an embedding of a complete graph of \(4m+1\) vertices. [PERSON] et al. [17] design a polynomial-time algorithm for finding embedding of a complete graphs into a subgraph if a Chimera graph, which is relevant for the case of hardware graphs with faulty qubits and/or couplers. [PERSON] et al. [18] improve on that result by increasing in some case the sizes of the cliques that can be embedded and reducing the chain sizes. [PERSON] et al. [19] design a heuristic algorithm that constructs an embedding of any graph (not necessarily clique) into the Chimera graph. [PERSON] et al. [20] explore alternative ways of mapping operational planning optimization problems to QUBO problems and embedding them into the D-Wave hardware, and analyze how different mappings and parameter choices affect the effectiveness of the annealers. [PERSON] et al. [21] develop a locally structured approach for embedding Boolean constraint satisfaction problems on the Chimera hardware and and propose decomposition algorithms for solving problems too large to fit into the hardware. [PERSON] et el.