Я заметил, что в последнее время на X стало гораздо больше шума вокруг квантовых компьютеров, поэтому я решил написать длинный пост о них. Краткое резюме: я не верю, что квантовые вычисления появятся в ближайшее время. Я так думаю, потому что за многие годы не было достигнуто никаких успехов в самой простой задаче, для которой можно использовать квантовые компьютеры, а именно в разложении на множители. Рекорд по квантовому разложению на множители держится на числе 15 (да, 15, 3 x 5!) уже целое десятилетие, и в последнее время не произошло никаких очевидных успехов. Мои рассуждения приведены ниже. Я собираюсь объяснить все для людей, которые не знают много о математике или информатике, но это может все равно напугать людей с фобией математики. Разложение больших чисел представляет интерес, потому что несколько важных криптографических алгоритмов зависят от того, что разложение достаточно большого числа на простые множители с использованием обычных компьютеров занимает очень много времени. Вы можете быстро разложить небольшое число (например, 21) вручную, просто попробовав разделить его на числа, начиная с 2, затем 3 и так далее, и вы быстро обнаружите, что 21 = 3 x 7. Однако это не работает для действительно больших чисел, потому что пространство всех чисел, которые вам нужно попробовать, становится слишком большим. Если бы вы могли разложить числа длиной более 1200 десятичных цифр (не число 1200, которое имеет четыре цифры, а числа с 1200 цифрами!), вы могли бы сломать множество криптографических систем, которые интересуют людей, но никто не знает, как сделать это достаточно быстро на обычном компьютере. (Достаточно быстро означает "до того, как все звезды на небе погаснут.") Несколько лет назад Питер Шор показал, что вы можете (по крайней мере, теоретически) быстро разложить числа с помощью квантовых компьютеров. Разложение с использованием алгоритма Шора, на мой взгляд, является самым очевидным сложным ориентиром для квантовых вычислений. В 2016 году число 15 (не 15-значное число, а число 15!) было впервые разложено (очевидно, на 3 x 5) в чистой, неподтасованной демонстрации алгоритма Шора. Это крошечное число, но это был старт. (Существует некоторый спор о том, было ли число 21 также разложено в неподтасованной демонстрации алгоритма Шора или нет.) Но опять же, 15 — это двузначное число. Мы хотим разложить числа в тысячи цифр, чтобы иметь возможность сломать криптографические системы. Однако с 2016 года в чистых демонстрациях алгоритма Шора не было разложено ни одно большее число. (Некоторые люди утверждали, что они разложили большие числа с использованием алгоритма Шора, но они всегда использовали трюки, которые требовали, чтобы они уже знали множители, чтобы сделать это, и настроили квантовый компьютер с тем, что по сути является предварительным знанием ответа, что на самом деле не является целью. Я ищу *неподтасованные* демонстрации.) Мы долго ждали, когда кто-то продемонстрирует разложение даже немного большего числа, чем 15. Вы бы надеялись, что может быть стабильный прогресс в этом, с тем, что кто-то разложит (скажем) число 77 (7 x 11), а затем что-то вроде 323 (17 x 19), затем что-то в тысячах и так далее. Однако никто не продемонстрировал машину, которая могла бы сделать что-то лучшее, чем число 15 (которое ребенок может разложить в уме на 3 и 5 за мгновение), и этот рекорд стоит уже очень долго. Таким образом, по этой задаче, по крайней мере, по действительно базовой, которую легко объяснить, не было стабильного прогресса в квантовых вычислениях. У нас было много шума, много людей, демонстрирующих квантовые компьютеры, якобы запускающие алгоритмы, которые не являются такими уж очевидно чистыми демонстрациями, но мы давно не видели ничего нового в разложении. Я буду верить, что произошел реальный прогресс в квантовых вычислениях, когда мы начнем видеть разложение больших чисел в чистых, неподтасованных демонстрациях алгоритма Шора. Я буду верить, что мы сделали реальный прогресс, когда сможем разложить числа с четырьмя десятичными цифрами, то есть числа в тысячах. Даже демонстрация чего-то, что могло бы разложить гораздо большее двузначное число, чем 15, была бы приветствована. Однако ни одна машина, которая могла бы это сделать, действительно не находится на ближайшем горизонте. Теперь, чтобы сломать коды, нужны машины, которые могут обрабатывать числа с *тысячами* цифр, но у нас даже нет трехзначных чисел на горизонте (или даже большинства двузначных чисел). Таким образом, моим личным ориентиром является увидеть даже немного прогресса в этом. Позвоните мне, когда у нас будут квантовые компьютеры, которые смогут разложить (скажем) 323 успешно, в чистой, неподтасованной демонстрации алгоритма Шора, которая могла бы обрабатывать любое составное число аналогичного размера. До тех пор я не думаю, что происходит что-то интересное, по крайней мере, не для меня.

(Кстати, я не хочу создать впечатление, что считаю квантовые вычисления невозможными или что-то в этом роде. Я просто говорю, что с моей точки зрения недавний прогресс не был очевиден, и мы все еще далеки от решения простых задач, таких как разложение чисел на множители с его помощью.)

Кстати, это также не означает, что такие компании, как Google, глупы, занимаясь чистыми исследованиями в области квантовых вычислений. Я думаю, что это стоит того, чтобы над этим работать. Просто это не имеет никакого немедленного практического применения. Также может быть, что NSA или другие подобные организации достигли более значительного прогресса в решении этой проблемы, чем открытый исследовательский мир, но, очевидно, это не та информация, к которой я имел бы доступ. Наконец, это не означает, что исследования в области постквантовых криптографических алгоритмов — плохая идея.

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

@defendtheworld Так что, в любом случае, снова: я начну верить, когда увижу, что технология продвигается дальше разложения на множители 15. И да, это означает, что уже будет проделана огромная работа, но также останется еще много работы, которую нужно будет сделать.