Ricottura quantistica

Ricottura quantistica. La ricottura quantistica (QA) è un processo di ottimizzazione per trovare il minimo globale di una data funzione obiettivo su un dato insieme di soluzioni candidate (stati candidati), mediante un processo che utilizza fluttuazioni quantistiche. La ricottura quantistica viene utilizzata principalmente per problemi in cui lo spazio di ricerca è discreto (problemi di ottimizzazione combinatoria) con molti minimi locali, come trovare lo stato fondamentale di un vetro di spin o risolvere problemi QUBO, che possono codificare un'ampia gamma di problemi come Max-Cut, colorazione dei grafici, SAT o il problema del commesso viaggiatore. Il termine "ricottura quantistica" è stato proposto per la prima volta nel 1988 da B. Apolloni, N. Cesa Bianchi e D. De Falco come algoritmo classico di ispirazione quantistica. È stato formulato nella sua forma attuale da T. Kadowaki e H. Nishimori (ja) nel 1998, sebbene una variante del tempo immaginario senza coerenza quantistica fosse stata discussa da A. B. Finnila, M. A. Gomez, C. Sebenik e J. D. Doll nel 1994.

Contesto teorico

La ricottura quantistica inizia da una sovrapposizione quantomeccanica di tutti gli stati possibili (stati candidati) con pesi uguali. Quindi il sistema evolve seguendo l'equazione di Schrödinger dipendente dal tempo, un'evoluzione quantomeccanica naturale dei sistemi fisici. Le ampiezze di tutti gli stati candidati continuano a cambiare, realizzando un parallelismo quantistico, secondo la forza dipendente dal tempo del campo trasversale, che provoca il tunneling quantistico tra gli stati o essenzialmente il tunneling attraverso i picchi. Se la velocità di variazione del campo trasversale è sufficientemente lenta, il sistema rimane vicino allo stato fondamentale dell'Hamiltoniano istantaneo (vedi anche calcolo quantistico adiabatico). Se la velocità di variazione del campo trasversale viene accelerata, il sistema può lasciare temporaneamente lo stato fondamentale ma produrre una maggiore probabilità di concludere nello stato fondamentale il problema finale hamiltoniano, cioè il calcolo quantistico diabatico. Il campo trasversale viene finalmente disattivato e ci si aspetta che il sistema abbia raggiunto lo stato fondamentale del modello di Ising classico che corrisponde alla soluzione del problema di ottimizzazione originale. Una dimostrazione sperimentale del successo della ricottura quantistica per magneti casuali è stata riportata subito dopo la proposta teorica iniziale. È stato anche dimostrato che la ricottura quantistica fornisce un veloce oracolo di Grover per l'accelerazione della radice quadrata nella risoluzione di molti problemi NP-completi.