  Enhancing classical machine learning (ML) algorithms through quantum kernels
is a rapidly growing research topic in quantum machine learning (QML). A key
challenge in using kernels -- both classical and quantum -- is that ML
workflows involve acquiring new observations, for which new kernel values need
to be calculated. Transferring data back-and-forth between where the new
observations are generated & a quantum computer incurs a time delay; this delay
may exceed the timescales relevant for using the QML algorithm in the first
place. In this work, we show quantum kernel matrices can be extended to
incorporate new data using a classical (chordal-graph-based) matrix completion
algorithm. The minimal sample complexity needed for perfect completion is
dependent on matrix rank. We empirically show that (a) quantum kernel matrices
can be completed using this algorithm when the minimal sample complexity is
met, (b) the error of the completion degrades gracefully in the presence of
finite-sampling noise, and (c) the rank of quantum kernel matrices depends
weakly on the expressibility of the quantum feature map generating the kernel.
Further, on a real-world, industrially-relevant data set, the completion error
behaves gracefully even when the minimal sample complexity is not reached.
