Lumaktaw sa pangunahing nilalaman

Algoritmo ni Simon

Ang algoritmo ni Simon ay isang quantum query algorithm para sa problemang kilala bilang problema ni Simon. Ito ay isang promise problem na may katulad na diwa sa Deutsch-Jozsa at Bernstein-Vazirani na mga problema, ngunit magkaiba ang mga detalye.

Ang algoritmo ni Simon ay mahalaga dahil nagbibigay ito ng exponential na kalamangan ng quantum kumpara sa classical (kasama ang probabilistic) na mga algorithm, at ang teknikang ginamit nito ang nagbigay inspirasyon kay Peter Shor para matuklasan ang isang episyenteng quantum algorithm para sa integer factorization.

Problema ni Simon​

Ang input na function para sa problema ni Simon ay may anyo

f:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m

para sa mga positibong integer na nn at m.m. Maaari nating limitahan ang ating atensyon sa kaso na m=nm = n para sa kasimplihan, ngunit wala masyadong mapapala sa paggawa ng assumption na ito — ang algoritmo ni Simon at ang pagsusuri nito ay halos pareho kahit saan.

Problema ni Simon

Input: isang function na f:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m
Promise: may isang string na s∈Σns\in\Sigma^n na kung saan [f(x)=f(y)]⇔[(x=y)∨(x⊕s=y)][f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)] para sa lahat ng x,y∈Σnx,y\in\Sigma^n
Output: ang string na ss

Tatalakayin natin ang promise para mas maunawaan kung ano ang sinasabi nito sa sandali, ngunit una, malinaw na ito ay nangangailangan na ang ff ay may napaka-espesyal na istruktura — kaya karamihan sa mga function ay hindi matutugunan ang promise na ito. Angkop din na kilalanin na ang problemang ito ay hindi inilaan para magkaroon ng praktikal na kahalagahan. Sa halip, ito ay isang medyo artipisyal na problema na espesyal na ginawa para maging madali para sa mga quantum computer at mahirap para sa mga classical computer.

May dalawang pangunahing kaso: ang unang kaso ay ang ss ay ang all-zero string na 0n,0^n, at ang ikalawang kaso ay ang ss ay hindi ang all-zero string.

  • Kaso 1: s=0n.s=0^n. Kung ang ss ay ang all-zero string, maaari nating gawing mas simple ang if and only if na pahayag sa promise para mabasa itong [f(x)=f(y)]⇔[x=y].[f(x) = f(y)] \Leftrightarrow [x = y]. Ito ay katumbas ng ff na isang one-to-one na function.

  • Kaso 2: s≠0n.s\neq 0^n. Kung ang ss ay hindi ang all-zero string, ang promise na natutugunan para sa string na ito ay nagpapahiwatig na ang ff ay two-to-one, ibig sabihin na para sa bawat posibleng output string ng f,f, may eksaktong dalawang input string na nagdudulot sa ff na mag-output ng string na iyon. Bukod dito, ang dalawang input string na ito ay dapat nasa anyo ng ww at w⊕sw \oplus s para sa ilang string na w.w.

Mahalaga na kilalanin na iisang string lamang na ss ang maaaring gumana kung ang promise ay natutugunan, kaya lagi may natatanging tamang sagot para sa mga function na natutugunan ang promise.

Narito ang isang halimbawa ng isang function na nasa anyo ng f:Σ3→Σ5f:\Sigma^3 \rightarrow \Sigma^5 na natutugunan ang promise para sa string na s=011.s = 011.

f(000)=10011f(001)=00101f(010)=00101f(011)=10011f(100)=11010f(101)=00001f(110)=00001f(111)=11010\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}

May 88 iba't ibang input string at 44 iba't ibang output string, bawat isa ay lumalabas nang dalawang beses — kaya ito ay isang two-to-one na function. Bukod dito, para sa anumang dalawang magkaibang input string na gumagawa ng parehong output string, makikita natin na ang bitwise XOR ng dalawang input string na ito ay katumbas ng 011,011, na katumbas ng pagsasabi na alinman sa isa sa kanila ay katumbas ng isa pang XORed sa s.s.

Pansinin na ang tanging bagay na mahalaga tungkol sa aktwal na output string ay kung pareho o magkaiba ang mga ito para sa iba't ibang pagpipilian ng input string. Halimbawa, sa halimbawa sa itaas, may apat na string (10011,(10011, 00101,00101, 00001,00001, at 11010)11010) na lumalabas bilang mga output ng f.f. Maaari nating palitan ang apat na string na ito ng iba't ibang string, basta't magkakaiba ang lahat, at ang tamang solusyon na s=011s = 011 ay hindi magbabago.

Paglalarawan ng algorithm​

Narito ang isang quantum circuit diagram na kumakatawan sa algoritmo ni Simon.

Algoritmo ni Simon

Para maging malinaw, may nn na qubit sa itaas na inaaksyunan ng mga Hadamard gate at mm na qubit sa ibaba na direktang pumapasok sa query gate. Mukhang katulad ito ng mga algorithm na tinalakay na natin sa aralin, ngunit sa pagkakataong ito ay walang phase kickback; ang lahat ng mm na qubit sa ibaba ay pumapasok sa query gate sa estado na ∣0⟩.\vert 0\rangle.

Para malutas ang problema ni Simon gamit ang circuit na ito ay talagang mangangailangan ng ilang independyenteng pagpapatakbo nito na sinusundan ng isang classical post-processing na hakbang, na ilalarawan mamaya pagkatapos masuri ang gawi ng circuit.

Pagsusuri​

Ang pagsusuri ng algoritmo ni Simon ay nagsisimula sa katulad na paraan sa algoritmo ng Deutsch-Jozsa. Pagkatapos isagawa ang unang layer ng mga Hadamard gate sa itaas na nn na qubit, ang estado ay nagiging

12n∑x∈Σn∣0m⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.

Kapag isasagawa ang Uf,U_f, ang output ng function na ff ay XORed sa all-zero na estado ng ibabang mm na qubit, kaya ang estado ay nagiging

12n∑x∈Σn∣f(x)⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.

Kapag isasagawa ang pangalawang layer ng mga Hadamard gate, makukuha natin ang sumusunod na estado sa pamamagitan ng paggamit ng parehong formula para sa aksyon ng isang layer ng mga Hadamard gate tulad ng dati.

12n∑x∈Σn∑y∈Σn(−1)x⋅y∣f(x)⟩∣y⟩\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle

Sa puntong ito, ang pagsusuri ay nag-iiba mula sa mga nauna sa araling ito.

Interesado tayo sa probabilidad na ang mga sukat ay magreresulta sa bawat posibleng string na y∈Σn.y\in\Sigma^n. Sa pamamagitan ng mga panuntunan para sa pagsusuri ng mga sukat na inilarawan sa aralin na Multiple systems ng kursong Basics of quantum information, nalaman natin na ang probabilidad na p(y)p(y) para makuha ang string na yy ay katumbas ng

p(y)=∥12n∑x∈Σn(−1)x⋅y∣f(x)⟩∥2.p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.

Para mas maunawaan ang mga probabilidad na ito, kailangan natin ng kaunting karagdagang notasyon at terminolohiya. Una, ang range ng function na ff ay ang set na naglalaman ng lahat ng output string nito.

range⁡(f)={f(x):x∈Σn}\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}

Pangalawa, para sa bawat string na z∈range⁡(f),z\in\operatorname{range}(f), maaari nating ipahayag ang set ng lahat ng input string na nagdudulot sa function na mag-evaluate sa output string na zz bilang f−1({z}).f^{-1}(\{z\}).

f−1({z})={x∈Σn:f(x)=z}f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}

Ang set na f−1({z})f^{-1}(\{z\}) ay kilala bilang ang preimage ng {z}\{z\} sa ilalim ng f.f. Maaari nating tukuyin ang preimage sa ilalim ng ff ng anumang set sa lugar ng {z}\{z\} sa katulad na paraan — ito ang set ng lahat ng elemento na iminamapa ng ff sa set na iyon. (Ang notasyong ito ay hindi dapat ipagkamali sa inverse ng function na f,f, na maaaring hindi umiiral. Ang katotohanan na ang argumento sa kaliwang bahagi ay ang set na {z}\{z\} sa halip na ang elemento na zz ang palatandaan na nagpapahintulot sa atin na maiwasan ang pagkalito na ito.)

Gamit ang notasyong ito, maaari nating hatiin ang sum sa ating expression para sa mga probabilidad sa itaas para makuha

p(y)=∥12n∑z∈range⁡(f)(∑x∈f−1({z})(−1)x⋅y)∣z⟩∥2.p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.

Ang bawat string na x∈Σnx\in\Sigma^n ay kinakatawan nang eksaktong isang beses ng dalawang summation — sa esensya ay inilalagay lamang natin ang mga string na ito sa magkakahiwalay na mga timba depende kung aling output string na z=f(x)z = f(x) ang magagawa nila kapag sinuri natin ang function na f,f, at pagkatapos ay magbibigay ng sum nang hiwalay sa lahat ng timba.

Maaari na nating suriin ang Euclidean norm squared para makuha

p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2.p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.

Para mas gawing simple ang mga probabilidad na ito, tingnan natin ang halaga

∣∑x∈f−1({z})(−1)x⋅y∣2(1)\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}

para sa isang arbitrary na pagpili ng z∈range⁡(f).z\in\operatorname{range}(f).

Kung mangyari na ang s=0n,s = 0^n, kung gayon ang ff ay isang one-to-one na function at lagi lamang may iisang elemento na x∈f−1({z}),x\in f^{-1}(\{z\}), para sa bawat z∈range⁡(f).z\in\operatorname{range}(f). Ang halaga ng expression na (1)(1) ay 11 sa kasong ito.

Kung, sa kabilang banda, ang s≠0n,s\neq 0^n, kung gayon may eksaktong dalawang string sa set na f−1({z}).f^{-1}(\{z\}). Para maging tumpak, kung pipiliin natin ang w∈f−1({z})w\in f^{-1}(\{z\}) na maging alinman sa dalawang string na ito, kung gayon ang kabilang string ay dapat w⊕sw \oplus s sa pamamagitan ng promise sa problema ni Simon. Gamit ang obserbasyon na ito maaari nating gawing simple ang (1)(1) tulad ng sumusunod.

∣∑x∈f−1({z})(−1)x⋅y∣2=∣(−1)w⋅y+(−1)(w⊕s)⋅y∣2=∣(−1)w⋅y(1+(−1)s⋅y)∣2=∣1+(−1)y⋅s∣2={4y⋅s=00y⋅s=1\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}

Kaya, lumalabas na ang halaga na (1)(1) ay independyente sa partikular na pagpili ng z∈range⁡(f)z\in\operatorname{range}(f) sa magkabilang kaso.

Maaari na nating tapusin ang pagsusuri sa pamamagitan ng pagtingin sa parehong dalawang kaso tulad ng dati nang hiwalay.

  • Kaso 1: s=0n.s = 0^n. Sa kasong ito ang function na ff ay one-to-one, kaya may 2n2^n na string na z∈range⁡(f),z\in\operatorname{range}(f), at makukuha natin

    p(y)=122n⋅2n=12n.p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.

    Sa madaling salita, ang mga sukat ay nagreresulta sa isang string na y∈Σny\in\Sigma^n na pinili nang uniformly at random.

  • Kaso 2: s≠0n.s \neq 0^n. Sa kasong ito ang ff ay two-to-one, kaya may 2n−12^{n-1} na elemento sa range⁡(f).\operatorname{range}(f). Gamit ang formula mula sa itaas, concludes tayo na ang probabilidad na sukatin ang bawat y∈Σny\in\Sigma^n ay

    p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2={12n−1y⋅s=00y⋅s=1p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}

    Sa madaling salita, nakukuha natin ang isang string na pinili nang uniformly at random mula sa set na {y∈Σn:y⋅s=0},\{y\in\Sigma^n : y \cdot s = 0\}, na naglalaman ng 2n−12^{n-1} na string. (Dahil ang s≠0n,s\neq 0^n, eksaktong kalahati ng mga binary string na may haba nn ay may binary dot product na 11 sa ss at ang iba pa ay may binary dot product na 00 sa s,s, tulad ng naobserbahan na natin sa pagsusuri ng algoritmo ng Deutsch-Jozsa para sa problema ng Bernstein-Vazirani.)

Classical post-processing​

Alam na natin kung ano ang mga probabilidad para sa mga posibleng resulta ng sukat kapag pinatakbo natin ang quantum circuit para sa algoritmo ni Simon. Sapat na ba ang impormasyong ito para matukoy ang ss?

Ang sagot ay oo, basta handa tayong ulitin ang proseso nang ilang beses at tanggapin na maaaring mabigo ito sa ilang probabilidad, na maaari nating gawing napakaliit sa pamamagitan ng pagpapatakbo ng circuit nang sapat na beses. Ang pangunahing ideya ay ang bawat pagpapatupad ng circuit ay nagbibigay sa atin ng estadistikal na katibayan tungkol sa s,s, at maaari nating gamitin ang katibayan na iyon para mahanap ang ss na may napataas na probabilidad kung pinatakbo natin ang circuit nang sapat na maraming beses.

Ipagpalagay natin na pinatakbo natin ang circuit nang nakapag-iisang kk beses, para sa k=n+10.k = n + 10. Walang espesyal tungkol sa partikular na bilang ng pag-uulit na ito — maaari tayong kumuha ng mas malaki (o mas maliit) na kk depende sa probabilidad ng pagkabigo na handa tayong tiisin, tulad ng makikita natin. Ang pagpili ng k=n+10k = n + 10 ay titiyak na mayroon tayong mahigit 99.999.9% na pagkakataon ng pagbawi ng s.s.

Sa pamamagitan ng pagpapatakbo ng circuit nang kk beses, makukuha natin ang mga string na y1,...,yk∈Σn.y^1,...,y^{k} \in \Sigma^n. Para maging malinaw, ang mga superscript dito ay bahagi ng mga pangalan ng mga string na ito, hindi mga exponent o mga index sa kanilang mga bit, kaya mayroon tayo

y1=yn−11⋯y01y2=yn−12⋯y02    ⋮yk=yn−1k⋯y0k\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}

Ngayon ay bumubuo tayo ng matris na MM na may kk na row at nn na column sa pamamagitan ng pagkuha ng mga bit ng mga string na ito bilang mga binary-valued na entry.

M=(yn−11⋯y01yn−12⋯y02⋮⋱⋮yn−1k⋯y0k)M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}

Ngayon, hindi natin alam kung ano ang ss sa puntong ito — ang ating layunin ay mahanap ang string na ito. Ngunit isipin sandali na alam natin ang string na s,s, at bumubuo tayo ng column vector na vv mula sa mga bit ng string na s=sn−1⋯s0s = s_{n-1} \cdots s_0 tulad ng sumusunod.

v=(sn−1⋮s0)v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}

Kung isasagawa natin ang matrix-vector multiplication na MvM v modulo 22 — ibig sabihin, ginagawa natin ang multiplication tulad ng dati at pagkatapos ay kinukuha ang natitirang bahagi ng mga entry ng resulta pagkatapos hatiin sa 22 — makukuha natin ang all-zero vector.

Mv=(y1⋅sy2⋅s⋮yk⋅s)=(00⋮0)M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}

Ibig sabihin, na tinatrato bilang isang column vector na vv tulad ng inilarawan lamang, ang string na ss ay laging magiging isang elemento ng null space ng matris na M,M, basta ginagawa natin ang aritmetika modulo 2.2. Ito ay totoo sa parehong kaso na s=0ns = 0^n at s≠0n.s\neq 0^n. Para maging mas tumpak, ang all-zero vector ay laging nasa null space ng M,M, at sinasamahan ito ng vector na ang mga entry ay ang mga bit ng ss sa kaso na ang s≠0n.s\neq 0^n.

Ang natitirang tanong ay kung magkakaroon pa ng ibang mga vector sa null space ng MM bukod sa mga katumbas ng 0n0^n at s.s. Ang sagot ay ito ay nagiging lalong hindi malamang habang tumaas ang kk — at kung pipiliin natin ang k=n+10,k = n + 10, ang null space ng MM ay hindi maglalaman ng ibang mga vector karagdagan sa mga katumbas ng 0n0^n at ss na may mahigit 99.999.9% na pagkakataon. Sa pangkalahatan, kung papalitan natin ang k=n+10k = n + 10 ng k=n+rk = n + r para sa isang arbitrary na pagpili ng positibong integer na r,r, ang probabilidad na ang mga vector na katumbas ng 0n0^n at ss ay mag-isa sa null space ng MM ay hindi bababa sa 1−2−r.1 - 2^{-r}.

Gamit ang linear algebra, posibleng mahusay na kalkulahin ang isang paglalarawan ng null space ng MM modulo 2.2. Partikular, maaari itong gawin gamit ang Gaussian elimination, na gumagana sa parehong paraan kapag ang aritmetika ay ginagawa modulo 22 tulad ng sa mga tunay o kumplikadong numero. Basta ang mga vector na katumbas ng 0n0^n at ss ay mag-isa sa null space ng M,M, na nangyayari nang may mataas na probabilidad, maaari nating ibukod ang ss mula sa mga resulta ng computation na ito.

Kahirapan ng classical​

Ilang query ang kailangan ng isang classical query algorithm para malutas ang problema ni Simon? Ang sagot ay: marami, sa pangkalahatan.

May iba't ibang tumpak na pahayag na maaaring gawin tungkol sa kahirapan ng classical ng problemang ito, at narito ang isa sa kanila. Kung mayroon tayong anumang probabilistic query algorithm, at ang algorithm na iyon ay gumagawa ng mas kaunting 2n/2−1−12^{n/2 - 1} - 1 na query, na isang bilang ng query na exponential sa n,n, kung gayon ang algorithm na iyon ay mabibigo sa paglutas ng problema ni Simon na may probabilidad na hindi bababa sa 1/2.1/2.

Minsan, ang pagpapatunay ng mga imposibilidad na resulta tulad nito ay maaaring napakahirap, ngunit ang ito ay hindi masyadong mahirap patunayan sa pamamagitan ng isang elementaryang probabilistic na pagsusuri. Dito, gayunpaman, ay maikling susuriin lamang natin ang pangunahing intuisyon sa likod nito.

Sinusubukan nating mahanap ang nakatagong string na s,s, ngunit basta hindi tayo nag-query ng function sa dalawang string na may parehong output value, makakakuha tayo ng limitadong impormasyon tungkol sa s.s. Sa intuwisyon, ang matututunan lamang natin ay ang nakatagong string na ss ay hindi ang exclusive-OR ng anumang dalawang magkaibang string na na-query natin. At kung mag-query tayo ng mas kaunting 2n/2−1−12^{n/2 - 1} - 1 na string, magkakaroon pa rin ng maraming pagpipilian para sa ss na hindi pa natin na-rule out dahil hindi sapat ang mga pares ng string para gawin ito. Hindi ito isang pormal na patunay, ito lamang ang pangunahing ideya.

Kaya, sa buod, ang algoritmo ni Simon ay nagbibigay sa atin ng kapansin-pansing kalamangan ng quantum kumpara sa mga classical algorithm sa loob ng query model. Sa partikular, ang algoritmo ni Simon ay naglulutas ng problema ni Simon gamit ang isang bilang ng query na linear sa bilang ng input bits na nn ng ating function, samantalang ang anumang classical algorithm, kahit probabilistic, ay kailangang gumawa ng isang bilang ng query na exponential sa nn para malutas ang problema ni Simon na may makatwirang probabilidad ng tagumpay.