Reproduce “ParaQAOA: Efficient Parallel Divide-and-Conquer QAOA for Large-Scale Max-Cut Problems Beyond 10,000 Vertices” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Po-Hsuan Huang, Xie-Ru Li, Chi Chuang, Chia-Heng Tu, Shih-Hao Hung

Researchers from National Taiwan University and National Cheng Kung University introduced ParaQAOA, a parallel divide-and-conquer framework for large-scale Max-Cut problems, enabling solutions for graphs beyond 10,000 vertices with up to 2,000x speedup over previous QAOA methods. The framework balances solution quality and execution time through tunable parameters and includes a novel performance evaluation metric.

Key insights

  • An efficient, linear-time graph partitioning algorithm is crucial for overcoming preprocessing bottlenecks in divide-and-conquer QAOA, enabling scalability to very large graphs.
  • Leveraging multi-GPU for subgraph QAOA execution and multi-core CPUs for parallel merging substantially improves overall runtime efficiency for hybrid quantum-classical algorithms.
  • Tunable parameters (K for selective bitstring retention and L for merge parallelism) provide systematic control over the trade-off between solution quality and computational efficiency.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.