  Quantum Approximate Optimization Algorithm (QAOA) is a promising hybrid
quantum-classical algorithm for solving combinatorial optimization problems.
However, it cannot overcome qubit limitation for large-scale problems.
Furthermore, the execution time of QAOA scales exponentially with the problem
size. We propose a Divide-and-Conquer QAOA (DC-QAOA) to address the above
challenges for graph maximum cut (MaxCut) problem. The algorithm works by
recursively partitioning a larger graph into smaller ones whose MaxCut
solutions are obtained with small-size NISQ computers. The overall solution is
retrieved from the sub-solutions by applying the combination policy of quantum
state reconstruction. Multiple partitioning and reconstruction methods are
proposed/ compared. DC-QAOA achieves 97.14% approximation ratio (20.32% higher
than classical counterpart), and 94.79% expectation value (15.80% higher than
quantum annealing). DC-QAOA also reduces the time complexity of conventional
QAOA from exponential to quadratic.
