# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 3 Results  
In this section, we evaluate the performance of the product 3-SAT model and covering heuristic formulated to apply the global variable substitution method to large 3-SAT instances. Since the unitary circuit depth for one iteration of QAOA is the maximum degree plus one or the maximum degree plus two, in all cases, we take the unitary circuit depth to be the maximum degree plus two since is the upper bound of the unitary circuit depth for one iteration. Thus, we compare the upper bound of the unitary circuit depth for one iteration achieved using the integer programming model and covering heuristic, which we denote \(\Delta^{\prime}_{I,P}\) and \(\Delta^{\prime}_{C}\), respectively, to the upper bound of the unitary circuit depth, denoted \(\Delta^{\prime}_{L}\), calculated using the linear model described in Section 2.3.1. We apply each formulation and method to 3-SAT problem instances from the SATLIB Benchmark Suite developed by [PERSON] and [PERSON] [19]. This suite is composed of thousands of SAT instances of varying families and sizes. We choose the first instance of each problem set to evaluate. The results in Table 3 indicate that the graphs derived using the product formulation combined with the GVS method result in significantly lower unitary circuit depth for one iteration of QAOA than the graphs derived from the linear formulation. For every problem instance, \(\Delta^{\prime}_{IP}<1/2\Delta_{L}\). The heuristic does not yield as large of a reduction, but most instances see a significant reduction in degree compared to the linear method. It is interesting to note that as the size of each 3-SAT instance increases, the \(\Delta\) of the derived graph does not increase significantly. We can attribute this to the uniformity in the ratio of the literals to clauses and the uniformity of the distribution of those literals amongst all problem instances. In nearly every 3-SAT instance, the GVS integer program makes more than or approximately equal to the amount of substitutions made by the covering heuristic method. However, the maximum degree of the IP derived graphs \(\Delta_{IP}\) are significantly lower than \(\Delta^{\prime}_{C}\). This trend can be seen in Figure (a)a,b which plot the maximum degree of the derived graph against the number of substitutions made for the uniform 3-SAT instances. This seems to indicate that simply minimizing the number of substitutions does not necessarily minimize the maximum degree of the GVS derived graph. In particular the uf50-218 instance from [19], which is a satisfiable instance with 50 variables and 218 clauses, achieves\(\Delta^{\prime}_{IP}=41\), which is accomplished by making 141 substitutions. The covering heuristic makes three more substitutions than the LP, but produces \(\Delta^{\prime}_{C}=54\). The unsatisfiable instance of the same size, uuf50-218, achieves \(\Delta^{\prime}_{IP}=41\) by making 138 substitutions. The covering heuristic in this instance made only six more substitutions, but resulted in a \(\Delta^{\prime}_{C}=50\). To investigate this trend, we plot the distribution of the degrees of each vertex in the derived graph for each method.