Variational quantum algorithms such as the Quantum Approximation Optimization
Algorithm (QAOA) in recent years have gained popularity as they provide the
hope of using NISQ devices to tackle hard combinatorial optimization problems.
It is, however, known that at low depth, certain locality constraints of QAOA
limit its performance. To go beyond these limitations, a non-local variant of
QAOA, namely recursive QAOA (RQAOA), was proposed to improve the quality of
approximate solutions. The RQAOA has been studied comparatively less than QAOA,
and it is less understood, for instance, for what family of instances it may
fail to provide high quality solutions. However, as we are tackling
$\mathsf{NP}$-hard problems (specifically, the Ising spin model), it is
expected that RQAOA does fail, raising the question of designing even better
quantum algorithms for combinatorial optimization. In this spirit, we identify
and analyze cases where RQAOA fails and, based on this, propose a reinforcement
learning enhanced RQAOA variant (RL-RQAOA) that improves upon RQAOA. We show
that the performance of RL-RQAOA improves over RQAOA: RL-RQAOA is strictly
better on these identified instances where RQAOA underperforms, and is
similarly performing on instances where RQAOA is near-optimal. Our work
exemplifies the potentially beneficial synergy between reinforcement learning
and quantum (inspired) optimization in the design of new, even better
heuristics for hard problems.

设计出更好的用于组合优化的量子算法，结合强化学习增强递归 QAOA 表现，与传统 QAOA 相比，表现更好。