HEP Quantum Pattern Recognition
A DOE-HEP QuantiSED Project
Classical iterative pattern recognition (PR) algorithms are computational tools used in High-Energy Physics (HEP) for data processing and background rejection but suffer from combinatorial explosion. As ever more powerful accelerators flood the detectors with billions of charged particle tracks per second, these highly optimized algorithms are becoming the limiting factor in the discovery potential of many HEP experiments. Charged particle track pattern recognition is therefore currently the subject of a vigorous research program in detector and algorithmic development.
Quantum Pattern Recognition (QPR) algorithms have the potential to provide orders of magnitude speed improvements and increased precision. QPR could transform our ability to select and analyse challenging signatures of new physics, e.g. long-lived particles or high mass particles decaying to dense particle jets. Therefore QPR may significantly expand the HEP discovery potential for new particles and interactions. The goal of the HEP.QPR pilot project is to create a community of computer scientists and physicists dedicated to addressing the challenges of HEP pattern recognition and to start building a suite of promising QPR algorithms and tools.
The Team
Our Berkeley Lab team:
Heather Gray (PI, also UC Berkeley), Wahid Bhimji, Paolo Calafiura, Wim Lavrijsen, Amitabh Yadav
Alumni: Steve Farrell, Lucy Linder (also HEIA-FR), Illya Shapoval, Alex Smith (also UC Berkeley)
The Projects
Quantum Associative Memory on Universal Quantum Computers
Quantum Associative Memory (QuAM) - a quantum variant of Associative Memory - employs a quantum system as a storage medium and two quantum algorithms for information storage and retrieval. Classical associative memories allow to find track candidates with a constant-time lookup, and therefore are commonly used for HEP real-time pattern recognition. The storage capacity of the associative memory determines the efficiency and fake rate of the track formation algorithm.
QuAM encodes information into the Hilbert space of a quantum system. The cardinality of arbitrary orthonormal basis of the Hilbert space admits optimal information storage capacity - the key property of a quantum storage medium - for a pattern of supported length. Equivalently, a quantum storage medium sustains strictly exponential scaling of its capacity as the pattern length grows.
A complete quantum circuit for 2-bit pattern storage produced by LBNL’s QISKit-based QuAM circuit generator for IBM Q Experience platforms
QUBO Pattern Reconstruction on D-Wave
D-Wave Systems Quantum Annealer (QA) finds the ground state of a Hamiltonian expressed as:
This Quantum Machine Instruction (QMI) is equivalent to a Quadratic Unconstrained Binary Optimization (QUBO) and can be transformed easily into an Ising model or an Hopfield network.
Following Stimpfl-Abele “Fast track finding with neural network”, we expressed the problem of classifying track seeds (doublets and triplets) as a QUBO, where the weights depends on physical properties such as the curvature, 3D orientation and length. We generated QUBOs that encode the pattern recognition problem at Run 2 LHC intensities using the TrackML dataset and solved them using qbsolv and the D-Wave Leap Cloud Service. Those early experiments achieved a performance in terms of purity, efficiency, and TrackML score that exceeds 95%. Our goal is to scale up our model to HL-LHC track densities using geographic partitioning methods. We are also looking into refining and optimizing our model in order to reduce execution time and to boost performance.