Ах да, когда рассказывают о концепции сохранять шифрограммы для расшифровки когда-то в будущем, то иногда приводят в пример огромный центр данных Агентства национальной безопасности США в штате Юта, который простирается на 10 га и объем дискового хранилища которого оценивался в 5 зеттабайт (зетта - это 10^21). Его назначение, естественно, засекречено, но злые языки говорят, что они сохраняют весь мировой интернет-трафик или существенную его часть (годовой интернет-трафик ведь тоже огромен: примерно 3 зеттабайта в 2020 году, так что вряд ли прямо весь) в надежде однажды его расшифровать и прочитать:)

Не зря я обратился к квантовой связи! 18 марта были объявлены лауреаты премии Тьюринга за 2026 год. Это самая престижная премия по информатике. В этом году лауреатами первооткрывателям квантовой криптографии Чарльзу Беннетту (Bennett) и Жилю Брассару (Brassard). Это настолько естественно, что я удивился, что это ещё не было сделано раньше. Открытый ими в 1984 году протокол, названный позже BB84, по первым буквам фамилий и году, до сих пор наиболее широко распространенный и проработанный протокол квантовой криптографии.

В прошлом году на ежегодной международной конференции по квантовой криптографии Жиль Брассар рассказал историю своего открытия. Первая идея была высказана физиком Стивеном Визнером (Wiesner) в 1960-е. Она называлась "квантовые деньги", которые из-за квантовых свойств не могут быть подделаны. Но поскольку это было на стыке физики и информатики, ни те ни те работу не приняли. Позже с идеей познакомился Беннетт и загорелся ей. Потом на пляже физик Беннетт познакомился с информатиком Брассаром:)

Работая вместе, они в итоге пришли к идее, что лучше презентовать не квантовые деньги, а систему квантового создания криптографического ключа. То есть при помощи протокола BB84 и других аналогичных протоколов два пользователя удалённо создают общую секретную случайную двоичную последовательность типа 00100011101..., которая требуется в (обычных, неквантовых) шифрах. Например, советский и российский шифр "Магма" (ранее известный попросту как шифр ГОСТ) требует ключ длины 256 бит. Сам алгоритм известен, но только имея ключ можно зашифровать или дешифровать сообщение. То есть квантовая криптография решает здесь вспомогательную, но критическую задачу, противоречивую по своей природе. Если два терминала имеют общий секретный ключ, то они могут с его помощью шифровать и посылать сообщения по прослушиваемому каналу связи. Но как им сформировать этот общий секретный ключ, если изначально у них ничего нет, а канал прослушивается? Квантовая криптография решает эту задачу.

Поэтому протокол BB84 называют протоколом квантового распределения ключей (quantum key distribution). Позже появились протоколы для других криптографических задач на основе квантовой механики - квантовая цифровая подпись, квантовое разделение секрета, непосредственная квантовая связь (т.е. не создание ключа для последующего шифрования сообщения, а именно прямая передача собственно сообщения). Квантовая криптография сейчас - более широкая область, чем квантовое разделение ключей. Квантовое распределение ключей - наиболее проработанная и доведённая до практики технология, так что часто эти два термина используются как синонимы.

Интересно, что Брассар в своём докладе сказал, что считает слово "распределение" неправильным и они с Беннеттом так не говорили. Распределение - это если кто-то генерирует случайную последовательность, а потом посылает (распределяет) её одному или многим терминалам. А здесь два терминала именно вместе её формируют, поэтому правильнее говорить "квантовое создание ключа" (quantum key establishment). Меня тоже, кстати, всегда смущало это слово "распределение":) Но оно уже стало здесь общепринятым.

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

Но строгое оформление этой простой идеи потребовало создания большой красивой математической теории. Её построение которой для случая идеального оборудования было завершено где-то, я бы сказал, к 2015 году (работа Tomamichel&Leverrier - моя "настольная" статья) - спустя 30 лет после открытия квантовой криптографии. А с учётом реального, неидеального оборудования... как я писал, происходит до сих пор.

Протокол BB84 настолько красив и фундаментален, что хочется сказать, что он именно открыт, а не изобретён. Это старый вопрос в философии математики - математики изобретают, то есть придумывают математические объекты и теории, или они их открывают, подобно тому как физики открывают физические законы. То есть существует ли математика "объективно", где-то на платоновских небесах, в умопостигаемом мире идей? То есть, как есть объективно существующие физические законы материального мира, так есть и объективно существующие математические (а также, допустим, музыкальные) законы умопостигаемого мира идей?

Вот про протокол BB84 хочется верить, что он, как натуральные числа, как тоника, мажор и минор, существует "объективно" и его не изобрели, а именно открыли!

А ещё на конференции торжественно отпраздновали 70-летие Жиля Брассара! Конференция проходила на острове Хайнань в Китае, Южно-Китайское море. Китайцы постарались и сделали вот такой гигантский торт - для всех участников конференции!

Поздравляем корифеев с заслуженной премией! Ура! 🎉

Вот в прошлом месяце вышла статья о том, что шифр RSA с длиной ключа 2048 бит можно (теоретически, при выполнении ряда допущений) взломать на квантовом компьютере, имея не миллионы, а "всего лишь" 100 тысяч кубитов. А тут сегодня появилась новая статья ряда авторов, в их числе - знаменитый Джон Прескилл (Preskill). Теперь уже достаточно и порядка 10 тысяч кубитов!

Этот график показывает, как число физических кубитов уменьшается со временем - благодаря прогрессу в квантовых кодах исправления ошибок, а также в самом квантовом алгоритме Шора: изобретены разные его модификации, в том числе более экономные по числу кубитов.

На графике мы видим, что буквально в последние годы был получен целый ряд новых результатов. Webster et al. ("et al." - это с латинского "и другие") - это как раз работа февраля, там 10^5 кубитов. А теперь ("This work") уже ещё на порядок меньше - 10^4.

Но, конечно, важны детали. В "проекте" Webster et al. квантовый компьютер со 100 тыс. кубитами будет взламывать шифр примерно однин день. А согласно проекту сегодняшней статьи, компьютер на 10 тыс. кубитов будет считать эту задачу примерно три года, а если всё-таки 100 тыс. кубитов, то примерно 100 дней. Это мы переключаемся между разными версиями алгоритма Шора: с меньшим количеством кубитов, но который дольше по времени работает или с большим количеством кубитов, но быстрее по времени.

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

Вероятность ошибки в физическом бите, которую авторы предполагают, - допустим, 0,1% (они рассматривают разные, но выделяют это значение). В обоих статьях цикл исправления ошибок - 1 миллисекунда. Т.е. каждую миллисекунду мы останавливаемся и проверяем на ошибки и затем исправляем их. Также на графике синим изображены расчеты для цикла исправления ошибок в 1 микросекунду, т.е. в 1000 раз чаще.

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

Хороший вопрос - реалистично ли, что квантовый компьютер будет работать месяцами и годами, сохраняя квантовое состояние, хрупкую суперпозицию. Теоретически, если каждую миллисекунду мы успеваем исправлять все ошибки, которые включают в том числе и частичный распад суперпозиции, то почему нет. На практике, конечно, много чего может всплыть: пока мы даже близко квантовые компьютеры не выполняют вычисления так долго. Например, нужно гарантировать высокую надёжность, а то произойдёт какой-нибудь сбой где-нибудь пусть и на последних секундах трёхлетнего вычисления - и начинай сначала:)

Кстати, помимо шифра RSA график показывает и взлом шифра на так называемых эллиптических кривых - ECC (Elliptic curve cipher). Это структурно похожий шифр, но использующий более сложную математику. Эллиптическая кривая - это вовсе не эллипс. Длина ключа может составлять всего лишь 256 бит. В классической криптографии это считается преимуществом: примерно ту же степень стойкости, что и RSA с ключом в 2048 бит, можно обеспечить более сложным шифром на эллиптических кривых с ключом в 10 раз короче. Шифры на эллиптических кривых тоже широко используются.

Но шифр на эллиптических кривых взламывается на квантовом компьютере тем же алгоритмом Шора, т.к. шифры структурно похожи. Так что для квантового компьютера шифр с более коротким ключом - подарок. Скажем, согласно расчётам этой статьи шифр на эллиптических кривых с длиной ключа 256 бит взламывается квантовым компьютером с теми же порядка 10 тыс. кубитов не за три года, а за 10 дней!

Вчера как-то не осознал, но вообще-то: если сейчас у квантовых компьютеров порядка 1000 кубитов, то 10 тысяч - всего на один порядок больше, не кажется большой фантастикой. Совсем недавно-то ещё только десятки были, потом сотни. Хотя, конечно, как мы говорили, дело далеко не только в количестве кубитов, но и во многих других критических факторах (точность выполнения операций, шумы, скорость декодирования кодов исправления ошибок), но тем не менее.

Новости каждый день! А сегодня вышел препринт (т.е. предварительная версия статьи) от Гугла и Эфириума про взлом криптовалют, использующих как раз криптографию на эллиптических кривых, о которой я вчера упомянул. Гугл развивает квантовые вычисления на основе сверхпроводящих кубитов, поэтому в этом препринте именно эта парадигма берётся за основу.

В отличие от вчерашней статьи, здесь используют не LDPC-коды, а более изученные поверхностные квантовые коды исправления ошибок. Как я писал, LDPC-коды более эффективны, но их недостаток - необходимость организации взаимодействия далёких кубитов, т.е. которые физически в "матрице" ("строю") из кубитов отстоят друг от друга далеко. Это не такая большая проблема для атомных и ионных реализаций кубтов, но это проблема для сверхпроводящих кубитов. Поверхностные коды требуют взаимодействия только физически соседствующих кубитов.

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

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

А вчера, 12 мая, было, между прочим, 85 лет как немецкий инженер Конрад Цузе (Zuse) представил общественности свою модель компьютера Z3 - 12 мая 1941 года. Как можно сделать вывод из названия, это была третья его модель, но именно она считается прорывной. Это была электромеханическая машина, т.е. переключения логических элементов осуществлялись под воздействием электрических сигналов, приводивших в действие механические "рубильники". Это, конечно, ограничивало скорость вычислений. Электронные машины, где переключения происходят на микроуровне электронов и токов без механических движений, появились несколько позже, уже (сразу) после войны. Зато это была свободно программируемая (при помощи перфолент) машина на двоичном коде, с операциями с плавающей запятой и всеми другими свойствами современного компьютера. Нет однозначного ответа на вопрос, какое устройство можно считать первым компьютером, поскольку это не одномоментное изобретение, но, пожалуй, Z3 может претендовать на это с наибольшим основанием.

В 1930-е годы Цузе работал на авиационном заводе и его утомляли многочисленные однотипные вычисления. Так он занялся изобретением машины, которая считала бы быстрее и автоматичнее, чем арифмометры. Моя бабушка-инженер рассказывала, что и у неё на работе так и говорили: "Лень - двигатель прогресса: ленишься что-то делать - изобретай!"

Позже после войны Цузе не смог угнаться за американскими конкурентами: всё-таки ресурсы разоренной в результате войны Германии были ограничены, центр науки и технологий переместился в США. В итоге (правда всё-таки уже в 1967 году: не так уж и скоро) он продал свою фирму компании "Сименс".

Постепенно он отошел от дел и занялся своим давним хобби - живописью. Цузе написал несколько портретов пионеров компьютерной отрасли, в том числе Билла Гейтса. В 1995 году, когда они познакомились, Цузе подарил Гейтсу его (Гейтса) портрет, который долгие годы украшал рабочий кабинет основателя корпорации Microsoft!

А на фото - портрет самого Конрада Цузе из компьютерных клавиш в компьютерном музее Хайнца Никсдорфа в Падерборне (Германия), который и вдохновил меня на этот канал. Так что исторически канал не только о квантовой информатике, но также и об истории информатики и компьютеров🙂

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

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

А раздел я сейчас читаю - "Сжатие данных с потерями". Это же очень практическая область! Взял даже с полки коллеги книгу "Digital communication" - казалось бы, название связано с практикой. Но нет, и там теория информации даётся так же абстрактно, в том числе этот раздел.

Придётся по другим источникам изучить что-то: форматы JPEG, MP3, без углубления в специфические подробности, но чтоб проиллюстрировать, как работают принципы теории информации.

Есть сейчас такая "мечта о квантовом интернете" - глобальной сети больших или маленьких квантовых компьютеров. Задачи, которые предполагается решать в таких сетях:

- Система защищенной связи (то бишь квантовая криптография)

- Системы из квантовых сенсоров для измерений и синхронизации времени сверхвысокой точности. В частности, что лично меня вдохновляет, мы можем выйти так и на квантовую гравитацию. Как-нибудь надо написать.

- Распределенные квантовые вычисления. В том числе "слепые" квантовые вычисления, когда клиент подключается к большому облачному квантовому компьютеру.

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

По квантовым сетям и квантовому интернету выходит сейчас очень много работ.

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

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

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

Но устройства квантового распределения ключей у нас связывают только пары участников. Как тогда наиболее оптимально собирать из парных ключей общий конференционный ключ? Оказывается, это связано с задачей оптимальной упаковки так называемых остовных деревьев в граф. Недавно в журнале Physical Review Applied опубликована наша статья (в свободном доступе) об этом. Она получила очень положительные отзывы рецензентов за свою актуальность.

На этом рисунке из нашей статьи приведены примеры таких упаковок. Граф - это наша сеть: узлы (вершины) и парные системы распределения ключей (рёбра). Остовное дерево - это подграф, в котором все вершины связаны, т.е. из любой можно попасть в любую, но обязательно этот путь только один, нет двух разных дорог. Эквивалентно можно сказать, что нет замкнутых путей.

Каждое ребро в графе можно использовать только один раз. Сколько таких деревьев мы сможем найти в графе, использовав по разу каждое ребро, столько бит конференционного ключа и сможем генерировать.

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

Отдельно мы рассматриваем вопрос оптимизации сети. Пусть нам выделены дополнительные ресурсы, на которые мы можем добавить в нашу сеть ещё одну парную связь. Тогда какие именно вершины дополнительно соединить: 1 и 4 или 6 и 2 на левом рисунке? Оказывается, 1 и 4 сильнее увеличивает скорость генерации конференционного ключа. А если можно ещё одну из вариантов, изображенных на рисунке справа? Тогда равнозначно можно 6 и 2 или 6 и 3, а вот 1 и 5 даёт меньший эффект.

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