# Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
## 4 Discussion  
In this paper, we analyze an approach to minimizing the unitary circuit depth of the quantum approximate optimization algorithm by expressing general combinatorial optimization problems in varying forms. We compare a linear formulation that is the natural choice in conventional optimization algorithms with a product formulation that we posit as natural for QAOA. The product formulation leads to monomials in more than two variables, which cannot be directly implemented on a quantum computer with two qubit gates. Thus, we introduce the global variable substitution method to decompose them into two variable terms which can be implemented on a quantum computer with two qubit gates. For each of these formulations, we analytically compute the unitary circuit depth in terms of the maximum degree of a graph derived from the problem instance and formulation. We demonstrate that the product formulation gives shallower circuits then the linear formulation for benchmark 3-SAT problems. The global variable substitution requires constraints that must be satisfied in order to obtain the optimal solution, as does the linear formulation. We can derive graphs for the linear and product formulations from the objective function and the appropriate constraints. The unitary circuit depth is directly related to the maximum degree of the derived graph. We evaluate the unitary circuit depth of the product formulation with global variable substitutions by writing an integer program that computes the minimal unitary circuit depth of the linear formulation and product formulation for a collection of benchmark problems. In all cases, the product formulation gives unitary circuit depth roughly half that of the linear formulation. The linear formulation for 3-SAT requires exactly three ancillary qubits per clause, where the product formulation requires four per substitution, although substitutions can sometimes be reused to reduce the number of ancillary qubits. We find several additional interesting features of the approach. We find that minimizing the number of substitutions per problem instance does not necessarily minimize the maximum degree. For example, when solving \"uf-100-430\", the covering heuristic makes 329 substitutions for a maximum degree of 60, whereas the IP makes 330 substitutions for a maximum degree of 46. We also note that the objective function for the IP can be modified to limit the number of substitutions. While this may drive up the degree of vertices, it also reduces the number of ancillary qubits, as each substitution requires four additional qubits. Thus, the problem formulation can be changed to accommodate different hardware. The focus of this work has been on using the product formulation of 3-SAT instances to minimize QAOA unitary circuit depth relative to a conventional linear formulation. Extending the analysis of linear and product formulations to more general problems will help determine additional types of problems that benefit from this approach. Additionally, there may be other formulations for specific problems that result in shallower circuits than the linear or product formulations. While the product formulation with GVS gives shallower circuits for 3-SAT, future work should determine if the reformulation gives a comparable outcome to the linear formulation in the same number of QAOA iterations. A final note is that the global variable substitution method can be used to rewrite problems in terms of gates acting on \(m\) qubits. If more general gates become available on quantum computers, then a similar analysis could lead to new approaches for minimizing depth. Conceptualization, R.H., L.T., J.O., P.C.L., T.S.H. and G.S. ; methodology, R.H., L.T. and J.O. ; software, R.H., L.T. and J.O. ; validation, R.H., L.T., J.O., P.C.L., T.S.H. and G.S. ; formal analysis, R.H., L.T., J.O., P.C.L., T.S.H. and G.S. ; investigation, R.H., L.T., J.O., P.C.L., T.S.H. and G.S. ; resources, R.H., L.T., J.O., P.C.L., T.S.H. and G.S. ; writing--original draft preparation, R.H., L.T. and J.O.