Quantum algorithms for jet clustering
Quantum algorithms for jet clustering
复制标题
DOI：
10.1103/physrevd.101.094015
复制
发表时间：
2019-08
影响因子：
5
通讯作者：
Annie Y. Wei;P. Naik;A. Harrow;J. Thaler
中科院分区：
文献类型：
--
作者：
Annie Y. Wei;P. Naik;A. Harrow;J. Thaler
识别高能粒子碰撞中形成的喷流需要解决潜在的大量最终状态粒子的优化问题。在这项工作中，我们考虑使用量子计算机来加速射流聚类算法的可能性。专注于电子-正电子碰撞的情况下，我们认为一个著名的事件形状称为推力，其最佳对应于最jetlike分离平面之间的一组粒子，从而定义两个半球射流。我们将展示如何制定推力作为一个量子退火问题和格罗弗搜索问题。我们的分析的一个关键组成部分是考虑现实的模型接口的经典数据与量子算法。通过一个顺序计算模型，我们展示了如何将著名的$O（{N}^{3}）$经典算法加速到$O（{N}^{2}）$量子算法，包括从$N$个末态粒子加载经典数据的$O（N）$开销。沿着的方式，我们还确定了一种方法，以加快经典算法$O（{N}^{2}\mathrm{log}N）$使用排序策略的灵感来自siscone射流算法，它没有自然的量子对应物。在一个并行计算模型下，我们实现了经典和量子情形下的O（N log N）标度.最后，我们考虑这些量子方法的推广到其他射流算法更密切相关的质子-质子碰撞在大型强子对撞机。
Identifying jets formed in high-energy particle collisions requires solving optimization problems over potentially large numbers of final-state particles. In this work, we consider the possibility of using quantum computers to speed up jet clustering algorithms. Focusing on the case of electron-positron collisions, we consider a well-known event shape called thrust whose optimum corresponds to the most jetlike separating plane among a set of particles, thereby defining two hemisphere jets. We show how to formulate thrust both as a quantum annealing problem and as a Grover search problem. A key component of our analysis is the consideration of realistic models for interfacing classical data with a quantum algorithm. With a sequential computing model, we show how to speed up the well-known $O({N}^{3})$ classical algorithm to an $O({N}^{2})$ quantum algorithm, including the $O(N)$ overhead of loading classical data from $N$ final-state particles. Along the way, we also identify a way to speed up the classical algorithm to $O({N}^{2}\mathrm{log}N)$ using a sorting strategy inspired by the siscone jet algorithm, which has no natural quantum counterpart. With a parallel computing model, we achieve $O(N\mathrm{log}N)$ scaling in both the classical and quantum cases. Finally, we consider the generalization of these quantum methods to other jet algorithms more closely related to those used for proton-proton collisions at the Large Hadron Collider.