Durezza nel caso medio della stima del numero di Betti

Abstract degli autori

Dimostriamo la durezza nel caso medio della stima del numero di Betti su complessi di clique casuali mediante una riduzione dal problema della clique piantata. Mostriamo inoltre che la nostra riduzione implica una serie di risultati di durezza per molti problemi nell’analisi topologica dei dati (TDA) classica e quantistica (qTDA). Sotto la congettura classica della clique piantata, nessuno stimatore randomizzato del numero di Betti in tempo polinomiale raggiunge un errore additivo inferiore a $\tfrac12$ con vantaggio costante. Sotto una nuova congettura quantistica della clique piantata, che introduciamo, la stessa conclusione vale per gli algoritmi quantistici in tempo polinomiale. Otteniamo inoltre risultati condizionali di durezza correlati per l’annullamento dell’omologia, approssimazioni additive con tolleranze d’errore maggiori, la preparazione di stati simplex e armonici, il recupero dei cicli e il conteggio degli autovalori a bassa energia. La nostra riduzione chiarisce i requisiti strutturali per ottenere un vantaggio quantistico nella TDA e offre una nuova prospettiva per indagare la complessità classica e quantistica dei problemi correlati.