Post #316

В следующий раз, когда будете читать про прорывы в квантовых вычислениях, как мы на пороге будущего и все такое, вспоминайте, что до сих пор квантовые компьютеры не смогли разложить на простые множители число...21 При этом число "15" разложили еще в 2001 году Почему? А потому, что разложение "21" требует 2.405 квантовых гейтов (вместо 21 гейта в разложении "15") Причина: повезло с числом 15 = 2⁴−1, его очень просто разложить с помощью алгоритма Шора https://algassert.com/post/2500 https://arxiv.org/abs/1301.7007 По сути, в таких работах алгоритм уже "знает" про правильное разложение