Mar 10 – 15, 2019
Steinmatte conference center
Europe/Zurich timezone

Charged Particle Tracking as a QUBO problem solved with Quantum Annealing-Inspired Optimization

Mar 11, 2019, 5:10 PM
Steinmatte Room A

Steinmatte Room A

Oral Track 2: Data Analysis - Algorithms and Tools Track 2: Data Analysis - Algorithms and Tools


Dr Jean-Roch Vlimant (California Institute of Technology (US))


With the upgrade of the LHC to high luminosity, an increased rate of collisions will place a higher computational burden on track reconstruction algorithms. Typical algorithms such as the Kalman Filter and Hough-like Transformation scale worse than quadratically. However, the energy function of a traditional method for tracking, the geometric Denby-Peterson (Hopfield) network method, can be described as a quadratic unconstrained binary optimization (QUBO) problem. Quantum annealers have shown shown promise in their ability to solve QUBO problems despite being NP-hard. We present a novel approach for track reconstruction by applying a quantum annealing-inspired algorithm to the Denby-Peterson method. We propose additional techniques to divide an LHC event into disjoint subgraphs in order to allow the problem to be embeddable on existing quantum annealing hardware, using multiple anneals to fit tracks to a single event. To accommodate this dimension reduction, we use Bayesian methods and further algorithms to pre- and post-process the data. Results on the TrackML dataset are presented, demonstrating the successful application of quantum annealing-inspired algorithms to the track reconstruction problem.

Primary authors

Alexander Zlokapa (California Institute of Technology (US)) Dr Jean-Roch Vlimant (California Institute of Technology (US)) Abhishek Anand (California Institute of Technology) Prof. Daniel Lidar (USC) Maria Spiropulu (California Institute of Technology) Dr Joshua Job (USC)

Presentation materials