Quantum algorithms for jet clustering

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\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\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.

Figure 1

Two equivalent definitions of thrust as (left) a partitioning problem and (right) an axis-finding problem. The best known classical algorithm is based on plane partitioning via a reference axis $\widehat{r}$ (which in general differs from the thrust axis).

Figure 2

Illustration of the sorting algorithm around the ${\overrightarrow{p}}_i$ axis (seen from the top down). The dashed vectors correspond to the doubling trick. As the blue partitioning plane sweeps in azimuth, the hemisphere momentum is updated according to Eq. (30).

Figure 3

Quantum search algorithm due to Dürr-Høyer to find the index corresponding to the maximum entry of an array $A[i]$ with $K$ elements [11]. The number of Grover steps is chosen at random, since this is a search over an unknown number of marked times [10].

Figure 4

Our Grover-based quantum thrust algorithm, written in terms of the abstract LOOKUP and SUM operations. The symbols $|\overrightarrow{0}⟩$, $|\widehat{0}⟩$, and $|0⟩$ refer to initial states for a three-momentum, normalized axis, and real number, respectively. Note that we have applied the doubling trick from Sec. 3b, such that each $\overrightarrow{p_k}$ has its negative $-\overrightarrow{p_k}$ in the set of three-momenta. Cases where ${\widehat{r}}_{ij}·{\overrightarrow{p}}_k=0$ are treated implicitly via Eq. (26). A key difference compared to Fig. 3 is that the quantity to maximize, $T_{ij}$, is calculated quantumly via the comp_t subroutine.

Figure 5

An example loading circuit mapping $|i⟩|0⟩|0⟩\mapsto |i⟩|0⟩|x_i⟩$. In our example, $i=i_1{i}_0$ is two bits and $(x_0,x_1,x_2,x_3)=(3,2,3,1)$. The ccnot gates are drawn with open (closed) circles if they are controlled on the source bit being zero (one).

Figure 6

Partitioning an event into a stable cone jet of radius $R$ and an unclustered region. This is the same as Fig. 1 when $R=\pi /2$.