Google sta correndo per sviluppare processori quantistici che utilizzano effetti meccanici quantistici per aumentare la velocità con cui i dati possono essere elaborati. A breve termine, Google ha ideato nuovi algoritmi quantistici che operano in presenza di rumore realistico. Il cosiddetto algoritmo di ottimizzazione approssimata quantistica, o QAOA in breve, è la pietra angolare di una moderna spinta verso lo sviluppo di algoritmi quantistici tolleranti al rumore.

Il celebre approccio adottato da Google in QAOA ha suscitato un vasto interesse commerciale e ha acceso una comunità di ricerca globale per esplorare nuove applicazioni. Ancora, si sa poco sui limiti delle prestazioni finali dell'algoritmo QAOA di Google.

Un team di scienziati del Deep Quantum Laboratory di Skoltech ha raccolto questa sfida contemporanea. Il team all-Skoltech guidato dal Prof. Jacob Biamonte ha scoperto e quantificato quello che sembra essere un limite fondamentale nell'approccio ampiamente adottato avviato da Google.

Informare Lettere di revisione fisica , gli autori descrivono dettagliatamente la scoperta dei cosiddetti deficit di raggiungibilità:gli autori mostrano che questi deficit pongono un limite fondamentale alla capacità di QAOA di approssimare anche una soluzione a un problema, esempio.

I risultati del team di Skoltech riportano una chiara limitazione dell'algoritmo quantistico QAOA variazionale. QAOA e altri algoritmi quantistici variazionali si sono rivelati estremamente difficili da analizzare utilizzando tecniche matematiche note a causa di un processo di feedback interno da quantistico a classico. Vale a dire, un dato calcolo quantistico può essere eseguito solo per un determinato periodo di tempo. Dentro questo tempo fisso, è possibile eseguire un numero fisso di operazioni quantistiche. QAOA cerca di utilizzare queste operazioni quantistiche in modo iterativo formando una sequenza di approssimazioni sempre più ottimali per minimizzare una funzione obiettivo. Lo studio pone nuovi limiti a questo processo.

Gli autori hanno scoperto che la capacità di QAOA di approssimare soluzioni ottimali per qualsiasi circuito quantistico a profondità fissa dipende fondamentalmente dalla "densità" dei problemi. Nel caso del problema chiamato MAX-SAT, la cosiddetta densità può essere definita come il rapporto tra i vincoli dei problemi e il conteggio delle variabili. Questo è talvolta chiamato densità di clausole.

Gli autori hanno scoperto casi problematici di alta densità con soluzioni ottimali che non possono essere approssimate con successo garantito, indipendentemente dal tempo di esecuzione dell'algoritmo.