Research map / Learning theory and algorithms / Sample complexity

Optimal algorithmic complexity of inference in quantum kernel methods

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Learning halfspaces under noise · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes inference cost in quantum kernel methods along two axes (sampling vs amplitude estimation; term-by-term vs all-at-once observable), showing an all-at-once amplitude-estimation strategy achieves O(||alpha||_1/eps) query complexity with a matching lower bound.

Problem

Inference in quantum kernel methods requires estimating a weighted sum of N kernel values to additive precision eps; the standard list-and-sum sampling approach costs O(N||alpha||_2^2/eps^2) queries.

Approach

Encode the full weighted kernel sum as the expectation value of a single observable (via a training-set oracle and LCU-style construction with a sign register), then apply quantum amplitude estimation, removing N from the query count; also characterize intermediate strategies and gate costs.

Key results

• All-at-once observable with quantum amplitude estimation achieves O(||alpha||_1/eps) query complexity, versus O(N||alpha||_2^2/eps^2) for naive sampling list-and-sum.
• A matching lower bound Omega(||alpha||_1/eps) is proven for applications of the amplitude-encoding unitary V, up to logarithmic factors.
• In gate count, list-and-sum with adaptive budget and amplitude estimation (O(G||alpha||_{2/3}/eps)) can beat the all-at-once strategy, which carries an extra factor of N in gates.

Surprising findings

• The query-optimal all-at-once strategy is not gate-optimal; list-and-sum with adaptive budget and amplitude estimation can use fewer total gates.

Limitations

• Lower bound is proven only in the V-query model; whether it extends to the full access model remains open.
• Analysis assumes black-box feature maps and non-vanishing kernel values; exponential kernel concentration makes the function trivially small.
• Gate complexity of the all-at-once approach scales with N, making it less practical on near-term hardware.

Experimental setup

Metrics: query complexity gate complexity

Baselines: list-and-sum with fixed budget via sampling list-and-sum with adaptive budget all-at-once via sampling

Builds on: quantum amplitude estimation linear combination of unitaries quantum kernel methods median-of-means

Closest papers by meaning

• Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.86)
• Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm (NeurIPS 2024 · similarity 0.86)
• Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.86)
• Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.86)
• Neural Auto-designer for Enhanced Quantum Kernels (ICLR 2024 · similarity 0.86)
• Characterizing Trainability of Instantaneous Quantum Polynomial Circuit Born Machine (NeurIPS 2026 · similarity 0.85)