# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 2 Materials and Methods
### Optimizing Global Variable Substitutions for 3-Sat
#### 2.6.1 Global Variable Substitution Integer Program  
Each substitution introduces new variables that correspond to ancillary qubits and impacts the degree of each vertex in the derived graph. In order to determine which of the possible combinations of substitutions are feasible, we create a graph \(G=(V(G),E(G))\), which we call the lovering graph. There are two sets of vertices in this graph. One set is the set of all 2-sets representing all possible two-variable substitutions \(u_{i,j}=x_{i}x_{j}\). We call this set of vertices \(S\) and denote the pairs \(x_{i}x_{j}\) in \(S\) as \(s_{i,j}\). Each \(s_{i,j}\) is a possible substitution, but not each \(s_{i,j}\) will result in a substitution \(u_{i,j}\). The other set is the one containing all three variable terms from the expansion, which we will call the lexpansion 3-set, \(ES_{3}\). Edges are placed between vertices \(g\) and \(h\) if the variables in the label of \(g\) are a proper subset of the variables in the label of \(h\). There are no edges between any sets of the same size, making the graph bipartite. See Figure 7 for an example, where \(S\) is the left set of vertices and \(ES_{3}\) is the right set for Example 1. Figure 6: The derived graph for solving Example 1 using GVS with substitutions \(x_{1}x_{3}=u_{1,3}\) and \(x_{2}x_{5}=u_{2,5}\). The vertices of this graph are the variables from the problem, \(x_{i}\) for \(i\in[5]\), along with the substitution variables, \(u_{1,3}\) and \(u_{2,5}\), and the three \(\delta_{c,k}\) variables needed per substitution. The solid edges correspond to the edges induced by the substitution, which correspond to products of two monomials in the Equations (12)–(14). The dashed edges represent the two variable terms from the expansion of the 3-SAT clauses that are not involved in substitutions. The maximum degree of this graph is 8, thus the unitary circuit depth for one layer of QAOA is 9 or 10. The nature of this problem naturally lends itself to a set covering or bipartite matching style formulation as each substitution \(u_{i,j}\) can cover, or be matched with, any clause containing the literals in that substitution. We have chosen to use a set covering problem formulation, i.e., we want to find a subset of \(S\) such that each vertex in \(ES_{3}\) is incident to a vertex in the subset. Since covering a vertex in \(ES_{3}\) more than once leads to unnecessary ancillary qubits and increases the degree, we need to add constraints to ensure that each clause \(c\in C\) is covered by exactly one substitution \(u_{i,j}\). Notice that more than one covering may be possible as seen in Figure 7.  
The objective of 3-SAT is to minimize the maximum degrees found in Equations (9) and (11),  
\[\min\ \max\{\deg(\delta_{c,k}),\deg(x_{i}),\deg(u_{i,j})\}\]  
which are derived from the GVS method. The covering graph developed in the previous paragraphs is used to aid in the minimization process. The integer program formulation of this problem is subject to the set covering constraints. Each clause \(x_{i}x_{j}x_{k}=c\) is covered by a pair \(s_{i,j}=x_{i}x_{j}\) and has a variable \(x_{k}\) that is not in a substitution. The indicator variable \(z(c,s_{i,j},x_{k})\) is defined as  
\[z(c,s_{i,j},x_{k})= \left\{ \begin{array}{l}1\ \text{if covering}\ (s_{i,j},x_{k})\ \text{is selected to cover clause}\ c\\ 0\ \text{else}\end{array} \right..\]  
The full integer program formulation to minimize the maximum degree vertex in the derived graph, \(obj\), is as follows:  
Figure 7: The covering graph for Example 1. We have emphasized all three different coverings by coloring the edges differently for each covering. They are the red dotted, blue dashed, and black solid edges.