# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 2 Materials and Methods
### Dualization and Unitary Circuit Depth  
Previously [14], we considered the method of dualizing constraints to solve CO problems of the form  
\[\min\ c(x) \tag{1}\] \[\text{s.t. }p_{i}(x)\leq b_{i} \forall i\in P\] (2) \[x\in\{0,1\}^{n} \tag{3}\]  
where \(p_{i}\) is contained in the collection of polynomial constraints \(P\). Both \(p_{i}\) and \(c\) are polynomial functions in \(\mathbb{R}^{n}[x_{1},x_{2},...,x_{n}]\) and \(b_{i}\in\mathbb{R}\). We eliminate constraints via dualization by subtracting \(b_{i}\) from both sides, adding in slack variables, squaring both sides, and adding the new expression to the objective function [14]. The _derived (hyper)graph_ from dualization is one in which there is a vertex for each variable and (hyper)edges between variables that appear in a monomial together. For example, if \(x_{1}x_{2}\) appears in the dualization, there is an edge between vertices \(x_{1}\) and \(x_{2}\).  
In graph theory, a proper edge coloring of a graph is a function \(f:E(G)\rightarrow[k]\) such that if two edges share a vertex, they receive different values, e.g., \(uv\) and \(xv\), \(f(uv)\
eq f(xv)\). Given the set \([k]=\{1,...,k\}\), each element of this set can be thought of as a color, hence the name edge coloring. The smallest number \(m\) such that a proper edge coloring of a graph \(G\) is possible with \(m\) colors is denoted \(\chi^{\prime}(G)\) and called either the chromatic index or the edge chromatic number. It has been shown that chromatic index of the derived (hyper)graph is directly related to the unitary circuit depth of one iteration of QAOA, if the size of each monomial in the objective function is at most the gate size the hardware can support [14]. In particular, the following theorem holds:  
Theorem 1: _Let \(H\) be the hypergraph derived from a combinatorial optimization problem instance. Every proper edge coloring of \(H\) corresponds to a valid circuit for a PUBO, where the unitary depth of the shallowest circuit is \(\chi^{\prime}(H)+1\)._  
Unitary Circuit Depth Example: MaxCut  
We will consider MaxCut as an example for how to construct a quantum circuit with minimal unitary depth. This process applies when determining the unitary circuit depth for QAOA to solve a general combinatorial optimization problem. Consider the triangle graph, which consists of three vertices that are pairwise adjacent, as seen in Figure 1. In the combinatorial optimization problem MaxCut, the vertices of a graph, \(G=(V,E)\), are partitioned into two sets such that the number of edges with an end point in each set is maximized. This problem can be formulated as  
\[\min_{x\in\{0,1\}^{n}}\sum_{ij\in E(G)}x_{j}(x_{i}-1)+x_{i}(x_{j}-1)=\min_{x \in\{0,1\}^{n}}\sum_{ij\in E(G)}2x_{i}x_{j}-x_{i}-x_{j}\]  
In order to solve MaxCut on the triangle graph, we want to minimize  
\[2(x_{1}x_{2}+x_{1}x_{3}+x_{2}x_{3})-2(x_{1}+x_{2}+x_{3}).\]  
There are three vertices in the derived graph for this function, namely \(x_{1},x_{2}\) and \(x_{3}\). There are also three edges, which are \(x_{1}x_{2}\), \(x_{1}x_{3}\), and \(x_{2}x_{3}\). Thus, the derived graph for this combinatorial optimization problem is also a triangle. To calculate the unitary circuit depth, we will properly edge color this graph in Figure 2. This graph requires three colors to be properly edge colored. Since each edge color class must be implemented in series, the unitary circuit depth is four, which is seen in Figure 3.  
Figure 1: A triangle graph.