# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 3 Results
\begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{**Problem Name**} & **Linear Formulation** & **IP Solution** & **Covering Heuristic** \\  & \(\Delta^{\prime}_{L}\) & (\(\Delta^{\prime}_{IP}\), \#Subs) & (\(\Delta^{\prime}_{C}\), \#Subs) \\ \hline uf20-91 & 84 & (34, 39) & (42, 45) \\ \hline uf50-218 & 100 & (41, 141) & (54, 143) \\ \hline uf75-325 & 115 & (48, 208) & (60, 214) \\ \hline uf100-430 & 103 & (46, 330) & (60, 329) \\ \hline uf125-538 & 133 & (56, 417) & (71, 419) \\ \hline uuf50-218 & 95 & (41, 135) & (50, 141) \\ \hline uuf75-325 & 106 & (43, 233) & (60, 240) \\ \hline uuf100-430 & 105 & (47, 337) & (65, 334) \\ \hline uuf125-538 & 126 & (54, 429) & (73, 430) \\ \hline RTI\_k3\_n100\_m429 & 132 & (61, 332) & (75, 334) \\ \hline BMS\_k3\_n100\_m289 & 110 & (53, 240) & (63, 236) \\ \hline CBS\_k3\_n100\_m403\_b10 & 94 & (43, 315) & (56, 309) \\ \hline CBS\_k3\_n100\_m403\_b30 & 94 & (45, 318) & (60, 309) \\ \hline CBS\_k3\_n100\_m403\_b50 & 96 & (43, 317) & (61, 319) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The unitary circuit depth upper bound for each SATLIB 3-SAT instance using the linear formulation and product formulation with GVS methods. The IP and Covering Heuristic columns also displays the number of substitutions made to cover every \(c\in\mathbb{C}\). Figure 8: _Cont._  
As shown in Figure 9a-d, the degrees of the literal vertices \(v_{i}\) are larger than those of the substitution vertices \(u_{i,j}\) for each 3-SAT instance we evaluated. We can attribute this to the GVS method of determining the degree for each vertex in the derived graph and the sparseness of the literals in each instance. Each unique pair \(s_{i,j}\) which is substituted will add three or four edges to the degree of the literal vertices \(v_{i}\) and \(v_{j}\). However, making this substitution only adds one edge to the corresponding substitution vertex \(u_{i,j}\). In both instances displayed here, a literal \(x_{i}\) is included in approximately thirteen clauses. Clearly, this severely limits the amount of clauses each substitution is able to cover. Consequently, this significantly increases the degree of each literal vertex as more unique substitutions are required to cover all clauses and simultaneously limits the degree of each substitution vertex \(u_{i,j}\) since each \(s_{i,j}\) is used very few times. We can see this represented in Figure 9b,d as nearly 40% of the substitutions made in both instances only cover one clause. The most clauses covered by a any substitution is five. The distribution of literal vertices of the integer program differs significantly from the distribution of the heuristics in both problem instances. A majority of the literal vertices in the graph derived from the IP take on the value of \(\Delta^{\prime}_{IP}\). It is clear that the integer program is not simply minimizing the number of substitutions made, but rather appears to limit the amount of substitutions per literal \(x_{i}\). For these sparse and uniform 3-SAT instances, the best method of minimizing the max degree of any \(v_{i}\) is to attempt to distribute the number of substitutions made evenly amongst all literal vertices \(v_{i}\). Figure 8: Plots of the upper bound of the maximum degree of the derived graph versus the number of substitutions made for the uniform 3-SAT instances found in Table 3. The satisfiable instances plotted are denoted ‘uf_n_-\(|C|^{\prime}\). The unsatisfiable instances are denoted ‘ufn_-\(|C|^{\prime}\). These instance names indicate the number of literals \(n\) and clauses \(C\) in each problem instance. We choose the upper bound of the maximum degree to be the y-axis since the largest unitary circuit depth for one iteration is the maximum degree plus two. Calculating the exact unitary depth requires finding the edge chromatic number of each graph, which is NP-hard, and results in a number that differs from the upper bound by at most one.