# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 2 Materials and Methods
### Sat
#### 2.3.1 SAT Linear Formulation  
Let \(\{z_{c}\}_{c\in C}\) be the collection of variables indicating if clause \(c\) is satisfied, and \(x_{i}\) be the indicator variable denoting if literal \(i\) is satisfied. Let \(TRUE_{c}\) be the set of literals that must be true to satisfy \(c\), and \(FALSE_{c}\) the rest. Then, 3-SAT can be written as  
\[\max \sum_{c\in C}z_{c}\] (4) s.t. \[\sum_{x_{i}=TRUE_{c}}x_{i}+\sum_{x_{i}=FALSE_{c}}(1-x_{i})\geq z _{c} \forall c\in C \tag{5}\] \[x_{i}, z_{c}\in\{0,1\}. \tag{6}\]  
Equation (5) has this form because 3-SAT is defined to have only OR conditions, so at least one \(x_{i}\) must be satisfied when \(z_{c}=1\). Standard QAOA does not have a way to incorporate constraints; we therefore adopt the aforementioned strategy of dualizing the constraints to yield an unconstrained optimization problem suitable for QAOA as follows. Before we can dualize Equation (5), we must change the inequality so it matches that of Equation (2). We therefore take the contrapositive of each constraint so Equation (5) has the form \(\sum_{x_{i}=TRUE}(1-x_{i})+\sum_{x_{i}=FALSE_{i}}x_{i}\leq 2+z_{c}\). We can express this constraint as an equality,  
\[\sum_{x_{i}=TRUE}(1-x_{i})+\sum_{x_{i}=FALSE_{i}}x_{i}+\delta_{c,1}+\delta_{c,2}=2+z _{c},\]  
Figure 3: The unitary circuit required to solve MaxCut using QAOA. Note that no two qubit unitary operators can be implemented simultaneously since any two act on one common qubit. Here, \(C_{x_{1},x_{3}}\) is a two qubit unitary, but is drawn as two single qubit unitary operators to avoid overlapping with \(|x_{2}\rangle\). Figure 2: The edge colored graph derived when solving MaxCut on a triangle.The solid black is one color class, and red densely dotted and blue dashed are the other two. There are three colors needed to properly edge color this graph, so the unitary circuit depth is four. by introducing two slack variables \(\delta_{c,1}\) and \(\delta_{c,2}\) that guarantee equality holds for any choice of \(x_{i}\) satisfying the constraint. Let us define  
\[f_{c}(\{x_{i},\delta_{c,j}\},z_{c})=\sum_{x_{i}=TRUE}(1-x_{i})+\sum_{x_{i}=FALSE}x_{i}+ \delta_{c,1}+\delta_{c,2}-(2+z_{c}).\]  
The quantity \(f_{c}(\{x_{i},\delta_{c,j}\},z_{c})\) is equal to zero when the constraints are satisfied. 3-SAT can now be expressed as an unconstrained optimization problem by introducing \(-\lambda f_{c}^{2}\) as a penalty term  
\[\max\ \sum_{c\in\mathbb{C}}(z_{c}-\lambda f_{c}(\{x_{i},\delta_{c,j}\},z_{c})^{2})\] \[x_{i},\ \delta_{c,i},\ z_{c}\in\{0,1\}.\]  
where \(\lambda\) is a large number [25]. The variables \(x_{i},\delta_{c,j}\), and \(z_{c}\) can take values of either 0 or 1, however, choices that violate \(f_{c}=0\) give penalties \(\lambda f_{c}(\{x_{i},\delta_{c,i}\},z_{c})^{2}<0\). This ensures that the optimal solution is identical to the original constrained problem. Since we introduce two \(\delta\) variables and one \(z\) per clause in the dualization, this formulation requires \(3|C|\) ancillary qubits. The term \(-\lambda\sum_{c\in\mathbb{C}}f_{c}(\{x_{i},\delta_{c,j}\},z_{c})^{2}\) must be expanded in order to determine all of the edges of the derived graph. The unitary circuit depth for one layer of QAOA is the chromatic index plus one, and the chromatic index is either the maximum degree of the derived graph, or the maximum degree of the derived graph plus one. Thus, the unitary circuit depth is either the maximum degree of the derived graph plus one or the maximum degree of the derived graph plus two. To compute the maximum degree, let \(C_{x_{i}}\subset C\) be the set of clauses containing \(x_{i}\). Then the degree of the \(x_{i}\) in the derived graph is  
\[\deg(x_{i})=5|C_{x_{i}}|-\sum_{j,j\
eq i}(|C_{x_{i},x_{j}}|-1)\]  
where \(C_{x_{i},x_{j}}=C_{x_{i}}\cap C_{x_{j}}\) is the set of clauses containing both \(x_{i}\) and \(x_{j}\). This value lies between \(3|C_{x_{i}}|\) and \(5|C_{x_{i}}|\).