Yapay Zeka · 8 dk okuma · 17 Nisan 2026
Quantum kernel inference cuts query cost by removing data-size dependence
New algorithm reduces quantum machine learning inference complexity from O(N) to O(1) in data size, achieving query-optimal bounds via amplitude estimation.
Kaynak: arxiv/cs.LG · Elies Gil-fuster, Seongwook Shin, Sofiene Jerbi, Jens Eisert, Maximilian J. Kramer · orijinali aç ↗ ↗
Quantum kernel inference can eliminate dependence on training set size N by encoding the full sum as a single observable and using amplitude estimation.
- — Standard inference requires O(N||α||₂²/ε²) queries by estimating each kernel term independently.
- — New approach encodes all kernel terms into one observable, reducing to O(||α||₁/ε) queries.
- — Removes N from query complexity entirely; quadratic gains in coefficient norm and precision.
- — Matching lower bound proves the algorithm is query-optimal up to logarithmic factors.
- — Gate complexity differs from query complexity; practical choice depends on hardware constraints.
- — All methods use amplitude estimation as core subroutine, suitable for near-term quantum devices.
- — Provides landscape of intermediate strategies for practitioners with varying hardware capabilities.
Sık sorulanlar
- Standard inference queries each of N kernel values independently, costing O(N||α||₂²/ε²) queries. The new method encodes all kernel terms into a single observable and applies quantum amplitude estimation, reducing cost to O(||α||₁/ε). This removes dependence on N entirely and provides quadratic improvements in both the coefficient norm and precision parameters.