Algoritmo ni Shor

Para sa modyul na ito ng Qiskit in Classrooms, kailangang may gumaganang Python environment ang mga estudyante na may naka-install na mga sumusunod na pakete:

• qiskit v2.1.0 o mas bago
• qiskit-ibm-runtime v0.40.1 o mas bago
• qiskit-aer v0.17.0 o mas bago
• qiskit.visualization
• numpy
• pylatexenc

Para ma-set up at ma-install ang mga paketeng nakalista sa itaas, tingnan ang gabay na Install Qiskit. Para makapag-run ng mga job sa tunay na quantum computer, kailangang mag-set up ng account sa IBM Quantum® ang mga estudyante sa pamamagitan ng mga hakbang sa gabay na Set up your IBM Cloud account.

Ang modyul na ito ay nasubok at gumamit ng tatlong segundo ng QPU time. Tantiya lamang ito. Maaaring mag-iba ang iyong aktwal na paggamit.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Panimula

Noong unang bahagi ng dekada 1990, lumakas ang sigasig sa potensyal ng mga quantum computer na malutas ang mga problemang mahirap para sa mga klasikal na computer. Ilang bihasang computer scientist ang nakalikha ng mga algoritmo na nagpapakita ng kapangyarihan ng quantum computing para sa ilang niche at naka-construct na mga problema, ngunit walang nakahanap ng isang "killer app" ng quantum computing na tiyak na mag-rerebolusiyon sa larangan. Iyon ay, hanggang 1994, nang matuklasan ni Peter Shor ang tinatawag na ngayon na algoritmo ni Shor para sa pag-factor ng malalaking numero.

Kilala na sa panahong iyon na ang paghanap ng mga prime factor ng isang malaking numero ay napakahirap para sa isang klasikal na computer. Sa katunayan, umaasa sa kahirapang ito ang mga internet security protocol. Nakahanap si Shor ng paraan upang mahanap ang mga factor na ito nang mas mahusay nang exponential sa pamamagitan ng pagpasa ng ilang mas mahirap na hakbang sa isang teoretikal, hinaharap na quantum computer.

Sa modyul na ito, tatalakayin natin ang algoritmo ni Shor. Una, magbibigay tayo ng kaunting konteksto sa algoritmo, pormal na ititakda ang problemang niresolba nito at ipapaliwanag ang kaugnayan sa cyber security. Susunod, magbibigay tayo ng maikling pagpapakilala sa modular mathematics at kung paano ito ilapat sa problema ng pag-factor, na nagpapakita kung paano nababawas ang pag-factor sa isa pang problema na tinatawag na "order-finding." Ipapakita natin kung paano gumaganap ang Quantum Fourier Transform at Quantum Phase Estimation na natutunan natin sa nakaraang modyul, at kung paano gamitin ang mga ito para malutas ang problema ng order-finding.

Sa wakas, magpapatakbo tayo ng algoritmo ni Shor sa tunay na quantum computer! Tandaan, gayunpaman, na ang algorithm na ito ay talagang magiging kapaki-pakinabang lamang kapag mayroon tayong malaki at fault-tolerant na quantum computer, na ilang taon pa ang layo. Kaya, mag-fa-factor lang tayo ng maliit na numero para ipakita kung paano gumagana ang algoritmo.

Ang problema sa pag-factor

Ang layunin ng problema sa pag-factor ay hanapin ang mga prime factor ng isang numero $N$. Para sa ilang numero $N$, medyo madali ito. Halimbawa, kung ang $N$ ay pare-pareho, ang isa sa mga prime factor nito ay magiging 2. Kung ang $N$ ay isang prime power, ibig sabihin $N=p^k$ para sa ilang prime number $p$, medyo madali ring hanapin ang $p$: tinatantya lang natin ang $k^{\text{th}}$ root ng $N$ at naghahanap ng malapit na mga prime na maaaring maging $p$.

Kung saan nahihirapan ang mga klasikal na computer, gayunpaman, ay kapag ang $N$ ay kakaibang numero at hindi isang prime power. Ito ang kaso na tinutugunan ng algoritmo ni Shor. Nakakahanap ang algoritmo ng dalawang factor $p$ at $q$ kung saan $N=pq$. Maaari itong ilapat nang recursive hanggang lahat ng factor ay prime na. Sa mga susunod na seksyon, makikita natin kung paano tinataklasan ang problemang ito.

Kaugnayan sa cyber security

Maraming cryptographic scheme ang itinayo batay sa katotohanan na mahirap i-factor ang malalaking numero, kabilang ang isa na karaniwang ginagamit ngayon, na tinatawag na RSA. Sa RSA, nililikha ang isang public key sa pamamagitan ng pagpaparami ng dalawang malaking prime number para makuha ang $N = p\cdot q$. Pagkatapos, kahit sino ay maaaring gumamit ng public key na ito para i-encrypt ang data. Ngunit tanging ang may hawak ng private key, $p$ at $q$, ang makaka-decrypt ng data na iyon.

Kung madaling i-factor ang $N$, kahit sino ay makakatukoy kung ano ang $p$ at $q$ at mababasag ang encryption. Ngunit hindi ganoon kadali. Ito ay isang kilalang mahirap na problema. Sa katunayan, ang mga prime factor ng isang numero na tinatawag na RSA1024, na may 1024 binary digit at 309 decimal digit ang haba, ay hindi pa natutuklasan, sa kabila ng $100,000 na premyong inaalok para sa pag-factor nito noong 1991.

Solusyon ni Shor

Noong 1994, napagtanto ni Peter Shor na ang isang quantum computer ay maaaring mag-factor ng malaking numero nang mas mahusay nang exponential kaysa sa isang klasikal na computer. Ang kanyang pananaw ay umaasa sa relasyon sa pagitan ng problemang ito sa pag-factor at modular arithmetic. Dadaan tayo sa maikling pagpapakilala sa modular arithmetic, at pagkatapos ay makikita natin kung paano natin ito magagamit para i-factor ang $N$.

Modular arithmetic

Ang modular arithmetic ay isang sistema ng pagbibilang na cyclic, ibig sabihin habang nagsisimula ang pagbibilang sa karaniwang paraan, gamit ang mga integer na 0, 1, 2, atbp., sa isang punto, pagkatapos ng isang panahon $N$, nagsisimulang muli ang pagbibilang. Tingnan natin kung paano ito gumagana gamit ang isang halimbawa. Sabihin nating ang ating panahon ay 5. Pagkatapos, habang nagbibilang tayo, kung saan karaniwan ay maaabot natin ang 5, sa halip ay nagsisimula tayong muli sa 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

Ito ay dahil sa "modulo-5" na mundo, ang 5 ay katumbas ng 0. Sinasabi natin na $5\bmod 5 \ = 0$. Sa katunayan, lahat ng multiple ng 5 ay magiging katumbas ng $0\bmod 5$.

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong sagot, pagkatapos i-click ang tatsulok para ihayag ang solusyon.

Gamitin ang modular arithmetic para malutas ang sumusunod na problema:

Umalis ka sa isang mahabang transcontinental na biyahe sa tren nang 8 AM. Ang biyahe sa tren ay 60 oras ang haba. Anong oras na kapag dumating ka?

Sagot:

Ang panahon ay 24, dahil may 24 oras sa isang araw. Kaya, ang problemang ito ay maaaring isulat sa modular arithmetic bilang:

$(8+60)\text{mod}(24) = 20$

Kaya, darating ka sa iyong destinasyon nang 20:00, o 8 PM.

$\mathbb{Z}_N$ at $\mathbb{Z}_N^*$

Kapaki-pakinabang na ipakilala ang dalawang set, $\mathbb{Z}_N$ at $\mathbb{Z}_N^*$. Ang $\mathbb{Z}_N$ ay simpleng ang set ng mga numerong umiiral sa isang "modulo-$N$" na mundo. Halimbawa, nang nagbibilang tayo ng modulo-5, ang set ay magiging $\mathbb{Z}_5=\{0,1,2,3,4\}$. Isa pang halimbawa: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Maaari tayong magsagawa ng karagdagan at pagpaparami (modulo $N$) sa mga elementong nasa $\mathbb{Z}_N$, at ang resulta ng bawat isa sa mga operasyong ito ay isang elemento rin sa $\mathbb{Z}_N$, na ginagawang ring — isang mathematical na bagay — ang $\mathbb{Z}_N$.

May espesyal na subset ng $\mathbb{Z}_N$ na partikular na interesado sa atin para sa algoritmo ni Shor. Iyon ay ang subset ng mga numero sa $\mathbb{Z}_N$ kung saan ang greatest common divisor sa pagitan ng bawat elemento at ng $N$ ay 1, kaya bawat elemento ay "co-prime" sa $N$. Kung kukuha tayo ng set ng mga numerong ito kasama ang modular multiplication operation, nabubuo nito ang isa pang mathematical na bagay, na tinatawag na group. Tinatawag nating $\mathbb{Z}_N^*$ ang group na ito. Lumalabas na sa $\mathbb{Z}_N^*$ (at sa mga finite group sa pangkalahatan), kung pipili tayo ng anumang elemento $a \in \mathbb{Z}_N^*$ at paulit-ulit na pararamihin ang $a$ sa sarili nito, palagi tayong makakarating sa numerong $1$ sa huli. Ang pinakamaliit na bilang ng beses na kailangang pararamihin ang $a$ sa sarili nito para makuha ang $1$ ay tinatawag na order ng $a$. Ang katotohanang ito ay magiging napakahalagang bahagi ng ating talakayan sa kung paano i-factor ang mga numero sa ibaba.

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong sagot, pagkatapos i-click ang tatsulok para ihayag ang solusyon.

Ano ang $\mathbb{Z}_{15}^*$?

Sagot:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Ibinukod natin ang mga sumusunod na numero:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

Ano ang order ng bawat isa sa mga elemento sa $\mathbb{Z}_{15}^*$?

Sagot:

Ang order na $r$ ay ang pinakamababang numero kung saan $a^r\text{mod}(15)=1$ para sa bawat elemento $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Tandaan na, habang nagawa nating hanapin ang order ng mga numero sa $\mathbb{Z}_{15}^*$, ito ay HINDI madaling gawain sa pangkalahatan, para sa mas malalaking $N$. Ito ang pangunahing punto ng problema sa pag-factor at kung bakit kailangan natin ng quantum computer. Makikita natin kung bakit habang tinatayo natin ang natitirang bahagi ng notebook.

Ilapat ang modular arithmetic sa problema ng pag-factor

Ang susi sa paghanap ng mga factor $p$ at $q$ kung saan $N=pq$ ay ang paghanap ng ilang iba pang integer $x$ kung saan

$x^2 \equiv 1 \bmod N$ at $x \not\equiv \pm 1 \bmod N.$

Paano nakakatulong ang paghanap ng $x$ para mahanap ang mga factor $p$ at $q$? Dumaan tayo sa argumento ngayon. Dahil $x^2 \equiv 1 \bmod N$, ibig sabihin $x^2 - 1 \equiv 0 \bmod N$. Sa ibang salita, ang $x^2 - 1$ ay multiple ng $N$. Kaya, para sa ilang integer $l$,

$x^2 - 1 = l N$

Maaari nating i-factor ang $x^2 - 1$ para makuha:

$(x+1)(x-1) = l N$

Mula sa ating mga unang pagpapalagay, alam natin na $x \not\equiv \pm 1 \bmod N$, kaya ang $N$ ay hindi nahahati nang pantay sa alinman sa $x+1$ o $x-1$. Kaya, ang dalawang factor ng $N$, ang $p$ at $q$, ay dapat na bawat isa ay hahatiin sa $x-1$ at $x+1$. Ang $p$ ay isang factor ng $x-1$ at ang $q$ ay isang factor ng $x+1$, o vice versa. Samakatuwid, kung kukuwentahin natin ang greatest common divisors (GCDs) sa pagitan ng $N$ at parehong $x-1$ at $x+1$, mabibigyan tayo ng mga factor na $p$ at $q$. Ang pagkalkula ng GCD sa pagitan ng dalawang numero ay isang klasikal na madaling gawain na maaaring magawa, halimbawa, gamit ang algoritmo ni Euclid.

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong sagot, pagkatapos i-click ang tatsulok para ihayag ang solusyon.

Maaaring mahirap maunawaan ang bawat hakbang ng lohika sa itaas, kaya subukang dumaan dito gamit ang isang halimbawa. Gamitin ang $N=15$ at $x=11$. Una, i-verify na $x^2 \equiv 1 \text{mod}(N)$ at $x \not\equiv \pm 1 \bmod N$. Pagkatapos ay magpatuloy na i-verify ang bawat hakbang. Sa wakas, kalkulahin ang $\text{GCD}(11\pm1,15)$ at i-verify na ang mga ito ay mga factor ng $15$.

Sagot:

$11^2 = 121$, na siyang $15*8 + 1$, kaya $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, na hindi katumbas ng $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, na hindi katumbas ng $0\bmod 15$. $\checkmark$

Ngayon, alam nating $(x+1)(x-1) = l N$ para sa ilang integer $l$. Ito ay na-verify kapag sinalin natin ang $x$ at $N$: $(12)(10) = l 15$ kapag $l = 8$. $\checkmark$

Ngayon, kailangan nating kalkulahin ang $\text{GCD}(12,15)$ at $\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

Kaya, nahanap natin ang mga factor ng $15$!

Ang algoritmo

Ngayon na nakita natin kung paano nakakatulong ang paghanap ng ilang integer $x$ kung saan $x^2 \equiv 1\bmod N$ para i-factor ang $N$, maaari na nating dumaan sa algoritmo ni Shor. Essentially, bumababa ito sa paghanap ng $x$:

1. Pumili ng random na integer Pumili ng random na integer $a$ kung saan $1 < a < N$.

• Kalkulahin ang $\text{GCD}(a, N)$ nang klasikal.
  • Kung ang $\text{GCD}(a, N) > 1$, nahanap na nito ang isang factor. Huminto.
  • Kung hindi, magpatuloy.

2. Hanapin ang order $r$ ng $a$ modulo $N$ Hanapin ang pinakamaliit na positibong integer $r$ na nagbibigay-kasiyahan sa $a^r \equiv 1 \pmod N$.

3. Suriin kung pare-pareho ang order

• Kung ang $r$ ay kakaibang numero, bumalik sa hakbang 1 at pumili ng bagong $a$.
• Kung ang $r$ ay pare-pareho, magpatuloy sa hakbang 4.

4. Kalkulahin ang $x = a^{r/2} \bmod N$

• Suriin na $x \not\equiv 1 \pmod N$ at $x \not\equiv -1 \pmod N$.
  • Kung $x \equiv \pm 1 \pmod N$, bumalik sa hakbang 1 at pumili ng bagong $a$.
• Kung hindi, kalkulahin ang mga gcd para makuha ang mga factor:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

Ang mga ito ay magiging hindi-trivial na mga factor ng $N$.

5. I-factor nang recursive kung kinakailangan

• Kung ang $p$ at/o $q$ ay hindi prime, ilapat ang algoritmo nang recursive para i-factor ang mga ito nang kumpleto.
• Kapag lahat ng factor ay prime na, kumpleto na ang pag-factor.

Batay sa pamamaraang ito, maaaring hindi malinaw kung bakit kailangan ng quantum computer para makumpleto ang gawaing ito. Kinakailangan ito dahil ang hakbang 2, ang paghanap ng order ng $a$ modulo $N$, ay klasikal na napakahirap na problema. Ang complexity ay nagsa-scale nang exponential sa numero $N$. Ngunit sa isang quantum computer, kailangan lang nating gamitin ang Quantum Phase Estimation para malutas ito. Ang hakbang 4, ang paghanap ng GCD ng dalawang integer, ay talagang medyo madaling gawin nang klasikal. Kaya, ang tanging hakbang na talagang nangangailangan ng kapangyarihan ng quantum computer ay ang hakbang ng order-finding. Sinasabi natin na ang problema ng pag-factor ay "nababawas" sa problema ng order-finding.

Ang mahirap na bahagi: order finding

Ngayon, dadaan tayo sa kung paano natin magagamit ang quantum computer sa order finding. Una, linawin natin kung ano ang ibig nating sabihin ng "order." Siyempre, sinabi ko na sa iyo kung ano ang ibig sabihin ng order nang matematika: ito ang unang non-zero na integer $r$ kung saan $a^r = 1 \pmod N.$ Ngunit tingnan natin kung makakakuha tayo ng kaunting intuwisyon para sa konsepto na ito.

Para sa sapat na maliit na $N$, maaari lang nating matukoy ang order sa pamamagitan ng pagkalkula ng bawat kapangyarihan ng $a$, pagkuha ng modulus $N$ ng numerong iyon, pagkatapos ay huminto kapag nahanap natin ang kapangyarihang $r$ na nagbibigay-kasiyahan sa $a^r = 1 \text{mod}(N)$. Iyon ang ginawa natin sa ating halimbawa, $N=15$, sa itaas. Tingnan natin ang ilang graph ng mga modular power na ito para sa ilang sample na halaga ng $a$ at $N$:

May napansin? Ang mga ito ay periodic na function! At ang order na $r$ ay kapareho ng panahon! Kaya, ang order-finding ay katumbas ng period-finding.

Ang mga quantum computer ay napakahusay sa paghanap ng panahon ng mga function. Para dito, maaari tayong gumamit ng isang algorithmic subroutine na tinatawag na Quantum Phase Estimation. Tinatalakay natin ang QPE at ang relasyon nito sa Quantum Fourier Transform sa nakaraang modyul. Para sa detalyadong refresher, pumunta sa QFT module o aralin ni John Watrous sa Quantum Phase Estimation sa kanyang kurso sa Quantum Algorithms. Dadaan tayo sa pangunahing proseso ngayon:

Sa Quantum Phase Estimation (QPE), nagsisimula tayo sa isang unitary na $U$ at isang eigenstate ng unitary na iyon na $|\psi\rangle$. Pagkatapos, ginagamit natin ang QPE para tantiyahin ang kaukulang eigenvalue, na, dahil ang operator ay unitary, ay magiging anyo ng $e^{2\pi i \theta}$. Kaya, ang paghanap ng eigenvalue ay katumbas ng paghanap ng halaga ng $\theta$ sa periodic na function. Ganito ang hitsura ng Circuit:

kung saan ang bilang ng mga control Qubit (ang nangungunang $m$ na Qubit sa larawan sa itaas) ay nagtatakda ng katumpakan ng pagtatantya.

Sa algoritmo ni Shor, ginagamit natin ang QPE sa unitary operator na $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Dito, ang $|y\rangle$ ay nagtatanda ng isang computational basis state ng multi-qubit register, kung saan ang binary na halaga ng mga Qubit ay tumutugma sa integer na $y$. Halimbawa, kung $N=15$ at $y = 2$, ang $|y\rangle$ ay kinakatawan ng four-qubit basis state na $|0010\rangle$, dahil apat na Qubit ang kailangan para i-encode ang mga numero hanggang 15. (Kung hindi pamilyar ang konseptong ito, tingnan ang introductory Qiskit in classrooms module para sa isang refresher sa binary encoding ng mga quantum state.)

Ngayon, kailangan nating malaman ang isang eigenstate ng unitary na ito. Kung nagsimula tayo sa state na $|1\rangle$, makikita natin na ang bawat sunod na aplikasyon ng $U$ ay pararamihin ang state ng ating register ng $a \pmod N$, at pagkatapos ng $r$ na aplikasyon, darating tayo muli sa state na $|1\rangle$. Halimbawa, sa $a = 3$ at $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Kaya ang mga superposition ng mga state sa cycle na ito ($|\psi_j\rangle$) na may anyo:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

ay lahat eigenstate ng $M_a$. (Mayroon pang mas maraming eigenstate kaysa sa mga ito. Ngunit interesado lang tayo sa mga may anyo sa itaas.)

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong sagot, pagkatapos i-click ang tatsulok para ihayag ang solusyon.

Hanapin ang isang eigenstate ng unitary na tumutugma sa $a=2$ at $N = 15$.

Sagot:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Kaya, ang order na $r=4$. Ang mga eigenstate na interesado tayo ay magiging pantay na superposition ng lahat ng mga state na na-cycle sa itaas, na may iba't ibang phase:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Sabihin nating nagawa nating i-initialize ang ating Qubit state sa isa sa mga eigenstate na ito (spoiler — hindi tayo. O, hindi man lang madali. Ipapaliwanag natin kung bakit at kung ano ang maaari nating gawin sa halip sa ilang sandali). Pagkatapos maaari tayong gumamit ng QPE para tantiyahin ang kaukulang eigenvalue, $\omega_j = e^{2 \pi i \theta_j}$ kung saan $\theta_j = \frac{j}{r}$. Pagkatapos, magagawa nating matukoy ang order na $r$ sa pamamagitan ng simpleng equation:

$r = \frac{j}{\theta_j}.$

Ngunit tandaan, sinabi ko na ang QPE ay tinatantya ang $\theta_j$ — hindi nito binibigyan tayo ng eksaktong halaga. Kailangan ng pagtatantya na sapat na tumpak upang mapagkaiba ang $r$ at $r+1$. Habang mas maraming control Qubit $m$ ang mayroon tayo, mas maganda ang pagtatantya. Sa mga problema sa katapusan ng aralin, hihilingin sa iyo na matukoy ang pinakamaliit na $m$ na kinakailangan para i-factor ang isang numero $N$.

Ngayon, kailangan nating ayusin ang isang problema. Ang lahat ng paliwanag sa itaas kung paano hanapin ang $r$ ay nagsisimula sa paghahanda ng eigenstate na $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Ngunit hindi natin alam kung paano gawin iyon nang hindi nalalaman ang $r$. Ang lohika ay paikot. Kailangan natin ng paraan para tantiyahin ang eigenvalue nang hindi nini-initialize ang eigenstate.

Sa halip na magsimula sa isang eigenstate ng $M_a$, maaari nating ihanda ang paunang state sa $n$-qubit na state na tumutugma sa $|1\rangle$ sa binary (tulad ng, $|000...01\rangle$). Kahit na ang state na ito mismo ay malinaw na hindi isang eigenstate ng $M_a$, ito ay isang superposition sa lahat ng eigenstate na $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong sagot, pagkatapos i-click ang tatsulok para ihayag ang solusyon.

I-verify na ang $|1\rangle$ ay katumbas ng superposition sa mga eigenstate na nahanap mo para sa $N=15$ at $a=2$ sa nakaraang check-in na tanong.

Sagot:

Ang apat na eigenstate ay:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Kaya,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

Paano nito matutulungan tayong mahanap ang order na $r$? Dahil ang paunang state ay isang superposition sa lahat ng eigenstate ng anyo na nakalista sa itaas, ang algoritmo ng QPE ay sabay-sabay na tinatantya ang bawat isa sa mga $\theta_k$ na tumutugma sa mga eigenstate na ito. Kaya, ang sukat ng $m$ na control Qubit sa katapusan ay magbubunga ng isang pagtatantya sa halaga ng $k/r$ kung saan ang $k \in \{0,1,2,...,r-1\}$ ay isa sa mga eigenvalue na pinili nang random. Kung uulitin natin ang Circuit na ito nang ilang beses at makakakuha ng ilang sample na may iba't ibang halaga ng $k$, mabilis tayong makakaabot sa $r$.

I-implement sa Qiskit

Gaya ng nabanggit namin kanina, hindi pa kayang i-factor ng aming hardware ang malalaking bilang tulad ng RSA1024. I-factor na lang natin ang isang maliit na numero para ipakita kung paano gumagana ang algorithm. Para sa demo na ito, gagamitin natin ang isang pinasimpleng bersyon ng code mula sa Shor's algorithm tutorial. Kung gusto mo ng mas maraming detalye, bisitahin ang tutorial.

Patatakbuhin natin ang algorithm gamit ang aming karaniwang framework para sa paglutas ng mga quantum na problema, ang tinatawag na Qiskit patterns framework. Ito ay binubuo ng apat na hakbang:

1. Pag-map ng iyong problema sa isang quantum Circuit
2. Pag-optimize ng Circuit para patakbuhin sa quantum hardware
3. Pagpapatakbo ng iyong Circuit sa quantum computer
4. Post-processing ng mga sukat

1. I-map

I-factor natin ang $N=15$, at pipiliin ang $a=2$ bilang aming co-prime na integer.

Una, kailangan nating itayo ang Circuit na magpapatupad ng modular multiplication unitary, $M_a$. Ito talaga ang pinakamahirap na bahagi ng buong implementasyon, at maaaring napaka-computationally expensive, depende sa kung paano ito ginagawa. Para rito, magsisimula tayo ng kaunti: Alam natin na nagsisimula tayo sa estado $|1\rangle$, at mula sa isang naunang check-in question,

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Kaya, magtatatayo tayo ng isang unitary na gumagawa ng tamang operasyon sa apat na estadong ito, ngunit iniiwan ang lahat ng iba pang estado nang walang pagbabago. Ito ay "pandaraya" dahil ginagamit natin ang ating kaalaman tungkol sa order ng $2\bmod 15$ para pasimplehin ang unitary. Kung talagang sinusubukan nating i-factor ang isang bilang na hindi natin alam ang mga factor, hindi natin magagawa ito.

Suriin ang iyong pag-unawa

Basahin ang (mga) tanong sa ibaba, isipin ang iyong sagot, pagkatapos i-click ang tatsulok para makita ang solusyon.

Gamit ang iyong kaalaman kung paano binabago ng operator na $M_2$ ang mga estado sa itaas, itatayo ang operator mula sa isang serye ng SWAP gates, na nagpapalitan ng mga estado ng dalawang Qubit. (Pahiwatig: ang pagsulat ng bawat estado $|i\rangle$ sa binary ay makakatulong.)

Sagot:

Isulat nating muli ang aksyon ng $M_2$ sa mga estado sa binary:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Ang bawat isa sa mga aksyong ito ay maaaring maisakatuparan gamit ang isang simpleng SWAP. Ang $M_2|0001\rangle$ ay nagagawa sa pamamagitan ng pagpapalitan ng mga estado ng Qubit $0$ at $1$. Ang $M_2|0010\rangle$ ay nagagawa sa pamamagitan ng pagpapalitan ng mga estado ng Qubit $1$ at $2$. At iba pa. Kaya, maaari nating i-deconstruct ang matrix na $M_2$ sa sumusunod na serye ng SWAP gates:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

Aalalahanin na ang mga operator ay kumikilos mula kanan pakaliwa, tiyakin nating mayroon itong epekto na gusto natin sa bawat estado:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Maaari na nating i-code ang Circuit na katumbas ng operator na ito sa Qiskit.

Una, i-import natin ang mga kinakailangang package:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Pagkatapos, gagawin natin ang operator na $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Ang QPE algorithm ay gumagamit ng controlled-$U$ Gate. Kaya, ngayon na mayroon na tayong Circuit na $M_2$, kailangan nating gawing controlled-$M_2$ Circuit ito:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Mayroon na tayong controlled-$U$ Gate. Ngunit para mapatakbo ang Quantum Phase Estimation algorithm, kakailanganin natin ang controlled-$U^2$, controlled-$U^4$, hanggang sa controlled-$U^{2^{m-1}}$, kung saan ang $m$ ay ang bilang ng mga Qubit na ginagamit para tantiyahin ang phase. Habang mas maraming Qubit, mas tumpak ang phase estimation. Gagamitin natin ang $m=8$ control Qubit para sa aming phase estimation procedure. Kaya, kailangan natin ang:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

kung saan ang index na $k$, na may $0 \le k \le m-1 = 7$, ay tumutugma sa control Qubit. Ngayon, kalkulahin natin ang $a^{2^k}\bmod N$ para sa bawat value ng $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Dahil ang $a^{2^k} \bmod N = 1$ para sa $k \ge 2$, lahat ng kaukulang operator ($M_8$ pataas) ay katumbas ng identity. Kaya, isa na lang pang matrix ang kailangan nating itayo, ang $M_4.$

Tandaan: Ang simplipikasyong ito ay gumagana lamang dito dahil ang order ng $2 \bmod 15$ ay $4$. Kapag ang $k=2$ (kaya $2^k = 4$), ang bawat kasunod na kapangyarihan ng operator ay ang identity. Sa pangkalahatan, para sa mas malalaking bilang na $N$ o ibang pagpili ng $a$, hindi mo maaaring laktawan ang pagtatayo ng mas mataas na mga kapangyarihan. Ito ay isa sa mga dahilan kung bakit ito ay itinuturing na isang toy example: ang maliliit na numero ay nagbibigay-daan sa mga shortcut na hindi gagana para sa mas malalaking kaso.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

At tulad ng dati, gagawin natin itong controlled-$M_4$ operator:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Ngayon, maaari na nating pagsamahin ang lahat para mahanap ang order ng $2\bmod 15$ gamit ang isang quantum Circuit, sa pamamagitan ng phase estimation:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. I-optimize

Ngayon na na-map na natin ang aming Circuit, ang susunod na hakbang ay ang pag-optimize nito para patakbuhin sa isang partikular na quantum computer. Una, kailangan nating i-load ang Backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Kung wala kang available na oras sa iyong account o gusto mong gumamit ng simulator sa anumang dahilan, maaari mong patakbuhin ang cell sa ibaba para mag-set up ng simulator na magpapanggap na quantum device na aming pinili sa itaas:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Isagawa

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Nakikita natin ang apat na malinaw na tuktok sa 00000000, 01000000, 10000000, at 11000000, na may ilang bilang sa iba pang mga bitstring dahil sa ingay sa quantum computer. Ibibukod natin ang mga ito at iingatan lang ang nangingibabaw na apat sa pamamagitan ng pagtatakda ng threshold: ang mga bilang na nasa itaas ng threshold na ito lamang ang itinuturing na tunay na signal na higit sa ingay.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Post-process

Para sa Shor's algorithm, malaking bahagi ng algorithm ay isinasagawa nang klasikal. Kaya, ilalagay natin ang natitirang bahagi sa hakbang na "post-processing," pagkatapos makuha ang ating mga sukat mula sa quantum computer. Ang bawat isa sa mga sukat sa itaas ay maaaring i-convert sa mga integer, na, pagkatapos nating hatiin sa $2^m$, ay ating mga pagtatantya para sa $\frac{k}{r}$, kung saan ang $k$ ay random sa bawat pagkakataon.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Konklusyon

Pagkatapos dumaan sa module na ito, maaaring magkaroon ka ng bagong pagpapahalaga sa katalinuhan ni Peter Shor na makagawa ng ganoong matalinong algorithm. Ngunit sana ay nakarating ka na rin sa isang bagong antas ng pag-unawa sa kanyang mapanlinlang na kasimplihan. Kahit na mukhang kahanga-hanga (o nakakatakot) ang algorithm, kung hahati-hatiin mo ito sa bawat hakbang ng lohika at dahan-dahang dadaanan, ikaw din ay makakapagtakbo ng Shor's algorithm.

Malayo pa tayo sa paggamit ng algorithm na ito para i-factor ang mga bilang tulad ng RSA1024, ngunit ang aming mga quantum computer ay nagiging mas mahusay araw-araw, at kapag naabot na ang isang threshold na tinatawag na fault tolerance, ang mga algorithm na tulad nito ay malapit nang sumunod. Kapana-panabik na panahon ito para matuto tungkol sa quantum computing!

Mga Problema

Mga kritikal na konsepto:

• Ang mga modernong cryptographic system ay umaasa sa klasikal na kahirapan ng pag-factor ng malalaking integer.
• Ang modular arithmetic — kabilang ang mga istruktura ng $\mathbb{Z}_N$ at $\mathbb{Z}_N^*$ — ay nagbibigay ng mathematical na pundasyon para sa Shor's algorithm.
• Ang problema ng pag-factor ng integer na $N$ ay maaaring bawasan sa problema ng paghanap ng order ng isang numero modulo $N$.
• Ang quantum order finding ay gumagamit ng mga quantum phase estimation technique para matukoy ang period ng function na $a^x \mod N$.
• Ang Shor's algorithm ay binubuo ng isang klasikal–quantum hybrid workflow na pumipili ng base, nagsasagawa ng quantum order finding, at pagkatapos ay klasikal na kinakalkula ang mga factor mula sa resulta.

Tama/Mali:

1. T/M Ang kahusayan ng Shor's algorithm ay nagbabanta sa seguridad ng RSA encryption.
2. T/M Ang Shor's algorithm ay maaaring maisakatuparan nang mahusay sa anumang makabagong quantum computer ngayon.
3. T/M Ang Shor's algorithm ay gumagamit ng quantum phase estimation (QPE) bilang isang pangunahing subroutine.
4. T/M Ang klasikal na bahagi ng Shor's algorithm ay kinabibilangan ng pagkalkula ng greatest common divisor (GCD).
5. T/M Ang Shor's algorithm ay gumagana lamang para sa pag-factor ng mga pantay na bilang.
6. T/M Ang isang matagumpay na pagtakbo ng Shor's algorithm ay palaging ginagarantiyahang tama ang mga factor.

Maikling sagot:

1. Bakit itinuturing na isang potensyal na banta sa hinaharap ang Shor's algorithm sa RSA encryption?
2. Bakit nakakatulong ang paghanap ng period, o order, ng isang modular exponential function para sa pag-factor ng isang numero sa Shor's algorithm?

Mga hamon na problema:

1. Ilang control Qubit na $m$ ang kailangan natin para sa isang ibinigay na bilang na $N$ na sinusubukan nating i-factor para makuha ang precision sa QPE na kinakailangan para mahanap ang tamang value ng order na $r$?

2. Sinusunod ang pamamaraan na aming binalangkas dito para i-factor ang 15, subukan mo ngayong i-factor ang 21.