QAOA ve velkém měřítku

Podívej se na video o QAOA ve velkém měřítku od Olivie Lanes, nebo ho otevři v samostatném okně na YouTube.

Přehled lekce:

Doufáme, že jsme ti v tomto kurzu dosud poskytli pevný základ rámce a nástrojů potřebných k řešení problémů ve velkém měřítku na kvantovém počítači. Teď se tyto nástroje konečně podíváme v akci.

V této lekci se pustíme do příkladu problému Max-Cut ve velkém měřítku, což je slavný problém z teorie grafů zabývající se tím, jak co nejlépe rozdělit graf na dvě části. Začneme jednoduchým grafem s pěti uzly, abychom si vybudovali intuici pro to, jak nám kvantový počítač může pomoci problém vyřešit, a pak to aplikujeme na verzi tohoto problému ve velkém měřítku.

Tato lekce bude sloužit jako obecný přehled přístupu, který používáme k řešení tohoto problému. Nepůjde o průchod kódem. K lekci ale patří tutoriál se skutečným kódem, který si můžeš spustit a vyřešit tak problém Max-Cut na kvantovém počítači.

Problém

Připomínám, že ne všechny výpočetní problémy jsou vhodné pro kvantové výpočty. Z „jednoduchých problémů" tato technologie žádnou výhodu nepřinese, protože klasické počítače je řeší bez problémů.

Tři oblasti, ve kterých jsme nejvíce optimističtí ohledně zkoumání, jsou:

1. simulace přírody
2. zpracování dat se složitou strukturou
3. optimalizace

Dnes se zaměříme na třetí oblast – optimalizaci. V optimalizačním problému obecně hledáme největší nebo nejmenší možnou hodnotu dané funkce. Obtížnost nalezení těchto extrémů klasickými metodami může exponenciálně růst s velikostí problému.

Optimalizační problém, který nás dnes zajímá, se nazývá Max-Cut a budeme ho řešit algoritmem zvaným Quantum Approximate Optimization Algorithm (QAOA).

Co je Max-Cut?

Začínáme grafem, který tvoří kolekce vrcholů (neboli uzlů), z nichž některé jsou spojeny hranami. V tomto problému máme za úkol rozdělit uzly grafu do dvou podmnožin „přeřezáním" hran, které je spojují. Chceme najít takové rozdělení, které maximalizuje počet takto přeřezaných hran – odtud název „Max-Cut."

Na obrázku výše je například pětiuzlový graf s řešením Max-Cut vpravo. Prochází pěti hranami, což je pro tento graf nejlepší možný výsledek.

Protože je pětiuzlový graf tak malý, není příliš těžké Max-Cut zjistit v hlavě nebo vyzkoušením několika řezů na papíře. Jak si ale dokážeš představit, problém se stává čím dál těžším s rostoucím počtem vrcholů – mimo jiné proto, že počet možných řezů, které je třeba zvážit, roste exponenciálně s počtem uzlů. A v určitém bodě je to obtížné i pro superpočítače při použití jakýchkoli známých klasických algoritmů.

Rádi bychom nalezli způsob, jak řešit problém Max-Cut pro tyto větší, složitější grafy, protože má mnoho praktických aplikací, včetně odhalování podvodů ve financích, shlukování grafů, návrhu sítí a analýzy sociálních médií. Max-Cut se často vyskytuje jako podproblém v rámci konkrétního přístupu k většímu problému. Je tedy mnohem běžnější, než bychom si naivně mysleli.

Řešení

Teď si projdeme přístup, který používáme k řešení problému Max-Cut na kvantovém počítači. Provedeme to na jednoduchém pětiuzlovém grafu. Můžeš sledovat v tutoriálu v pythonském notebooku. Po tomto jednoduchém příkladu tě tutoriál provede příkladem tohoto problému ve velkém měřítku.

Prvním krokem je vytvoření grafu definováním počtu uzlů a hran, které spojují dva uzly. Uděláš to importem balíčku rustworkx, jak je ukázáno v tutoriálu. Výsledkem bude graf, který vypadá takto:

K nalezení řešení Max-Cut pro tento graf na kvantovém počítači použijeme rámec Qiskit patterns.

Mapování

Musíme problém namapovat na náš kvantový počítač. Nejprve si všimni, že maximalizaci počtu řezů v grafu lze matematicky zapsat jako:

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

kde $i$ a $j$ jsou uzly grafu a $x_i$ a $x_j$ nabývají hodnot 0 nebo 1 podle toho, na které straně rozdělení se daný uzel nachází (jedna skupina je označena „0" a druhá „1"). Jsou-li $x_i$ a $x_j$ na stejné straně rozdělení, výraz v součtu se rovná nule. Jsou-li na opačných stranách – tedy existuje mezi nimi řez – výraz se rovná jedné. Maximalizace počtu řezů proto odpovídá maximalizaci tohoto součtu.

Můžeme to také obrátit a hledat minimum tak, že všechny hodnoty vynásobíme zápornou jedničkou.

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

Teď jsme připraveni přistoupit k samotnému mapování. Přechod od grafu, který jsme právě nakreslili, ke kvantovému Circuit může působit skličujícím dojmem – provedeme ho ale krok za krokem.

Pamatuj, že budeme řešit Max-Cut pomocí QAOA. V metodologii QAOA potřebujeme nakonec mít operátor (jinak řečeno Hamiltonián), který bude reprezentovat nákladovou funkci našeho hybridního algoritmu, a dále parametrizovaný Circuit (ansatz), jímž vyjadřujeme možná řešení problému.

QUBO

Z těchto kandidátních řešení můžeme vzorkovat a pak je vyhodnotit pomocí nákladové funkce. K tomu využijeme řadu matematických přeformulování, mimo jiné notaci Quadratic Unconstrained Binary Optimization – zkráceně QUBO –, což je užitečný způsob kódování kombinatorických optimalizačních problémů. V QUBO hledáme:

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

kde $Q$ je matice reálných čísel o rozměru $n\times n$ a $n$ odpovídá počtu uzlů v grafu – tady je to pět.

Abychom mohli použít QAOA, musíme náš problém zformulovat jako Hamiltonián – funkci nebo matici reprezentující celkovou energii systému. Konkrétně chceme sestavit Hamiltonián nákladové funkce s tou vlastností, že základní stav odpovídá minimální hodnotě funkce. Abychom tedy vyřešili náš optimalizační problém, pokusíme se připravit základní stav $H$ na kvantovém počítači. Vzorkování z tohoto stavu pak s vysokou pravděpodobností poskytne řešení $\min 𝑓(𝑥)$.

Mapování na Hamiltonián nákladové funkce

Máme štěstí: QUBO problém totiž úzce souvisí s jedním z nejslavnějších a nejrozšířenějších Hamiltonánů ve fyzice – Isingovým Hamiltonánem – a ve skutečnosti je mu výpočetně ekvivalentní.

Abychom mohli QUBO problém zapsat jako Isingův Hamiltonián, stačí provést jednoduchou změnu proměnných:

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

Všechny kroky zde rozebírat nebudeme, jsou ale vysvětleny v přiloženém notebooku. Výsledkem je, že minimalizace QUBO výrazu je totéž co minimalizace tohoto výrazu:

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

Po dalším mírném přepsání dostaneme Hamiltonián nákladové funkce, kde minimum výrazu reprezentuje základní stav, Z je Pauliho operátor Z a $b$ je reálný skalární koeficient:

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

Teď, když máme svůj Hamiltonián, ho potřebujeme přepsat pomocí dvoulokálních Pauliho operátorů ZZ, které lze snadno převést na dvouQubitové Gate v našem kvantovém Circuit. Výsledkem bude šest objektů – tzv. Pauliho řetězců (Pauli strings) –, kde každý odpovídá jedné z šesti hran grafu. Každý z pěti prvků řetězce reprezentuje operaci na uzlu: identita, pokud uzel k dané hraně nepatří, a Pauliho operátor Z, pokud patří. V Qiskitu jsou bitové řetězce reprezentující Qubity indexovány pozpátku. Například hrana mezi uzly 0 a 1 je zakódována jako IIIZZ a hrana mezi uzly 2 a 4 jako ZIZII.

Sestavení kvantového Circuit

Když máme Hamiltonián zapsaný pomocí Pauliho operátorů, jsme připraveni sestavit kvantový Circuit, který nám umožní vzorkovat dobrá řešení na kvantovém počítači:

Algoritmus QAOA čerpá inspiraci z adiabatického teorému, který říká, že pokud začneme v základním stavu časově závislého Hamiltoniánu a ten se vyvíjí dostatečně pomalu a po dostatečně dlouhou dobu, bude výsledný stav základním stavem konečného Hamiltoniánu. QAOA lze chápat jako diskrétní, trotterizovanou verzi tohoto kvantového adiabatického algoritmu, kde každý trotterovský krok představuje jednu vrstvu QAOA. Namísto plynulého přechodu z jednoho stavu do druhého tedy v každé vrstvě střídavě přecházíme mezi Hamiltonánem nákladové funkce a tzv. „mixerovým" Hamiltonánem, který si popíšeme za chvíli.

Výhodou QAOA je, že je rychlejší než kvantový adiabatický algoritmus, avšak vrací přibližná řešení namísto optimálních. V limitě, kdy počet vrstev jde do nekonečna, QAOA konverguje k výsledku kvantového adiabatického algoritmu, což je ovšem výpočetně velmi nákladné.

Pro sestavení kvantového Circuit použijeme střídající se operátory parametrizované hodnotami $\gamma$ a $\beta$, které reprezentují diskretizaci časového vývoje.

Tři hlavní části Circuit QAOA jsou tedy:

1. počáteční zkušební stav, zobrazený šedě, což je základní stav mixeru, vytvořený aplikací Hadamardova Gate na každý Qubit
2. evoluce pod Hamiltonánem nákladové funkce, o níž jsme mluvili dříve, zobrazená tmavě fialově
3. evoluce pod mixerovým Hamiltonánem, který jsme zatím neprobírali, zobrazená světle fialově.

Náš počáteční Hamiltonián se nazývá Mixer, protože jeho základní stav je superpozicí všech možných bitových řetězců, které nás zajímají – čímž se na začátku vynucuje směs všech možných řešení.

Mixerový Hamiltonián je jednoduchý součet Pauliho operátorů X na každém uzlu grafu. Qiskit ti umožňuje použít jiný, vlastní mixerový operátor, ale my zde použijeme standardní. Vidíš tedy, že Qiskit za nás odstraňuje spoustu práce – nalezení mixerového Hamiltoniánu a počátečního stavu je triviální. Jediná práce, kterou jsme museli udělat, bylo sestavení nákladové funkce.

Každá iterace těchto operátorů se nazývá vrstva. Tyto vrstvy lze chápat jako diskretizaci časového vývoje systému, jak jsme popsali dříve. Střídavý vzor vychází z trotterova rozkladu a aproximuje exponenciální funkce nekomutujících matic. Obecně platí: čím více vrstev nebo kroků zahrneme, tím blíže budeme k vývoji ve spojitém čase jako v kvantovém adiabatickém algoritmu, a výsledek by tedy v teorii měl být přesnější. Pro tento příklad ale začneme vzorkováním pouze s jednou vrstvou. Pamatuj, že jak Hamiltonián nákladové funkce, tak mixer jsou parametrizovány – stále ještě potřebujeme najít optimální hodnoty $\gamma$ a $\beta.$

Optimalizace

Ačkoliv obvod, který jsme právě vytvořili, vypadá dost jednoduše a hodí se k budování intuitivního porozumění, pamatuj, že kvantový čip neví, co je to QAOA hradlo. Musíme ho převést na sérii jednobitových a dvobitových „nativních" hradel, která lze přímo provádět na hardwaru. Nativní hradla jsou ta, jež lze přímo aplikovat na qubity. O takovýchto obvodech se říká, že jsou zapsány v Instrukční sadě architektury (ISA) backendu.

Knihovna Qiskit nabízí řadu transpilačních průchodů, které pokrývají širokou škálu transformací obvodů. Chceme se ujistit, že obvod je optimalizován pro náš účel.

Vzpomeň si z předchozí lekce, že proces transpilace zahrnuje několik kroků:

• Počáteční mapování qubitů v obvodu (tj. rozhodovacích proměnných) na fyzické qubity zařízení.
• Rozbalení instrukcí v kvantovém obvodu na nativní hardwarové instrukce, kterým backend rozumí.
• Směrování qubitů v obvodu, které spolu interagují, na fyzické qubity sousedící navzájem.

A jako vždy, další podrobnosti najdeš v dokumentaci.

Před transpilací ale musíme zvolit, na kterém backendu náš obvod spustíme, protože transpilér optimalizuje jinak pro různé procesory. To je další důvod, proč je důležité používat automatizovaný transpilér — nechceš přece procházet časově náročným procesem ruční optimalizace obvodu, aby ses pak zjistil/a, že chceš obvod spustit na jiném procesoru s jinými vlastnostmi.

Předej svůj vybraný backend transpilační funkci a urči úroveň optimalizace. V tutoriálu si zvolíš úroveň 3, která je nejvyšší a nejdůkladnější.

A s tím máme transpilovaný obvod připravený ke spuštění na hardwaru!

Spuštění

Doposud jsme transpilovali obvod a nechali parametry gamma a beta stranou — ale obvod nemůžeme skutečně spustit bez jejich zadání. V rámci workflow QAOA se optimální parametry QAOA hledají v iterační optimalizační smyčce, kde spouštíme sérii vyhodnocení obvodu a poté používáme klasický optimalizátor k nalezení optimálních parametrů 𝛽 a 𝛾. Musíme však někde začít, takže zadáme počáteční odhad $\gamma=\pi/2$ a $\beta=\pi.$

Režimy spuštění

Nyní jsme téměř připraveni spustit obvod — slibuji! Ale nejprve je důležité poznamenat, že svou úlohu můžeš odeslat různými způsoby, které se nazývají režimy spuštění.

• Režim úlohy (Job mode): Je provedena jediná primitiva žádost estimátoru nebo sampleru bez správce kontextu. Obvody a vstupy jsou zabaleny jako primitive unified blocs (PUBs) a odeslány jako úloha ke spuštění na kvantovém počítači.

• Dávkový režim (Batch mode): Správce více úloh pro efektivní spouštění experimentu sestaveného ze svazku nezávislých úloh. Dávkový režim použij k současnému odeslání více primitiva úloh.

• Režim session (Session mode): Vyhrazené okno pro spouštění víceúlohové zátěže. To umožňuje uživatelům experimentovat s variačními algoritmy předvídatelnějším způsobem a dokonce spouštět více experimentů současně s využitím paralelismu v zásobníku. Použij session pro iterativní pracovní zátěže nebo experimenty vyžadující vyhrazený přístup. Příklady najdeš v části Spouštění úloh v session.

Pro QAOA experiment by session byla dobrá volba, pokud k ní máš přístup, protože potřebujeme vzorkovat náš obvod mnohokrát s různými hodnotami parametrů, abychom nalezli optimum.

Zpět k optimalizačnímu problému. Potřebujeme najít lepší hodnoty gamma a beta než jen naše hrubé první odhady. Uděláme to tím, že zapojíme naši cenovou funkci a tyto počáteční odhady do scipy optimalizátoru COBYLA.

Zde vidíš hodnotu cenové funkce v průběhu iterací. Zpočátku trochu poskakuje nahoru a dolů, ale pak se ustálí na nízké hodnotě. Použijeme hodnoty, které scipy nalezlo a které odpovídají nejnižšímu vyhodnocení cenové funkce.

Nyní, když jsme dokázali snížit naši cenovou funkci nalezením lepších hodnot parametrů, spustíme náš obvod s novými hodnotami, které jsme nalezli pro gamma a beta. Vypsal/a jsem konkrétní hodnoty, které zde používám, ale pamatuj, že až si to sám/sama vyzkoušíš nebo i jen znovu spustíš stejný tutoriálový notebook, tyto hodnoty se mohou mírně lišit. Nyní spustíme náš optimalizovaný obvod s těmito hodnotami a najdeme kandidátní řešení našeho Max-Cut problému.

Ve fázi post-processingu analyzujeme data a zobrazíme výsledky, abychom zjistili, zda náš kvantový algoritmus nalezl správná řešení.

Post-processing

Nyní vykreslíme histogram dat, abychom se podívali na konečné řešení:

Bitové řetězce představují, jak byly jednotlivé uzly rozděleny do dvou skupin (označených „0" a „1") řezem. Měla by existovat čtyři řešení, která všechna dávají maximální hodnotu přeřezaných hran. Tato čtyři jsou znázorněna fialově. Hned vidíš, že 4 řešení jsou mnohem pravděpodobnější než ostatní. Nejvyšší, a tedy nejpravděpodobnější bitový řetězec řešení je 0,1,0,1,1. (Pamatuj – pořadí qubitů je v bitových řetězcích grafu obrácené!)

Z tohoto grafu můžeme vzít nejpravděpodobnější bitový řetězec a zobrazit ho jako rozděleného grafu s řezem procházejícím pěti hranami:

Toto je skutečně řešení Max-Cut. Ale není jediné! Kvůli symetrii tohoto grafu existuje více správných řešení. Místo toho, aby uzly 0 a 3 byly uvnitř řezu, mohly by být zahrnuty uzly 2 a 4. Vidíš, že jsem musel/a udělat jen to, že jsem otočil/a řez tak, aby zahrnoval tyto nové body. Počet přeřezaných hran zůstává pět. Ukazuje se, že existují čtyři řešení max cut, protože každé ze dvou řešení, která jsme zaznamenali, má také „opačného" partnera, kde jsou fialové uzly šedé a šedé uzly fialové – takže řez zůstává stejný, ale každý uzel se efektivně přepne na opačnou stranu oddílu.

Podívejme se ještě chvíli na histogram a čtyři nejpravděpodobnější řešení. Ideálně by každé z nich bylo jedním ze čtyř skutečných řešení Max-Cut. Problém je, že algoritmus ve skutečnosti neidentifikoval čtvrté a poslední řešení jako jedno ze čtyř nejpravděpodobnějších odpovědí. Bylo páté nejpravděpodobnější. Čtvrté řešení, které algoritmus identifikoval, je nesprávné — kdybys ho nakreslil/a, viděl/a bys, že řešení má pouze čtyři řezy.

Ale pamatuj: jde o přibližný algoritmus. Není neomylný a není správný 100 % času. Musíš použít část vlastních znalostí a porozumění, abys provedl/a základní kontrolu správnosti řešení.

Tato chyba může vzniknout z několika příčin:

1. Může jít o přibližnou povahu samotného algoritmu a malý počet vrstev, které jsem použil/a.
2. Může jít o chybu konečného vzorkování, kterou lze snížit zvýšením počtu shots v experimentu.
3. Může jít také o chybu čtení (readout error), protože čtvrté skutečné řešení se liší jen o jeden bit.

Tento druh analýzy chyb je to, co je potřeba k tomu, aby ses stal/a praktikem kvantového počítání. Musíš rozumět výkonu hardwaru a tomu, jak může přispívat k určitým typům chyb a jak je opravovat.

Nezapomínejme však, že existovalo 32 možných bitových řetězců a čtyři skutečná řešení byla zahrnuta v pěti nejlepších kandidátech. A použili jsme k tomu pouze dvě vrstvy. Obecně, kdybychom chtěli zvýšit šance na nalezení nejlepšího Max-Cut pokaždé, mohli bychom zvýšit hloubku vrstev. Jsou s tím spojeny určité jemnosti, ale to je na pozdější lekci.

Ve velkém měřítku (utility-scale)

Teď, když sis vyzkoušel/a řešení malého Max-Cut problému na kvantovém počítači, vyzývám tě, abys to zkusil/a ve velkém měřítku. Sleduj přiložený tutoriál a zjisti, kolik řezů dokážeš získat v grafu s 125 uzly.