Shorův algoritmus

Pro tento modul Qiskit in Classrooms musí mít studenti funkční prostředí Python s nainstalovanými následujícími balíčky:

• qiskit v2.1.0 nebo novější
• qiskit-ibm-runtime v0.40.1 nebo novější
• qiskit-aer v0.17.0 nebo novější
• qiskit.visualization
• numpy
• pylatexenc

Jak nastavit a nainstalovat výše uvedené balíčky, najdeš v průvodci Instalace Qiskitu. Aby mohli studenti spouštět úlohy na skutečných kvantových počítačích, budou si muset zřídit účet u IBM Quantum® podle kroků v průvodci Nastavení účtu IBM Cloud.

Tento modul byl otestován a využil tři sekundy času QPU. Jedná se pouze o odhad. Skutečná spotřeba se může lišit.

# 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'

Úvod

Na začátku 90. let panoval velký entuziasmus ohledně potenciálu kvantových počítačů řešit problémy, které byly pro klasické počítače obtížné. Několik nadaných počítačových vědců navrhlo algoritmy, které demonstrovaly sílu kvantového výpočtu pro některé okrajové, uměle zkonstruované problémy, ale nikomu se nepodařilo najít jedinou „zabijáckou aplikaci" kvantového výpočtu, která by obor bezpochyby revolucionizovala. To se změnilo v roce 1994, kdy Peter Shor přišel s tím, co se dnes nazývá Shorův algoritmus pro faktorizaci velkých čísel.

V té době bylo dobře známo, že nalezení prvočíselných dělitelů velkého čísla je pro klasický počítač nesmírně obtížné. Internetové bezpečnostní protokoly se na tuto obtížnost přímo spoléhaly. Shor našel způsob, jak tyto dělitele nalézt exponenciálně efektivněji tím, že část náročnějších kroků přenesl na teoretický, budoucí kvantový počítač.

V tomto modulu prozkoumáme Shorův algoritmus. Nejprve si trochu více přiblížíme kontext algoritmu, formalizujeme problém, který řeší, a vysvětlíme jeho relevanci pro kybernetickou bezpečnost. Dále si stručně představíme modulární matematiku a to, jak ji aplikovat na problém faktorizace – ukážeme, jak se faktorizace redukuje na jiný problém zvaný „hledání řádu". Ukážeme, jak do toho vstupují Kvantová Fourierova transformace a Kvantové fázové odhadování, o nichž jsme se učili v předchozím modulu, a jak je použít k řešení problému hledání řádu.

Nakonec spustíme Shorův algoritmus na skutečném kvantovém počítači! Měj ale na paměti, že tento algoritmus bude skutečně užitečný až tehdy, až budeme mít velký, bezchybově tolerantní kvantový počítač, což je stále ještě několik let vzdálené. Proto faktorizujeme jen malé číslo, abychom ukázali, jak algoritmus funguje.

Problém faktorizace

Cílem problému faktorizace je najít prvočíselné dělitele čísla $N$. Pro některá čísla $N$ je to celkem snadné. Pokud je například $N$ sudé, jedním z jeho prvočíselných dělitelů bude 2. Pokud je $N$ mocninou prvočísla, tedy $N=p^k$ pro nějaké prvočíslo $p$, je také poměrně snadné $p$ najít: stačí přibližně spočítat $k$-tou odmocninu z $N$ a hledat blízká prvočísla, která by mohla být $p$.

Klasické počítače ale mají potíže tehdy, když je $N$ liché a není mocninou prvočísla. To je případ, s nímž Shorův algoritmus pracuje. Algoritmus najde dva dělitele $p$ a $q$ tak, že $N=pq$. Lze ho rekurzivně aplikovat, dokud nejsou všechny dělitele prvočísla. V dalších částech uvidíme, jak se k tomuto problému přistupuje.

Relevance pro kybernetickou bezpečnost

Mnoho kryptografických schémat bylo vybudováno na základě skutečnosti, že faktorizace velkých čísel je obtížná, včetně jednoho, které se dnes běžně používá a nazývá se RSA. V RSA se veřejný klíč vytvoří tak, že se dvě velká prvočísla vynásobí a získá se $N = p\cdot q$. Kdokoli pak může tento veřejný klíč použít k šifrování dat. Ale pouze ten, kdo má soukromý klíč, tedy $p$ a $q$, může tato data dešifrovat.

Kdyby šlo $N$ snadno faktorizovat, mohl by kdokoli zjistit, jaká jsou $p$ a $q$, a prolomit šifrování. Ale tak tomu není. Jde o proslule obtížný problém. Prvočíselné dělitele čísla zvaného RSA1024, které má 1024 binárních číslic a 309 desetinných číslic, nebyly dosud nalezeny, přestože za jejich faktorizaci byla v roce 1991 nabídnuta odměna ve výši $100 000.

Shorovo řešení

V roce 1994 si Peter Shor uvědomil, že kvantový počítač dokáže faktorizovat velké číslo exponenciálně efektivněji než klasický počítač. Jeho poznatek se opíral o vztah mezi tímto faktorizačním problémem a modulární aritmetikou. Projdeme si stručný úvod do modulární aritmetiky a poté uvidíme, jak ji lze využít k faktorizaci $N$.

Modulární aritmetika

Modulární aritmetika je systém počítání, který je cyklický – zatímco počítání začíná obvyklým způsobem celými čísly 0, 1, 2 atd., v určitém okamžiku, po období délky $N$, se počítání znovu spustí od začátku. Podívejme se, jak to funguje, na příkladu. Řekněme, že naše perioda je 5. Pak při počítání tam, kde bychom normálně dosáhli 5, začínáme znovu od 0:

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

Je to proto, že ve světě „modulo-5" je 5 ekvivalentní 0. Říkáme, že $5\bmod 5 \ = 0$. Všechny násobky 5 budou ve skutečnosti ekvivalentní $0\bmod 5$.

Ověř si porozumění

Přečti si níže uvedenou otázku, zamysli se nad odpovědí a poté klikni na trojúhelník a odhal řešení.

Pomocí modulární aritmetiky vyřeš následující úlohu:

Vyrážíš na dlouhou transkontinentální cestu vlakem v 8 hodin ráno. Jízda trvá 60 hodin. Kolik bude hodin, až dorazíš?

Odpověď:

Perioda je 24, protože den má 24 hodin. Tento problém lze tedy zapsat v modulární aritmetice takto:

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

Dorazíš do cíle tedy ve 20:00, neboli v 8 hodin večer.

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

Často je užitečné zavést dvě množiny, $\mathbb{Z}_N$ a $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ je jednoduše množina čísel, která existují ve světě „modulo-$N$". Například při počítání modulo-5 by tato množina byla $\mathbb{Z}_5=\{0,1,2,3,4\}$. Další příklad: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Na prvcích $\mathbb{Z}_N$ lze provádět sčítání a násobení (modulo $N$) a výsledek každé z těchto operací je také prvkem $\mathbb{Z}_N$, takže $\mathbb{Z}_N$ tvoří matematický objekt zvaný okruh.

Pro Shorův algoritmus nás zajímá jedna speciální podmnožina $\mathbb{Z}_N$. Je to podmnožina čísel z $\mathbb{Z}_N$ taková, že největší společný dělitel každého prvku a čísla $N$ je 1, tedy každý prvek je „nesoudělný" s $N$. Vezmeme-li množinu těchto čísel spolu s operací modulárního násobení, vznikne jiný matematický objekt zvaný grupa. Tuto grupu nazýváme $\mathbb{Z}_N^*$. Ukázalo se, že u $\mathbb{Z}_N^*$ (a konečných grup obecně) platí: zvolíme-li libovolný prvek $a \in \mathbb{Z}_N^*$ a budeme $a$ opakovaně násobit sám sebou, vždy nakonec dostaneme číslo $1$. Minimální počet, kolikrát musíme $a$ vynásobit sám sebou, abychom dostali $1$, se nazývá řád čísla $a$. Tento fakt bude pro naši diskusi o faktorizaci čísel níže velmi důležitý.

Ověř si porozumění

Přečti si níže uvedenou otázku, zamysli se nad odpovědí a poté klikni na trojúhelník a odhal řešení.

Jaká je množina $\mathbb{Z}_{15}^*$?

Odpověď:

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

Vyloučili jsme tato čísla:

$$\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}$$

Jaký je řád každého z prvků množiny $\mathbb{Z}_{15}^*$?

Odpověď:

Řád $r$ je nejmenší číslo takové, že $a^r\text{mod}(15)=1$ pro každý prvek $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}$$

Všimni si, že ačkoli jsme dokázali najít řád čísel v $\mathbb{Z}_{15}^*$, obecně to pro větší $N$ NENÍ snadný úkol. To je jádro faktorizačního problému a důvod, proč potřebujeme kvantový počítač. Proč tomu tak je, uvidíme, až projdeme zbytek tohoto notebooku.

Aplikace modulární aritmetiky na problém faktorizace

Klíč k nalezení dělitelů $p$ a $q$ takových, že $N=pq$, spočívá v nalezení nějakého jiného celého čísla $x$ takového, že

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

Jak nám nalezení $x$ pomůže najít dělitele $p$ a $q$? Projděme si tento argument nyní. Protože $x^2 \equiv 1 \bmod N$, plyne z toho, že $x^2 - 1 \equiv 0 \bmod N$. Jinými slovy, $x^2 - 1$ je násobkem $N$. Pro nějaké celé číslo $l$ tedy platí:

$x^2 - 1 = l N$

Výraz $x^2 - 1$ lze rozložit na:

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

Z našich počátečních předpokladů víme, že $x \not\equiv \pm 1 \bmod N$, takže $N$ se nedělí beze zbytku ani do $x+1$, ani do $x-1$. Oba dělitelé $N$, tedy $p$ a $q$, se proto musí každý dělit do $x-1$ a $x+1$. Buď je $p$ dělitelem $x-1$ a $q$ dělitelem $x+1$, nebo naopak. Pokud tedy vypočítáme největší společné dělitele (GCD) mezi $N$ a oběma hodnotami $x-1$ a $x+1$, získáme dělitele $p$ a $q$. Výpočet GCD dvou čísel je klasicky snadný úkol, který lze provést například pomocí Eukleidova algoritmu.

Ověř si porozumění

Přečti si níže uvedenou otázku, zamysli se nad odpovědí a poté klikni na trojúhelník a odhal řešení.

Každý krok výše uvedené logiky může být trochu složité pochopit, proto zkus projít příkladem. Použij $N=15$ a $x=11$. Nejprve ověř, že $x^2 \equiv 1 \text{mod}(N)$ a $x \not\equiv \pm 1 \bmod N$. Poté pokračuj v ověřování každého kroku. Nakonec vypočítej $\text{GCD}(11\pm1,15)$ a ověř, že jde o dělitele čísla $15$.

Odpověď:

$11^2 = 121$, což je $15*8 + 1$, takže $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, což není ekvivalentní $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, což není ekvivalentní $0\bmod 15$. $\checkmark$

Víme, že $(x+1)(x-1) = l N$ pro nějaké celé číslo $l$. To se ověří, když dosadíme $x$ a $N$: $(12)(10) = l 15$ pro $l = 8$. $\checkmark$

Nyní musíme vypočítat $\text{GCD}(12,15)$ a $\text{GCD}(10,15)$.

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

Nalezli jsme tedy dělitele čísla $15$!

Algoritmus

Teď, když jsme viděli, jak nám nalezení celého čísla $x$ takového, že $x^2 \equiv 1\bmod N$, pomáhá rozložit $N$ na součin, můžeme projít Shorův algoritmus. V podstatě se celý scvrkne na nalezení $x$:

1. Vyber náhodné celé číslo Vyber náhodné celé číslo $a$ takové, že $1 < a < N$.

• Klasicky spočítej $\text{GCD}(a, N)$.
  • Pokud $\text{GCD}(a, N) > 1$, už jsi našel(la) dělitele. Zastav se.
  • Jinak pokračuj.

2. Najdi řád $r$ čísla $a$ modulo $N$ Najdi nejmenší kladné celé číslo $r$, které splňuje $a^r \equiv 1 \pmod N$.

3. Zkontroluj, zda je řád sudý

• Pokud je $r$ liché, vrať se ke kroku 1 a vyber nové $a$.
• Pokud je $r$ sudé, pokračuj ke kroku 4.

4. Spočítej $x = a^{r/2} \bmod N$

• Ověř, že $x \not\equiv 1 \pmod N$ a $x \not\equiv -1 \pmod N$.
  • Pokud $x \equiv \pm 1 \pmod N$, vrať se ke kroku 1 a vyber nové $a$.
• Jinak spočítej největší společné dělitele a vyextrahuj dělitele:

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

To budou netriviální dělitelé $N$.

5. Rekurzivně rozlož, pokud je to potřeba

• Pokud $p$ a/nebo $q$ nejsou prvočísla, aplikuj algoritmus rekurzivně, dokud je úplně nerozložíš.
• Jakmile jsou všechny dělitele prvočísla, je rozklad hotový.

Na základě tohoto postupu nemusí být na první pohled zřejmé, proč je k jeho provedení potřeba kvantový počítač. Je to nutné proto, že krok 2 – nalezení řádu $a$ modulo $N$ – je klasicky velmi obtížný problém. Složitost roste exponenciálně v závislosti na $N$. Ale s kvantovým počítačem stačí využít Kvantové fázové odhadování. Krok 4, nalezení největšího společného dělitele dvou celých čísel, je klasicky docela snadný. Takže jediný krok, který skutečně potřebuje sílu kvantového počítače, je krok hledání řádu. Říkáme, že problém faktorizace se „redukuje" na problém hledání řádu.

Nejtěžší část: hledání řádu

Teď projdeme, jak můžeme při hledání řádu použít kvantový počítač. Nejdřív si ujasněme, co myslíme slovem „řád". Samozřejmě jsem ti matematický význam řádu už vysvětlil(a): je to nejmenší nenulové celé číslo $r$ takové, že $a^r = 1 \pmod N.$ Ale zkusme pro tento pojem získat trochu více intuice.

Pro dostatečně malá $N$ můžeme řád zjistit jednoduše tak, že vypočítáme každou mocninu $a$, vezmeme zbytek po dělení $N$ a zastavíme se, až najdeme mocninu $r$ splňující $a^r = 1 \text{mod}(N)$. Přesně to jsme dělali v našem příkladu s $N=15$ výše. Pojďme se podívat na grafy těchto modulárních mocnin pro několik vzorových hodnot $a$ a $N$:

Všiml(a) sis něčeho? Jsou to periodické funkce! A řád $r$ je stejný jako perioda! Hledání řádu je tedy ekvivalentní hledání periody.

Kvantové počítače jsou k nalezení periody funkcí velmi dobře přizpůsobené. K tomu můžeme využít algoritmickou podrutinu zvanou Kvantové fázové odhadování. QPE a jeho vztah ke Kvantové Fourierově transformaci jsme probírali v předchozím modulu. Pro podrobné osvěžení znalostí navštiv modul QFT nebo lekci Johna Watrouse o Kvantovém fázovém odhadování v jeho kurzu Kvantové algoritmy. Teď projdeme jádro postupu:

V Kvantovém fázovém odhadování (QPE) začínáme s unitárním operátorem $U$ a jeho vlastním stavem $|\psi\rangle$. Poté pomocí QPE přibližně určíme odpovídající vlastní hodnotu, která – jelikož je operátor unitární – bude mít tvar $e^{2\pi i \theta}$. Nalezení vlastní hodnoty je tedy ekvivalentní nalezení hodnoty $\theta$ v periodické funkci. Circuit vypadá takto:

kde počet řídicích Qubitů (horních $m$ Qubitů na obrázku výše) určuje přesnost aproximace.

V Shorově algoritmu používáme QPE na unitární operátor $M_a$:

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

Zde $|y\rangle$ označuje stav výpočetní báze víceQubitového registru, kde binární hodnota Qubitů odpovídá celému číslu $y$. Například pokud $N=15$ a $y = 2$, pak $|y\rangle$ je reprezentován čtyřQubitovým bázovým stavem $|0010\rangle$, protože ke kódování čísel až do 15 jsou potřeba čtyři Qubity. (Pokud ti tento pojem není povědomý, podívej se na úvodní modul Qiskit ve třídách, kde najdeš osvěžení o binárním kódování kvantových stavů.)

Teď musíme přijít na to, jaký je vlastní stav tohoto unitárního operátoru. Pokud začneme ve stavu $|1\rangle$, vidíme, že každá následující aplikace $U$ vynásobí stav našeho registru číslem $a \pmod N$, a po $r$ aplikacích se opět dostaneme do stavu $|1\rangle$. Například pro $a = 3$ a $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}$$

Superpozice stavů v tomto cyklu ($|\psi_j\rangle$) ve tvaru:

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

jsou tedy všechny vlastními stavy operátoru $M_a$. (Existuje více vlastních stavů než jen tyto. Ale zajímají nás pouze ty ve výše uvedeném tvaru.)

Ověř si porozumění

Přečti si níže uvedené otázky, zamysli se nad odpovědí a pak klikni na trojúhelník, aby se zobrazilo řešení.

Najdi vlastní stav unitárního operátoru odpovídajícího hodnotám $a=2$ a $N = 15$.

Odpověď:

$$\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}$$

Takže řád je $r=4$. Vlastní stavy, které nás zajímají, budou stejnoměrnou superpozicí všech stavů, jimiž jsme prošli výše, s různými fázemi:

$$\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}$$

Řekněme, že jsme schopni inicializovat stav našeho Qubitu do jednoho z těchto vlastních stavů (spoiler — nejsme. Nebo alespoň ne snadno. Za chvíli vysvětlíme proč a co místo toho lze udělat). Pak bychom mohli použít QPE k odhadnutí odpovídající vlastní hodnoty $\omega_j = e^{2 \pi i \theta_j}$, kde $\theta_j = \frac{j}{r}$. Poté budeme schopni určit řád $r$ jednoduchým vztahem:

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

Ale pamatuj, řekl jsem, že QPE odhaduje $\theta_j$ — nedává nám přesnou hodnotu. Odhad musí být dostatečně přesný, aby bylo možné rozlišit mezi $r$ a $r+1$. Čím více řídicích Qubitů $m$ máme, tím přesnější odhad bude. V úlohách na konci lekce budeš vyzván/a, abys určil/a minimální $m$ potřebné k faktorizaci čísla $N$.

Nyní musíme vyřešit jeden problém. Celé výše uvedené vysvětlení, jak najít $r$, začíná přípravou vlastního stavu $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Jenže nevíme, jak to udělat, aniž bychom $r$ již znali. Logika je kruhová. Potřebujeme způsob, jak odhadnout vlastní hodnotu bez inicializace vlastního stavu.

Místo zahájení z vlastního stavu $M_a$ můžeme připravit počáteční stav jako $n$-qubitový stav odpovídající $|1\rangle$ v binárním zápisu (tj. $|000...01\rangle$). Ačkoli tento stav sám o sobě zjevně není vlastním stavem $M_a$, je superpozicí všech vlastních stavů $|\psi_k\rangle$:

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

Ověř si porozumění

Přečti si níže uvedené otázky, zamysli se nad odpovědí a pak klikni na trojúhelník, aby se zobrazilo řešení.

Ověř, že $|1\rangle$ je ekvivalentní superpozici přes vlastní stavy, které jsi nalezl/a pro $N=15$ a $a=2$ v předchozí kontrolní otázce.

Odpověď:

Čtyři vlastní stavy byly:

$$\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}$$

Tedy:

$$\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}$$

Jak nám to pomůže najít řád $r$? Protože počáteční stav je superpozicí přes všechny výše uvedené vlastní stavy, algoritmus QPE současně odhaduje každé z $\theta_k$ odpovídajících těmto vlastním stavům. Měření $m$ řídicích Qubitů na konci tedy vydá přibližnou hodnotu $k/r$, kde $k \in \{0,1,2,...,r-1\}$ je jedna z náhodně zvolených vlastních hodnot. Pokud tento Circuit zopakujeme několikrát a získáme několik vzorků s různými hodnotami $k$, budeme schopni $r$ rychle odvodit.

Implementace v Qiskit

Jak jsme zmínili dříve, náš hardware ještě není na takové úrovni, abychom mohli faktorizovat obrovská čísla jako RSA1024. Faktorizujeme jen malé číslo, abychom ukázali, jak algoritmus funguje. Pro tuto ukázku použijeme zjednodušenou verzi kódu uvedeného v tutoriálu Shorova algoritmu. Pokud chceš více podrobností, navštiv daný tutoriál.

Algoritmus spustíme pomocí našeho standardního rámce pro řešení kvantových problémů, který se nazývá rámec Qiskit patterns. Skládá se ze čtyř kroků:

1. Převod tvého problému na kvantový Circuit
2. Optimalizace Circuitu pro spuštění na kvantovém hardwaru
3. Spuštění Circuitu na kvantovém počítači
4. Následné zpracování měření

1. Mapování

Faktorizujme $N=15$ a jako naše nesoudělné celé číslo zvolme $a=2$.

Nejprve musíme sestavit Circuit, který implementuje unitární operátor modulárního násobení $M_a$. To je ve skutečnosti nejtrickovější část celé implementace a může být výpočetně velmi náročné v závislosti na způsobu provedení. Zde si trochu podvedeme: víme, že začínáme ve stavu $|1\rangle$ a z dřívější kontrolní otázky platí:

$$\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}$$

Sestrojíme tedy unitární operátor, který provede správné operace na těchto čtyřech stavech, ale ostatní stavy ponechá beze změny. To je podvod, protože využíváme znalost řádu čísla $2\bmod 15$ ke zjednodušení unitárního operátoru. Kdybychom se skutečně snažili faktorizovat číslo, jehož faktory nám nejsou známy, nemohli bychom to takto udělat.

Ověř si porozumění

Přečti si otázku (otázky) níže, zamysli se nad odpovědí a pak klikni na trojúhelník, aby se zobrazilo řešení.

Na základě svých znalostí o tom, jak operátor $M_2$ transformuje výše uvedené stavy, zkonstruuj tento operátor jako posloupnost hradel SWAP, která vzájemně vyměňují stavy dvou qubitů. (Nápověda: pomůže ti zapsat každý stav $|i\rangle$ ve dvojkové soustavě.)

Odpověď:

Přepišme působení $M_2$ na stavy ve dvojkové soustavě:

$$\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}$$

Každé z těchto zobrazení lze provést jednoduchým hradlem SWAP. $M_2|0001\rangle$ získáme prohozením stavů qubitu $0$ a $1$. $M_2|0010\rangle$ získáme prohozením stavů qubitu $1$ a $2$. A tak dále. Matici $M_2$ tedy lze rozložit na následující posloupnost hradel SWAP:

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

S vědomím, že operátory působí zprava doleva, ověřme, že to má požadovaný efekt na každý ze stavů:

$$\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}$$

Nyní můžeme zakódovat Circuit, který je ekvivalentní tomuto operátoru, v Qiskitu.

Nejprve naimportujeme potřebné balíčky:

# 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

Pak vytvoříme operátor $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)

Algoritmus QPE používá řízené hradlo $U$ (controlled-$U$). Teď, když máme Circuit pro $M_2$, musíme z něj udělat řízený-$M_2$ Circuit:

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)

Nyní máme naše řízené hradlo $U$. Abychom ale mohli spustit algoritmus Quantum Phase Estimation, budeme potřebovat řízené $U^2$, řízené $U^4$, až po řízené $U^{2^{m-1}}$, kde $m$ je počet qubitů použitých k odhadu fáze. Čím více qubitů, tím přesnější odhad fáze. Pro náš postup odhadu fáze použijeme $m=8$ řídicích qubitů. Potřebujeme tedy:

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

kde index $k$, přičemž $0 \le k \le m-1 = 7$, odpovídá řídicímu qubitu. Vypočítejme nyní $a^{2^k}\bmod N$ pro každou hodnotu $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]

Protože $a^{2^k} \bmod N = 1$ pro $k \ge 2$, jsou všechny odpovídající operátory ($M_8$ a vyšší) ekvivalentní identitě. Potřebujeme tedy zkonstruovat jen jednu další matici: $M_4.$

Poznámka: Toto zjednodušení funguje zde pouze proto, že řád $2 \bmod 15$ je $4$. Jakmile $k=2$ (tedy $2^k = 4$), každá další mocnina operátoru je identita. Obecně platí, že pro větší čísla $N$ nebo jiné volby $a$ nelze přeskočit konstrukci vyšších mocnin. To je jeden z důvodů, proč se jedná o hračkový příklad: malá čísla umožňují zkratky, které by pro větší případy nefungovaly.

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)

A stejně jako předtím z něj uděláme řízený-$M_4$ operátor:

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)

Nyní vše složíme dohromady, abychom s pomocí odhadu fáze nalezli řád $2\bmod 15$ pomocí kvantového Circuit:

# 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. Optimize

Teď, když jsme namapovali náš Circuit, je dalším krokem jeho optimalizace pro spuštění na konkrétním kvantovém počítači. Nejprve musíme načíst Backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Pokud nemáš na svém účtu dostupný čas nebo chceš z jakéhokoli důvodu použít simulátor, můžeš spustit níže uvedenou buňku a nastavit simulátor, který bude napodobovat kvantové zařízení, které jsme vybrali výše:

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. Execute

# 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))

Vidíme čtyři zřetelné vrcholy u 00000000, 01000000, 10000000 a 11000000, přičemž v ostatních bitových řetězcích jsou určité počty způsobené šumem kvantového počítače. Tyto výsledky budeme ignorovat a ponecháme pouze dominantní čtyři tím, že zavedeme prahovou hodnotu: za skutečný signál nad šumem se považují pouze počty přesahující tento práh.

# 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

V případě Shorova algoritmu se velká část algoritmu provádí klasicky. Proto zbytek umístíme do kroku „post-processingu", poté co získáme měření z kvantového počítače. Každé z výše uvedených měření lze převést na celá čísla, která po vydělení hodnotou $2^m$ tvoří naše aproximace $\frac{k}{r}$, kde $k$ je pokaždé náhodné.

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 ***

Závěr

Po absolvování tohoto modulu možná budeš nově obdivovat genialitu Petera Shora, který přišel s tak důmyslným algoritmem. Doufejme však, že jsi také dosáhl nové úrovně porozumění jeho klamné jednoduchosti. Ačkoli se algoritmus může zdát působivě (nebo intimidujícím způsobem) složitý, pokud ho rozložíš do jednotlivých logických kroků a projdeš je pomalu, i ty budeš schopen spustit Shorův algoritmus.

I když jsme daleko od použití tohoto algoritmu k faktorizaci čísel jako RSA1024, naše kvantové počítače se každým dnem zlepšují a jakmile bude dosažena hranice nazývaná odolnost vůči chybám, brzy budou následovat i takovéto algoritmy. Je to vzrušující doba pro studium kvantové informatiky!

Úlohy

Klíčové pojmy:

• Moderní kryptografické systémy se spoléhají na klasickou obtížnost faktorizace velkých celých čísel.
• Modulární aritmetika — včetně struktur $\mathbb{Z}_N$ a $\mathbb{Z}_N^*$ — poskytuje matematický základ Shorova algoritmu.
• Problém faktorizace celého čísla $N$ lze redukovat na problém nalezení řádu čísla modulo $N$.
• Kvantové hledání řádu využívá techniky kvantové fázové estimace k určení periody funkce $a^x \mod N$.
• Shorův algoritmus se skládá z klasicko-kvantového hybridního postupu, který vybere základ, provede kvantové hledání řádu a poté klasicky vypočítá faktory z výsledku.

Pravda/Nepravda:

1. P/N Efektivita Shorova algoritmu ohrožuje bezpečnost RSA šifrování.
2. P/N Shorův algoritmus lze efektivně spustit na jakémkoli moderním kvantovém počítači.
3. P/N Shorův algoritmus využívá kvantovou fázovou estimaci (QPE) jako klíčový podprogram.
4. P/N Klasická část Shorova algoritmu zahrnuje výpočet největšího společného dělitele (NSD).
5. P/N Shorův algoritmus funguje pouze pro faktorizaci sudých čísel.
6. P/N Úspěšné spuštění Shorova algoritmu vždy zaručuje správné faktory.

Krátké odpovědi:

1. Proč je Shorův algoritmus považován za potenciální budoucí hrozbu pro RSA šifrování?
2. Proč je nalezení periody neboli řádu modulární exponenciální funkce užitečné pro faktorizaci čísla v Shorově algoritmu?

Náročné úlohy:

1. Kolik kontrolních Qubitů $m$ potřebujeme pro dané číslo $N$, které se pokoušíme faktorizovat, abychom získali přesnost QPE potřebnou k nalezení správné hodnoty řádu $r$?

2. Podle postupu, který jsme zde nastínili pro faktorizaci čísla 15, zkus nyní faktorizovat číslo 21.