Speaker
Description
Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning.
A key bottleneck is the cost of inference: evaluating a weighted sum of kernel values to additive precision.
The standard approach estimates each term independently via sampling, yielding a query complexity that scales with the number of training data and the 2-norm of the weights squared.
In this work, we combine two independent improvements: estimating the kernel values via quantum amplitude estimation and collecting the sum under a single observable.
We show that the improved approach achieves a query complexity that scales only with the 1-norm of the weights, removing the explicit dependence on the size of the training set.
We prove a matching lower bound of, establishing query-optimality.
We also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity.
We identify a different strategy based on importance sampling, which yields a lower total gate count. We thus provide both a query-optimal algorithm and a practically-optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners.
All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.
This way, we settle the question how inference in quantum kernel methods should be implemented once and for all.
| Topic | Quantum kernel methods and their applications |
|---|---|
| Additional Topic | Quantum algorithms for machine learning applications |