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 jet-like 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.

arXiv comment21 pages, 1 table, 6 figures. v2: correction to doubling trick and additional discussion of resource requirements; approximate version to appear in PRD

References in corpus (46)

• PYTHIA 6.4 Physics and Manual
• PYTHIA 6.2 Physics and Manual
• Quantum Computing in the NISQ era and beyond
• The anti-k_t jet clustering algorithm
• An Introduction to PYTHIA 8.2
• FastJet user manual
• Elementary gates for quantum computation
• Quantum Annealing in the Transverse Ising Model
• Dispelling the N^3 myth for the Kt jet-finder
• Quantum random access memory
• Identifying Boosted Objects with N-subjettiness
• Quantum annealing with more than one hundred qubits
• Quantum Networks for Elementary Arithmetic Operations
• The Catchment Area of Jets
• Towards Jetography
• N-Jettiness: An Inclusive Event Shape to Veto Jets
• Maximizing Boosted Top Identification by Minimizing N-subjettiness
• A Quantum Algorithm for Finding the Minimum
• Halving the cost of quantum addition
• A practical Seedless Infrared-Safe Cone jet algorithm
• Studies of Hadronic Event Structure in e+e- Annihilation from 30 GeV to 209 GeV with the L3 Detector
• A quantum algorithm for high energy physics simulations
• The Metric Space of Collider Events
• Measurement of event shape distributions and moments in e+e- -> hadrons at 91-209 GeV and a determination of alpha_s
• A study of the energy evolution of event shape distributions and their means with the DELPHI detector at LEP
• Quantum Annealing for Combinatorial Clustering
• Measurement of alpha_s(M_Z^2) from Hadronic Event Observables at the Z^0 Resonance
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• XCone: N-jettiness as an Exclusive Cone Jet Algorithm
• Quantum speedup of branch-and-bound algorithms
• On Building Better Cone Jet Algorithms
• Resolving Boosted Jets with XCone
• Quantum adiabatic machine learning with zooming
• Cutting Multiparticle Correlators Down to Size
• Towards a standard jet definition
• Jet reconstruction in hadronic collisions by Gaussian filtering
• Optimal Jet Finder
• Quantum Associative Memory in HEP Track Pattern Recognition
• A new jet algorithm based on the k-means clustering for the reconstruction of heavy states from jets
• Fuzzy Jets
• Deterministic Annealing as a jet clustering algorithm in hadronic collisions
• Jet analysis by Deterministic Annealing
• FFTJet: A Package for Multiresolution Particle Jet Reconstruction in the Fourier Domain
• Separated at Birth: Jet Maximization, Axis Minimization, and Stable Cone Finding
• Quantum-assisted cluster analysis
• The Georgi Algorithms of Jet Clustering

Cited by in corpus (45)

• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Quantum simulation of non-equilibrium dynamics and thermalization in the Schwinger model
• Quantum Machine Learning for Particle Physics using a Variational Quantum Classifier
• Ultra-High-Energy Cosmic Rays: The Intersection of the Cosmic and Energy Frontiers
• Event Classification with Quantum Machine Learning in High-Energy Physics
• Quantum simulation of open quantum systems in heavy-ion collisions
• Quantum Computing for Quantum Tunnelling
• Towards a Quantum Computing Algorithm for Helicity Amplitudes and Parton Showers
• Linearized Optimal Transport for Collider Events
• Medium induced jet broadening in a quantum computer
• Quantum Science and the Search for Axion Dark Matter
• Quantum algorithm for Feynman loop integrals
• Quantum integration of elementary particle processes
• Selected topics of quantum computing for nuclear physics
• Collider Events on a Quantum Computer
• Quantum speedup for track reconstruction in particle accelerators
• The Efficacy of Event Isotropy as an Event Shape Observable
• Cutting Multiparticle Correlators Down to Size
• Quantum Annealing for Jet Clustering with Thrust
• Adiabatic Quantum Algorithm for Multijet Clustering in High Energy Physics
• Opening the Black Box Inside Grover's Algorithm
• Quantum Amplitude Amplification Operators
• Fitting a Collider in a Quantum Computer: Tackling the Challenges of Quantum Machine Learning for Big Datasets
• Efficient Quantum Simulation of QCD Jets on the Light Front
• A Digital Quantum Algorithm for Jet Clustering in High-Energy Physics
• Track clustering with a quantum annealer for primary vertex reconstruction at hadron colliders
• A Quantum Algorithm for Model-Independent Searches for New Physics
• A Novel Quantum Realization of Jet Clustering in High-Energy Physics Experiments
• Reconstructing charged particle track segments with a quantum-enhanced support vector machine
• Loop Feynman integration on a quantum computer
• Unsupervised Event Classification with Graphs on Classical and Photonic Quantum Computers
• Initial-State Dependent Optimization of Controlled Gate Operations with Quantum Computer
• Quantum computation in fermionic thermal field theories
• Quantum integration of decay rates at second order in perturbation theory
• Quantum jet clustering with LHC simulated data
• Quantum simulation of quantum mechanical system with spatial noncommutativity
• Quantum-annealing-inspired algorithms for multijet clustering
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Quantum clustering and jet reconstruction at the LHC
• Quantum algorithm for unstructured search of ranked targets
• Semi-Inclusive Jet Functions and Jet Substructure in $J_{E_T}^{(I)}$ and $J_{E_T}^{(II)}$ Algorithms
• Leveraging Quantum Annealer to identify an Event-topology at High Energy Colliders
• Energy Flow in Particle Collisions
• Quantum Chebyshev Probabilistic Models for Fragmentation Functions
• Quantum Gate Pattern Recognition and Circuit Optimization for Scientific Applications