Quantum machine learning advantages beyond hardness of evaluation

1. Il Problema e il Contesto

Negli ultimi anni, sono state fornite prove rigorose di vantaggi quantistici nell'apprendimento automatico (QML), in particolare quando i dati sono etichettati da funzioni crittografiche o intrinsecamente quantistiche. Tuttavia, la maggior parte di questi risultati si basa sull'ipotesi che la funzione di etichettatura vera sia difficile da valutare per circuiti classici di dimensioni polinomiali. Di conseguenza, il vantaggio quantistico deriva spesso dalla capacità di valutare la funzione appresa su nuovi punti, piuttosto che dal processo di apprendimento (identificazione) stesso.

Il paper si concentra sul compito di identificazione (identification task): l'obiettivo è "semplicemente" identificare la funzione di etichettatura sottostante a un dataset, senza necessariamente doverla valutare efficientemente su nuovi input. Questo scenario è cruciale per applicazioni pratiche come l'apprendimento di Hamiltoniani o la ricerca di parametri d'ordine, dove il fine ultimo è scoprire la funzione generatrice dei dati.

Il problema centrale affrontato è: esiste un vantaggio quantistico nell'identificare una funzione quantistica, anche se non si richiede di valutarla efficientemente?
Fino ad ora, i vantaggi di identificazione erano stati provati solo in contesti crittografici sfruttando la "random generatability" (la capacità di generare efficientemente campioni etichettati casualmente). Tuttavia, per le funzioni quantistiche (BQP-complete), si sospetta che questa proprietà non valga, rendendo necessarie nuove strategie di prova.

2. Metodologia e Assunzioni

Gli autori adottano un approccio basato sulla complessità computazionale, utilizzando il framework PAC (Probably Approximately Correct) e la gerarchia polinomiale (PH).

• Funzioni Quantistiche: Vengono definite come funzioni caratteristiche di linguaggi in BQP (o PromiseBQP), che possono essere stimate efficientemente da un computer quantistico ma non da algoritmi classici.
• Ipotesi di Complessità: I risultati si basano sull'assunzione che BQP non sia contenuto in livelli bassi della Gerarchia Polinomiale (PH) (specificamente, che BQP non sia in $HeurBPP^{NP}$ o livelli superiori).
• Nuova Strategia di Prova: Poiché le funzioni quantistiche non sono "random generatable" (non si possono generare campioni etichettati casualmente in modo classico), gli autori non possono usare le tecniche standard usate per le funzioni crittografiche. Invece, sviluppano una strategia che "inverte" il processo di apprendimento all'interno della gerarchia polinomiale.

3. Contributi Chiave

Il paper presenta quattro contributi principali:

1. Non-Generabilità Casuale delle Funzioni Quantistiche:
   Gli autori dimostrano che le funzioni quantistiche non sono "random generatable" (né esattamente né approssimativamente) a meno che BQP non sia contenuto nel secondo livello della PH ($P^{NP}$). Questo risultato è fondamentale perché esclude l'uso di tecniche basate sulla generazione di dati per provare la durezza dell'identificazione per le funzioni quantistiche.

2. Identificazione Verificabile (Verifiable Identification):
   Viene introdotto il compito di "identificazione verificabile", dove l'algoritmo deve rifiutare dataset invalidi (inconsistenti con qualsiasi concetto della classe). Viene provato che l'identificazione verificabile classica di una funzione target quantistica è impossibile, a meno che BQP non sia contenuto in $BPP^{NP}$.

3. Identificazione Non Verificabile (Non-Verifiable Identification):
   Questo è il risultato principale. Gli autori identificano condizioni sufficienti (classe di concetti c-distinct o average-case-smooth) tali per cui un'identificazione classica "semplice" (senza rifiuto di dataset) implicherebbe un'identificazione verificabile approssimata all'interno della PH.

   • Se un algoritmo classico efficiente risolvesse il compito di identificazione per queste classi, ciò implicherebbe che BQP è contenuto in $HeurBPP^{NP^{NP^{NP}}}$ (quattro livelli della gerarchia polinomiale).

4. Esempi Fisici e Separazione Quantistica:
   Vengono forniti esempi concreti di compiti di apprendimento motivati dalla fisica (come l'apprendimento di osservabili quantistici) che soddisfano le condizioni sopra descritte. Per questi compiti, esiste un algoritmo di apprendimento quantistico che risolve il compito di identificazione, mentre qualsiasi metodo classico efficiente fallirebbe (sotto le ipotesi di complessità standard).

4. Risultati Teorici Principali

Il teorema centrale (Teorema 5) stabilisce che per una vasta classe di compiti di identificazione quantistica, esiste un vantaggio quantistico esponenziale (o una separazione rigorosa) a meno che $BQP \subseteq HeurBPP^{NP^{NP^{NP}}}$.

La logica della prova (illustrata nella Figura 1 del paper) procede come segue:

1. Si assume l'esistenza di un algoritmo classico di identificazione approssimativamente corretto.
2. Per classi di concetti "c-distinct" o "smooth", questo algoritmo può essere trasformato in un algoritmo di identificazione "approssimativamente verificabile" che opera nel primo livello della PH (NP).
3. Utilizzando un oracolo NP, è possibile "invertire" questo algoritmo per costruire un dataset coerente con la funzione target.
4. Questo processo permette di valutare la funzione BQP utilizzando oracoli NP a livelli superiori, portando al collasso della gerarchia polinomiale (o alla dimostrazione che BQP è contenuto in un livello basso della PH), che è considerato improbabile.

5. Significato e Implicazioni

• Superamento della Durezza di Valutazione: Il paper dimostra che il vantaggio quantistico nel machine learning non è limitato alla fase di valutazione finale. Anche il processo di identificazione della funzione generatrice dei dati può essere intrinsecamente più efficiente per un computer quantistico.
• Rilevanza Fisica: A differenza di molti risultati teorici astratti, questo lavoro collega direttamente la durezza computazionale a compiti fisici reali, come l'apprendimento di osservabili, l'apprendimento di Hamiltoniani (in contesti specifici) e la determinazione di parametri d'ordine in sistemi di materia condensata.
• Limiti dell'Apprendimento Classico: I risultati suggeriscono che per molti compiti legati alla fisica quantistica, l'intero processo di apprendimento (dall'acquisizione dei dati all'identificazione del modello) beneficia della computazione quantistica, e non solo la fase di inferenza.
• Nuove Frontiere di Complessità: Il lavoro introduce nuove connessioni tra la teoria dell'apprendimento, la generazione di campioni e la gerarchia polinomiale, fornendo nuovi strumenti per analizzare la potenza relativa dei computer quantistici rispetto a quelli classici.

In sintesi, questo lavoro fornisce le prime prove formali che l'identificazione di funzioni quantistiche è un compito intrattabile per gli algoritmi classici (sotto ipotesi di complessità ragionevoli), aprendo la strada a una nuova comprensione dei vantaggi quantistici nel machine learning che va oltre la semplice valutazione di funzioni difficili.