  We develop a global variable substitution method that reduces $n$-variable
monomials in combinatorial optimization problems to equivalent instances with
monomials in fewer variables. We apply this technique to $3$-SAT and analyze
the optimal quantum circuit depth needed to solve the reduced problem using the
quantum approximate optimization algorithm. For benchmark $3$-SAT problems, we
find that the upper bound of the circuit depth is smaller when the problem is
formulated as a product and uses the substitution method to decompose gates
than when the problem is written in the linear formulation, which requires no
decomposition.
