1 of 16

Shorův algoritmus

Kvantová magie v praxi

Jan Horalík, JOpenspace 2022

2 of 16

Loňská přednáška - Nebojte se kvantových počítačů

Magické vlastnosti kvantových počítačů

Dostupné v cloudech

4 of 16

Magické vlastnosti na reálném příkladu

Problém faktorizace (rozklad velkého čísla na součin prvočísel)

RSA

Shorův algoritmus

💣

5 of 16

Trocha matematiky

Pro a,b nesoudělné, existují p, m, že:

a^p= b . m + 1

g^p= N . m + 1

(g^p/2+1)(g^p/2-1) = N.m

Bezoutova identita

g .. guess, N .. číslo, které faktorizujeme

hledáme exponent p

Dva kandidáty na faktory N

6 of 16

Shorův algoritmus (pravděpodobnostní)

Tipneme si prvočíslo g, pokud dělí N, máme faktor
Pokud ne, hledáme exponent p, aby: g^p mod “nějaký násobek N” = 1
Pomocí Euklidova algoritmu dopočítáme faktory (g^p/2-1) a (g^p/2+1)

Možné problémy

Pokud p liché, tak g^p/2 není celé číslo => začneme znova, tipneme jiné g
Mohou mi vyjít faktory čísla m (ne N) => začneme znova, tipneme jiné g

Ve ⅜ případů nenastane ani problém 1 ani problém 2

Krok 2 je na klasických počítačích neúnosně pomalý

Kvantový

algoritmus

7 of 16

Superpozice

Jednotka paměti 1 qbit

Stav - body na povrchu jednotkové sféry

Kvantová hradla - mění stav

Měření (čtení) - vrátí 0 nebo 1

8 of 16

Magie #1: Superpozice

|1, g¹> + |2, g²> + |3, g³> +..

|1> + |2> + |3>+..

gˣ

mod (m.N)

|1, 17> + |2, 5> + |3, 92> +..

Paralelní výpočet

Pokud ale superpozici změříme, dostaneme jenom jeden náhodný vzorek

9 of 16

Interference

Interference je eliminace těch kvantových stavů v superpozici, které vedou k nesprávným výsledkům, tak aby zbyly stavy vedoucí k žádoucím výsledkům kvantového výpočtu.

Zdroj: https://www.spiceworks.com/tech/artificial-intelligence/articles/what-is-quantum-computing/

10 of 16

Ještě trocha matematiky

g^x = m.N + r

Pak také

g^x+p = m₂.N + r

Superpozice má

opakující se vlastnost p

|1, 17> + |2, 5> + |3, 92> +.. + |p+1, 17> + |p+2, 5> + .. + |1+2p, 17> + ..

vzdálenost p

11 of 16

Magie #2: Interference

|1, 17> + |2, 5> + |3, 92> +.. + |p+1, 17> + ..

vzdálenost p

|5>

| 2, 5> + |12, 5> + |22, 5> +..

Částečné měření,

Měříme jenom zbytek

V superpozici zůstaly jenom stavy se zbytkem 5 (odpovídající naměřené hodnotě)

12 of 16

Magie #2: Interference - pokračujeme

| 2, 5> + |12, 5> + |22, 5> +..

Superpozice má teď periodu p, neboli frekvenci 1/p

| x> + |x+p> + |x+2p> +..

Quantum Fourier

Transformation

| 1/p>

Fourierova transformace (QFT) rozloží “signál” na jeho frekvence

13 of 16

Shorův algoritmus - dokončení

Z QFT zjistíme exponent p
Pomocí Euklidova algoritmu dopočítáme kandidáty na faktory (g^p/2-1) a (g^p/2+1)
Máme šanci ⅜, že jsou faktory N

14 of 16

Počet q-bitů v čase

Zdroj: https://www.researchgate.net/figure/A-chart-shows-the-progress-of-quantum-computer-with-numbers-Quantum-Bits-Source-75_fig1_342377828

15 of 16

Shrnutí, zdroje

Shorův algoritmus na faktorizaci

Klasický kvantový algoritmus (1994)
Používá superpozici a interferenci
Kvantová část řeší jenom malou klíčovou část algoritmu
Pro reálnou implementaci na velkých číslech nemáme zatím dost qbitů

Zdroje

Youtube kanál MinutePhysics