CV-QAOA: ottimizzazione quantistica efficiente a bassa profondità di variabili continue

Abstract degli autori

Studiamo un algoritmo di ottimizzazione approssimata quantistica a variabili continue (CV-QAOA) per l’ottimizzazione continua ad alta dimensionalità. La nostra formulazione estende una proposta precedente di CV-QAOA con uno stato iniziale ottimizzato variazionalmente e recupera le garanzie di convergenza di Quantum Hamiltonian Descent (QHD) nel limite di alta profondità. Dimostriamo rigorose garanzie di prestazione di CV-QAOA per diverse famiglie di funzioni di costo. Per prima cosa, mostriamo che CV-QAOA a $d$ passi minimizza qualsiasi funzione quadratica strettamente convessa in $d$ dimensioni con $2d$ interrogazioni quantistiche alla funzione di costo. Analizziamo poi una famiglia di funzioni non convesse «Rotated Double Well» (RDW), con $2^d$ minimi locali, introdotta da arXiv:2311.00811. Mentre lavori precedenti hanno mostrato che QHD raggiunge il minimo globale con $\tilde O(d^3)$ interrogazioni, dimostriamo che CV-QAOA a 1 passo risolve RDW con appena due interrogazioni quantistiche. Sebbene i risolutori classici di uso generale richiedano un tempo superpolinomiale per RDW e la consapevolezza della struttura possa ridurre il costo a un tempo polinomiale, mostriamo che il protocollo CV-QAOA a 1 passo può essere dequantizzato in modo efficiente e che una ricerca lineare allineata al gradiente riesce con $O(d)$ interrogazioni, avvicinandosi al limite inferiore informativo di $Ω(d/\log d)$ interrogazioni. Per andare oltre il regime dequantizzabile, introduciamo il problema «Rotated Square Well» (RSW), il cui paesaggio globalmente piatto sopprime le informazioni utili fornite dai gradienti locali. Per questa famiglia, mostriamo che un’evoluzione adiabatica simulata da CV-QAOA può raggiungere il minimo globale usando $d^{o(1)}$ interrogazioni. D’altra parte, dimostriamo che qualsiasi algoritmo classico che apprenda la rotazione nascosta in RSW richiede almeno $Ω(d^2/\log d)$ interrogazioni; un limite a cui ci avviciniamo con un algoritmo classico esplicito che usa $Θ(d^2\log d)$ interrogazioni. Le simulazioni numeriche sulle funzioni della molla corrugata deviata e di Easom illustrano le promettenti prestazioni di CV-QAOA su problemi più generali.