# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 1 Introduction  
The quantum approximate optimization algorithm (QAOA) was introduced to approximately solve combinatorial optimization problems [1, 2]. QAOA research has mostly focused on a small subset of combinatorial optimization (CO) problems such as MaxCut, MaxIndSet, and Max k-cover [3, 4, 5, 6, 7, 8, 9]. These problems can be easily written as quadratic unconstrained binary optimization (QUBO) problems by identifying each variable with a qubit. QUBOs are implementable on current hardware [10, 11]. Recent work has examined how QAOA can be used on CO problems that can be written as polynomial unconstrained binary optimization (PUBO) problems [12, 13]. When solving a CO problem using QAOA, each monomial in \(k\) vertices in the problem formulation corresponds to a \(k\) qubit gate. The unitary circuit depth for one layer of QAOA for combinatorial optimization problems was shown in [14] to be the edge chromatic number of the graph, or hypergraph, derived from these problems. Here the unitary circuit depth is the number of layers of one- and two-qubit unitary operators that are performed in series to implement the circuit. When the combinatorial optimization problem can be written as a QUBO, the derived graph is not a hypergraph, so the edge chromatic number is either the maximum degree, or the maximum degree plus one [15]. When the derived graph is a hypergraph, the edge chromatic number may be more difficult to compute.  
Some classes of combinatorial optimization problems, however, can be written in more than one way, where each formulation may have monomials of different sizes. For example,Boolean satisfiability problems (SAT) can be written as a QUBO or a more general PUBO. SAT problems have been studied extensively in a classical setting [16; 17] but there have been few studies into solving them in a quantum setting [18]. They form the backbone of complexity theory and can be written in a linear form, which requires two-qubit gates to implement, or a product form, which requires larger multi-qubit gates. Since these larger multi-qubit gates are not easily implementable on current hardware, polynomial formulations must be decomposed into sums of two variable monomials. We show in the context of 3-SAT that decomposing the PUBO can lead to a shallower circuit needing fewer qubits than using the natural QUBO formulation [14]. This has implications for more general combinatorial problems, as modeling approaches can have a significant impact on the design of the resulting circuit.  
In this paper, we first review QAOA, the classical linear and product formulations of SAT problems, and how they translate to QUBOs in Section 2. Then, in Section 2.5, we introduce a substitution method, called the global variable substitution (GVS) method, to decompose monomials consisting of \(k\geq 3\) variables into ones that can be implemented on current hardware. Next, we discuss how to optimize GVS for 3-SAT problems in Section 2.6 and then apply this work to instances from the SATLIB Benchmark Problems suite [19] in Section 3. Finally, we summarize the results and discuss future work in Section 4.