# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 2 Materials and Methods
### Global Variable Substitution
#### 2.5.2 3-Sat  
Notice that Theorem 2 reduces to  
\[\deg(\delta_{c,k}) \in\{2,3\}\] \[\deg(x_{i}) =\big{[}\sum_{u_{j}\in U_{i}}4\big{]}+|C^{\prime}_{x_{i}}|\] \[\deg(u_{j}) =5+|C_{s_{j}}|\]  
for 3-SAT since \(|u_{j}|=2\), \(z_{i,p}|U_{i}\cap U_{p}|\in\{0,1\}\), and \(m=1\). This is the degree for each variable due to the substitution. In order to determine the total degree, we need to look at two variable terms in the expansions and add one to the degree for each unique term.  
To compute the unitary circuit depth for one layer of QAOA, we must compute the maximum vertex degree in the derived graph. We focus here on the example of 3-SAT. A similar approach can be used to decompose other classes of combinatorial optimization problems. In order to calculate the total degree of a vertex in the derived graph from 3-SAT, we need to add the degrees of a vertex due to a substitution \(u_{j}\), from Theorem 2, to the degree from two vertex monomials that were not substituted. Since \(\delta_{c,k}\) and \(u_{i,j}\) are introduced in order to make the substitutions, their degrees are exactly the quantity in Theorem 2.  
In order to count the number of edges induced by pairs that are not substituted, we define \(P\) as the set of all two variable monomials that result from the expansion of the product formulation of each clause in a 3-SAT instance. These two variable monomials will be denoted \(s_{i,j}\). For example, if we have the clauses \((1-x_{1})x_{2}x_{3}=x_{2}x_{3}-x_{1}x_{2}x_{3}\) and \((1-x_{2})x_{4}(1-x_{5})=x_{4}-x_{2}x_{4}-x_{4}x-5+x_{2}x_{4}x_{5}\) and the substitutions \(u_{1,3}\) and \(u_{4,5}\) are made, in this case, \(P=\{x_{2}x_{3},x_{2}x_{4}\}\). The subset of \(P\) containing a vertex \(a\) is denoted \(P_{a}\). Here, \(P_{2}=P\), since \(x_{2}\) is in each monomial, \(P_{3}=\{x_{2}x_{3}\}\), and \(P_{4}=\{x_{2}x_{4}\}\). Let \(||P||=(|P_{1}|,|P_{2}|,...,|P_{n}|)\).  
These sets can be used to determine the number of edges incident to a vertex \(x_{i}\) that are from the two variable terms in the expansions of each clause, which we denote \(\deg_{e}(x_{i})\). Let us fix variable \(x_{i}\). Since \(|P_{i}|\) counts the number of two variable terms containing \(x_{i}\), it is added to Theorem 2. If one of the two variable terms from the expansion of the clauses is substituted, i.e., if \(x_{i}x_{j}\in P_{i}\) and \(u_{i,j}\) is a substitution, then adding \(|P_{i}|\) to the degree double counts the edge \(x_{i}x_{j}\). Thus, the number of substitutions that appear in \(P_{i}\) need to be subtracted. If \(S_{i}\) is the set of substitutions containing variable \(x_{i}\) and \(y_{s}\) is an indicator variable that determines if the substitution \(s_{i,j}\) was used, the total degree of \(x_{i}\) is  
\[\deg(x_{i})=4\sum_{s_{i,j}\in S_{i}}y_{s_{i,j}}-\sum_{s_{i,j}\in P_{i}}y_{s_{i,j}}+|P_{i}|+|C^{\prime}_{x_{i}}|=\deg_{s}(x_{i})+\deg_{e}(x_{i}),\]  
where \(\deg_{e}(x_{i})=-\sum_{s_{i,j}\in P_{i}}y_{s_{i,j}}+|P_{i}|\).  
The QAOA unitary circuit depth is then given as \(\max\{\deg(\delta_{c,k}),\deg(x_{i}),\deg(u_{ij})\}\), where  
\[\deg(\delta_{c,k})\in\{2,3\} \tag{9}\] \[\deg(x_{i})=4\sum_{s_{ij}\in S_{i}}y_{s_{ij}}-\sum_{s_{ij}\in P_{i }}y_{s_{ij}}+|P_{i}|+|C^{\prime}_{x_{i}}|\] (10) \[\deg(u_{i,j})=5+|C_{u_{ij}}|, \tag{11}\]  
for 3-SAT. Note that \(\delta_{c,k}\in\{2,3\}\) since the size of each substitution \(|u_{ij}|=2\) and \(m=n-|u_{ij}|=3-2=1\), which also simplifies \(\deg(u_{ij})\). Furthermore, note that \(U_{i}\cap U_{p}\in\{0,1\}\ \forall\ i\
eq p,\ i,p\in[n]\), which simplifies \(\deg(x_{i})\).