Il bilanciamento dei gradi come confine di complessità a grana fine per il SAT quantistico

Abstract degli autori

Il problema hamiltoniano locale è il problema canonico completo per $\mathsf{QMA}$; nel caso peggiore, è noto che può essere risolto con algoritmi classici in tempo $O(2^n)$ e con algoritmi quantistici in tempo $O(2^{n/2})$. Non è chiaro come migliorare queste strategie brute force per un’ampia classe di istanze del problema, perché in generale gli stati fondamentali sono altamente entangled e non possiamo applicare direttamente le strategie note per i CSP classici. In questo lavoro presentiamo algoritmi classici e quantistici esponenzialmente più veloci, sotto due ipotesi deboli: (1) l’hamiltoniana è priva di frustrazione nelle istanze YES e (2) è approssimativamente regolare, ossia ogni qubit è soggetto a un numero approssimativamente uguale di vincoli. Completiamo questi limiti superiori mostrando che, assumendo (Q)SETH, il quantum 5-SAT non ammette accelerazioni non banali nel caso peggiore. Il nostro limite inferiore dimostra inoltre che la dipendenza dei nostri algoritmi dalla regolarità è, in un certo senso, quasi ottimale. In particolare, il quantum 5-SAT rimane difficile per (Q)SETH anche per hamiltoniane in cui tutti i qubit tranne $O(\sqrt{n})$ partecipano a un numero costante di vincoli, mentre ciascuno dei restanti $O(\sqrt{n})$ qubit partecipa a $O(\sqrt{n})$ vincoli. Al contrario, se si riduce di un fattore $n^δ$ la dimensione di questo sottoinsieme di qubit ad alto grado oppure il grado dei suoi qubit, per qualsiasi $δ>0$, il nostro algoritmo risolve il problema in tempo $O(2^{(1- \varepsilon)n})$ per qualche $\varepsilon>0$. Nel loro insieme, i nostri limiti superiori e inferiori stabiliscono una dicotomia di complessità a grana fine per la soddisfacibilità quantistica.