Apr 2 – 5, 2019
Jardí Botànic de València
Europe/Zurich timezone

QUBO for Track Reconstruction on D-Wave

Apr 3, 2019, 10:15 AM
Jardí Botànic de València

Jardí Botànic de València

Carrer Quart 80, 46008 València, Spain
Talk 1: Machine learning, algorithms and theoretical analysis


Lucy Linder (School of Engineering and Architecture of Fribourg (Switzerland), HES-SO, iCoSys Institute)


D-Wave Systems Quantum Annealer (QA) finds the ground state of a Hamiltonian expressed as:

$$ O(a;b;q)= \sum_{i=1}^{N} a_i q_i +\sum_i^{N} \sum_{j < i}^{N} b_{ij} q_i q_j $$
This Quantum Machine Instruction (QMI) is equivalent to a Quadratic Unconstrained Binary Optimization (QUBO) and can be transformed easily into an Ising model or a Hopfield network.

Following Stimpfl-Abele[1], we expressed the problem of classifying track seeds (doublets and triplets) as a QUBO, where the weights depend on physical properties such as the curvature, 3D orientation, and length.

We generated QUBOs that encode the pattern recognition problem at the LHC using the TrackML dataset[2] and solved them using qbsolv[3] and the D-Wave Leap Cloud Service[4]. Those early experiments achieved a performance in terms of purity, efficiency, and TrackML score that exceeds 95%.

Our goal is to develop a strategy appropriate for HL-LHC track densities by using techniques including improved seeding algorithms and geographic partitioning. We also plan to refine our model in order to reduce execution time and to boost performance.

[1] "Fast track finding with neural networks - ScienceDirect." 1 Apr. 1991, https://www.sciencedirect.com/science/article/pii/001046559190048P. Accessed 29 Oct. 2018.
[2] "TrackML Particle Tracking Challenge | Kaggle." 17 Jan. 2018, https://www.kaggle.com/c/trackml-particle-identification. Accessed 29 Oct. 2018.
[3] "Partitioning Optimization Problems for Hybrid Classical ... - D-Wave." 9 Jan. 2017, https://www.dwavesys.com/sites/default/files/partitioning_QUBOs_for_quantum_acceleration-2.pdf. Accessed 29 Oct. 2018.
[4] "D-Wave Leap." https://cloud.dwavesys.com/leap/. Accessed 29 Oct. 2018.

Primary authors

Lucy Linder (School of Engineering and Architecture of Fribourg (Switzerland), HES-SO, iCoSys Institute) Paolo Calafiura (Lawrence Berkeley National Lab. (US)) Wim Lavrijsen (Lawrence Berkeley National Lab. (US)) Steven Farrell (Lawrence Berkeley National Lab (US)) Wahid Bhimji (Lawrence Berkeley National Lab. (US)) Heather Gray (LBNL) Frederic Bapst (School of Engineering and Architecture of Fribourg (Switzerland), HES-SO, iCoSys Institute)

Presentation materials