Future colliders such as the HL-LHC and Circular Electron Positron Collider (CEPC) will require enormous computing resources and bring us to the “exabyte” data era. At the HL-LHC, annual computing costs are expected to increase by a factor of 10 to 20 from the current LHC. Track reconstruction is the most computing-consuming reconstruction task and innovations are eagerly awaited to overcome this challenge. Recently, a research team led by Prof. Hideki Okawa at the Institute of High Energy Physics of the Chinese Academy of Sciences and Prof. Man-Hong Yung from the Shenzhen Institute for Quantum Science and Engineering has succeeded in applying novel quantum-annealing-inspired algorithms to track reconstruction under the High Luminosity Large Hadron Collider (HL-LHC) conditions and achieved 10,000 speed-up. This work, “Quantum-Annealing-Inspired Algorithms for Track Reconstruction at High-Energy Colliders”, was published in Springer Computing and Software for Big Science on Aug 28, 2024 (H Okawa, QG Zeng, XZ Tao, MH Yung, Comput. Softw. Big Sci. 8 (2024) 16).

In physics, annealing refers to a process of heating and gradually cooling materials, by which the atoms inside the materials will be arranged more orderly, thereby reducing their energy level. Similarly, in computation, we can use an algorithm called "simulated annealing" to solve optimization problems. Simulated annealing emulates the physical annealing process to gradually approach the ground state of the system, thereby finding the optimal solution to the problem. The corresponding process in quantum annealing refers to the evolution from one Hamiltonian system to another. The quantum adiabatic theorem ensures that if this process proceeds slowly enough, the eigenstates of the system will not change. From this, we can obtain the ground state of complex systems by preparing the ground state of simple systems. Quantum-annealing-inspired algorithms are developed stimulated by the ideas from quantum computing but "implemented on classical hardware". Specifically, the simulated bifurcation (SB), provides promising performance in solving combinatorial optimization problems in a short period of time, and can solve track reconstruction problems with thousands of particle in less than one second (with the spin numbers exceeding 100,000 after being transformed into Ising problems).

Being quantum-inspired but “classical” algorithms, SB has no limitation on the “number of bits” and can directly handle ultra-large-scale (the number of bits can reach hundreds of millions) datasets. Furthermore, unlike simulated annealing, SB can run on CPUs and is also suitable for parallel acceleration using GPUs and FPGAs. On the other hand, due to its inherent limitations, simulated annealing can only update spins serially and is unsuitable for parallel processing. Ballistic SB (bSB), a variant of SB algorithms, brings in approximately 10,000 times speed-up (Figure 1) compared to Neal, a Python library that implements simulated annealing for the highest track multiplicity conditions at the HL-LHC (Figure 2) and provides excellent reconstruction efficiency and purity.

This novel quantum-inspired method is a new technology for the future. It can be applied not only to currently operating colliders, such as the LHC and Beijing Spectrometer III at Beijing Electron-Positron Collider II, but is also expected to be applied to larger-scale future colliders.

Paper link: https://doi.org/10.1007/s41781-024-00126-z

Figure 1: Evolution of Ising energies in the highest particle multiplicity event (9435 particles, the number of spins after conversion to the Ising problem is 109,498) evaluated for the three quantum-annealing-inspired algorithms. The solid lines indicate the average from the 50 shots, whereas the envelopes represent the best and worst cases among these shots.

Figure 2: Display of the highest particle multiplicity event considered in the study. The green (red) lines indicate correctly (incorrectly) reconstructed tracks, whereas the blue lines are those not reconstructed. This display is generated with the hepqpr-qallse framework.