Quantum graph neural networks

Project goal

The goal of this project is to explore the feasibility of using quantum algorithms to help track the particles produced by collisions in the LHC more efficiently. This is particularly important as the rate of collisions is set to increase dramatically in the coming years.

R&D topic
Quantum technologies
Project coordinator(s)
Sofia Vallecorsa
Team members
Fabio Fracas, Cenk Tüysüz, Jean-Roch Vlimant, Bilge Demirkoz, Kristiane Novotny, Carla Rieger.
Collaborator liaison(s)
Daniel Dobos, Karolos Potamianos


Project background

The LHC at CERN is producing collisions at unprecedented collider energy. The hundreds of particles created during the collisions are recorded by large detectors composed of several sub-detectors. At the centre of these detectors there is usually a tracker detector, precisely recording the signal of the passage of charged particles through thin layers of active material. The trajectories of particles are bent by a magnetic field to allow the measurement of the particle momentum. There is an expected ten-fold increase in the number of tracks produced per bunch crossing after the high-luminosity upgrade of LHC.

Classical algorithms perform the reconstruction of the trajectory of charged particles; these make use of Kalman filter formalism. Although they are quite accurate, they scale worse than quadratically with the number of tracks. Several ways are explored to mitigate the increase in the computing needs, such as new detector layout, deep-learning and code parallelisation. Quantum computing has been shown to provide speed-ups for certain problems and different R&D initiatives are exploring how quantum tracking algorithms could exploit such capabilities. We are developing a quantum-based track-finding algorithm aimed at reducing the combinatorial background during the initial seeding stage for the Kalman filters. We are using the publicly available dataset designed for the Kaggle ‘TrackML’ challenge for this work.

Recent progress

We have developed a prototype quantum graph neural network (QGNN) algorithm for tracking the particles produced by collision events. The model uses a graph interpretation for trajectory reconstruction by representing detector hits with nodes in a graph and segments among hits as graph connections. The quantum model is based on cascade hierarchical classifiers, identifying nodes and segments belonging to particle tracks.

Several architectures have been investigated, ranging from tree tensor networks to multi-scale entanglement renormalization ansatz (MERA)  graphs, and the results were compared against classical graph neural networks (GNNs). We studied the way in which both quantum effects, such as entanglement, and the expressibility of quantum circuits impacts the final performance. In addition, a student project during the summer focused on the design and optimisation of a hybrid approach to data embedding, combining a classical multi-layer perceptron to a quantum circuit. The results were presented at several international conferences and workshops, including Connecting The Dots 2020 and IOP Quantum 2020.

In parallel to the high-energy physics use case, we also started investigating the application of this methodology to the collision-avoidance systems used for commercial air traffic.

Next steps

This work represents a first complete look at particle track reconstruction using a QGNNs. Our results show that the prototype can perform at a similar level to classical approaches. We have also learned about how scaling the network depth can improve its performance. However, it is known that there are many obstacles to the efficient training of extended QGNNs. Therefore, we are currently maintaining a conservative attitude towards the advantages offered by such networks.

Our plan is to improve the model by introducing better strategies for encoding information. We will also continue the analysis of the properties of the quantum circuits, in order to avoid the problems typically encountered when training hybrid models, such as the effect of vanishing gradients.


    C. Tüysüz, F. Carminati, B. Demirköz, D. Dobos, F. Fracas, K. Novotny, K. Potamianos, S. Vallecorsa, J.-R. Vlimant, A Quantum Graph Neural Network Approach to Particle Track Reconstruction. arXiv e-prints, p. arXiv:2007.06868 [cs.DC], 2020. cern.ch/go/6H88
    K. Novotny, C. Tüysüz, C. Rieger, D. Dobos, K. Potamianos, B. Demirköz, F. Carminati, S. Vallecorsa, J. R. Vlimant, F. Fracas, Quantum Track Reconstruction Algorithms for non-HEP applications. Published at Proceeding of science, 2020. cern.ch/go/cX7w
    C. Rieger, Exploring hybrid quantum-classical neural networks for particle tracking. Published at Zenodo, 2020. cern.ch/go/96wK
    C. Tüysüz, K. Novotny, C. Rieger, F. Carminati, B. Demirköz, D. Dobos, F. Fracas, K. Potamianos, S. Vallecorsa, J. R. Vlimant, Performance of Particle Tracking Using a Quantum Graph Neural Network. Published at Cornell University, 2021. cern.ch/go/J7sp
    C. Tüysüz, C. Rieger, K. Novotny, B. Demirköz, D. Dobos, K. Potamianos, S. Vallecorsa, J.R. Vlimant, R. Forster, Hybrid quantum classical graph neural networks for particle track reconstruction. Published at SpringerLink, 2021. cern.ch/go/cn9m


    F. Carminati, Particle Track Reconstruction with Quantum Algorithms (7 November). Presented at Conference on Computing in High Energy & Nuclear Physics, Adelaide, 2019. cern.ch/go/7Ddm
    D. Dobos, HEP Graph Machine Learning for Industrial & Humanitarian Applications (26 November). Presented at Conference on HEPTECH AIME19 AI & ML, Budapest, 2019. cern.ch/go/9Rvl
    C. Tüysüz, A Quantum Graph Neural Network Approach to Particle Track Reconstruction (22 January). Presented at the CERN openlab Technical Workshop, CERN, 2020. cern.ch/go/6TMH
    C. Tüysüz, A Quantum Graph Neural Network Approach to Particle Track Reconstruction (20 April). Presented at the 6th International Workshop “Connecting the dots”, Princeton University, 2020. cern.ch/go/9Tdt
    C. Tüysüz, Quantum Graph Neural Networks for Track Reconstruction in Particle Physics and Beyond (22 October). Presented at 4th Inter-experiment Machine Learning Workshop, 2020. cern.ch/go/6QQT
    C. Tüysüz, Performance of Particle Tracking using a Quantum Graph Neural Network (8 October). Presented at BAŞARIM 2020 Konferansı, 2020. cern.ch/go/kn9v
    K. S. Novotny, Quantum Track Reconstruction Algorithms for non-HEP applications (29 July). Presented at the 40th International Conference on High Energy Physics, Prague, 2020. cern.ch/go/8HFG
    K. S. Novotny, Exploring (Quantum) Track Reconstruction Algorithms for non-HEP applications (21 April). Presented at the 6th International Workshop “Connecting the dots”, Princeton University, 2020. cern.ch/go/bMM
    C. Rieger, C. Tüysüz, K. Novotny, S. Vallecorsa, B. Demirköz, K. Potamianos, D. Dobos, J. Vlimant, R. Forster, Embedding of particle tracking data using hybrid quantum classical neural networks (20 May). Presented at the 25th International Conference on Computing in High-Energy and Nuclear Physics, 2021. cern.ch/go/6HRW
    C. Tüysüz, C. Rieger, Hybrid Quantum-Classical Graph Neural Networks for Track ReconstructioN (11 March). Presented at CERN openlab Technical Workshop, Geneva, 2021. cern.ch/go/9Cjh
    C. Tüysüz, C. Rieger, Hybrid Quantum-Classical Graph Neural Networks for Track ReconstructioN (26 April). Presented at Quantum Technology Initiative meeting, 2021. cern.ch/go/Qbx6
    C. Rieger (October). Presented at the IOP Quantum 2020 conference, 2020.