С обычным архивом это вышло бы, но в самораспаковывающимся есть одна хитрость, которая, по-моему, хорошо иллюстрирует, почему колмогоровская сложность не вычислима. Там же можно формально перебирать и кусок кода-деархиватора, то есть создание оптимального самораспаковывающегося архива будет эквивалентно решению проблемы остановки машины Тьюринга, которая алгоритмически неразрешима.
Там по ссылке наверное действительно не очень понятно, почему они взяли самораспаковывающийся архив. Мне кажется, это просто по определению колмогоровской сложности. В длине кода деархиватора как раз и «зашифрована» связь с теорией сложности вычислений, но так как изначально пост был про время вычислений, а не занимаемое место, то, наверное, колмогоровская сложность не совсем по теме.
В квантовых компьютерах ускорение не за счёт тактовый частоты, «квантовый параллелизм» и всякое такое. Это скорее к обратимым вычислениям вопрос, где можно уменьшить выделение тепла.
Например, известный эксперт по сложности и квантовым вычисленим Скотт Ааронсон поставил $200 тыс. на то, что доказательство не верно.
Не совсем, он пишет «я поставил бы, как в прошлый раз...». Он уже один раз отредактировал свой блог, убрав ссылку на неверное сообщение об ошибке, Любош Мотль по этому поводу ещё позлобствовал.
Там выше целая ветка комментариев про эти 51 кубит. Просто как-то неожиданно всё это было, к моменту доклада даже препринт ещё не появился. Видео или хотя бы слайды самого доклада тоже что-то не найти.
Для взлома RSA требуется (при идеальной надежности двухкубитных вентилей, алгоритм Шора и обратимая схема возведения в степень по модулю) как минимум в 1.5-2 раза больше кубитов, чем длина ключа в битах ([1], [2], [3]).
Увы, идеальная надёжность — это без учёта необходимости коррекции ошибок. Иначе получается гораздо больше. Просто для примера: дорожная карта с оценкой в сотни миллионов кубитов для разложения 1000 битового ключа.
Для примера того, как управлять квантовым регистром, можете посмотреть SDK (Python) на который ссылаются в статье IBM. Надо только зарегистрироваться и получить соответствующий код. Конечно на 5 и даже на 16 кубитах особо не поломаешь, но представление можно получить.
Я всё никак не могу дождаться (или найти) рекламы типа, что мол вот с квантовым компьютером WannaCry был бы не страшен, он же RSA использует, который можно взломать алгоритмом Шора.
two-qubit controlled-Z и 24 однокубитных вращения «Clifford»
не образуют универсальных набора. Это следует из теоремы Готтесмана-Нилла. Авторы статьи этого и не утверждают. Они эти операции для бенчмарки только используют. Для универсальности к ним надо добавить ещё какое-нибудь однокубитовое вращение.
немногодругое.Увы, идеальная надёжность — это без учёта необходимости коррекции ошибок. Иначе получается гораздо больше. Просто для примера: дорожная карта с оценкой в сотни миллионов кубитов для разложения 1000 битового ключа.
Не совсем понял? Вот, например, вопрос и достаточно стандартное возражение по этому поводу.
не образуют универсальных набора. Это следует из теоремы Готтесмана-Нилла. Авторы статьи этого и не утверждают. Они эти операции для бенчмарки только используют. Для универсальности к ним надо добавить ещё какое-нибудь однокубитовое вращение.
Но в ReactOS 0.4.4 Lazarus 1.6.4 работает без этого бага.