Scienceworld | Cesta ke kvantovému počítači (3)

Cesta ke kvantovému počítači (3) – Shorův algoritmus

Fyzika | 22.10.2004

Shor si uvědomil, že v kvantovém počítači získá hodinová aritmetika značnou výhodu: velké množství výpočtů, které je zapotřebí provést, abychom získali číselnou vlnu, lze provést současně. Stejně jako světelné nebo zvukové vlny lze i číselné vlny analyzovat pomocí mocného nástroje, který se nazývá Fourierova transformace. Jednou z informací, kterou lze pomocí něj získat, je právě perioda vlny.

Sdílet

Shorovi se jeho průlom podařil díky matematické lsti: když se matematik setká se vzpurným problémem, pokouší se ho „zobrazit“ na jednodušší úlohu. Jsou-li obě úlohy ekvivalentní, pak vyřešení jedné z nich je zcela rovnocenné s vyřešením druhé.
Podle legendy skvěle demonstroval tento druh obratnosti německý matematik Carl Friedrich Gauss. Jeho učitel na základní škole dal své třídě únavný a vyčerpávající úkol, totiž sečíst dohromady úplně všechna čísla od 1 do 100. Zatímco jeho spolužáci pracně sčítali 1 + 2, pak 3 + 4, pak 5 + 6 a tak dále, Gauss rychle našel lepší postup: sečti 1 + 100, pak 2 + 99, pak 3 + 98 a tak dále, až dojdete k 50 + 51. Všechny tyto součty však ve skutečnosti nemusíte provést. Každý z nich je zjevně 101, celkem jich je 50, a proto 50 × 101 = 5050.
Gauss vymyslel algoritmus, který šetří čas: sečtěte první a poslední číslo (1 + 100), pak tento součet vynásobte polovinou většího čísla. Sečíst všechna čísla od 1 do 1000 starým způsobem by trvalo nejméně desetkrát déle než sečíst čísla od 1 do 100. Ale s Gaussovým algoritmem prostě jen vynásobíte 1001 × 500. Abyste sečetli všechna čísla do milionu, vynásobte 1 000 001 × 500 000. Procedura bude trvat o trochu déle než při součtu od 1 do 10, ale rozhodně ne 100 000krát déle. Algoritmus se škáluje mnohem pomaleji.
Když Shor hledal svoji zkratku napříč časem, výhodně využil překvapivé skutečnosti, kterou matematikové znali už dávno. Díky hluboké souvislosti ve struktuře matematického světa je možné úlohu faktorizace zobrazit na jiný, zcela odlišný problém: zkoumání posloupnosti číslic a zjišťování jejich periodičnosti, tedy toho, zda a jak často se opakují. Například posloupnost 123123123123 má periodu 3. Můžete si ho představit jako vlnu.

Poznámka: Úryvek je, přepokládáme, srozumitelný i bez obrázků, které najdete v tištěné knize.

Abychom našli dělitele daného čísla, dosadíme ho nejprve do jednoduchého vzorce, který vytvoří jeden z takových zvlněných proudů číslic. V jeho rytmu jsou zakódováni příslušní dělitelé. Úloha nyní spočívá v tom, jak je odhalit. Stejně jako lze analyzovat zvukové vlny anebo vlnění světla a hledat v nich skryté obrazce, lze totéž provést i s číselnou vlnou. Vpusťte ji do vhodného algoritmu (jakéhosi matematického filtru) a vypadnou z něj hledaní dělitelé. Až celou proceduru níže popíšeme podrobněji, bude vše poněkud jasnější. Pro tento okamžik si můžete prostě představit, že číslo projde jakýmsi matematickým hranolem, který na stěnu promítne jeho dělitele.
I při použití této nepřímé metody řešení problému faktorizace je stále zapotřebí provést enormní množství výpočtů. Chceme-li ve stručnosti charakterizovat, co se vlastně Shorovi podařilo, pak šlo o objev, že všechny tyto výpočty lze provést najednou v kvantové superpozici. Anebo jinak: jeho algoritmus dokáže vytvořit kvantovou vlnu, která představuje každého možného dělitele a kterou pak lze zkolabovat, aby nám poskytla žádanou odpověď.
To je podstata celé myšlenky. S trochou trpělivosti je však možné nahlédnout dovnitř do černé skříňky a ocenit algoritmus v ještě větším detailu. Toto delší vysvětlení, které učiní objev daleko konkrétnějším a bohatším, je založeno na využití modulové neboli „hodinové“ aritmetiky. Tento předmět se může zdát ezoterický, ale ve skutečnosti není o moc složitější než běžná schopnost říci, jaký je správný čas.

Číselný systém si obvykle představujeme jako nekonečnou posloupnost přirozených čísel: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15… Sečíst 7 a 6 znamená začít na pozici 7 a poskočit o 6 míst doprava, takže skončíte na pozici 13. Modulová aritmetika však místo toho používá jednoduchý kruhový číselný systém, který se podobá ciferníku hodin.

Kolik je 7 hodin plus 6 hodin? Je to 13 hodin? Nikoli, pokud používáme obvyklý časový systém. Správný výsledek dostanete tak, že začnete na 7 a posunete se o 6 míst dopředu okolo ciferníku, takže skončíte na hodnotě 1. V tomto systému platí, že 7 + 6 = 1. A 10 + 4 = 2. Než abyste si ukazovali prstem dokola ciferníku, můžete výsledek získat následující aritmetickou operací: sečtěte obvyklým způsobem 10 a 4 a dostanete 14. Pak vydělte 14 číslem 12 (což je počet čísel na ciferníku hodin) a dostanete zby-
tek 2, což je hledaná odpověď. Matematik to zapíše jako 10 + 4 = 2 (mod 12). Čte se to „modulo 12“.
Číselný systém typu mod 5 odpovídá hodinám, jejichž ciferník má jen pět čísel. Počítáte-li dokola ciferníku, dostanete 4 + 5 = 4 (mod 5). Což lze získat sečtením 4 a 5, které dá 9, a to vydělíte 5. Výsledek je 1 ze zbytkem 4. Což lze říci ještě jinak, totiž že 9 z našeho běžného systému je rovno číslu 4 v mod 5 systému. Čemu je rovno číslo 33? Začněte na pozici 1 a popojděte o 33 míst dokola ciferníku. Skončíte na pozici 3, takže 33 = 3 (mod 5). Pro velká čísla se takovéto počítání stává poněkud náročným. Proto je rychlejší vydělit 33 číslem 5 a jen se podívat na zbytek po tomto dělení.
Chceme-li faktorizovat v modulové aritmetice, pak první krok spočívá v tom, že si vyrobíme speciální ciferník: ten obsahuje právě tolik pozic, kolik je hodnota čísla, jež máte rozložit. Abychom našli dělitele například čísla 15, vezmeme hodiny, které mají na ciferníku vyznačeno právě 15 čísel.

Poté použijeme tento matematický strojek a vyrobíme číselnou vlnu. Zjištěním její periody neboli toho, s jakou frekvencí se v ní znaky čísel opakují, lze nalézt dělitele. Celou proceduru, i když vypadá poněkud pracně, lze popsat jako posloupnost jednoduchých kroků zcela jasného algoritmu.
Nejprve zvolíme libovolné číslo, jež je menší než to, které máme rozložit. (I když to vypadá podivně, funguje to.) Nechť je to například 7. Pak toto číslo umocníme na druhou, třetí, čtvrtou atd. mocninu. Takto získaná čísla přeložíme do hodinové aritmetiky.
Začneme samotným číslem 7. Když se posouváme podél našeho ciferníku, zjistíme, že i v soustavě mod 15 je sedmička rovna 7 (neboli 7 děleno 15 je nula se zbytkem 7).
Nyní umocníme 7 na druhou, což dá číslo 49. Patnáctka se do něj vejde třikrát a zbude 4. Takže už máme první dvě čísla z naší posloupnosti: 7 a 4.
Pokračujme dále: umocníme 7 na třetí, což dá 7 × 7 × 7 = 343. Patnáctka se do něj vejde 22krát a zbude 13. Pro 7 umocněné na čtvrtou dostaneme podobně zbytek 1, pro 7 na pátou dostaneme zbytek 7.
Stalo se cosi zvláštního. Jak umocňujeme číslo 7 na vyšší a vyšší mocniny, vynořuje se nám posloupnost čísel, které se stále opakují: 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1… a tak dále do nekonečna. Konkrétní čísla sama však nejsou důležitá, podstatný je jejich rytmus – vznikla vlna, která má periodu 4.

A teď přichází vyvrcholení. Abychom z číselné vlny vyloudili dělitele čísla 15, odložíme ji nyní stranou a provedeme pár drobných výpočtů. Nejprve vezmeme periodu vlny, kterou jsme právě získali, a vydělíme ji dvěma. Pak umocníme 7, tedy číslo, které jsme na počátku našeho matematického maratonu libovolně zvolili, na tuto mocninu. Takže 4 děleno 2 dá 2 a pak 7 na druhou dá číslo 49.
Poslední krok spočívá v tom, že vezmeme dvě nejbližší čísla po obou stranách čísla 49, tedy 48 a 50. Obě porovnáme se zadaným číslem 15 a zjistíme, jací jsou jejich největší společní dělitelé, neboli čísla, která se do obou beze zbytku vejdou. Společným dělitelem 48 a 15 je číslo 3. Pro 50 a 15 je to číslo 5. A vskutku: 3 a 5 jsou dělitelé zadaného čísla 15. Problém je vyřešen.
Naprosto stejný výsledek bychom získali, i kdybychom se vydali jinou cestou tím, že bychom na počátku namísto sedmičky zvolili číslo 2 nebo třeba 11. Dosazením jiného čísla do algoritmu bychom vygenerovali jinou číselnou vlnu s jinou periodou. Na konci analýzy bychom však vždy obdrželi stejné dělitele čísla 15, tedy 3 a 5. (Procedura není vždy úplně spolehlivá. Občas dostaneme posloupnost, jejíž perioda je liché číslo. Tím vzniká problém, neboť ji nelze celočíselně vydělit dvěma. Počítač však může zkoušet různé hodnoty tak dlouho, než získá vlnu, která funguje.)
Je samozřejmě mnohem snazší faktorizovat malá čísla (jako například 15) obvyklým způsobem tak, že je postupně dělíme čísly 2, 3, 4 atd. a pak se díváme, zda nechávají zbytek po dělení. Ale pro velmi velká čísla je řešení v hodinové aritmetice o něco rychlejší než metoda pokusu a omylu. Nový algoritmus se také škáluje exponenciálně, i když explozivní nárůst není tak strmý. Je výhodnější, ale nepříliš výrazně. Pro větší a větší čísla je množství operací stále nezvládnutelné.
To ovšem platí jen pro klasický stroj. Shor si uvědomil, že v kvantovém počítači získá hodinová aritmetika značnou výhodu: velké množství výpočtů, které je zapotřebí provést, abychom získali číselnou vlnu, lze provést současně. Samozřejmě že i mnoho dělení v prastaré metodě pokusu a omylu by bylo možné nějak provést v superpozici (a je zcela v pořádku o něčem takovém uvažovat). Existoval však velmi dobrý důvod následovat Gaussův příklad a použít nepřímý postup. Stejně jako světelné nebo zvukové vlny lze totiž i číselné vlny analyzovat pomocí mocného nástroje, který se nazývá Fourierova transformace (po francouzském matematikovi jménem Jean-Baptiste Joseph Fourier). Jednou z informací, kterou lze pomocí něj získat, je právě perioda vlny.
Shor věděl, že jeho kolegové nedávno narazili na cosi, co se v té době zdálo být pouhou kuriozitou, totiž že by šlo provést Fourierovu proceduru pomocí hypotetického kvantového počítače.6 Je lepší ponechat na tomto místě zmíněnou techniku v obalu svého jména: její rozbalení a hlubší pochopení by zde přeci jen bylo poněkud tvrdším oříškem. Stačí jen uvést, že Fourierova transformace spočívá ve své podstatě ve vytvoření svazku testovacích vln, z nichž každá má jinou periodu, a v jejich postupném porovnání s vlnou, kterou chcete analyzovat. V kvantovém počítači lze všechna tato porovnání provést najednou. Shor věřil, že uvedená technika by mohla být použita k rychlému zjištění dělitelů.
Připomeňme si, že algoritmus hodinového ciferníku začíná volbou libovolného čísla, které je menší než to, které máme faktorizovat. To je použito jako „násada“, umocněno na první, druhou, třetí a další mocniny, čímž je odpověď převedena do řeči modulové aritmetiky. Dostaneme posloupnost, jejíž perioda v sobě obsahuje hledané dělitele. Shorův algoritmus začíná vložením všech těchto exponentů, tedy čísel 1, 2, 3, 4 atd., do kvantové superpozice. Nejprve musí být samozřejmě zakódovány do binární soustavy: 0, 1, 10, 11, 100, 101, 110, 111, 1000… A jak jsme již viděli, všechny tyto řetězce jedniček a nul je možné současně reprezentovat pomocí superponovaného stavu řetízku otáčejících se atomů. Budeme je nazývat „vstupní registr“.
Když se nyní všechna tato čísla najednou vznášejí ve vstupním registru, provedeme s nimi výpočet, kterým je umocnění násady na tyto stále větší mocniny. Shor ukázal, jak je možné něco takového provést pomocí kvantových ekvivalentů hradel AND, OR a NOT. Atomy jsou v registru uspořádány tak, že některé spolu souvisejí. Jestliže se jeden otáčí jistým směrem, pak jiný se musí otáčet naopak. Jakmile jsou atomy správně „propleteny“, vhodně zvolená sekvence laserových impulzů provede příslušný modulární výpočet. A protože se vstupní hodnoty nacházejí v superponovaném stavu, jsou všechny výpočty – v podobě číselné vlny – provedeny naráz.
Nyní přichází to nejtěžší: výsledek se objeví zase v podobě superpozice ve „výstupním registru“, který se také skládá z řádky otáčejících se atomů. (Můžete si představovat, že každý atom ze vstupního registru je kvantově mechanicky propojen neboli „propleten“ s příslušným atomem výstupního registru, podobně jako oba fotony v EPR experimentu.) Předpokládejme, že kvantový počítač právě dokončil aplikaci řady laserových pulzů, aby faktorizoval číslo 15. Všechny prvky vzniklé číselné vlny, tedy 1, 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, se nyní nacházejí v superpozici ve výstupním registru.
Jediné, co zbývá, je zjistit periodu vlny. Když změříme výstupní registr, náhodným způsobem zkolabuje do jednoho jediného čísla z posloupnosti, například do hodnoty 7. To nám samo o sobě neřekne nic užitečného. Ale protože jsou oba registry navzájem „propletené“, vstupní registr přitom kupodivu částečně zkolabuje, a to do superpozice všech možných vstupních čísel (mocnin), které vygenerovaly 7, když jsme s nimi obíhali dokola ciferníku našeho pomyslného hodinového mlýnku: do superpozice čísel 1, 5, 9, 13, 17, 21 atd.
Povšimněte si, že v posloupnosti těchto čísel ve vstupním registru je řád: navzájem se liší právě o 4 jednotky. Jinými slovy, mají stejný rytmus, jako je perioda výstupní posloupnosti. To je ona číselná vlna, na níž stačí provést závěrečné měření. Kvantový počítač tedy vypálí finální salvu světelných impulzů, které provedou Fourierovu transformaci: testovací vlny různých frekvencí jsou současně porovnány s číselnou vlnou ve vstupním registru. Ta vlna, která se dokonale hodí, zjeví výsledek. A pak už jen zbývá provést trochu obyčejné aritmetiky. Po několika jednoduchých výpočtech, které lze provést i na docela obyčejném klasickém počítači, vypadnou ven hledaní dělitelé.
Když už jsme došli takhle daleko, můžeme nyní Shorův algoritmus zase zabalit a jeho detaily odložit stranou. Odteď ho opět můžeme chápat jako černou skříňku, která důvtipným způsobem používá kvantové superpozice, aby se prodrala výpočetní houštinou a v rekordním čase faktorizovala každé číslo. Co funguje pro malá čísla jako 15, funguje stejně dobře i pro čísla veliká, pokud ovšem máme k dispozici dostatek atomů, které mohou být naverbovány, aby sloužily jako q-bity. A proto tolik laboratoří na tomto úkolu nyní tvrdě pracuje: odměna za jejich úsilí by byla ohromná. Připomeňme, že nejrychlejšímu superpočítači, jehož fungování je omezeno zákony klasické fyziky, by trvalo celé věky, než by faktorizoval číslo, které má pár set cifer. Pomocí Shorova algoritmu by se to dalo zvládnout za pár minut.

Úryvek z knihy
Geogre Johnson: Zkratka napříč časem – cesta ke kvantovému počítači, přeložili Pavel Cejnar a Jiří Podolský, Argo a Dokořán, Praha, 2004.