  With the rapid advancement of quantum computing, Quantum Approximate
Optimization Algorithm (QAOA) is considered as a promising candidate to
demonstrate quantum supremacy, which exponentially solves a class of Quadratic
Unconstrained Binary Optimization (QUBO) problems. However, limited qubit
availability and restricted coherence time challenge QAOA to solve large-scale
pseudo-Boolean problems on currently available Near-term Intermediate Scale
Quantum (NISQ) devices. In this paper, we propose a distributed QAOA which can
solve a general pseudo-Boolean problem by converting it to a simplified Ising
model. Different from existing distributed QAOAs' assuming that local solutions
are part of a global one, which is not often the case, we introduce community
detection using Louvian algorithm to partition the graph where subgraphs are
further compressed by community representation and merged into a higher level
subgraph. Recursively and backwards, local solutions of lower level subgraphs
are updated by heuristics from solutions of higher level subgraphs. Compared
with existing methods, our algorithm incorporates global heuristics into local
solutions such that our algorithm is proven to achieve a higher approximation
ratio and outperforms across different graph configurations. Also, ablation
studies validate the effectiveness of each component in our method.
