Amplificazione del gap per Hamiltoniane locali con solidità combinatoria

Abstract degli autori

La congettura quantum PCP è uno dei principali problemi aperti della teoria della complessità quantistica. Finora ha resistito ai tentativi di soluzione, in parte perché molti strumenti impiegati nella dimostrazione del teorema classico PCP, come l’amplificazione del gap che preserva la località e la riduzione dell’alfabeto, non hanno analoghi quantistici evidenti a causa del no-cloning quantistico. L’amplificazione del gap che preserva la località è una procedura che prende in input un’istanza di un problema di Hamiltoniana locale e produce una nuova istanza con un gap di promessa più ampio, senza aumentare la località dell’Hamiltoniana e aumentando invece moderatamente la dimensione locale dei qudit. Ottenere questo tipo di controllo sulla località durante l’amplificazione del gap è fondamentale per il successo di molte strategie note per dimostrare il teorema classico PCP. In questo lavoro presentiamo il primo schema praticabile noto per l’amplificazione quantistica del gap che preserva la località e dimostriamo che la nostra procedura amplifica il gap combinatorio delle Hamiltoniane locali. Il nostro lavoro introduce un nuovo quadro per ragionare sull’amplificazione quantistica del gap in termini di computazione tollerante ai guasti e illumina una possibile strada per trasferire nell’ambito quantistico uno degli ingredienti centrali dei PCP classici. In particolare, ci basiamo sulle idee del recente PCP classico di Bafna--Minzer--Vyas, fondato su espansori ad alta dimensionalità, e sulla costruzione da circuito a Hamiltoniana di Anshu--Breuckmann--Nguyen, oltre che su diversi recenti progressi nella teoria dei codici quantistici.