QAOA la scară de utilitate

Urmărește videoclipul despre QAOA la scară de utilitate cu Olivia Lanes sau deschide videoclipul într-o fereastră separată pe YouTube.

Prezentarea lecției:

Până acum, în acest curs, sperăm că ți-am oferit o bază solidă a cadrului și instrumentelor necesare pentru a rezolva probleme la scară de utilitate pe un calculator cuantic. Acum vom vedea în sfârșit aceste instrumente în acțiune.

În această lecție, ne vom murdări mâinile cu un exemplu la scară de utilitate al problemei Max-Cut, care este o problemă celebră din teoria grafurilor ce implică cum să partiționezi optim un graf în două. Vom începe cu un graf simplu de cinci noduri pentru a ne construi intuiția despre cum ne poate ajuta un calculator cuantic să rezolvăm problema, apoi vom aplica aceasta la o versiune a problemei la scară de utilitate.

Această lecție va servi drept o prezentare generală a abordării pe care o folosim pentru a rezolva această problemă. Nu va fi o demonstrație pas cu pas a codului. Alături de această lecție există totuși un tutorial cu cod real pe care îl poți rula pentru a rezolva problema Max-Cut pe un calculator cuantic.

Problema

Ca reamintire, nu toate problemele computaționale sunt potrivite pentru calculul cuantic. „Problemele ușoare" nu vor obține niciun avantaj din această tehnologie, deoarece calculatoarele clasice le rezolvă deja foarte bine.

Cele trei cazuri de utilizare față de care suntem cel mai optimiști în privința explorării sunt:

1. simularea naturii
2. procesarea datelor cu structură complexă
3. optimizarea

Astăzi ne vom concentra pe cel de-al treilea caz de utilizare: optimizarea. Într-o problemă de optimizare, căutăm în general cea mai mare sau cea mai mică valoare posibilă pentru o funcție dată. Dificultatea de a găsi aceste extreme prin metode clasice poate crește exponențial pe măsură ce dimensiunea problemei crește.

Problema de optimizare care ne interesează astăzi se numește Max-Cut și o vom rezolva folosind un algoritm numit Quantum Approximate Optimization Algorithm (QAOA).

Ce este Max-Cut?

Pornim de la un graf, care constă dintr-o colecție de vârfuri (sau noduri), unele dintre ele conectate prin muchii. În problemă, ni se cere să împărțim nodurile grafului în două submulțimi prin „tăierea" muchiilor care le conectează. Vrem să găsim partiția care maximizează numărul de muchii tăiate în acest fel – de unde și numele „Max-Cut."

De exemplu, figura de mai sus arată un graf cu cinci noduri, cu soluția Max-Cut în dreapta. Aceasta taie prin cinci muchii, ceea ce este cel mai bun rezultat posibil pentru acest graf.

Deoarece un graf cu cinci noduri este atât de mic, nu e prea greu să determini Max-Cut în minte sau încercând câteva tăieturi pe o bucată de hârtie. Dar, după cum îți poți imagina, problema devine tot mai dificilă pe măsură ce numărul de vârfuri crește — parțial pentru că numărul de tăieturi posibile de luat în considerare crește exponențial față de numărul de noduri. La un moment dat, aceasta devine grea chiar și pentru supercalculatoare, folosind orice algoritm clasic cunoscut.

Am dori o modalitate de a rezolva problema Max-Cut pentru aceste grafuri mai mari și mai complexe, deoarece problema are multe aplicații practice, inclusiv detectarea fraudelor în finanțe, clusterizarea grafurilor, proiectarea rețelelor și analiza rețelelor sociale. Max-Cut este întâlnit adesea ca subproblemă în cadrul unei anumite abordări a unei probleme mai mari. Prin urmare, este mult mai frecvent decât am crede în mod naiv.

Soluția

Acum vom parcurge abordarea pe care o folosim pentru a rezolva problema Max-Cut pe un calculator cuantic. Vom face asta cu un graf simplu cu cinci noduri. Poți urma exemplul folosind tutorialul din notebook-ul Python. După acel exemplu simplu, tutorialul te va ghida printr-un exemplu la scară de utilitate al problemei.

Primul pas este să creezi graful definind numărul de noduri și muchiile care conectează două noduri. Poți face asta importând un pachet numit rustworkx, așa cum este demonstrat în tutorial. Rezultatul va fi un graf care arată astfel:

Vom folosi framework-ul de tipare Qiskit pentru a găsi soluțiile Max-Cut pentru acest graf pe calculatorul nostru cuantic.

Mapare

Trebuie să mapăm problema pe calculatorul nostru cuantic. Pentru a face asta, să observăm mai întâi că maximizarea numărului de tăieturi într-un graf poate fi scrisă matematic astfel:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

Unde $i$ și $j$ sunt noduri în graf, iar $x_i$ și $x_j$ sunt fie 0, fie 1, în funcție de care parte a partiției se află fiecare nod (un grup este etichetat „0" și celălalt „1"). Când $x_i$ și $x_j$ se află pe aceeași parte a partiției, expresia din sumă este egală cu zero. Când se află pe laturi opuse, deci există o tăietură între ele, expresia este egală cu unu. Prin urmare, maximizarea numărului de tăieturi va maximiza suma.

Putem, de asemenea, să inversăm acest lucru și să căutăm minimul înmulțind fiecare dintre valori cu minus unu.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

Acum suntem gata să mapăm. Poate părea descurajant să te gândești cum să treci de la un graf ca cel pe care tocmai l-am desenat la un Circuit cuantic. Dar vom proceda pas cu pas.

Amintește-ți că vom încerca să rezolvăm Max-Cut folosind QAOA. În metodologia QAOA, vrem în cele din urmă să avem un operator (sau, cu alte cuvinte, un Hamiltonian) care va fi folosit pentru a reprezenta funcția de cost a algoritmului nostru hibrid, precum și un Circuit parametrizat (ansatz-ul) pe care îl folosim pentru a reprezenta soluțiile posibile la problemă.

QUBO

Putem eșantiona din aceste soluții candidate și apoi le putem evalua folosind funcția de cost. Pentru a face asta, profităm de o serie de reformulări matematice, inclusiv notația Quadratic Unconstrained Binary Optimization — sau QUBO pe scurt — care este o modalitate utilă de a codifica problemele de optimizare combinatorie. În QUBO, vrem să găsim:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

unde $Q$ este o matrice $n\times n$ de numere reale, iar $n$ corespunde numărului de noduri din graful nostru, în cazul de față, cinci.

Pentru a aplica QAOA, trebuie să formulăm problema noastră ca un Hamiltonian — care este o funcție sau matrice ce reprezintă energia totală a unui sistem. Concret, vrem să creăm un Hamiltonian al funcției de cost care să aibă proprietatea că starea fundamentală corespunde valorii minime a funcției. Astfel, pentru a rezolva problema de optimizare, vom încerca să pregătim starea fundamentală a lui $H$ pe un calculator cuantic. Eșantionând din această stare, vom obține cu probabilitate mare soluția pentru $\min 𝑓(𝑥)$.

Maparea la un Hamiltonian al funcției de cost

Se dovedește că suntem norocoși, deoarece problema QUBO este foarte strâns legată de — și de fapt echivalentă din punct de vedere computațional cu — unul dintre cei mai celebri și ubicui Hamiltonieni din fizică: Hamiltonianul Ising.

Pentru a scrie problema QUBO ca Hamiltonianul Ising, tot ce trebuie să facem este o simplă schimbare de variabile:

$$x_i = \frac{1-z_i}{2}.$$

Nu vom parcurge toți pașii aici, dar aceștia sunt explicați în notebook-ul atașat. În final, minimizarea expresiei QUBO este echivalentă cu minimizarea acestei expresii:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Rescriind din nou ușor, obținem Hamiltonianul funcției de cost, unde minimul expresiei reprezintă starea fundamentală, Z este operatorul Pauli Z, iar $b$ este un coeficient scalar real:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Acum că avem Hamiltonianul nostru, trebuie să-l rescriem în termeni de operatori Pauli ZZ cu două locații, pe care îi putem converti ușor în porți cu doi qubiți în circuitul nostru cuantic. Vom ajunge cu șase obiecte — sau șiruri Pauli — unde fiecare corespunde unuia dintre cele șase muchii ale grafului. Fiecare dintre cele cinci elemente dintr-un șir reprezintă o operație pe un nod — identitatea dacă nodul nu este conectat la acea muchie particulară, și operatorul Pauli Z dacă este. În Qiskit, șirurile de biți care reprezintă qubiți sunt indexate invers. De exemplu, o muchie între nodurile 0 și 1 este codificată ca IIIZZ, iar o muchie între 2 și 4 este codificată ca ZIZII.

Construirea Circuit-ului cuantic

Cu Hamiltonianul nostru scris în termeni de operatori Pauli, suntem pregătiți să construim Circuit-ul nostru cuantic, care ne permite să eșantionăm soluții bune folosind un calculator cuantic:

Algoritmul QAOA se inspiră din Teorema Adiabatică, care afirmă că dacă pornim din starea fundamentală a unui Hamiltonian dependent de timp, dacă Hamiltonianul evoluează suficient de lent și dacă avem suficient timp, starea finală va fi starea fundamentală a Hamiltonianului final. QAOA poate fi gândit ca versiunea discretă, trotterizată a acestui Algoritm Cuantic Adiabatic, unde fiecare pas trotter reprezintă un strat al algoritmului QAOA. Astfel, în loc să evoluăm dintr-o stare în alta, în fiecare strat vom comuta înapoi și înainte între Hamiltonianul funcției noastre de cost și un așa-numit Hamiltonian „mixer", pe care îl vom acoperi mai târziu în această lecție.

Avantajul QAOA este că este mai rapid decât algoritmul cuantic adiabatic, dar returnează soluții aproximative în loc de cele optime. La limita în care numărul de straturi tinde la infinit, QAOA converge spre cazul QAA, dar desigur, aceasta este foarte costisitoare din punct de vedere computațional.

Pentru a crea Circuit-ul nostru cuantic, vom aplica operatori alternanți, parametrizați de $\gamma$ și $\beta$, care vor reprezenta discretizarea evoluției temporale.

Astfel, cele trei componente principale ale Circuit-ului QAOA sunt:

1. starea inițială de încercare, în gri, care este starea fundamentală a mixerului, creată prin aplicarea unui Gate Hadamard pe fiecare Qubit
2. evoluția funcției de cost, pe care am discutat-o anterior, în violet închis
3. evoluția sub Hamiltonianul mixer, pe care nu l-am acoperit încă, în violet deschis.

Hamiltonianul nostru de pornire se numește Mixer deoarece starea sa fundamentală este superpoziția tuturor șirurilor de biți posibile de interes: impunând astfel un amestec al tuturor soluțiilor posibile la început.

Hamiltonianul mixer este simpla sumă a operațiilor Pauli-X pe fiecare nod al grafului. Qiskit îți permite să folosești un operator mixer personalizat diferit dacă dorești, dar noi vom folosi cel standard aici. Deci, din nou, poți vedea că cu Qiskit, o mare parte din muncă este eliminată pentru noi, făcând găsirea Hamiltonianului mixer și a stării inițiale triviale. Singura muncă pe care a trebuit s-o facem a fost să găsim funcția de cost.

Fiecare iterație a acestor operatori se numește strat. Aceste straturi pot fi văzute ca discretizare a evoluției temporale a sistemului, așa cum a fost descris anterior. Modelul alternant provine din descompunerea trotter și aproximează funcțiile exponențiale ale matricelor necomutante. În general, cu cât includem mai multe straturi sau pași, cu atât ne apropiem mai mult de evoluția în timp continuu, ca în QAA, deci în teorie, cu atât rezultatul va fi mai precis. Dar pentru acest exemplu, vom începe prin a eșantiona cu un singur strat. Ține minte, atât Hamiltonianul funcției de cost, cât și mixerul sunt parametrizați; trebuie să găsim în continuare valorile optime pentru $\gamma$ și $\beta.$

Optimizare

Deși Circuit-ul pe care tocmai l-am creat pare destul de simplu și este util pentru a construi o înțelegere intuitivă, ține minte că cipul cuantic nu înțelege ce este Gate-ul QAOA. Trebuie să transformăm aceasta într-o serie de Gate-uri native cu un singur Qubit și cu doi qubiți, care pot fi executate direct pe hardware. Gate-urile native sunt cele care pot fi executate direct pe qubiți. Astfel de Circuit-uri se spune că sunt scrise în Arhitectura Setului de Instrucțiuni (ISA) a Backend-ului.

Biblioteca Qiskit oferă o serie de pași de transpilare care acoperă o gamă largă de transformări ale Circuit-ului. Vrem să ne asigurăm că Circuit-ul este optimizat pentru scopul nostru.

Amintește-ți din lecția noastră anterioară că procesul de transpilare implică mai mulți pași:

• Maparea inițială a qubiților din Circuit (adică variabilele de decizie) pe qubiții fizici ai dispozitivului.
• Desfășurarea instrucțiunilor din Circuit-ul cuantic în instrucțiunile native ale hardware-ului pe care Backend-ul le înțelege.
• Rutarea qubiților din Circuit care interacționează pe qubiți fizici adiacenți unul cu celălalt.

Și, ca întotdeauna, mai multe detalii despre aceasta pot fi găsite în documentație.

Înainte de a transpila, totuși, trebuie să alegem pe ce Backend vom rula Circuit-ul nostru, deoarece Transpiler-ul optimizează diferit pentru procesoare diferite. Acesta este încă un motiv pentru care este important să folosești un Transpiler automatizat — nu ai dori să treci prin procesul care consumă mult timp de optimizare manuală a Circuit-ului tău, doar pentru a realiza că de fapt vrei să rulezi Circuit-ul pe un alt procesor cu proprietăți diferite.

Trece Backend-ul ales prin funcția Transpiler-ului și specifică nivelul de optimizare. În tutorial, vei selecta nivelul 3, care este cel mai înalt și mai riguros nivel.

Și cu aceasta, avem un Circuit transpilat care este gata să fie executat pe hardware!

Execuție

Până acum, am transpilat Circuit-ul lăsând parametrii gamma și beta neatinși — dar nu putem rula efectiv Circuit-ul fără a specifica acești parametri. În fluxul de lucru QAOA, parametrii optimi QAOA sunt găsiți într-o buclă de optimizare iterativă, unde rulăm o serie de evaluări ale Circuit-ului și apoi folosim un optimizator clasic pentru a găsi parametrii optimi 𝛽 și 𝛾. Totuși, trebuie să pornim de undeva, deci facem o estimare inițială de $\gamma=\pi/2$ și $\beta=\pi.$

Moduri de execuție

Acum suntem aproape gata să rulăm Circuit-ul — promit! Dar mai întâi, este important să știi că poți trimite jobul în mai multe moduri diferite, numite moduri de execuție.

• Modul Job: O singură cerere primitivă a Estimator-ului sau Sampler-ului este efectuată fără un manager de context. Circuit-urile și intrările sunt ambalate ca blocuri unificate primitive (PUB-uri) și trimise ca sarcină de execuție pe calculatorul cuantic.

• Modul Batch: Un manager multi-job pentru rularea eficientă a unui experiment format dintr-un grup de joburi independente. Folosește modul batch pentru a trimite simultan mai multe joburi primitive.

• Modul Session: O fereastră dedicată pentru rularea unei sarcini de lucru cu mai multe joburi. Aceasta le permite utilizatorilor să experimenteze cu algoritmi variaționali într-un mod mai previzibil și chiar să ruleze mai multe experimente simultan, valorificând paralelismul din stivă. Folosește Session-uri pentru sarcini de lucru iterative sau experimente care necesită acces dedicat. Consultă „Rulează joburi într-o Session" pentru exemple.

Pentru un experiment QAOA, o Session ar fi o alegere bună dacă ai acces la ea, deoarece trebuie să eșantionăm Circuit-ul de multe ori cu valori diferite ale parametrilor pentru a găsi optimul.

Înapoi la problema de optimizare. Trebuie să găsim valori mai bune pentru gamma și beta decât simplele noastre prime estimări aproximative. Vom face asta introducând funcția noastră de cost și aceste estimări inițiale într-un optimizator scipy COBYLA.

Aici poți vedea valoarea funcției de cost de-a lungul iterațiilor. Începe puțin haotic și urcă și coboară, dar apoi se stabilizează la o valoare mică. Vom folosi valorile găsite de scipy care corespund celei mai mici evaluări a funcției de cost.

Acum că am reușit să reducem funcția de cost găsind valori mai bune ale parametrilor noștri, vom rula Circuit-ul folosind noile valori găsite pentru gamma și beta. Am listat valorile specifice pe care le folosesc aici, dar ține minte — când îți vei încerca mâna la asta sau chiar dacă vei rerula același notebook de tutorial, aceste valori s-ar putea schimba ușor. Acum vom rula Circuit-ul nostru optimizat cu aceste valori și vom găsi soluția candidat pentru problema noastră Max-Cut.

În etapa de post-procesare, vom analiza datele și vom afișa aceste rezultate pentru a vedea dacă algoritmul nostru cuantic a găsit soluțiile corecte.

Post-procesare

Acum să trasăm o histogramă a datelor pentru a examina soluția finală:

Șirurile de biți reprezintă modul în care fiecare dintre noduri a fost partiționat în două grupuri (etichetate „0" și „1") prin tăietură. Ar trebui să existe patru soluții care oferă toate valoarea maximă a muchiilor tăiate. Aceste patru sunt afișate în violet. Poți vedea imediat că 4 soluții sunt mult mai probabile decât oricare altele. Cel mai probabil șir de biți, și astfel cel mai probabil ca soluție, este 0,1,0,1,1. (Ține minte — ordinea Qubit-urilor este inversată în șirurile de biți din grafic!)

Din acest grafic, putem lua cel mai probabil șir de biți și îl putem reprezenta ca un graf partiționat, cu tăietura trecând prin cinci muchii:

Deci, aceasta este într-adevăr o soluție Max-Cut. Dar nu este singura! Din cauza simetriei acestui graf, există mai multe soluții corecte. În loc să avem nodurile 0 și 3 în interiorul tăieturii, am putea include nodurile 2 și 4. Poți vedea că tot ce a trebuit să fac a fost să rotesc tăietura pentru a include aceste noi puncte. Numărul de muchii tăiate rămâne cinci. Se dovedește că există patru soluții Max-Cut, deoarece fiecare dintre cele două soluții notate are și un „partener opus", unde nodurile violete sunt gri și nodurile gri sunt violete — deci tăietura rămâne aceeași, dar fiecare nod se mută efectiv pe partea opusă a partiției.

Să ne uităm din nou la histogramă și la cele patru soluții cele mai probabile pentru un moment. În mod ideal, acestea ar fi fiecare dintre cele patru soluții Max-Cut adevărate. Problema este că algoritmul de fapt nu a identificat a patra și ultima soluție ca fiind una dintre primele 4 cele mai probabile răspunsuri. A fost a cincea ca probabilitate. A patra soluție identificată de algoritm este incorectă — dacă ai desena-o, ai vedea că soluția are doar patru tăieturi.

Dar ține minte: acesta este un algoritm aproximativ. Nu este infailibil și nu este corect 100% din timp. Trebuie să folosești o parte din propriile cunoștințe și înțelegere pentru a verifica soluțiile.

Această eroare poate apărea din mai multe locuri:

1. Ar putea fi natura aproximativă a algoritmului în sine și numărul mic de straturi pe care le-am folosit.
2. Ar putea fi o eroare de eșantionare finită; aceasta ar putea fi redusă dacă măresc numărul de shots în experimentul meu.
3. Ar putea fi și o eroare de citire, deoarece a patra soluție reală diferă doar cu un bit.

Acest tip de analiză a erorilor este ceea ce trebuie să faci pentru a deveni un practician al informaticii cuantice. Trebuie să înțelegi performanța hardware-ului și cum poate aceasta contribui la anumite tipuri de erori și cum să le corectezi.

Totuși, să nu uităm că au existat 32 de șiruri de biți posibile și că cele patru soluții reale au fost incluse în primii cinci cei mai buni candidați. Și am folosit doar două straturi pentru a găsi asta. În general, dacă am vrea să creștem șansele de a găsi cel mai bun Max-Cut de fiecare dată, am putea crește adâncimea straturilor. Există câteva subtilități în legătură cu asta, dar acelea sunt pentru o lecție ulterioară.

La scară utilitară