Optimal algorithmic complexity of inference in quantum kernel methods

Titel: Optimale algoritmische complexiteit van inferentie in quantum kernel-methoden

Auteurs: Elies Gil-Fuster et al.
Datum: 17 april 2026

1. Probleemstelling

Quantum kernel-methoden zijn een van de meest veelbelovende kandidaten om een quantum-voordeel (quantum advantage) te behalen binnen supervised learning. Een fundamenteel knelpunt in deze methoden is de kost van inferentie: het evalueren van een getraind model op nieuwe data.

De inferentiestap vereist het berekenen van een gewogen som van $N$ kernel-waarden:
$$f_\alpha(x) = \sum_{i=1}^N \alpha_i k(x, x_i)$$
waarbij $\alpha \in \mathbb{R}^N$ de vector is van getrainde coëfficiënten en $k(x, x_i)$ de quantum kernel-functie is.

De standaardbenadering ("list-and-sum") schat elke term $\alpha_i k(x, x_i)$ onafhankelijk af via sampling. Dit resulteert in een query-complexiteit (het aantal benodigde quantum-orakel-aanroepen) van:
$$O\left(\frac{N \|\alpha\|_2^2}{\varepsilon^2}\right)$$
waarbij $\varepsilon$ de gewenste additieve precisie is en $\|\alpha\|_2$ de $L_2$-norm van de coëfficiënten. Deze schaling is problematisch omdat deze lineair afhankelijk is van de grootte van de trainingsset ($N$) en kwadratisch van de precisie ($1/\varepsilon^2$), wat de schaalbaarheid beperkt.

2. Methodologie

De auteurs analyseren systematisch de inferentie-problematiek door twee onafhankelijke ontwerpaspecten te combineren:

1. Hoe worden individuele kernel-waarden geschat?

   • Sampling: Klassieke sampling van meetresultaten (precisie $\propto 1/\sqrt{M}$).
   • Quantum Amplitude Estimation (QAE): Een quantum-algoritme dat een kwadratische snelheidswinst biedt ten opzichte van sampling (precisie $\propto 1/M$).

2. Hoe wordt de som over de trainingspunten benaderd?

   • List-and-sum: Elke term wordt onafhankelijk geschat en klassiek opgeteld. Dit kan met een vast budget of een adaptief budget (waarbij meer resources worden toegewezen aan termen met grotere $|\alpha_i|$).
   • All-at-once: De volledige inferentie-som wordt gecodeerd als de verwachtingswaarde van één enkel observabel. Dit vereist het creëren van een quantum-toestand die de gewichten $\alpha$ en de trainingsdata $x_i$ coherent combineert.

De auteurs definiëren een orakel-model dat toegang biedt tot de data-encoding unitary $U(x)$, de coëfficiënten-orakel $W(\alpha)$, en een trainingsset-orakel $O^\dagger(S)$. Ze analyseren alle vier mogelijke combinaties van de bovenstaande keuzes.

3. Belangrijkste Bijdragen

• Ontdekking van een "All-at-once" Observabel: De auteurs bewijzen dat de volledige som $f_\alpha(x)$ kan worden herschreven als de verwachtingswaarde van één enkel begrensd Hermitisch observabel $M(\alpha, S)$, zonder dat elke term individueel hoeft te worden geschat. Dit wordt gerealiseerd door de coëfficiënten in een quantum-toestand te coderen en een "training-set orakel" te gebruiken dat de inverse van de feature maps toepast.
• Optimale Query-Complexiteit: Door de "all-at-once" aanpak te combineren met Quantum Amplitude Estimation (QAE), wordt een query-complexiteit bereikt van:
  $$O\left(\frac{\|\alpha\|_1}{\varepsilon}\right)$$
  Dit verwijdert de afhankelijkheid van $N$ uit het aantal queries en biedt een kwadratische verbetering in zowel de norm van de coëfficiënten ($\|\alpha\|_1$ vs $\|\alpha\|_2^2$) als in de precisie ($1/\varepsilon$ vs $1/\varepsilon^2$).
• Matching Ondergrens: De auteurs bewijzen een ondergrens van $\Omega(\|\alpha\|_1/\varepsilon)$, wat aantoont dat hun "all-at-once" strategie met QAE query-optimale is (tot op logaritmische factoren).
• Gate-Complexiteit Analyse: Ze tonen aan dat de query-optimale strategie niet altijd de meest praktische is. Voor realistische hardware (waar de totale poort-aantallen tellen), kan een adaptieve "list-and-sum" strategie met QAE voordeliger zijn omdat deze minder diepe circuits vereist en geen grote overhead heeft voor het implementeren van het "all-at-once" observabel.

4. Resultaten en Vergelijking van Strategieën

De paper presenteert een overzicht van de complexiteit voor verschillende strategieën (zie ook Tabel B.1 in de supplementen):

| Strategie | Methode van Schatting | Query-Complexiteit | Gate-Complexiteit (Asymptotisch) | Status |
| :--- | :--- | :--- | :--- :--- |
| Naïef | List-and-sum (Vast budget) | Sampling | $O(N \|\alpha\|_2^2 / \varepsilon^2)$ | $O(G N \|\alpha\|_2^2 / \varepsilon^2)$ | Referentiepunt |
| Query-Optimaal | All-at-once | QAE | $O(\|\alpha\|_1 / \varepsilon)$ | $\tilde{O}((NG + n)\|\alpha\|_1 / \varepsilon)$ | Beste voor queries |
| Gate-Optimaal | List-and-sum (Adaptief budget) | QAE | $O(\|\alpha\|^{2/3} / \varepsilon)$ | $O(G \|\alpha\|^{2/3} / \varepsilon)$ | Beste voor poorten |
| Adaptief | List-and-sum (Adaptief budget) | Sampling | $O(\|\alpha\|_1^2 / \varepsilon^2)$ | $O(G \|\alpha\|_1^2 / \varepsilon^2)$ | Goed voor NISQ |

• Query-Optimaliteit: De "all-at-once" + QAE strategie elimineert de $N$-factor uit de query-complexiteit. Dit is cruciaal voor grote datasets.
• Gate-Optimaliteit: Hoewel "all-at-once" minder queries nodig heeft, vereist het circuits die dieper zijn en meer qubits gebruiken (door de noodzaak van gecontroleerde operaties over de hele trainingsset). Voor hardware met beperkte coherentie of hoge poortkosten, kan de adaptieve "list-and-sum" strategie met QAE in totaal minder quantum-poorten vereisen.

5. Betekenis en Conclusie

Dit werk biedt een volledig landschap van algoritmische keuzes voor inferentie in quantum kernel-methoden:

1. Fundamentele Limiet: Het bewijst dat de query-complexiteit van inferentie fundamenteel kan worden verbeterd tot $O(\|\alpha\|_1/\varepsilon)$, wat een grote stap is richting schaalbare quantum machine learning.
2. Praktische Richtlijnen: Het biedt practitioners concrete richtlijnen afhankelijk van de hardware:
   • Gebruik "All-at-once" + QAE als coherent multi-query toegang beschikbaar is en query-complexiteit de beperkende factor is (vroege fault-tolerant regime).
   • Gebruik Adaptieve "List-and-sum" + QAE als de totale gate-count (en dus circuitdiepte en foutgevoeligheid) de beperkende factor is.
3. Toekomstperspectief: De algoritmen vereisen alleen amplitude-estimation als sub-routine, wat hen natuurlijke kandidaten maakt voor implementatie in het vroege fault-tolerant tijdperk. De auteurs merken ook op dat hun resultaten relevant zijn voor kernel-methoden waar de kernel-waarden niet exponentieel naar nul gaan (een bekend probleem in quantum kernels), en stellen vragen over de uitbreiding naar het trainingsproces.

Samenvattend, dit artikel transformeert het begrip van de complexiteit van quantum kernel-inferentie van een lineaire afhankelijkheid van de datasetgrootte naar een optimale schaling die alleen afhankelijk is van de norm van de coëfficiënten en de gewenste precisie.