Limiti quasi ottimali sulla densità degli stati a bassa energia degli Hamiltoniani $k$-locali e algoritmi quantistici più veloci

Abstract degli autori

La stima delle energie basse e la preparazione degli stati per Hamiltoniani generali $k$-locali sono sfide fondamentali nella teoria della complessità quantistica. Buhrman et al.~ [BGLGST, PRL 2025] hanno recentemente superato il limite naturale di Grover $O^\ast(2^{n/2})$ per entrambi i problemi, con un miglioramento che dipende dall’accuratezza relativa $\varepsilon$ e dalla località $k$. In questo lavoro presentiamo algoritmi quantistici esponenziali più veloci per questi problemi, il cui esponente del tempo di esecuzione è determinato dalla funzione di entropia binaria. Per valori sufficientemente piccoli di $\varepsilon/k$, i nostri algoritmi migliorano l’esponente di un fattore pari a $\log(k/\varepsilon)$ rispetto a [BGLGST, PRL 2025]. Il nostro principale risultato tecnico è un limite inferiore, governato dall’entropia, sulla dimensione del sottospazio a bassa energia dell’Hamiltoniana, ottenuto depolarizzando il suo stato fondamentale. Per $k$ fissato, questo limite è ottimale a meno di fattori costanti nell’esponente. Lo stesso quadro teorico fornisce limiti più stringenti per i modelli di Heisenberg, $XY$ e Ising su grafi di interazione arbitrari.