V poslední době jsem viděl mnohem více humbuku kolem kvantových počítačů na X, takže jsem si řekl, že o nich udělám dlouhý příspěvek. Shrnutí: Nevěřím, že kvantové výpočty v dohledné době přijdou. Myslím si to proto, že za mnoho let nedošlo k žádnému pokroku v nejpřímějším problému, pro který lze kvantové počítače použít, a tím je faktoring. Rekord kvantového faktoringu se již deset let pohybuje kolem čísla 15 (ano, 15, 3 x 5!) a v poslední době nedošlo k žádnému zjevnému pokroku. Moje úvahy jsou níže. Rozeberu to pro lidi, kteří toho moc nevědí o matematice nebo informatice, ale stále by to mohlo vyděsit lidi s fobiemi z matematiky. Faktorizace velkých čísel je zajímavá, protože několik důležitých kryptografických algoritmů závisí na skutečnosti, že rozklad dostatečně velkého čísla na jeho prvočíselné dělitele pomocí konvenčních počítačů trvá velmi dlouho. Malé číslo (řekněme 21) můžete velmi rychle rozložit ručně, zkuste ho vydělit čísly začínajícími na 2, pak 3 a tak dále, a rychle zjistíte, že 21 je 3 x 7. To však nefunguje pro opravdu velká čísla, protože prostor všech čísel, která byste museli vyzkoušet, je příliš velký. Pokud byste mohli rozložit čísla delší než asi 1200 desetinných míst (ne číslo 1200, které má čtyři číslice, čísla s 1200 číslicemi!), mohli byste prolomit spoustu kryptografických systémů, na kterých lidem záleží, ale nikdo neví, jak to udělat dostatečně rychle na normálním počítači. (Dost rychle znamená "než všechny hvězdy na obloze vyhoří".) Před několika lety Peter Shor ukázal, že pomocí kvantových počítačů můžete (alespoň teoreticky) velmi rychle faktorizovat čísla. Faktoring pomocí Shorova algoritmu je podle mého názoru nejzřejmějším těžko zfalšovatelným benchmarkem pro kvantové výpočty. V roce 2016 bylo číslo 15 (ne 15místné číslo, ale číslo 15!) poprvé rozloženo (samozřejmě do 3 x 5) v čisté, nezmanipulované demonstraci Shorova algoritmu. To je malé číslo, ale byl to začátek. (Existují spory o tom, zda číslo 21 bylo také zohledněno v nezmanipulované demonstraci Shorova algoritmu nebo ne.) Ale znovu, 15 je dvouciferné číslo. Chceme rozložit čísla v tisících číslic, abychom byli schopni prolomit kryptografické systémy. Od roku 2016 však nebyla v čistých demonstracích Shorova algoritmu zohledněna žádná větší čísla. (Někteří lidé tvrdili, že pomocí Shorova algoritmu rozložili větší čísla, ale vždy používali triky, které vyžadovaly, aby už tyto faktory znali, aby to mohli udělat a nastavit kvantový počítač s tím, co se rovná předběžné znalosti odpovědi, což ve skutečnosti není pointa. Hledám *nezmanipulované* ukázky.) Dlouho jsme čekali, až někdo předvede rozklad i jen o trochu většího čísla než 15. Doufali byste, že by v tomto ohledu mohl být stálý pokrok, kdy někdo rozloží (řekněme) číslo jako 77 (7 x 11), a pak číslo jako 323 (17 x 19), pak něco jako tisíce a tak dále. Nikdo však nepředvedl stroj, který by uměl něco lepšího než číslo 15 (které si dítě může v hlavě rozložit na 3 a 5 během několika okamžiků) a tento rekord platí velmi dlouho. Takže přinejmenším v tomto problému, opravdu základním, který lze snadno vysvětlit, nedošlo v kvantových počítačích k žádnému trvalému pokroku. Měli jsme spoustu humbuku, spoustu lidí předváděli kvantové počítače, které údajně provozují algoritmy, které nejsou tak očividně čistými demonstracemi, ale za dlouhou dobu jsme neviděli nic o faktoringu. Věřím, že v kvantových počítačích došlo ke skutečnému pokroku, když začneme vidět větší čísla započítávaná do čistých, nezmanipulovaných demonstrací Shorova algoritmu. Budu věřit, že jsme dosáhli skutečného pokroku, když dokážeme dělat čtyři desetinná čísla, tedy čísla v tisících. Dokonce i demonstrace něčeho, co by mohlo udělat mnohem větší dvouciferné číslo než 15, by byla vítána. Žádný stroj, který by to dokázal, však není v blízké budoucnosti skutečně na obzoru. Schopnost lámat kódy vyžaduje stroje, které zvládnou zpracovávat čísla s *tisíci* číslicemi, ale zatím nemáme v dohledu ani třímístná čísla (nebo dokonce většinu dvouciferných čísel). Takže můj osobní benchmark v tomto ohledu zaznamenává i malý pokrok. Zavolejte mi zpět, až budeme mít kvantové počítače, které dokážou úspěšně rozložit (řekněme) 323 v čisté, nezmanipulované ukázce Shorova algoritmu, který by zvládl jakékoli složené číslo podobné velikosti. Do té doby si myslím, že se toho moc neděje, alespoň ne pro mě.

(BTW, nechci vzbudit dojem, že si myslím, že kvantové výpočty jsou nemožné nebo tak něco. Jen říkám, že z místa, kde stojím, nebyl nedávný pokrok zřejmý a stále jsme daleko od řešení jednoduchých problémů, jako je rozklad čísel.)

Mimochodem, to také neznamená, že společnosti jako Google jsou hloupé, když se věnují čistému výzkumu kvantových počítačů. Myslím, že stojí za to na tom pracovat. Prostě to nemá žádné bezprostřední praktické využití. Může to být také tím, že NSA nebo jiné podobné organizace učinily v tomto problému významnější pokrok, než učinil svět otevřeného výzkumu, ale to samozřejmě není informace, do které bych byl zasvěcen. A konečně, to neznamená, že výzkum postkvantových kryptografických algoritmů je špatný nápad.

Ve svém původním příspěvku nahoře jsem se vyhnul zmínce o tom, jak těžké jsou problémy s měřítkem. Většinou jsem se soustředil na to, že k žádnému škálování ve skutečnosti nedošlo. A aby bylo jasno, v určitém okamžiku je velmi pravděpodobné, že se začnou objevovat věci na opravu chyb. Ale škálování na faktorizaci vážných čísel nenastane den poté.

@defendtheworld Takže znovu: začnu věřit, až uvidím, že se technologie posune od faktoringu 15. A ano, to znamená, že obrovské množství práce již bylo vykonáno, ale také to zanechá obrovské množství práce, kterou je třeba ještě udělat.