Mga klasikal na komputasyon sa quantum computers

Ngayon ay ilalipat natin ang ating atensyon sa pag-implement ng mga klasikal na algorithm sa quantum computers. Makikita natin na ang anumang komputasyon na maisasagawa gamit ang isang klasikal na Boolean circuit ay maisasagawa rin ng isang quantum circuit na may katulad na asymptotic na computational cost. Bukod dito, magagawa ito sa isang "malinis" na paraan na ipapaliwanag natin sa ilang sandali, na isang mahalagang kinakailangan para magamit ang mga komputasyong ito bilang mga subroutine sa loob ng mas malalaking quantum na komputasyon.

Pag-simulate ng mga Boolean circuit gamit ang mga quantum circuit

Ang mga Boolean circuit ay binubuo ng mga AND, OR, NOT, at FANOUT gate. Para ma-simulate ang mga Boolean circuit gamit ang mga quantum circuit, magsisimula tayo sa pagpapakita kung paano masisimulate ang bawat isa sa apat na gate na ito gamit ang mga quantum gate. Kapag nagawa na iyon, ang pag-convert ng isang partikular na Boolean circuit sa isang quantum circuit ay isang simpleng bagay lamang ng pag-simulate ng isang gate sa isang pagkakataon. Ang kailangan lang natin ay mga NOT gate, controlled-NOT gate, at Toffoli gate para gawin ito, na pawang mga deterministikong operasyon bukod sa pagiging unitary.

Mga Toffoli gate

Ang mga Toffoli gate ay maaari ring ilarawan bilang controlled-controlled-NOT gate, na ang aksyon sa mga standard basis state ay makikita sa sumusunod na figure.

Tandaan na gumagamit tayo ng ordering convention ng Qiskit, kung saan ang mga qubit ay nakaayos sa pataas na kahalagahan mula sa itaas pababa, ang matrix representation ng gate na ito ay ganito.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Isa pang paraan para pag-isipan ang mga Toffoli gate ay ang mga ito ay essentially mga query gate para sa AND function, sa kahulugang sumusunod sila sa pattern na nakita natin sa nakaraang aralin para sa mga unitary query gate na implementasyon ng mga arbitrary na function na may binary string na input at output.

Ang mga Toffoli gate ay hindi kasama sa default na gate set na tinukoy kanina sa aralin, ngunit posible itong buuin mula sa $H,$ $T,$ $T^{\dagger},$ at mga CNOT gate tulad ng sumusunod.

Pag-simulate ng mga Boolean gate gamit ang Toffoli, controlled-NOT, at NOT gate

Ang isang Toffoli gate, kapag ginamit kasama ang ilang NOT gate, ay maaaring mag-implement ng isang AND at OR gate, at ang mga FANOUT gate ay madaling maiimplementa gamit ang mga controlled-NOT gate, tulad ng iminumungkahi ng mga sumusunod na diagram.

Sa lahat ng tatlong kaso, ang mga qubit na kinakatawanan ng mga AND, OR, at FANOUT gate ay pumapasok mula sa kaliwa bilang mga input, at nangangailangan din tayo ng isang workspace qubit na initialized sa zero state para sa bawat isa. Ang mga workspace qubit na ito ay lumalabas sa loob ng mga kahon na kumakatawan sa mga gate na implementasyon upang ipahiwatig na bago sila, at samakatuwid ay bahagi ng gastos ng mga implementasyong ito.

Para sa mga AND at OR gate, mayroon ding dalawang qubit na natitira, bukod sa output qubit. Halimbawa, sa loob ng kahon sa diagram na kumakatawan sa simulation ng isang AND gate, ang dalawang qubit sa itaas ay naiwan sa mga estado na $\vert a\rangle$ at $\vert b\rangle.$ Ang mga qubit na ito ay inilalarawan na nananatili sa loob ng mga kahon dahil hindi na sila kailangan at hindi bahagi ng output. Maaari silang balewalain sa ngayon, bagama't babalik tayo sa kanila sa ilang sandali.

Ang natitirang Boolean gate, ang NOT gate, ay kasama sa ating default na set ng mga quantum gate, kaya hindi na tayo nangangailangan ng simulation para dito.

Gate-by-gate na simulation ng mga Boolean circuit

Ngayon, ipagpalagay na mayroon tayong isang ordinaryong Boolean circuit na pinangalanang $C,$ na binubuo ng mga AND, OR, NOT, at FANOUT gate, at may $n$ na input bit at $m$ na output bit. Hayaan ang $t = \operatorname{size}(C)$ ang bilang ng mga gate sa $C,$ at pangalanan natin ang function na kinukuwenta ng $C$ bilang $f,$ na may anyo

$$f:\Sigma^n\rightarrow\Sigma^m$$

para sa $\Sigma = \{0,1\}.$

Ngayon ay pag-isipan kung ano ang mangyayari kapag isa-isa tayong dumaan sa mga AND, OR, at FANOUT gate ng $C,$ pinapalitan ang bawat isa ng katumbas na simulation na inilarawan sa itaas, kasama ang pagdaragdag ng mga kinakailangang workspace qubit. Pangalanan natin ang resultang circuit bilang $R,$ at ayusin ang mga qubit ng $R$ upang ang $n$ na input bit ng $C$ ay tumutugma sa pinakataas na $n$ qubit ng $R$ at ang mga workspace qubit ay nasa ibaba.

Dito, ang $k$ ay ang bilang ng mga workspace qubit na kailangan — isa para sa bawat AND, OR, at FANOUT gate ng $C$ — at ang $g$ ay isang function na may anyo $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ na naglalarawan ng mga estado ng mga natitira at naiwan na qubit na nilikha ng mga gate simulation pagkatapos patakbuhin ang $R.$ Sa figure, ang mga qubit na tumutugma sa output na $f(x)$ ay nasa itaas at ang mga natitirang, naiwan na qubit na nag-iimbak ng $g(x)$ ay nasa ibaba. Maaari nating pilitin itong mangyari kung nais natin sa pamamagitan ng muling pag-aayos ng mga qubit gamit ang mga SWAP gate, na maaaring maiimplementa gamit ang tatlong controlled-NOT gate tulad nito:

Tulad ng makikita natin sa susunod na seksyon, hindi talaga mahalaga ang muling pag-aayos ng mga output qubit tulad nito, ngunit madali itong gawin kung pipiliin natin.

Ang function na $g$ na naglalarawan ng mga klasikal na estado ng mga natitira at naiwan na qubit ay tinutukoy ng circuit na $C,$ ngunit hindi na tayo masyadong kailangang mag-alala tungkol dito; hindi tayo nagmamalasakit kung anong estado ang mga qubit na ito kapag natapos na ang komputasyon. Ang titik na $g$ ay sumusunod sa $f,$ kaya ito ay makatwirang pangalan para sa function na ito sa kadahilanang iyon, ngunit may mas magandang dahilan para piliin ang pangalang $g$ — ito ay maikli para sa basura.

Paglilinis ng basura

Kung ang tanging interes natin ay ang pag-evaluate ng function na $f$ na kinukuwenta ng isang partikular na Boolean circuit na $C$ gamit ang isang quantum circuit, hindi na tayo kailangang magpatuloy pa kaysa sa gate-by-gate na simulation na inilarawan lamang. Nangangahulugan ito na, bukod sa output ng function, magkakaroon tayo ng maraming basura na natitira.

Gayunpaman, hindi ito sapat kung gusto nating magsagawa ng mga klasikal na komputasyon bilang mga subroutine sa loob ng mas malalaking quantum na komputasyon, dahil ang mga garbage qubit na iyon ay magdudulot ng mga problema. Ang penomenon ng interference ay kritikal na mahalaga sa mga quantum algorithm, at ang mga garbage qubit ay maaaring masira ang mga interference pattern na kailangan para gumana ang mga quantum algorithm.

Sa kabutihang palad, hindi mahirap linisin ang basura, sa madaling sabi. Ang susi ay ang paggamit ng katotohanang dahil ang $R$ ay isang quantum circuit, maaari nating patakbuhin ito nang baligtad, sa pamamagitan lamang ng pagpapalit ng bawat gate ng inverse nito at pag-apply ng mga ito sa baligtad na pagkakasunud-sunod, na makakakuha ng quantum circuit para sa operasyon na $R^{\dagger}.$ Ang mga Toffoli gate, CNOT gate, at NOT gate ay pawang sarili nilang mga inverse, kaya ang pagpapatakbo ng $R$ nang baligtad ay isang bagay lamang ng pag-apply ng mga gate sa baligtad na pagkakasunud-sunod — ngunit sa pangkalahatan, ang anumang quantum circuit ay maaaring i-reverse tulad ng inilarawan.

Partikular, ang magagawa natin ay magdagdag ng $m$ pang qubit (alalahanin na ang function na $f$ ay may $m$ na output bit), gumamit ng mga CNOT gate para kopyahin ang output ng $R$ sa mga qubit na ito, at i-reverse ang $R$ para linisin ang basura. Ang sumusunod na figure ay naglalarawan ng resultang circuit at inilalarawan ang aksyon nito sa mga standard basis state.

Kung lalagyan natin ng kahon ang buong circuit at tatawagin itong $Q,$ magmumukhang ganito ito:

Dahil ang $C$ ay may $t$ na gate, ang circuit na $Q$ ay magkakaroon ng $O(t)$ na gate.

Kung hindi natin isasaalang-alang ang $k$ na karagdagang workspace qubit, ang mayroon tayo ay isang circuit na $Q$ na gumagana nang eksaktong tulad ng isang query gate para sa function na $f.$ Kung simpleng gusto nating kuwentahin ang function na $f$ sa ilang string na $x,$ maaari nating itakda ang $y = 0^m$ at ang resultang halaga ng $f(x)$ ay lalabas sa pinakailalim na $m$ qubit — o maaari tayong mag-feed ng iba't ibang estado sa pinakailalim na $m$ qubit kung nais natin (marahil para magamit ang isang phase kickback, tulad ng sa Deutsch's o ang Deutsch-Jozsa algorithm).

Nangangahulugan ito na para sa anumang query algorithm, kung mayroon tayong Boolean circuit na kukuwenta sa input function, maaari nating palitan ang bawat query gate ng isang circuit implementation nito, at ang query algorithm ay gagana nang tama.

Tandaan na ang mga workspace qubit ay kailangan para gumana ang prosesong ito, ngunit ibinabalik ang mga ito sa kanilang mga paunang estado kapag naisagawa na ang pinagsamang circuit. Nagbibigay-daan ito sa mga qubit na ito na muling magamit bilang mga workspace qubit para sa iba pang layunin. Mayroon ding mga kilalang estratehiya para bawasan ang bilang ng mga workspace qubit na kailangan (na may kapalit na paggawa ng mga circuit na mas malaki), ngunit hindi natin tatalakaying ang mga estratehiyang iyon dito.

Pag-implement ng mga invertible na function

Ang konstruksyon na inilarawan ay nagbibigay-daan sa atin na ma-simulate ang anumang Boolean circuit gamit ang isang quantum circuit sa isang garbage-free na paraan. Kung ang $C$ ay isang Boolean circuit na nag-iimplementa ng function na $f:\Sigma^n \rightarrow \Sigma^m,$ kung gayon nakakakuha tayo ng quantum circuit na $Q$ na gumagana tulad ng sumusunod sa mga standard basis state.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

Ang bilang na $k$ ay nagpapahiwatig kung ilang workspace qubit ang kailangan sa kabuuan. Sapat ito para sa mga layunin ng kursong ito, ngunit posible na dalhin ang metodolohiyang ito nang isang hakbang pa kapag ang function na $f$ mismo ay invertible.

Para maging tiyak, ipagpalagay na ang function na $f$ ay may anyo na $f:\Sigma^n \rightarrow \Sigma^n,$ at ipagpalagay din na mayroong function na $f^{-1}$ na ang $f^{-1}(f(x)) = x$ para sa bawat $x\in\Sigma^n$ (na kinakailangang natatangi kapag umaandar ito). Nangangahulugan ito na ang operasyon na nagbabago ng $\vert x \rangle$ sa $\vert f(x) \rangle$ para sa bawat $x\in\Sigma^n$ ay unitary, kaya maaari tayong umasa na makabuo ng isang quantum circuit na nag-iimplementa ng unitary operation na tinukoy ng

$$U \vert x \rangle = \vert f(x) \rangle$$

para sa bawat $x\in\Sigma^n.$

Para maging malinaw, ang katotohanang ito ay isang unitary operation ay nakasalalay sa pagiging invertible ng $f$ — hindi ito unitary kapag ang $f$ ay hindi invertible. Kung hindi isasaalang-alang ang mga workspace qubit, ang $U$ ay naiiba mula sa operasyon na ipinapatupad ng circuit na $Q$ dahil hindi tayo nagpapanatili ng kopya ng input at nagXO-or ito sa isang arbitrary na string, pinapalitan natin ang $x$ ng $f(x).$

Ang tanong ay: kapag ang $f$ ay invertible, magagawa ba natin ito?

Ang sagot ay oo, sa kondisyon na pinapayagan tayong gumamit ng mga workspace qubit at, bukod sa pagkakaroon ng isang Boolean circuit na kukuwenta sa $f,$ mayroon din tayong isa para kukuwenta sa $f^{-1}.$ Kaya, hindi ito isang shortcut para sa computational na pag-invert ng mga function kapag hindi natin alam kung paano gawin iyon! Ang sumusunod na diagram ay naglalarawan kung paano ito maisasagawa sa pamamagitan ng pag-compose ng dalawang quantum circuit, $Q_f$ at $Q_{f^{-1}},$ na nakukuha nang hiwalay para sa mga function na $f$ at $f^{-1}$ sa pamamagitan ng paraan na inilarawan sa itaas, kasama ang $n$ na swap gate, na kinukuha ang $k$ bilang pinakamataas na bilang ng mga workspace qubit na kailangan ng $Q_f$ at $Q_{f^{-1}}.$