  In recent years, research on near-term quantum machine learning has explored
how classical machine learning algorithms endowed with access to quantum
kernels (similarity measures) can outperform their purely classical
counterparts. Although theoretical work has shown provable advantage on
synthetic data sets, no work done to date has studied empirically whether
quantum advantage is attainable and with what kind of data set. In this paper,
we report the first systematic investigation of empirical quantum advantage
(EQA) in healthcare and life sciences and propose an end-to-end framework to
study EQA. We selected electronic health records (EHRs) data subsets and
created a configuration space of 5-20 features and 200-300 training samples.
For each configuration coordinate, we trained classical support vector machine
(SVM) models based on radial basis function (RBF) kernels and quantum models
with custom kernels using an IBM quantum computer, making this one of the
largest quantum machine learning experiments to date. We empirically identified
regimes where quantum kernels could provide advantage on a particular data set
and introduced a terrain ruggedness index, a metric to help quantitatively
estimate how the accuracy of a given model will perform as a function of the
number of features and sample size. The generalizable framework introduced here
represents a key step towards a priori identification of data sets where
quantum advantage could exist.
