论文标题
用于社区发现及其经验跑步时的量子算法
Quantum Algorithms for Community Detection and their Empirical Run-times
论文作者
论文摘要
我们将最近的工作应用于对量子加速的经验估计，将其用于复杂网络中社区检测的实际任务。我们设计了一种流行的古典算法（用于社区检测的Louvain算法）的几种量子变体，并首先以通常的方式研究它们的复杂性，然后在各种人工和真实的投入中对其复杂性进行经验分析。我们发现，这种分析可以通过渐近分析获得我们无法获得的见解，从而进一步强调了这种经验方法的实用性。特别是，我们观察到，具有较大渐近速度的复杂量子算法可能不是最快的算法，并且具有适度速度的简单量子算法实际上可能是表现最佳的算法。此外，我们反复发现，诸如需要扩大量子子程序的成功概率（例如Grover搜索）的成功概率，例如Grover Search产生的开销可能会消除理论上最坏情况或期望分析可能提出的任何加速。
We apply our recent work on empirical estimates of quantum speedups to the practical task of community detection in complex networks. We design several quantum variants of a popular classical algorithm -- the Louvain algorithm for community detection -- and first study their complexities in the usual way, before analysing their complexities empirically across a variety of artificial and real inputs. We find that this analysis yields insights not available to us via the asymptotic analysis, further emphasising the utility in such an empirical approach. In particular, we observe that a complicated quantum algorithm with a large asymptotic speedup might not be the fastest algorithm in practice, and that a simple quantum algorithm with a modest speedup might in fact be the one that performs best. Moreover, we repeatedly find that overheads such as those arising from the need to amplify the success probabilities of quantum sub-routines such as Grover search can nullify any speedup that might have been suggested by a theoretical worst- or expected-case analysis.
