Student World

Skok je to celkem slušný, předchozí rekord z roku 2012 byl totiž faktorizace čísla 143. Zajímavé je, že nyní použitým postupem nebyl známý Shorův algoritmus, jedna z prvních technik, pomocí nichž se výhodnost (vyšší rychlost) kvantových počítačů vůbec demonstrovala, ale metoda zvaná minimalizace. Výzkumníci uvádějí, že současné implementace Shorova algoritmu de facto vyžadují znalost odpovědi předem, což pro minimalizaci neplatí. Navíc se Shorův algoritmus zatím dostal jen k číslu 21, pro jehož rozklad bylo třeba 10 qubitů. Minimalizace funguje dle původního zdroje tak, že rozklad se převede na problém optimalizace a zde se najdou hodnoty, který sice ještě nejsou přímo děliteli, ale nějak jim odpovídají.

Číslo 56 153 se podobně jako předchozí 143 rozložilo počítačem pracujícím na principu jaderné magnetické rezonance (v originále doslova NMR, stejně u metody zobrazování mozku), který fungoval při pokojové teplotě.
Nike Dattani z Oxford University u univerzity v japonském Kjótu a Nathaniel Bryans (Microsoft a University of Calgary) popsali své výsledky v nedávném dokumentu zveřejněné na arXiv.org. Nyní hodlají na 6 qubitovém kvantovém systému zkusit rozklad čísla 291 311. K dalším cílům patří implementace rozkladu čísla 175 na 5 x 5 x 7, tj. úlohy, kde jsou více než 2 činitelé. Rozklad čísla 175 by měl zvládnout 3qubitový systém.

Číslo 56 153, oproti číslům, které se rozkládají na klasických počítačích, je stále samozřejmě titěrné. V letech 2007-2009 se podařil rozklad čísla o 768 bitech (což souviselo s šifrou RSA, navíc je to ale zde trochu složitější, protože se používají ne složená čísla náhodně vybraná, ale tzv. „semiprimes“, tedy čísla, u nichž se předpokládá, že rozklad bude zvlášť obtížný). Kvantový algoritmus minimalizace na 4 qubitech by šel samozřejmě snadno provést i na klasickém počítači (kde by složitost rostla řádově krát 2 na 4), bylo by to pořád ještě jednodušší. Komerčně nasazený kvantový počítač a dnes největší známé zařízení tohoto typu D-Wave Two má 512 qubitů a už by na klasickém počítači simulovat prakticky nešel, nepoužívá se ale pro faktorizaci.
Ještě k minimalizaci, zajímavé je, že metoda údajně funguje různě rychle pro různá složená čísla. Příští cíl, 291 311 = 557 x 523 byl vybrán, neb zde by měl počítač rozklad dobře zvládnout prý proto, že oba činitelé se od sebe hodně liší – míněno v binárním zápisu, kde je u jednoho čísla 0, tak u druhého obvykle na odpovídajícím místě 1 atd.
A snad ještě na závěr: 56 153 = 241 x 233.

Zdroj: Phys.org a další

autor Pavel Houser