Optimal algorithmic complexity of inference in quantum kernel methods

1. Problem Statement

Quantum kernel methods are a leading candidate for achieving quantum advantage in supervised learning. The core inference task involves evaluating a trained hypothesis $f_\alpha(x)$ on new data $x$:
$$f_\alpha(x) = \sum_{i=1}^N \alpha_i k(x, x_i)$$
where $N$ is the size of the training set, $\alpha \in \mathbb{R}^N$ are trained coefficients, and $k(x, x_i) = |\langle \psi(x) | \psi(x_i) \rangle|^2$ is the quantum kernel value.

The Bottleneck:
The standard approach ("list-and-sum") estimates each of the $N$ kernel terms independently via sampling and sums them classically. This results in a query complexity of $O(N \|\alpha\|_2^2 / \varepsilon^2)$ to achieve additive precision $\varepsilon$. This scaling is problematic because:

1. It depends linearly on the training set size $N$.
2. It scales quadratically with the inverse precision $1/\varepsilon$.
3. It scales quadratically with the $\ell_2$-norm of the coefficients.

The paper seeks to determine the optimal algorithmic complexity for this inference step by exploring two independent design axes:

1. Sum Approximation: How to handle the summation? (Term-by-term "list-and-sum" vs. encoding the full sum as a "single observable" "all-at-once").
2. Estimation Method: How to estimate individual values? (Classical sampling vs. Quantum Amplitude Estimation - QAE).

2. Methodology

The authors analyze all four combinations of the design axes within an oracle query model. They define specific oracles for accessing the data ($U(x)$), coefficients ($W(\alpha)$), and the training set ($O^\dagger(S)$).

A. The "All-at-once" Observable

The authors prove that the weighted sum $f_\alpha(x)$ can be cast as the expectation value of a single Hermitian observable $M(\alpha, S)$ acting on a specific quantum state $|\phi(x)\rangle$:
$$f_\alpha(x) = \langle \phi(x) | M(\alpha, S) | \phi(x) \rangle$$
This observable is constructed using a "training-set oracle" $O^\dagger(S)$, which applies controlled inverse feature maps $U^\dagger(x_i)$ conditioned on an index register. This allows the entire inference sum to be evaluated in a single coherent quantum procedure rather than $N$ separate measurements.

B. Estimation Techniques

1. Sampling: Measures the observable $M$ (or individual terms) $M$ times. Precision scales as $O(1/\sqrt{M})$.
2. Quantum Amplitude Estimation (QAE): Uses the amplitude amplification framework to estimate the amplitude of a "good" state. Precision scales as $O(1/M)$, offering a quadratic speedup over sampling.

C. Algorithmic Landscape

The paper systematically derives the complexity for:

• List-and-sum (Fixed Budget): Equal resources for all terms.
• List-and-sum (Adaptive Budget): Resources allocated based on coefficient magnitude $|\alpha_i|$.
• All-at-once: Encoding the full sum into one observable.

3. Key Contributions & Results

A. Query Complexity Optimality

The paper establishes that the query-optimal strategy is "All-at-once" combined with Quantum Amplitude Estimation.

• Complexity: $O(\|\alpha\|_1 / \varepsilon)$.
• Improvements:
  • Removes the linear dependence on $N$ from the query count.
  • Improves the dependence on the coefficient norm from $\|\alpha\|_2^2$ (naive) to $\|\alpha\|_1$.
  • Improves precision scaling from $1/\varepsilon^2$ to $1/\varepsilon$ (quadratic improvement).
• Lower Bound: The authors prove a matching lower bound of $\Omega(\|\alpha\|_1 / \varepsilon)$, establishing that this strategy is optimal up to logarithmic factors within the black-box oracle model.

B. Gate Complexity vs. Query Complexity

While the "All-at-once" + QAE strategy is query-optimal, it is not always gate-optimal due to the high cost of implementing the training-set oracle $O^\dagger(S)$, which requires $O(N)$ gates per query.

• Gate-Optimal Strategy: "List-and-sum" with adaptive budget combined with Quantum Amplitude Estimation.
• Complexity: $O(G \|\alpha\|^{2/3} / \varepsilon)$, where $G$ is the gate cost of the feature map.
• Trade-off: This strategy avoids the $N$-factor gate overhead of the all-at-once approach, making it more practical for early fault-tolerant devices where gate counts are the primary constraint, even though it requires more queries than the optimal strategy.

C. Summary of Strategies

Strategy	Estimation Method	Query Complexity	Gate Complexity	Status
Naive	List-and-sum (Fixed)	Sampling	$O(N \|\alpha\|_2^2 / \varepsilon^2)$	$O(G N \|\alpha\|_2^2 / \varepsilon^2)$
Query-Optimal	All-at-once	QAE	$O(\|\alpha\|_1 / \varepsilon)$	$\tilde{O}((NG+n)\|\alpha\|_1 / \varepsilon)$
Gate-Optimal	List-and-sum (Adaptive)	QAE	$O(\|\alpha\|^{2/3} / \varepsilon)$	$O(G \|\alpha\|^{2/3} / \varepsilon)$

(Note: $\tilde{O}$ hides logarithmic factors. $n$ is the number of qubits in the feature map.)

4. Significance and Implications

1. Scalability of Quantum Kernels: The results demonstrate that the inference cost in quantum kernel methods does not inherently scale linearly with the training set size $N$ in terms of query complexity. This removes a major theoretical barrier to the scalability of quantum kernel methods.
2. Practical Guidelines: The paper provides a "zoo" of algorithms, offering practitioners a clear decision tree based on hardware capabilities:
   • Use All-at-once + QAE if the hardware supports coherent multi-query access and query depth is the bottleneck (early fault-tolerant regime).
   • Use List-and-sum (Adaptive) + QAE if gate count is the dominant constraint (near-term or limited coherence).
3. Theoretical Rigor: By providing matching upper and lower bounds, the work settles the fundamental complexity of the inference problem in the oracle model, showing that no further asymptotic improvements are possible without exploiting specific structural properties of the feature map beyond black-box access.
4. Robustness to Concentration: The authors address the issue of "exponential kernel concentration" (where kernel values vanish). They argue that while concentration makes the values small, it does not invalidate the algorithm's complexity scaling; rather, it implies the model itself lacks predictive power in those regimes, which is a separate issue from the inference algorithm's efficiency.

Conclusion

This work fundamentally re-evaluates the inference step in quantum kernel methods. It proves that by encoding the inference sum into a single observable and utilizing Quantum Amplitude Estimation, one can achieve query-optimal scaling independent of the training set size. However, it crucially highlights that query optimality does not guarantee gate optimality, providing a nuanced roadmap for implementing these algorithms on realistic quantum hardware.