  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.
