Translating the Nearest Convex Hull Classifier from Classical to Quantum Computing
Grégoire Cattan, Anton Andreev, Quentin Barthélemy · Quantum Reports · 2025
The nearest convex hull (NCH) classifier is a promising algorithm for the classification of biosignals, such as electroencephalography (EEG) signals, especially when adapted to the classification of symmetric positive definite matrices. In this paper, we implemented a version of this classifier that can execute either on a traditional computer or a quantum simulator, and we tested it against state-of-the-art classifiers for EEG classification. This article addresses the practical challenges of adapting a classical algorithm to one that can be executed on a quantum computer or a quantum simulator. One of these challenges is to find a formulation of the classification problem that is quadratic, is binary, and accepts only linear constraints—that is, an objective function that can be solved using a variational quantum algorithm. In this article, we present two approaches to solve this problem, both compatible with continuous variables. Finally, we evaluated, for the first time, the performance of the NCH classifier on real EEG data using both quantum and classical optimization methods. We selected a particularly challenging dataset, where classical optimization typically performs poorly, and demonstrated that the nearest convex hull classifier was able to generalize with a modest performance. One lesson from this case study is that, by separating the objective function from the solver, it becomes possible to allow an existing classical algorithm to run on a quantum computer, as long as an appropriate objective function—quadratic and binary—can be found.