# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 2 Materials and Methods
### Optimizing Global Variable Substitutions for 3-Sat
#### 2.6.2 IP Formulation and Solution for Example 1  
Let us examine Example 1,  
\[x_{1}\lor x_{2}\vee\backsim x_{3}\] \[x_{1}\lor x_{3}\lor x_{4}\] \[\backsim x_{2}\lor x_{4}\lor x_{5}\] \[x_{1}\vee\backsim x_{2}\lor x_{5}.\]  
The reformulation and expansion of each of these four 3-SAT clauses yields a three variable monomial \(c\), two variable monomials \(s_{ij}\in P\), and potential coverings \((s_{ij},x_{k})\).The first statement holds if and only if \((1-x_{1})(1-x_{2})x_{3}=x_{3}-x_{1}x_{3}-x_{2}x_{3}+x_{1}x_{2}x_{3}\) holds. The other clauses, when expanded, give expressions \(1+x_{1}x_{4}+x_{3}x_{4}-x_{1}x_{3}x_{4}\), \(x_{2}-x_{2}x_{4}-x_{2}x_{5}+x_{2}x_{4}x_{5}\), and \(x_{2}-x_{1}x_{2}-x_{2}x_{5}+x_{1}x_{2}x_{5}\). The two variable terms are \(s_{ij}\in P\). Each \(c\in C\) has \(\binom{3}{2}\) pairs that can cover it. In this example, we have five variables and four clauses. A summary of the clauses, their corresponding \(P\) and potential covering are found in Table 2.  
\[S=\{s_{1,2},\,s_{1,3},\,s_{1,4},\,s_{1,5},\,s_{2,3},\,s_{2,4},\,s_{2,5},\,s_{3,4},\, s_{4,5}\}\] \[P=\{s_{1,2},\,s_{1,3},\,s_{1,4},\,s_{2,3},\,s_{2,4},\,s_{2,5},\,s_{3,4}\}\] \[||P||=(3,4,3,3,1).\]  
After determining these sets, we are able to formulate our constraints. First we add a constraint for each literal vertex \(v_{a}\in V\) in the form of Equation (16). For \(a=1\):  
\[\deg(x_{1})= 3y_{s_{1,2}}+3y_{s_{1,3}}+3y_{s_{1,4}}+4y_{s_{1,5}}+z(c_{0},s_{2,3 },x_{1})+z(c_{1},s_{3,4},x_{1})+z(c_{3},s_{2,5},x_{1})\] \[+3\leq obj.\]  
Next, we add a constraint for each unique substitution \(u_{s}\) corresponding to an \(s\in S\) in the form of Equation (17). For \(s=(x_{1},x_{2})\):  
\[\deg(u_{1,2})=5+z(c_{0},s_{1,2},x_{3})+z(c_{3},s_{1,2},x_{5})\leq obj.\]  
For each \(c\in C\) we add a constraint in the form of Equation (18) to assert that a clause \(c\) must be covered by exactly one of its three potential coverings found in Table 2. For clause \(c_{0}\):  
\[z(c_{0},s_{1,2},x_{3})+z(c_{0},s_{1,3},x_{2})+z(c_{0},s_{2,3},x_{1})=1.\]  
Finally, for each covering containing a pair \(s_{i,j}\), we add a constraint in the form of Equation (19). This asserts that if any covering containing \(s_{i,j}\) is selected for a substitution, \(x_{s_{i,j}}\) is forced to \(1\). For \(s=(x_{1},x_{2})\) we add the constraints  
\[z(c_{0},s_{1,2},x_{3})-y_{s_{1,2}}\leq 0\] \[z(c_{3},s_{1,2},x_{5})-y_{s_{1,2}}\leq 0.\]  
The solution to this IP is  
\[y_{1,3},y_{2,5}=1\] \[z(c_{0},s_{1,3},x_{2}),z(c_{1},s_{1,3},x_{4}),z(c_{2},s_{2,5},x_{ 4}),z(c_{3},s_{2,5},x_{1})=1,\]  
which indicates that the optimal solution is to substitute pairs \(s_{1,3}\) and \(s_{2,5}\). Using these substitutions, \(\Delta_{G}=8\) and the degree of each vertex in the derived graph is  
\[\deg(x_{1})=7\ \ \deg(x_{2})=8\ \ \deg(x_{3})=6\ \ \deg(x_{4})=5\] \[\deg(x_{5})=4\ \ \deg(u_{1,3})=7\ \ \deg(u_{2,5})=7\]  
so the unitary circuit depth is at most nine.  
\begin{table}
\begin{tabular}{l c c c c c c} \hline  & **c (\(\mathbf{x}_{i}x_{j}\mathbf{x}_{k}\))** & \(\mathbf{s}_{i,j}\in\mathbf{P}\) & **Covering 1** & **Covering 2** & **Covering 3** \\ \hline c0 & \(x_{1}x_{2}x_{3}\) & \(s_{1,3},s_{2,3}\) & \((s_{1,2},x_{3})\) & \((s_{1,3},x_{2})\) & \((s_{2,3},x_{1})\) \\ \hline c1 & \(x_{1}x_{3}x_{4}\) & \(s_{1,3},s_{1,4},s_{3,4}\) & \((s_{1,3},x_{4})\) & \((s_{1,4}