Nový rekord: Na kvantovém počítači se podařilo faktorizovat číslo 56 153

Fyzika |

Vzpomínáte si ještě, jak kvantový počítač dokázal s velkou slávou rozložit číslo 15 na 3 x 5? Nyní jsme přece jen o kousek dál. Stačily k tomu navíc pouze 4 qubity.

Nový rekord: Na kvantovém počítači se podařilo faktorizovat číslo 56 153



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ší



Úvodní foto: NASA, Wikipedia, licence public domain




Související články




Komentáře

Napsat vlastní komentář

Pro přidání příspěvku do diskuze se prosím přihlašte v pravém horním rohu, nebo se prosím nejprve registrujte.