Shtetl-Optimized » Архив блога » «Алгоритм JVG» — чушь

Извините, что прерываю ваши обычные программы об апокалипсисе искусственного интеллекта и т. д. и возвращаюсь к традиционному ритму самых ранних лет существования этого блога… но теперь я получил несколько сообщений с просьбой прокомментировать нечто, называемое «Алгоритм JVG (Джесси-Виктор-Гарабаги)» (да, авторы назвали его в честь себя). Это представлено как значительное улучшение по сравнению с алгоритмом факторинга Шора, который мог (согласно популярные статьи) позволяют взломать RSA-2048, используя всего 5000 физических кубитов.

При внимательном рассмотрении большая новая идея статьи состоит в том, что на ключевом этапе алгоритма Шора, где вы вычисляете x^р mod N в суперпозиции по всем r, вместо этого вы предварительно вычисляете x^р mod N на классическом компьютере, а затем загрузить их все в квантовое состояние.

Хорошо, дети, почему это не работает? Может, позвоним кому-нибудь в конце класса? любой курс квантовых вычислений для студентов в мире? Да, класс, это правда! Существует экспоненциально много r. Их вычисление занимает экспоненциальное время, а загрузка их в квантовый компьютер также занимает экспоненциальное время. Мы вышли из н²-время сковороде, но в 2^н-время пожара. Это может только выглядеть так, как будто выигрыш в небольших числах; на больших числах это безнадежно.

Если вы хотите, чтобы люди объясняли одну и ту же тему более вежливо и подробно, попробуйте это из Hacker News или это с Postquantum.com.

Есть ли здесь что-нибудь, что могло бы вызвать подозрение даже у тех, кто ничего не знает о квантовых алгоритмах?

1. Статья появилась не на arXiv, а на каком-то сайте Preprints.org. Если подумать, мне следует добавить это к моему знаменитому Десять признаков того, что заявленный математический прорыв ошибочен! Не то чтобы на arXiv тоже нет тонны дерьма, но я пока что видел довольно много только чушь в репозиториях препринтов, кроме arXiv, ЕСССи МАКР.
2. Судя по поиск Googleэто утверждение, похоже, бесконечно размножалось на новостных сайтах, занимающихся кликбейтом и ссылочным фармом, но игнорировалось авторитетными научными новостными агентствами — да, даже обычные квантовые хайпестеры не касались этого!

Часто, когда что-то этот плохо, милосердный ответ — позволить ему умереть в безвестности. В данном случае, мне кажется, имелся достаточный уровень интеллектуального хулиганства, просто полное отсутствие заботы о том, что правда, что вовлеченные лица заслуживают этого. Shtetl-Оптимизированный постить как крошечный кусочек яйца на их лицах навсегда.