Quantum algorithms for jet clustering

Abstract

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.