Il problema dell’Hamiltoniana locale commutante: evidenza relativizzata contro la BQP-difficoltà

Abstract degli autori

Il problema dell’Hamiltoniana locale commutante (CLH) è una versione ristretta del problema dell’Hamiltoniana locale, in cui i termini dell’Hamiltoniana devono commutare a due a due. Un’ampia letteratura ha dimostrato che il problema appartiene a $\mathsf{NP}$ per alcune famiglie di Hamiltoniane locali commutanti. Tuttavia, non vi è stata alcuna evidenza formale contro la possibilità che il problema CLH generale sia $\mathsf{QMA}$-completo. CLH è completo per la classe di complessità $\mathsf{QIMA}$, definita tramite verificatori quantistici i cui gate locali commutano. Pertanto, CLH è $\mathsf{QMA}$-completo se e solo se $\mathsf{QIMA}=\mathsf{QMA}$. In questo lavoro introduciamo un analogo con oracolo classico, $\mathsf{QIMA}^{\mathcal{O}}$, e costruiamo un oracolo classico $\mathcal{O}$ tale che $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Poiché $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ per qualsiasi oracolo classico $\mathcal{O}$, ciò implica che $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ per l’oracolo che abbiamo costruito. Il nostro risultato fornisce quindi evidenza relativizzata contro la possibilità che il problema generale dell’Hamiltoniana locale commutante sia $\mathsf{BQP}$-difficile e, di conseguenza, anche contro la possibilità che sia $\mathsf{QMA}$-completo.