Optimal algorithmic complexity of inference in quantum kernel methods
Elies Gil-fuster, Seongwook Shin, Sofiene Jerbi, Jens Eisert, Maximilian J. Kramer
Abstract
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 trained model on new data requires estimating a weighted sum of kernel values to additive precision , where is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of . In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of , removing the dependence on from the query count and yielding a quadratic improvement in both and . We prove a matching lower bound of , establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, 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. Our results 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.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper provides a complete complexity-theoretic analysis of the inference step in quantum kernel methods — the task of evaluating to additive precision . The authors identify two orthogonal algorithmic design axes: (1) how the sum is approximated (term-by-term "list-and-sum" vs. encoding as a single "all-at-once" observable), and (2) how expectation values are estimated (classical sampling vs. quantum amplitude estimation). They systematically analyze all four combinations plus intermediate variants.
The headline result is that the query-optimal combination — encoding the full inference sum as a single observable and applying quantum amplitude estimation — achieves query complexity, compared to the naive . This removes dependence on from the query count and provides quadratic improvement in precision. A matching lower bound establishes optimality up to logarithmic factors.
Methodological Rigor
The paper is methodologically thorough and well-structured. Several aspects stand out:
Completeness of analysis: Rather than presenting only the optimal algorithm, the authors analyze all six strategies (four main combinations plus adaptive budget variants and a sample-and-average interpolation). Each has a formal algorithm specification and proven complexity bounds.
Matching lower bound: The lower bound (Corollary 11) via reduction to single-term amplitude estimation is clean and establishes query-optimality within the access model. The authors are transparent that the lower bound is proven only for the -query model and acknowledge the open question of whether it extends to the full access model.
Distinction between query and gate complexity: A particularly valuable contribution is the analysis showing that query-optimal gate-optimal. The all-at-once approach requires gates per query (due to the training-set oracle), meaning list-and-sum with adaptive budget via QAE ( gates) can be preferable. The ratio analysis in Eq. (21) is a practical insight.
Access model transparency: The oracle access model (Definition 4) is clearly specified and realistic — the authors explicitly note that no QRAM is required and that the controlled unitaries can be compiled offline. The cost per query of the training-set oracle is inherent to any method touching all training points.
One limitation in rigor: the concentration analysis for quantum amplitude estimation in the list-and-sum template (Theorem B.1) treats QAE estimators as sub-Gaussian when they are technically sub-exponential. The authors acknowledge this requires checking a Bernstein condition but proceed with the variance-dominated regime. This is standard practice but slightly weakens the formal guarantees.
Potential Impact
Practical quantum ML: The paper directly addresses a recognized bottleneck in quantum kernel methods — the cost of inference scaling with training set size. The -independent query count could meaningfully improve the viability of quantum kernel approaches, especially as training sets grow.
Practitioner guide: The "zoo" of algorithms with clear guidelines (use all-at-once for query optimality, list-and-sum with adaptive budget for gate optimality) makes this immediately useful for implementation decisions on early fault-tolerant hardware.
Early fault-tolerant regime: All algorithms require only amplitude estimation as a subroutine — no deep quantum phase estimation or complex coherent protocols — making them natural candidates for near-term fault-tolerant devices. This positions the work well within the current hardware trajectory.
Connections to broader algorithmic design: The connection to LCU frameworks, compressed sensing trade-offs, and basis optimization in quantum chemistry (Section II D) suggests the techniques may find applications beyond kernel methods.
Timeliness & Relevance
The work is timely for several reasons: (1) quantum kernel methods remain among the few QML approaches with provable advantages [LAT21]; (2) the community is actively preparing for early fault-tolerant quantum computing; (3) recent negative results on exponential kernel concentration [TWCH24] have raised concerns about quantum kernel scalability, which this paper partially addresses by noting the algorithms remain valid but the kernel itself is the bottleneck.
The paper also engages with very recent results on amplitude estimation requiring inverses [TW25, TWZ25], grounding the analysis in the latest theoretical understanding.
Strengths & Limitations
Key strengths:
Notable limitations:
Overall Assessment
This is a solid theoretical contribution that provides the first complete and optimal complexity analysis of inference in quantum kernel methods. The systematic treatment of all algorithmic combinations, combined with the matching lower bound and the practical gate-vs-query distinction, makes it a useful reference for both theorists and practitioners. While the results are primarily asymptotic and lack experimental validation, they fill a genuine gap in the quantum kernel methods literature and provide actionable guidance for early fault-tolerant implementations.
Generated Apr 17, 2026
Comparison History (40)
Paper 2 achieves the first improvement in 18 years on the quantum capacity threshold of the depolarizing channel—a fundamental and long-standing open problem in quantum information theory. The result surpasses all previous improvements combined and introduces a powerful new framework (symmetric subspace optimization) with broad implications for quantum communication and coding theory. Paper 1 provides rigorous and useful algorithmic improvements for quantum kernel inference, but addresses a more specialized optimization problem. The breakthrough nature and breadth of impact of Paper 2 gives it higher scientific impact potential.
Paper 2 addresses a fundamental hardware scalability challenge in superconducting quantum computing—moving beyond planar architectures via 3D integration with vertical tunable couplers. This experimental demonstration of high-fidelity inter-chip gates and entanglement has broad impact: it enables scaling toward fault-tolerant quantum computation, a critical bottleneck for the entire field. Paper 1 provides rigorous theoretical optimization of quantum kernel inference complexity, which is valuable but more niche, targeting a specific algorithmic subroutine. The hardware breakthrough in Paper 2 has wider implications across all quantum computing applications and is more immediately transformative.
Paper 1 addresses a fundamental and high-impact problem: quantum simulation of Navier-Stokes equations, which has enormous potential applications across engineering and science (aerodynamics, climate modeling, etc.). It presents the first quantum algorithm based on a quantum-like wave formulation of genuine Navier-Stokes equations including pressure, dissipation, and vorticity, combining novel techniques (tensor-network Carleman embedding of Hamilton-Jacobi equations). While Paper 2 provides rigorous and elegant complexity-theoretic results for quantum kernel inference with matching bounds, its scope is narrower—optimizing a specific subroutine in quantum ML. Paper 1's broader interdisciplinary impact and potential to unlock quantum advantage for fluid dynamics gives it higher estimated impact.
Paper 1 addresses a fundamental bottleneck in quantum kernel methods—inference complexity—with provably optimal algorithms and matching lower bounds. It provides a complete theoretical landscape connecting query and gate complexity, directly relevant to near-term quantum computing. Its breadth of impact spans quantum machine learning, algorithm design, and practical early-fault-tolerant implementations. Paper 2, while solid, investigates a more specific problem (cat-state generation in microring resonators) with incremental theoretical advances over existing approaches in quantum optics, limiting its cross-field impact.
Paper 1 resolves a major bottleneck in quantum machine learning by completely removing the dependence on the dataset size N for inference query complexity. Its bridge between theoretical optimality and practical hardware implementation gives it broad applicability across quantum computing and ML. While Paper 2 provides rigorous mathematical improvements to a quantum trace inequality, Paper 1's algorithmic breakthrough in a highly active, application-driven field offers greater potential for immediate real-world impact and broader cross-disciplinary relevance.
Paper 1 provides a fundamental algorithmic breakthrough in quantum machine learning, establishing theoretically optimal query complexity bounds for quantum kernel inference. Its rigorous theoretical foundation and direct pathway to early-fault-tolerant applications offer a broader and more enduring scientific impact compared to the architecture-specific hardware-software co-design framework presented in Paper 2.
Paper 1 offers a broadly relevant, rigorously characterized algorithmic advance for quantum machine learning: it identifies the optimal query complexity for quantum-kernel inference, provides an explicit query-optimal algorithm, and proves a matching lower bound, plus practical gate-cost tradeoffs. This combination of tight complexity theory, concrete algorithms, and near-term implementation relevance (amplitude estimation, early fault-tolerant regimes) suggests strong cross-field impact (QML, quantum algorithms, complexity, benchmarking). Paper 2 is novel and important for quantum certification, but its scope is narrower (randomized measurements/invariants) and likely impacts a more specialized community.
Paper 2 demonstrates a groundbreaking experimental achievement—1 THz bandwidth all-optical quantum teleportation—that overcomes a fundamental electronic bottleneck limiting quantum optical computing. This represents a ~10,000x improvement over prior bandwidths and opens pathways to terahertz-clock quantum computers and high-capacity quantum internet. Its experimental nature, broad implications across quantum computing, communications, and networking, and the removal of a key technological barrier give it higher impact than Paper 1, which, while rigorous and query-optimal, provides incremental algorithmic improvements within the narrower domain of quantum kernel methods.
Paper 1 is likely to have higher impact: it delivers a provably query-optimal algorithm (matching lower bound) for a central bottleneck in quantum kernel ML inference, with clear complexity improvements and practical guidance on gate costs—high rigor and immediate relevance to near-/early-fault-tolerant quantum computing. Its applications span quantum machine learning, algorithm design, and resource estimation, affecting multiple communities. Paper 2 is novel for collective-spin open quantum systems, but is more specialized, with narrower cross-field uptake and less direct near-term technological impact.
Paper 2 has higher impact potential due to a broadly applicable, rigorously optimal result: it gives a query-optimal inference algorithm for quantum kernel methods with a matching lower bound, and provides a systematic landscape plus practical gate-complexity guidance. This directly targets a key bottleneck in a timely, fast-moving area (quantum machine learning) with clear implications for near-term fault-tolerant implementations. Paper 1 is novel and rigorous for mean-field spin-glass dynamics, but its applicability is narrower and more model-specific, making its cross-field and practical impact likely smaller.