QAOA-in-QAOA: Solving Large-Scale MaxCut Problems on Small Quantum Machines

The design of fast algorithms for combinatorial optimization greatly contributes to a plethora of domains such as logistics, finance, and chemistry. Quantum approximate optimization algorithms (QAOAs), which utilize the power of quantum machines and inherit the spirit of adiabatic evolution, are approaches to tackle combinatorial problems with potential runtime speedups. However, hurdled by the limited quantum resources nowadays, QAOAs are infeasible to manipulate large-scale problems. To address this issue, here we revisit the MaxCut problem via the divide-and-conquer heuristic: seek the solutions of subgraphs in parallel and then merge these solutions to obtain the global solution. Because of the Z2 symmetry in MaxCut, we prove that the merging process can be further cast into a new MaxCut problem and thus be addressed by QAOAs or other MaxCut solvers. In view of this, we propose QAOA-in-QAOA (QAOA2) to solve arbitrary large-scale MaxCut problems using small quantum machines. We also prove that the performance of QAOA2 is lower bounded with respect to the divide-and-conquer process. Experiment results illustrate that, under different graph settings, QAOA2 attains a competitive or even better performance over classical algorithms when the node count is around 2000. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale combinatorial optimization problems.