  The quantum approximate optimization algorithm (QAOA) has the potential to
approximately solve complex combinatorial optimization problems in polynomial
time. However, current noisy quantum devices cannot solve large problems due to
hardware constraints. In this work, we develop an algorithm that decomposes the
QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on
the reduced graph. The algorithm requires a subroutine that can be classical or
quantum--in this work, we implement the algorithm twice on each graph. One
implementation uses the classical solver Gurobi in the subroutine and the other
uses QAOA. We solve these reduced problems with QAOA. On average, the reduced
problems require only approximately 1/10 of the number of vertices than the
original MaxCut instances. Furthermore, the average approximation ratio of the
original MaxCut problems is 0.75, while the approximation ratios of the
decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this
decomposition, we are able to measure optimal solutions for ten 100-vertex
graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion
quantum computer H1-1, sampling each circuit only 500 times. This approach is
best suited for sparse, particularly $k$-regular graphs, as $k$-regular graphs
on $n$ vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$
vertices in polynomial time. Further reductions can be obtained with a
potential trade-off in computational time. While this paper applies the
decomposition method to the MaxCut problem, it can be applied to more general
classes of combinatorial optimization problems.
