Utility-scale QAOA

Panoorin ang video tungkol sa utility-scale QAOA ni Olivia Lanes, o buksan ang video sa hiwalay na window sa YouTube.

Pangkalahatang-ideya ng aralin:

Sa ngayon sa kursong ito, umaasa kaming nabigyan namin kayo ng matibay na pundasyon ng framework at mga tool na kailangan para malutas ang mga utility-scale na problema sa isang quantum computer. Ngayon, makikita na natin ang mga tool na ito na ginagamit sa aksyon.

Sa araling ito, makikipaglaro tayo sa isang utility-scale na halimbawa ng Max-Cut problem, na isang sikat na problema sa graph theory tungkol sa kung paano pinakamahusay na hatiin ang isang graph sa dalawa. Magsisimula tayo sa isang simpleng five-node graph para mabuo ang ating intuwisyon kung paano makakatulong ang isang quantum computer sa paglutas ng problema, pagkatapos ay ilalapat natin ito sa isang utility-scale na bersyon ng problema.

Ang araling ito ay magsisilbing malawak na pangkalahatang-ideya ng paraan ng ating pagtackle sa problemang ito. Hindi ito magiging code walk-through. Kasama ng araling ito, may tutorial na may aktwal na code na maaari mong patakbuhin para malutas ang Max-Cut problem sa isang quantum computer.

Ang Problema

Bilang paalala, hindi lahat ng mga computational problem ay angkop para sa quantum computing. Ang mga "madaling problema" ay hindi makakakuha ng anumang kalamangan mula sa teknolohiyang ito dahil mahusay na ang mga klasikal na computer sa paglutas ng mga ito.

Ang tatlong use-case na pinakaoptimistiko nating tuklasin ay:

1. pagsimulate ng kalikasan
2. pagproseso ng data na may kumplikadong istraktura
3. optimization

Ngayon, magtutuon tayo sa ikatlong use-case, ang optimization. Sa isang optimization problem, karaniwang naghahanap tayo ng pinakamalaki o pinakamaliit na posibleng halaga para sa isang ibinigay na function. Ang kahirapan ng paghanap ng mga extrema na ito gamit ang mga klasikal na paraan ay maaaring lumago nang exponential habang lumalaki ang laki ng problema.

Ang optimization problem na interesado tayo ngayon ay tinatawag na Max-Cut, na lululusin natin gamit ang isang algorithm na tinatawag na Quantum Approximate Optimization Algorithm (QAOA).

Ano ang Max-Cut?

Nagsisimula tayo sa isang graph, na binubuo ng koleksyon ng mga vertex (o node), kung saan ang ilan ay konektado ng mga edge. Sa problema, hinihingi sa atin na hatiin ang mga node ng graph sa dalawang subset sa pamamagitan ng "pagputol" ng mga edge na nag-uugnay sa kanila. Gusto nating hanapin ang partisyon na nagpapalaki ng bilang ng mga edge na naputol sa ganitong paraan — kaya ang pangalan, "Max-Cut."

Halimbawa, ang figure sa itaas ay nagpapakita ng isang five-node graph na may Max-Cut solution sa kanan. Ito ay nagputol ng limang edge, na siyang pinakamahusay na magagawa sa graph na ito.

Dahil napakaliit ng isang five-node graph, hindi masyadong mahirap malaman ang Max-Cut sa isip o sa pamamagitan ng pagsubok ng ilang pagputol sa papel. Ngunit habang maiisip mo, nagiging mas mahirap at mas mahirap ang problema habang lumalaki ang bilang ng mga vertex — bahagi nito ay dahil ang bilang ng mga posibleng pagputol na dapat isaalang-alang ay lumalago nang exponential sa bilang ng mga node. At sa isang punto, kahit mahirap na ito para sa mga supercomputer gamit ang anumang kilalang klasikal na algorithm.

Gusto nating makahanap ng paraan para malutas ang Max-Cut problem para sa mga mas malalaki at mas kumplikadong graph na ito, dahil maraming praktikal na aplikasyon ang problema, kabilang ang fraud detection sa pananalapi, graph clustering, network design, at social media analysis. Ang Max-Cut ay madalas na nasalubong bilang subproblem sa loob ng isang partikular na paraan ng pagtackle sa mas malaking problema. Kaya, mas karaniwan ito kaysa sa ating simpleng inaakala.

Ang Solusyon

Ngayon, lalakaran natin ang paraan na ginagamit natin para malutas ang Max-Cut problem sa isang quantum computer. Gagawin natin ito gamit ang isang simpleng five-node graph. Maaari kang sumabay gamit ang python notebook tutorial. Pagkatapos ng simpleng halimbawang iyon, ang tutorial ay gagabay sa iyo sa isang utility-scale na halimbawa ng problema.

Ang unang hakbang ay ang lumikha ng ating graph sa pamamagitan ng pagtukoy ng bilang ng mga node at mga edge na nag-uugnay sa dalawang node. Magagawa mo ito sa pamamagitan ng pag-import ng isang package na tinatawag na rustworkx, tulad ng ipinapakita sa tutorial. Ang resulta ay isang graph na ganito ang hitsura:

Gagamitin natin ang Qiskit patterns framework para mahanap ang mga Max-Cut solution para sa graph na ito sa ating quantum computer.

Map

Kailangan nating i-map ang problema sa ating quantum computer. Para magawa ito, una nating tandaan na ang pagmaximize ng bilang ng mga pagputol sa isang graph ay maaaring isulat sa matematika bilang:

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

Kung saan ang $i$ at $j$ ay mga node sa graph, at ang $x_i$ at $x_j$ ay alinman sa 0 o 1, depende kung aling panig ng partisyon ang bawat node (ang isang grupo ay may label na "0" at ang isa ay may label na "1"). Kapag ang $x_i$ at $x_j$ ay nasa parehong panig ng partisyon, ang expression sa sum ay katumbas ng zero. Kapag nasa magkabilang panig sila, kaya may pagputol sa pagitan nila, ang expression ay katumbas ng isa. Kaya, ang pagmaximize ng bilang ng mga pagputol ay magmamaximize ng sum.

Maaari rin nating baligtarin ito, at hanapin ang minimum sa pamamagitan ng pagmumultiplika ng bawat halaga ng negatibong isa.

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

Ngayon, handa na tayong mag-map. Maaaring medyo nakakatakot na isipin kung paano pumunta mula sa isang graph tulad ng isa na kaka-draw natin patungo sa isang quantum circuit. Ngunit gagawin natin ito nang isa-isang hakbang.

Tandaan, susubukan nating lutasin ang Max-Cut gamit ang QAOA. Sa QAOA methodology, gusto nating magkaroon ng operator (o sa madaling salita, isang Hamiltonian) na gagamitin para kumatawan sa cost function ng ating hybrid algorithm, pati na rin ang isang parametrized circuit (ang ansatz) na ginagamit natin para kumatawan sa mga posibleng solusyon sa problema.

QUBO

Maaari tayong mag-sample mula sa mga candidate na solusyong ito at pagkatapos ay suriin ang mga ito gamit ang cost function. Para gawin ito, sinasamantala natin ang isang serye ng mga mathematical reformulation, kabilang ang Quadratic Unconstrained Binary Optimization notation — o QUBO para sa maikli — na isang kapaki-pakinabang na paraan para i-encode ang mga combinatorial optimization problem. Sa QUBO, gusto nating hanapin ang:

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

kung saan ang $Q$ ay isang $n\times n$ na matrix ng mga tunay na numero, at ang $n$ ay katumbas ng bilang ng mga node sa ating graph, dito, lima.

Para ilapat ang QAOA, kailangan nating i-formulate ang ating problema bilang isang Hamiltonian — na isang function o matrix na kumakatawan sa kabuuang enerhiya ng isang sistema. Sa partikular, gusto nating lumikha ng cost function Hamiltonian na may katangiang ang ground state ay katumbas ng minimum na halaga ng function. Kaya, para malutas ang ating optimization problem, susubukan nating ihanda ang ground state ng $H$ sa isang quantum computer. Pagkatapos, ang pag-sample mula sa state na ito ay magbubunga ng solusyon sa $\min 𝑓(𝑥)$ na may mataas na probabilidad.

Pag-map sa cost function Hamiltonian

Lumalabas na mapalad tayo, dahil ang QUBO problem ay malapit na nauugnay sa, at talagang computationally equivalent sa, isa sa mga pinakasikat at pinakakaraniwang Hamiltonian sa pisika: ang Ising Hamiltonian.

Para isulat ang QUBO problem bilang Ising Hamiltonian, ang kailangan lang nating gawin ay gumawa ng simpleng pagbabago ng mga variable:

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

Hindi natin lalakaran ang lahat ng mga hakbang dito, ngunit ipinaliwanag ang mga ito sa kalakip na notebook. Sa katapusan, ang minimization ng QUBO expression ay katulad ng minimization ng expression na ito:

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

Isusulat muli nang bahagya at mayroon na tayong cost function Hamiltonian, kung saan ang minimum ng expression ay kumakatawan sa ground state, ang Z ay ang Pauli Z operator, at ang $b$ ay isang tunay na scalar coefficient:

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

Ngayon na mayroon na tayong Hamiltonian, kailangan nating isulat ito sa mga two-local Pauli ZZ operator, na madali nating mako-convert sa two-qubit gate sa ating quantum circuit. Magtatatapos tayo ng anim na bagay — o Pauli string — kung saan ang bawat isa ay katumbas ng bawat isa sa anim na edge sa graph. Ang bawat isa sa limang elemento sa isang string ay kumakatawan sa isang operasyon sa isang node — ang identity kung ang node ay hindi konektado sa partikular na edge na iyon, at ang Pauli Z operator kung ito ay konektado. Sa Qiskit, ang mga bitstring na kumakatawan sa mga qubit ay naka-index nang pabaligtad. Halimbawa, ang isang edge sa pagitan ng mga node 0 at 1 ay naka-encode bilang IIIZZ, at ang isang edge sa pagitan ng 2 at 4 ay naka-encode bilang ZIZII.

Pagtayo ng quantum circuit

Kapag naisulat na ang ating Hamiltonian sa mga Pauli operator, handa na tayong itayo ang ating quantum circuit, na nagpapahintulot sa atin na mag-sample ng mga magagandang solusyon gamit ang isang quantum computer:

Ang QAOA algorithm ay kumukuha ng inspirasyon mula sa Adiabatic Theorem, na nagsasabing kung magsisimula tayo sa ground state ng isang time-dependent na Hamiltonian, kung ang Hamiltonian ay evo-evolve nang dahan-dahan, at bibigyan ng sapat na oras, ang final state ay magiging ground state ng final Hamiltonian. Ang QAOA ay maaaring ituring bilang discrete, trotterized na bersyon ng Quantum Adiabatic Algorithm na ito, kung saan ang bawat trotter step ay kumakatawan sa isang layer ng QAOA algorithm. Kaya sa halip na mag-evolve mula sa isang estado patungo sa isa pa, sa bawat layer, magpapalit-palit tayo sa pagitan ng ating cost function Hamiltonian at ng tinatawag na "mixer" Hamiltonian, na tatalakayin natin sa bandang huli ng araling ito.

Ang kalamangan ng QAOA ay mas mabilis ito kaysa sa quantum adiabatic algorithm, ngunit nagbabalik ito ng approximate na mga solusyon kaysa sa optimal. Sa limitasyon kung saan ang bilang ng mga layer ay pumunta sa infinity, ang QAOA ay nagko-converge sa QAA case, ngunit siyempre ito ay napaka-computationally expensive.

Para lumikha ng ating quantum circuit, mag-a-apply tayo ng alternating na mga operator, na na-parameterize ng $\gamma$ at $\beta$, na kumakatawan sa discretization ng time evolution.

Kaya, ang tatlong pangunahing bahagi ng QAOA circuit ay:

1. ang initial trial state, sa kulay abo, na siyang ground state ng mixer, na nilikha sa pamamagitan ng pag-apply ng Hadamard gate sa bawat qubit
2. ang cost function evolution, na tinalakay natin kanina, sa malalim na kulay lila
3. ang evolution sa ilalim ng mixer Hamiltonian, na hindi pa natin natatakpan, sa maliwanag na kulay lila.

Ang ating panimulang Hamiltonian ay tinatawag na Mixer dahil ang ground state nito ay ang superposition ng lahat ng posibleng bitstring ng interes: kaya't nagpapatupad ng pinagsamang lahat ng posibleng solusyon sa simula.

Ang mixer Hamiltonian ay ang simpleng sum ng mga Pauli-X operation sa bawat node ng graph. Binibigyan ka ng Qiskit na gumamit ng iba, custom na mixer operator kung gusto mo, ngunit gagamit tayo ng standard dito. Kaya muli, makikita mo na sa Qiskit, marami sa trabaho ay tinanggal para sa atin, na ginagawang trivial ang pagdating sa mixer Hamiltonian at sa panimulang estado. Ang tanging trabaho na kailangan nating gawin ay ang hanapin ang cost function.

Ang bawat pag-ulit ng mga operator na ito ay tinatawag na layer. Ang mga layer na ito ay maaaring makita bilang discretization ng time evolution ng sistema, tulad ng naibigay na inilarawan. Ang alternating na pattern ay nagmumula sa trotter decomposition at nagtatantiya ng exponential na mga function ng mga non-commuting matrix. Sa pangkalahatan, habang mas maraming layer o hakbang ang isinama natin, mas malapit tayo sa continuous time evolution, tulad ng sa QAA, kaya sa teorya, mas tumpak ang resulta. Ngunit para sa halimbawang ito, magsisimula tayo sa pamamagitan ng pag-sample na may isang layer lamang. Tandaan, ang parehong cost function Hamiltonian at ang mixer ay na-parameterize, kailangan pa rin nating makahanap ng optimal na mga halaga para sa $\gamma$ at $\beta.$

Optimize

Habang ang circuit na kaka-create natin ay mukhang medyo simple at kapaki-pakinabang para mabuo ang isang intuitive na pag-unawa, tandaan, hindi naiintindihan ng quantum chip kung ano ang QAOA gate. Kailangan nating i-turn ito sa isang serye ng single- at two-qubit "native" na gate na maaaring direktang isagawa sa hardware. Ang mga native gate ay ang mga maaaring direktang isagawa sa mga qubit. Ang mga circuit na ito ay sinasabing nakasulat sa Instruction Set Architecture (ISA) ng backend.

Nag-aalok ang Qiskit library ng isang serye ng mga transpilation pass na tumutugon sa malawak na hanay ng mga circuit transformation. Gusto nating tiyakin na ang circuit ay na-optimize para sa ating layunin.

Alalahanin mula sa ating nakaraang aralin na ang proseso ng transpilation ay nagsasangkot ng ilang mga hakbang:

• Paunang pag-map ng mga qubit sa circuit (iyon ay, mga decision variable) sa mga pisikal na qubit sa device.
• Pag-unroll ng mga instruction sa quantum circuit patungo sa mga hardware native na instruction na naiintindihan ng backend.
• Routing ng anumang mga qubit sa circuit na nagkikipag-interact sa mga pisikal na qubit na magkakatabi sa isa't isa.

At tulad ng lagi, higit pang detalye tungkol dito ay makikita sa dokumentasyon.

Bago mag-transpile, kailangan nating piliin kung aling backend ang ating ipa-patakbo ng ating circuit, dahil ang transpiler ay nag-o-optimize nang iba para sa iba't ibang processor. Isa pa itong dahilan kung bakit mahalaga ang paggamit ng automated transpiler — hindi mo gustong dumaan sa time-consuming na proseso ng pag-optimize ng iyong circuit nang mano-mano, para lang mapagtanto na gusto mo palang patakbuhin ang iyong circuit sa ibang processor na may iba't ibang katangian.

Ipasa ang iyong napiling backend sa pamamagitan ng transpiler function at tukuyin ang iyong optimization level. Sa tutorial, pipiliin mo ang level 3, na siyang pinakamataas at pinaka-komprehensibong level.

At sa ganoon, mayroon na tayong transpiled circuit na handa nang isagawa sa hardware!

Execute

Sa ngayon, na-transpile natin ang circuit habang iniiwan ang mga parameter na gamma at beta — ngunit hindi natin maaaring aktwal na patakbuhin ang circuit nang hindi tinuktukoy ang mga parameter na ito. Sa QAOA workflow, ang mga optimal na QAOA parameter ay nakikita sa isang iterative optimization loop, kung saan nagpapatakbo tayo ng isang serye ng mga circuit evaluation at pagkatapos ay gumagamit ng klasikal na optimizer para mahanap ang mga optimal na 𝛽 at 𝛾 parameter. Gayunpaman, kailangan nating magsimula sa isang lugar, kaya gumagawa tayo ng initial guess na $\gamma=\pi/2$ at $\beta=\pi.$

Mga Execution Mode

Ngayon, halos handa na tayong patakbuhin ang circuit — pangako ko! Ngunit una, mahalagang tandaan na maaari mong ipadala ang iyong job sa iba't ibang paraan, na tinatawag na mga execution mode.

• Job mode: Isang solong primitive na kahilingan ng estimator o sampler ay ginagawa nang walang context manager. Ang mga circuit at input ay naka-package bilang primitive unified bloc (PUB) at isinumite bilang isang execution task sa quantum computer.

• Batch mode: Isang multi-job manager para sa mahusay na pagpapatakbo ng isang eksperimento na binubuo ng bundle ng mga independyenteng job. Gamitin ang batch mode para magsumite ng maraming primitive job nang sabay-sabay.

• Session mode: Isang dedicated na window para sa pagpapatakbo ng isang multi-job workload. Nagbibigay-daan ito sa mga gumagamit na mag-eksperimento sa mga variational algorithm sa mas predictable na paraan, at kahit magpatakbo ng maraming eksperimento nang sabay-sabay, sinasamantala ang parallelism sa stack. Gumamit ng mga session para sa mga iterative workload o eksperimento na nangangailangan ng dedicated access. Tingnan ang Run jobs in a session para sa mga halimbawa.

Para sa isang QAOA experiment, ang isang session ay magiging magandang pagpipilian kung mayroon kang access dito, dahil kailangan nating mag-sample ng ating circuit nang maraming beses na may iba't ibang halaga ng parameter para mahanap ang optimum.

Balik sa optimization problem. Kailangan nating makahanap ng mas magandang mga halaga ng gamma at beta kaysa sa ating magaslaw na unang mga hula. Gagawin natin ito sa pamamagitan ng paglalagay ng ating cost function at mga initial guess na ito sa isang scipy optimizer na COBYLA.

Dito makikita mo ang halaga ng cost function sa mga iterasyon. Nagsisimula itong medyo pabago-bago at paakyat-pababa, ngunit pagkatapos ay nag-settle sa mababang halaga. Gagamitin natin ang mga halagang nahanap ng scipy na katumbas ng pinakamababang evaluation ng cost function.

Ngayong nagawa na nating bawasan ang ating cost function sa pamamagitan ng paghanap ng mas magandang mga halaga ng ating mga parameter, ipa-patakbo natin ang ating circuit gamit ang mga bagong halagang nahanap natin para sa gamma at beta. Inilista ko ang mga partikular na halaga na ginagamit ko dito, ngunit tandaan, kapag sinubukan mo ito o kahit muling patakbuhin ang parehong tutorial notebook, ang mga halagang ito ay maaaring magbago nang bahagya. Ngayon ipa-patakbo natin ang ating na-optimize na circuit gamit ang mga halagang ito at hanapin ang ating candidate na solusyon sa ating Max-Cut problem.

Sa post-processing stage, suriin natin ang data at ipakita ang mga resultang ito para makita kung nahanap ng ating quantum algorithm ang mga tamang solusyon.

Post-process

Ngayon i-plot natin ang isang histogram ng data para tingnan ang final na solusyon:

Ang mga bit string ay kumakatawan kung paano hinati ang bawat node sa dalawang grupo (na may label na "0" at "1") ng pagputol. Dapat may apat na solusyon na lahat ay nagbibigay ng maximum na halaga ng mga edge na naputol. Ang apat na ito ay ipinapakita sa kulay lila. Makikita mo agad na ang 4 na solusyon ay mas malamang kaysa sa iba pa. Ang pinakamataas, at kaya pinaka-malamang na bit string na solusyon ay 0,1,0,1,1. (Tandaan – ang order ng mga qubit ay baligtad sa plot bitstring!)

Mula sa plot na ito, maaari tayong kumuha ng pinaka-malamang na bitstring at katawanin ito bilang isang partitioned na graph, na ang pagputol ay dumadaan sa limang edge:

Kaya, ito ay isang Max-Cut solution nga. Ngunit hindi ito ang tanging isa! Dahil sa symmetry ng graph na ito, maraming tamang solusyon. Sa halip na ang mga node 0 at 3 ay nasa loob ng pagputol, maaari ring kasama ang mga node 2 at 4. Makikita mo na ang kailangan ko lang gawin ay i-rotate ang aking pagputol para isama ang mga bagong punto na ito. Ang bilang ng mga edge na naputol ay nananatiling lima. Lumalabas na may apat na max cut solution, dahil ang bawat isa sa dalawang solusyon na binanggit natin ay may "kabaligtaran" na katambal din, kung saan ang mga purple na node ay kulay abo at ang mga kulay abong node ay lila — kaya ang pagputol ay nananatiling pareho, ngunit ang bawat node ay epektibong lumipat sa kabaligtaran na panig ng partisyon.

Tingnan muli ang histogram at ang apat na pinaka-malamang na solusyon sa isang sandali. Sa ideyal, bawat isa sana ay isa sa apat na tunay na Max-Cut solution. Ang problema ay ang algorithm ay talagang hindi natukoy ang ikaapat at huling solusyon bilang isa sa nangungunang 4 na pinaka-malamang na sagot. Ito ang ikalimang pinaka-malamang. Ang ikaapat na solusyon na natukoy ng algorithm ay mali — kung ito ay iguguhit mo, makikita mong ang solusyon ay may apat lamang na pagputol.

Ngunit tandaan: ito ay isang approximate na algorithm. Hindi ito mapagkakatiwalaan nang buo, at hindi ito tama 100% ng oras. Kailangan mong gumamit ng iyong sariling kaalaman at pag-unawa para suriin ang mga solusyon.

Ang error na ito ay maaaring magmula sa ilang lugar:

1. Maaari itong maging approximate na katangian ng algorithm mismo, at ang maliit na bilang ng mga layer na ginamit ko.
2. Maaari itong maging finite sampling error, na maaaring mabawasan kung pinadami ko ang bilang ng mga shot sa aking eksperimento.
3. Maaari rin itong maging readout error, dahil ang ikaapat na tunay na solusyon ay naiiba lamang ng isang bit.

Ang ganitong uri ng error analysis ang kinakailangan para maging isang practitioner ng quantum computing. Kailangan mong maunawaan ang performance ng hardware at kung paano ito maaaring mag-ambag sa ilang uri ng mga error at kung paano ito iwasto.

Gayunpaman, huwag nating kalimutan na may 32 posibleng bit string, at ang apat na tunay na solusyon ay kasama sa nangungunang limang pinakamahusay na kandidato. At dalawang layer lamang ang ginamit natin para mahanap ito. Sa pangkalahatan, kung gusto nating palakasin ang ating pagkakataon na palaging mahanap ang pinakamahusay na Max-Cut, maaari nating pataasin ang layer depth. May ilang subtlety dito, ngunit iyon ay para sa susunod na aralin.

Sa utility-scale

Ngayong natikman mo na ang proseso ng paglutas ng isang maliit na Max-Cut problem sa isang quantum computer, hinahamon kita na gawin ito sa scale. Sundan ang naka-link na tutorial para makita kung gaano karaming pagputol ang makukuha mo sa isang 125-node graph.