© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2402.14718 · Computing and Software for Big Science

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

H. Okawa, Q. Zeng, Xian-Zhe Tao, Man‐Hong Yung

Published Aug 28, 2024• 6 citations

Abstract

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.

DOI: 10.1007/s41781-024-00126-z

Related papers

A Pattern Recognition Algorithm for Quantum Annealers

Frédéric Bapst, W. Bhimji, P. Calafiura +4 more

Abstract The reconstruction of charged particles will be a key computing challenge for the high-luminosity Large Hadron Collider (HL-LHC) where increased data rates lead to a large increase in running time for current pattern recognition algorithms. An alternative approach explored here expresses pattern recognition as a quadratic unconstrained binary optimization (QUBO), which allows algorithms to be run on classical and quantum annealers. While the overall timing of the proposed approach and its scaling has still to be measured and studied, we demonstrate that, in terms of efficiency and purity, the same physics performance of the LHC tracking algorithms can be achieved. More research will be needed to achieve comparable performance in HL-LHC conditions, as increasing track density decreases the purity of the QUBO track segment classifier.

arXiv:1902.08324•Computing and Software for Big Science•Dec 9, 2019•48 citations

Charged particle tracking with quantum annealing optimization

Alexander Zlokapa, Abhishek Anand, Jean-Roch Vlimant +4 more

Abstract At the High Luminosity Large Hadron Collider (HL-LHC), traditional track reconstruction techniques that are critical for physics analysis will need to be upgraded to scale with track density. Quantum annealing has shown promise in its ability to solve combinatorial optimization problems amidst an ongoing effort to establish evidence of a quantum speedup. As a step towards exploiting such potential speedup, we investigate a track reconstruction approach by adapting the existing geometric Denby-Peterson (Hopfield) network method to the quantum annealing framework for HL-LHC conditions. We develop additional techniques to embed the problem onto existing and near-term quantum annealing hardware. Results using simulated annealing and quantum annealing with the D-Wave 2X system on the TrackML open dataset are presented, demonstrating the successful application of a quantum annealing algorithm to the track reconstruction challenge. We find that combinatorial optimization problems can effectively reconstruct tracks, suggesting possible applications for fast hardware-specific implementations at the HL-LHC while leaving open the possibility of a quantum speedup for tracking.

arXiv:1908.04475•Quantum Machine Intelligence•Nov 2, 2021•40 citations

Quantum annealing algorithms for track pattern recognition

M. Saito, P. Calafiura, Heather M. Gray +7 more

The High-Luminosity Large Hadron Collider (HL-LHC) starts from 2027 to extend the physics discovery potential at the energy frontier. The HL-LHC produces experimental data with a much higher luminosity, requiring a large amount of computing resources mainly due to the complexity of a track pattern recognition algorithm. Quantum annealing might be a solution for an efficient track pattern recognition in the HL-LHC environment. We demonstrated to perform the track pattern recognition by using the D-Wave annealing machine and the Fujitsu Digital Annealer. The tracking efficiency and purity for the D-Wave quantum annealer are comparable with those for a classical simulated annealing at a low pileup condition, while a drop in performance is found at a high pileup condition, corresponding to the HL-LHC pileup environment. The tracking efficiency and purity for the Fujitsu Digital Annealer are nearly the same as the classical simulated annealing.

EPJ Web of Conferences•Jan 1, 2020•9 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.13249•Journal of Physics Conference Series•Apr 1, 2026•4 citations

Quantum pattern recognition algorithms for charged particle tracking

Heather M. Gray

High-energy physics is facing a daunting computing challenge with the large datasets expected from the upcoming High-Luminosity Large Hadron Collider in the next decade and even more so at future colliders. A key challenge in the reconstruction of events of simulated data and collision data is the pattern recognition algorithms used to determine the trajectories of charged particles. The field of quantum computing shows promise for transformative capabilities and is going through a cycle of rapid development and hence might provide a solution to this challenge. This article reviews current studies of quantum computers for charged particle pattern recognition in high-energy physics. This article is part of the theme issue 'Quantum technologies in particle physics'.

Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Dec 20, 2021•11 citations

Track reconstruction of charged particles using a 4D quantum algorithm

David Spataro, Federico Meloni, Y. C. Yap

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.

European Physical Society Conference on High Energy Physics (EPS-HEP)•Jan 19, 2024•0 citations

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.

Abstract The reconstruction of charged particles will be a key computing challenge for the high-luminosity Large Hadron Collider (HL-LHC) where increased data rates lead to a large increase in running time for current pattern recognition algorithms. An alternative approach explored here expresses pattern recognition as a quadratic unconstrained binary optimization (QUBO), which allows algorithms to be run on classical and quantum annealers. While the overall timing of the proposed approach and its scaling has still to be measured and studied, we demonstrate that, in terms of efficiency and purity, the same physics performance of the LHC tracking algorithms can be achieved. More research will be needed to achieve comparable performance in HL-LHC conditions, as increasing track density decreases the purity of the QUBO track segment classifier.

Abstract At the High Luminosity Large Hadron Collider (HL-LHC), traditional track reconstruction techniques that are critical for physics analysis will need to be upgraded to scale with track density. Quantum annealing has shown promise in its ability to solve combinatorial optimization problems amidst an ongoing effort to establish evidence of a quantum speedup. As a step towards exploiting such potential speedup, we investigate a track reconstruction approach by adapting the existing geometric Denby-Peterson (Hopfield) network method to the quantum annealing framework for HL-LHC conditions. We develop additional techniques to embed the problem onto existing and near-term quantum annealing hardware. Results using simulated annealing and quantum annealing with the D-Wave 2X system on the TrackML open dataset are presented, demonstrating the successful application of a quantum annealing algorithm to the track reconstruction challenge. We find that combinatorial optimization problems can effectively reconstruct tracks, suggesting possible applications for fast hardware-specific implementations at the HL-LHC while leaving open the possibility of a quantum speedup for tracking.

The High-Luminosity Large Hadron Collider (HL-LHC) starts from 2027 to extend the physics discovery potential at the energy frontier. The HL-LHC produces experimental data with a much higher luminosity, requiring a large amount of computing resources mainly due to the complexity of a track pattern recognition algorithm. Quantum annealing might be a solution for an efficient track pattern recognition in the HL-LHC environment. We demonstrated to perform the track pattern recognition by using the D-Wave annealing machine and the Fujitsu Digital Annealer. The tracking efficiency and purity for the D-Wave quantum annealer are comparable with those for a classical simulated annealing at a low pileup condition, while a drop in performance is found at a high pileup condition, corresponding to the HL-LHC pileup environment. The tracking efficiency and purity for the Fujitsu Digital Annealer are nearly the same as the classical simulated annealing.

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.

High-energy physics is facing a daunting computing challenge with the large datasets expected from the upcoming High-Luminosity Large Hadron Collider in the next decade and even more so at future colliders. A key challenge in the reconstruction of events of simulated data and collision data is the pattern recognition algorithms used to determine the trajectories of charged particles. The field of quantum computing shows promise for transformative capabilities and is going through a cycle of rapid development and hence might provide a solution to this challenge. This article reviews current studies of quantum computers for charged particle pattern recognition in high-energy physics. This article is part of the theme issue 'Quantum technologies in particle physics'.

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.