# Embedding Equality Constraints of Optimization Problems into a Quantum Annealer +
## 2 Problem Formulation  
Let \(\mathcal{C}\) be the set of all binary variables \(\mathbf{x}=x_{1},\ldots,x_{n}\) satisfying constraint (2) and \(\mathcal{C}=\mathbb{B}^{n}\setminus\mathcal{C}\), where \(\mathbb{B}=\{0,1\}\). The typical implementation of the constraint (2) is as a penalty term of the type  
\[P(\mathbf{x})=M\left(\sum_{i=1}^{n}x_{i}-k\right)^{2}, \tag{3}\]  
where \(\mathbf{x}=x_{1},\ldots x_{n}\). Ignoring the scaling factor \(M\), the squared difference term \((\sum_{i=1}^{n}x_{i}-k)^{2}\) has the following relevant properties:  
(i) \[\text{for each }\mathbf{x}\in\mathcal{C},\,P(\mathbf{x})=0;\] (ii) \[\text{for each }\mathbf{x}\in\mathcal{C},\,P(\mathbf{x})\geq\gamma\text{ for some }\gamma>0\text{ (}\gamma=1\text{ in this case).}\]  
Clearly, the larger the value of the parameter \(\gamma\), which is called \(gap\), for which (ii) is satisfied, the larger the \"penalty\" to the objective, if a solution to the optimization problem violates the constraint. Hence, one would like to solve the following problem:  
\[\text{\emph{Find a QUBO problem satisfying the conditions (i) and (ii) with the largest possible value of }\gamma,} \tag{4}\]  
where the QUBO problem is normalized with specific restrictions on the values of its coefficients. For such restrictions, we will use the maximum values of biases allowed on qubits and couplers by D-Wave hardware, as discussed later.  
To allows values of \(\gamma\) that are better than (3), one can use ancillary binary variables \(\mathbf{t}=t_{1},\ldots,t_{m}\) and consider a quadratic binary form of both \(\mathbf{x}\) and \(\mathbf{t}\) variables of the type  
\[Q(\mathbf{x},\mathbf{t})=\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\  
**Problem 1**.: _Find coefficients \(\mathbf{a}=\{a_{ij}\}\), \(\mathbf{b}=\{b_{ij}\}\), and \(\mathbf{c}=\{c_{ij}\}\) such that the QUBO problem (5) satisfies the conditions_  
1. \(\forall\mathbf{x}\in\mathcal{C}\ \exists t\in\mathbb{B}^{m}\) _s.t._ \(Q(\mathbf{x},\mathbf{t})=\mu\)_,_
2. \(\forall\mathbf{x}\in\mathcal{C}\ \forall t\in\mathbb{B}^{m}\ Q(\mathbf{x},\mathbf{t})\geq\mu\)_,_
3. \(\forall\mathbf{x}\
ot\in\mathcal{C}\ \forall t\in\mathbb{B}^{m}\ Q(\mathbf{x},\mathbf{t}) \geq\mu+\gamma\)_,_  
_for some \(\gamma>0\). (Please note that we use a parameter \(\mu\) to account for the lack of constant terms in (5) and (1)._  
Conditions (C1) and (C2) correspond to (i) and (C3) corresponds to (ii). We also take into account the physical properties of the quantum processing unit (QPU), which includes constraints on the minimum and maximum values of the coefficients \(\mathbf{a}\), \(\mathbf{b}\), and \(\mathbf{c}\), which describe the range of values that the QPU hardware allows, and complying with the topology of the Chimera graph, which means that only a specific small subset of \(\mathbf{a}\), \(\mathbf{b}\), and \(\mathbf{c}\) coefficients are allowed to be non-zeros. Please note that while the standard penalty version (3) of the constraint does not explicitly include ancillary variables, such variables implicitly appear when \(P(\mathbf{x})\) is embedded in the QPU, since the embedding represents most of the variables by chains (sets) of qubits, i.e., uses extra variables. Moreover, the number of these extra (ancillary) variables grows asymptotically as the square of the problem variables, i.e., \(m=\Omega(n^{2})\), which is very inefficient. Therefore, we will be looking for solutions in which \(m\) is a subquadratic function of \(n\); specifically, we propose a solution where \(m=O(nk)\), and \(m=O(n)\) if \(k\) is bounded by a constant.