qCLUE: a quantum clustering algorithm for multi-dimensional datasets

Frontiers in Quantum Science and Technology, vol. 3

Abstract

Clustering algorithms are at the basis of several technological applications, and are fueling the development of rapidly evolving fields such as machine learning. In the recent past, however, it has become apparent that they face challenges stemming from datasets that span more spatial dimensions. In fact, the best-performing clustering algorithms scale linearly in the number of points, but quadratically with respect to the local density of points. In this work, we introduce qCLUE, a quantum clustering algorithm that scales linearly in both the number of points and their density. qCLUE is inspired by CLUE, an algorithm developed to address the challenging time and memory budgets of Event Reconstruction (ER) in future High-Energy Physics experiments. As such, qCLUE marries decades of development with the quadratic speedup provided by quantum computers. We numerically test qCLUE in several scenarios, demonstrating its effectiveness and proving it to be a promising route to handle complex data analysis tasks – especially in high-dimensional datasets with high densities of points.

Authors 6

1. Dhruv Gopalakrishnan corresponding

   University of Waterloo · Perimeter Institute

   Affiliation as printed

   Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada

   Institute for Quantum Computing, University of Waterloo, Waterloo, ON, Canada

   Perimeter Institute of Theoretical Physics, Waterloo, ON, Canada

2. Luca Dellantonio corresponding

   University of Waterloo · University of Exeter

   Affiliation as printed

   Department of Physics and Astronomy, University of Exeter, Exeter, United Kingdom

   Department of Physics and Astronomy, University of Waterloo, Waterloo, ON, Canada

   Institute for Quantum Computing, University of Waterloo, Waterloo, ON, Canada

3. Antonio Di Pilato corresponding

   European Organization for Nuclear Research

   Affiliation as printed

   CERN, Geneva, Switzerland

4. W. Redjeb corresponding Aachen

   European Organization for Nuclear Research · RWTH Aachen University

   Affiliation as printed

   CERN, Geneva, Switzerland

   RWTH Aachen University Physikalisches Institut III A, Aachen, Germany

5. Felice Pantaleo corresponding

   European Organization for Nuclear Research

   Affiliation as printed

   CERN, Geneva, Switzerland

6. Michele Mosca corresponding

   University of Waterloo · Perimeter Institute

   Affiliation as printed

   Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada

   Department of Physics and Astronomy, University of Waterloo, Waterloo, ON, Canada

   Institute for Quantum Computing, University of Waterloo, Waterloo, ON, Canada

   Perimeter Institute of Theoretical Physics, Waterloo, ON, Canada