European Physical Society Conference on High Energy Physics (EPS-HEP)

Track reconstruction of charged particles using a 4D quantum algorithm

David Spataro, Federico Meloni, Y. C. Yap

Published Jan 19, 2024• 0 citations

Abstract

Particle track reconstruction plays a crucial role in the exploration of new physical phenomena, particularly when rare signal tracks are obscured by a significant background. In muon colliders where beam muons interacting with the detector produce secondary and tertiary background par- ticles, track reconstruction can be computationally intensive due to the large number of detector hits. The formulation of the reconstruction task as quadratic unconstrained binary optimisation (QUBO) enables the use of quantum computers, which are believed to offer an advantage over classical computers in such optimisation scenarios. The QUBO parameters are determined by combining spatial and temporal information from detector hits, resulting in a 4D quantum al- gorithm. To demonstrate the effectiveness of this approach, the quantum algorithm is used to reconstruct signal tracks from samples consisting of Monte Carlo simulated charged particles overlaid with background hits for a Muon Collider tracking detector. We will present the obtained reconstruction performance and discuss possible paths for further improvements.

DOI: 10.22323/1.449.0560

Related papers

Particle Track Reconstruction with Quantum Algorithms

Cenk Tüysüz, Federico Carminati, Bilge Melahat Demirköz +6 more

Accurate determination of particle track reconstruction parameters will be a major challenge for the High Luminosity Large Hadron Collider (HL-LHC) experiments. The expected increase in the number of simultaneous collisions at the HL-LHC and the resulting high detector occupancy will make track reconstruction algorithms extremely demanding in terms of time and computing resources. The increase in number of hits will increase the complexity of track reconstruction algorithms. In addition, the ambiguity in assigning hits to particle tracks will be increased due to the finite resolution of the detector and the physical “closeness” of the hits. Thus, the reconstruction of charged particle tracks will be a major challenge to the correct interpretation of the HL-LHC data. Most methods currently in use are based on Kalman filters which are shown to be robust and to provide good physics performance. However, they are expected to scale worse than quadratically. Designing an algorithm capable of reducing the combinatorial background at the hit level, would provide a much “cleaner” initial seed to the Kalman filter, strongly reducing the total processing time. One of the salient features of Quantum Computers is the ability to evaluate a very large number of states simultaneously, making them an ideal instrument for searches in a large parameter space. In fact, different R&D initiatives are exploring how Quantum Tracking Algorithms could leverage such capabilities. In this paper, we present our work on the implementation of a quantum-based track finding algorithm aimed at reducing combinatorial background during the initial seeding stage. We use the publicly available dataset designed for the kaggle TrackML challenge.

arXiv:2003.08126EPJ Web of ConferencesJan 1, 202029 citations

Quantum-Annealing-Inspired Algorithms for Track Reconstruction at High-Energy Colliders

H. Okawa, Q. Zeng, Xian-Zhe Tao +1 more

Abstract Charged particle reconstruction or track reconstruction is one of the most crucial components of pattern recognition in high-energy collider physics. It is known to entail enormous consumption of computing resources, especially when the particle multiplicity is high, which will be the conditions at future colliders, such as the High Luminosity Large Hadron Collider and Super Proton–Proton Collider. Track reconstruction can be formulated as a quadratic unconstrained binary optimization (QUBO) problem, for which various quantum algorithms have been investigated and evaluated with both a quantum simulator and hardware. Simulated bifurcation algorithms are a set of quantum-annealing-inspired algorithms, known to be serious competitors to other Ising machines. In this study, we show that simulated bifurcation algorithms can be employed to solve the particle tracking problem. The simulated bifurcation algorithms run on classical computers and are suitable for parallel processing and usage of graphical processing units, and they can handle significantly large amounts of data at high speed. These algorithms exhibit reconstruction efficiency and purity comparable to or sometimes improved over those of simulated annealing, but the running time can be reduced by as much as four orders of magnitude. These results suggest that QUBO models together with quantum-annealing-inspired algorithms are valuable for current and future particle tracking problems.

arXiv:2402.14718Computing and Software for Big ScienceAug 28, 20246 citations

Particle track reconstruction with noisy intermediate-scale quantum computers

Tim Schwägerl, Ç. İşsever, Karl Jansen +4 more

Abstract The reconstruction of trajectories of charged particles is a key computational challenge for current and future collider experiments. Considering the rapid progress in quantum computing, it is crucial to explore its potential for this and other problems in high-energy physics. The problem can be formulated as a quadratic unconstrained binary optimization (QUBO) and solved using the variational quantum eigensolver (VQE) algorithm. In this work the effects of dividing the QUBO into smaller sub-QUBOs that fit on the hardware available currently or in the near term are assessed. Then, the performance of the VQE on small sub-QUBOs is studied in an ideal simulation, using a noise model mimicking a quantum device and on IBM quantum computers. This work serves as a proof of principle that the VQE could be used for particle tracking and investigates modifications of the VQE to make it more suitable for combinatorial optimization.

arXiv:2303.13249Journal of Physics Conference SeriesApr 1, 20264 citations

A Quantum Computing Approach to Track Reconstruction in Strip-Type Detectors

Seungyeob Jwa, Hyunyong Kim, Jangho Kim +1 more

This study investigates the use of quantum annealing for particle track reconstruction in strip-type gaseous detectors. In such detectors, ghost hits and multiple hit combinations can turn pattern recognition into a combinatorial optimization problem. We formulate two reconstruction subproblems as quadratic unconstrained binary optimization problems. The first subproblem selects detector hits associated with a single photon track inside a localized candidate region. The second subproblem selects cluster triplets from different detector layers so that multiple track candidates can be handled within a single quantum processing unit(QPU) submission. The proposed formulations are tested using simulated DAMSA detector events. For the single track hit selection task, the QPU based reconstruction gives position and angular resolutions close to those obtained with a Kalman based reconstruction. In the simultaneous association task, valid cluster triplets are first extracted from the QPU samples and then connected using an association rule based on graph connectivity to construct track candidates. The DAMSA event topology studied here has low pileup and is dominated by the two photon signal from axion-like particle(ALP) decay. In this setting, the results show that the QUBO formulations can reproduce local reconstruction decisions. This provides a practical basis for further studies of reconstruction methods that combine quantum and classical computing in more complex tracking environments.

quant-pharXiv:2607.12821Jul 15, 20260 citations

Investigating Quantum Speedup for Track Reconstruction: Classical and Quantum Computational Complexity Analysis

Duarte Magano, Akshat Kumar, Mārtiņš Kālis +10 more

To investigate the fundamental nature of matter and its interactions, particles are accelerated to very high energies and collided inside detectors, producing a multitude of other particles that are scattered in all directions. As the charged particles traverse the detector, they leave signals of their passage. The problem of track reconstruction is to recover the original trajectories from these signals. This represents a very challenging data analysis problem, which will become even more demanding as the luminosity of future accelerators keeps increasing, leading to collision events with a more complex structure. Therefore, there is a pressing need to develop more efficient methods, capable of sieving through the vast amount of data produced by these machines, in order to find the extremely rare events that may contain the clues for new Physics. In light of these challenges, approaches to track reconstruction based on quantum computation have recently been put forward. In this work, we study track reconstruction from a computational complexity perspective. Namely, we analyse a standard algorithm for tracking, the Combinatorial Track Finder, in the asymptotic limit of infinitely many recorded particles. First, we show that it is possible to improve the classical algorithm in this regime. Then, we show how to use quantum search routines to reach a lower computational complexity. And - although the found quantum speed-up is modest and of limited practical advantage in finite scenarios - to the best of our knowledge this constitutes the first theoretical proof of a quantum advantage for a state-of-the-art track reconstruction method, which we hope can further inspire classical and quantum improvements to High-Energy Physics computational challenges.

Apr 23, 20210 citations

Quantum Algorithms for Charged Particle Track Reconstruction in the LUXE Experiment

Arianna Crippa, Lena Funcke, Tobias Hartung +8 more

The LUXE experiment is a new experiment in planning in Hamburg, which will study quantum electrodynamics at the strong-field frontier. LUXE intends to measure the positron production rate in this unprecedented regime using, among others, a silicon tracking detector. The large number of expected positrons traversing the sensitive detector layers results in an extremely challenging combinatorial problem, which can become computationally expensive for classical computers. This paper investigates the potential future use of gate-based quantum computers for pattern recognition in track reconstruction. Approaches based on a quadratic unconstrained binary optimisation and a quantum graph neural network are investigated in classical simulations of quantum devices and compared with a classical track reconstruction algorithm. In addition, a proof-of-principle study is performed using quantum hardware.

arXiv:2304.01690Jan 1, 20233 citations