Kvantové počítače společnosti D-Wave jsou podle všeho dnes jedinými systémy užívanými i v komerční sféře. Nejde ovšem o univerzální systémy, ale o specializovaná/jednoúčelová zařízení určená pro provádění kvantového žíhání (annealing), tedy operace hledající minima/maxima ve stavovém prostoru.
Vědci nyní tato zařízení dokázali využít i k faktorizaci – rozkladu složeného čísla na prvočísla. Efektivní faktorizace by znamenala prolomení široce rozšířeného šifrovacího algoritmu RSA.
Nyní je třeba trochu odbočit od původního textu (poznámka PH: s rizikem, že následující výklad bude obsahovat chyby). Faktorizaci na univerzálních kvantových počítačích umožňuje Shorův algoritmus, efektivnější než veškeré známé algoritmy klasické. Na počítači D-Wave se ovšem Shorův algoritmus provést nedá. Autoři nové studie ovšem dokázali nějak (?) převést faktorizaci na úlohu hledání maxim/minim. Načež se podařilo rozložit na prvočísla číslo 8 219 999 (32 749 x 251). Netřeba dodávat, že na klasickém superpočítači by tato úloha zabrala zlomek sekundy. Nicméně v případě kvantového systému se jedná o rekord.
„Celkově bylo kvůli vadným qubitům a omezeným zdrojům času na kvantových procesorech 8 219 999 = 32 749 × 251 nejvyšším prvočíselným součinem, který jsme byli schopni faktorizovat. Podle našich nejlepších znalostí se jedná o největší číslo, které kdy bylo faktorizováno s využitím kvantového zařízení, aniž bychom se museli spoléhat na externí vyhledávací nebo předzpracovávací procedury provozované na klasických počítačích,“ uvádí spoluautor výzkumu Roberto Sebastiani z italské University of Trento.
Na klasických počítačích není znám způsob (algoritmus), jak faktorizaci řešit s menší než exponenciální (respektive subexponenciální) složitostí.
Autoři nového výzkumu považují za perspektivní cestu vývoj hybridních postupů, kdy kvantové žíhání bude využíváno a „zavoláno“ klasickými postupy k řešení malých, ale výpočetně velmi náročných kombinatorických podproblémů.
Jingwen Ding et al, Effective prime factorization via quantum annealing by modular locally-structured embedding, Scientific Reports (2024). DOI: 10.1038/s41598-024-53708-7
Zdroj: TechXplore.com
