QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines

Understand

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 novel 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.