# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 2 Materials and Methods
### Global Variable Substitution
#### 2.5.1 Degree of Substituted Variables  
We now give a formula for the degrees of vertices \(\delta_{c,k}\) and \(u_{\mathsf{j}}\), as well as determine the contribution of each substitution to the degree of \(x_{i}\). These degrees, in conjunction with the \(x_{i}x_{j}\) terms, can be used to compute the unitary circuit depth, as shown explicitly in the example of Section 2.5.3. Theorem 2: _Let \(U\) denote the set of all substitutions made. Let us denote the set of substitutions containing \(x_{i}\) as \(U_{i}\). For \(u_{\mathsf{j}}\in U\) we let \(|u_{\mathsf{j}}|\) denote the number of variables substituted in substitution \(u_{\mathsf{j}}\). The number of edges incident to each vertex in the derived graph due to the substitution is denoted \(\deg_{s}(v)\) and is_  
\[\deg_{s}(\delta_{c,k}) \in\{2,|u_{\mathsf{j}}|+m_{u_{\mathsf{j}}}\}\] \[\deg_{s}(x_{i}) =\sum_{u_{\mathsf{j}}\in U_{i}}\big{[}|u_{\mathsf{j}}|+m_{u_{ \mathsf{j}}}+1\big{]}-\sum_{p\in[n]\setminus i}z_{i,p}\big{[}|U_{i}\cap U_{p}| -1\big{]}+|C^{\prime}_{x_{i}}|\] \[\deg_{s}(u_{\mathsf{j}}) =2|u_{\mathsf{j}}|+m_{u_{\mathsf{j}}}+|C_{u_{\mathsf{j}}}|\]  
_where \(m_{u_{\mathsf{j}}}\) denotes the number of \(\delta_{c,k}\) variables in Equation (7) for the substitution \(\mathsf{j}\), \(z_{i,p}\) is an indicator variable denoting whether or not \(U_{i}\cap U_{p}=\{\varnothing\}\), \(|C^{\prime}_{x_{i}}|\) refers to the number of monomials containing \(x_{i}\) which do not have any \(u_{s}\) containing \(x_{i}\) substituted, and \(|C_{u_{\mathsf{j}}}|\) refers to the number of monomials with more than two variables using the substitution \(u_{\mathsf{j}}\)._  
Proof: First, we will consider the degree of each \(\delta_{c,k}\) by counting the number of terms that contain \(\delta_{c,k}\) in each dualized constraint. Note that in the first constraint, there are \(1+|u_{\mathsf{j}}|+m\) variables total, so \(|u_{\mathsf{j}}|+m\) of these are multiplied times a single \(\delta_{c,k}\) term upon dualization. Thus, the degree of \(\delta_{c,k}\) in this constraint is \(|u_{\mathsf{j}}|+m\). In each of the following constraints, note that there are three variables: \(u_{\mathsf{j}}\), \(x_{i}\) and \(\delta_{c,k}\). Thus, the degree of \(\delta_{c,k}\) from these constraints is 2. Since the \(\delta_{c,k}\) terms in each constraint are different, they do not add, so \(\deg_{s}\delta_{c,k}\in\{2,|u_{\mathsf{j}}|+m_{u_{\mathsf{j}}}\}\). Next, we consider the degree of each \(x_{i}\) in the graph derived from the dualization. In the first constraint, there are \(|u_{\mathsf{j}}|+m_{u_{\mathsf{j}}}\) terms containing each \(x_{i}\) and there is exactly one constraint aside from the first that contains \(x_{i}\). This constraint only has two terms containing \(x_{i}\), but the contribution to the degree from this is one since the edge \(u_{\mathsf{j}}x_{i}\) already exists in the graph from the first constraint. Now, we must consider how many \(u_{\mathsf{j}}\) contain \(x_{i}\) as a variable. If there is more than one substitution containing \(x_{i}\), there are multiple constraints that have the form of the first one. Each of those constraints contain new \(u_{\mathsf{j}}\) variables and new \(\delta_{c,k}\) variables since the substitutions are different. Thus, the only double counting that can happen is in products of \(x_{i}x_{j}\), since these are the only other edges possible in the graph derived from the dualization. We must subtract the number of times each of these terms occurs in each constraint except for one. Additionally, we must count the clauses that contain \(x_{i}\) but in which \(x_{i}\) is not contained in a substitution, since it will be incident to the substitution in the derived graph. We denote the number of these clauses as \(|C^{\prime}_{x_{i}}|\). Then, \(\deg_{s}(x_{i})=\big{[}\sum_{u_{\mathsf{j}}\in U_{i}}|u_{\mathsf{j}}|+m_{u_{ \mathsf{j}}}+1\big{]}-\sum_{p\in[n]\setminus i}z_{i,p}\big{[}|U_{i}\cap U_{p}| -1\big{]}+|C^{\prime}_{x_{i}}|\). Finally, we need to consider the degree of each substituted, \(u_{\mathsf{j}}\).