Квантовая информатика

Это всё касалось пока классических каналов связи. Известна теорема кодирования и для квантовых каналов, т.е. когда передаются не классические биты, а квантовые состояния. То же самое: несколько физических кубитов могут кодировать один логический. Ну или блок из n физических кубитов может кодировать k<n логических, тогда k/n - квантовая кодовая скорость. Тоже выводится формула пропускной способности - предела этого отношения.

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

И вот этим летом при помощи ИИ произошел прорыв, причем многие исследователи шли наперегонки: в один день один коллектив публикует, через несколько дней другие уже могли это обобщить. Приведу лишь обобщающий текст от Марко Томамихеля (Tomamichel):
https://marcotom.info/the-tale-of-two-proofs-of-the-strong-converse/

В конце там приведены ссылки на две его работы (обе сентябрьские!), где он доказывает сильное обращение двумя способами, а в середине текста содержится ссылка и на статью моих друзей и коллег из Дюссельдорфского университета, которые летом доказали эту теорему для определенных классов квантовых каналов. Томамихель с соавторами обобщили на все так называемые конечномерные каналы (когда мы кодируем информацию только в конечное число "степеней свободы" квантовой частицы). Одна из статей так и называется - "No information transmission through quantum channels above capacity" - "Невозможность передачи информации по квантовым каналам выше пропускной способности".

А на этой неделе появилась и ещё статья Марка Вайлда (Wilde) с доказательством строгого обращения для важного и практического класса уже бесконечномерных каналов:
https://arxiv.org/abs/2609.16608

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

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

Ошибка декодирования - это ситуация, когда ошибок произошло слишком много, что код уже не может все их исправить. Скажем, вот мы повторили каждый бит трижды: 0->000, 1->111. Если произошла не одна, а две ошибки, т.е. вместо 000 получили 011, то получатель подумает, что было послано 111 и произошла одна ошибка в первой позиции. В результате он декодирует неправильно: не в 0, а в 1. Вот эта ошибка должна стремится к нулю.

А во-вторых, теорема Шеннона доказывает, что лучше - нельзя. Это довольно обычная схема, которую знают и школьники-олимпиадники по математике, "пример+оценка", кажется это называется: надо с одной стороны предъявить пример того, что можно достичь нужного "показателя качества", а с другой - доказать, что ещё лучше - нельзя.

И вот тут в случае с теоремой кодирования и есть тонкость. Что значит "нельзя"? Можно сформулировать так: если мы увеличиваем длину блока, но добавляем слишком мало проверочных битов, т.е. пытаемся передавать информацию быстрее, чем допускает пропускная способность, то вероятность ошибки декодирования НЕ стремится к нулю. Это называется "слабое обращение".

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

Так вот "сильное обращение" (доказанное уже не Шенноном, а позже) утверждает, что нет: если мы вставляем слишком мало проверочных битов для данного уровня шума, то вероятность ошибки не просто не стремится к нулю, а стремится к единице! Причём стремится очень быстро (экспоненциально, в геометрической прогрессии) с размером блока. Вот это уже точно никуда не годится: не один раз из ста, а ПОЧТИ ВСЕГДА мы будем декодировать ошибочно. Никакую информацию так передавать нельзя, так что пропускная способность канала - действительно предел.

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

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

Ключевая характеристика здесь - это отношение информационных битов к сумме информационных и проверочных. В данном случае оно равно 1/3: каждый бит повторяется три раза, т.е. именно информацию несут только треть битов, остальные проверочные. Код Хемминга, который упомянут по ссылке, более экономный: на 4 информационных бита приходится 3 проверочных, так что это отношение равно 4/(4+3)=4/7. Это отношение называется "кодовой скоростью" (code rate). А можно ли ещё лучше? Так вот основнополагающая теорема Шеннона из упомянутой в предыдущей записи работы "Математическая теория связи" устанавливает предельную возможность: к какой предельной кодовой скорости теоретически можно приблизиться при заданной вероятности ошибок. Ну то есть одно дело, когда ошибка возникает в каждом третьем бите, а другое - когда только в каждом сотом. Разумеется, во втором случае нам нужно меньше проверочных битов и можно достигнуть более высоких кодовых скоростей. Теорема Шеннона говорит, каких именно. Предельная теоретически возможная кодовая скорость называется пропускной способностью (capacity) канала связи.

Что значит "предельная" и "теоретически возможная". Для улучшения кодовой скорости лучше кодировать не отдельными битами, а блоками. Вот как код Хемминга берёт не отдельные биты, а блоки по 4 бита. Когда у нас блок, то у нас больше возможностей, мы можем осуществлять более "коллективные" операции. Так что беря блоки всё большей и большей длины, мы можем придумывать коды с более высокой кодовой скоростью.

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

Только вот я настаиваю (перечитывая объявление), чтоб наша подобласть называлась по-русски не "квантовые коммуникации", а "квантовая связь". "Квантовые коммуникации" - это транслитерация с английского "quantum communications" и как будто утвердилась по-русски, но вообще-то неудачная: в русском языке "коммуникации" - это скорее провода и трубы, "проложены коммуникации".

Скажем, основополагающие труды Шеннона "Mathematical theory of communication" и "Communication theory of secrecy systems" переведены на русский как "Математическая теория связи" и "Теория связи в секретных системах". Так что в науке о связи, передаче информации, "communications" так и переводят - "связь". Поэтому и "quantum communications" предлагаю переводить "квантовая связь".

Ну и заодно вот попалось объявление от образовательной программы в МИФИ, где я консультант. 👆 Пишут, что предварительное знакомство с квантовыми технологиями не требуется, то есть, должно быть, это довольно доступное мероприятие.

Регистрация на «Хакни квант» открыта!

Уже скоро пройдёт студенческий хакатон по квантовым технологиям от команды SPARQ и партнёров.

📝 Направления испытаний:
🟢 Квантовые вычисления
🟢 Квантовые коммуникации

Ребята, которым удастся справиться с задачами и впечатлить организаторов, смогут пройти собеседование в компаниях-партнёрах!

🗓 Важные даты:
➖ регистрация (до 23 сентября);
➖ хакатон (25 сентября — 4 октября).

⛓ Регистрация и подробности по ссылке

Хакни квант — войди в кванты через задачу!

#QE_events

Ну и минутка рекламы: образовательный курс в МИАН+онлайн про квантовые алгоритмы от моих замечательных друзей и коллег Евгения Киктенко, Максима Гавреева и Всеволода Яшина. 👆 Очень здорово, что затронуты не только классические алгоритмы Шора и Гровера, но и современные. Скажем, недавно рецензировал статью про "decoded quantum interferometry" - DQI ("декодированная квантовая интерферометрия"?). Подумал: ничего себе, сколько новых вещей сейчас возникает - надо бы разобраться. И тут вижу эту тему в этом курсе - коллеги, оказывается, уже разобрались! 🤝

Этой осенью стартует курс «Введение в квантовые алгоритмы»

Друзья, в рамках Научно-образовательной программы МИАН пройдёт курс, подготовленный сотрудниками Российского квантового центра.

📔НОЦ МИАН — это открытая образовательная программа при Математическом институте им. В. А. Стеклова РАН. Её идея — дать студентам и молодым исследователям возможность изучать современную математику и физику непосредственно у действующих учёных и постепенно включаться в настоящую исследовательскую работу. Лекции проходят по вечерам, посещение свободное; можно подключаться удалённо, а также смотреть лекции в записи.

Курс посвящён одной из центральных областей современной теории квантовых вычислений — квантовым алгоритмам. Слушатели разберутся, как устроены отдельные алгоритмы и какие общие принципы лежат в основе их построения:

🔹 откуда возникает квантовое ускорение;
🔹 какой математический аппарат используют квантовые алгоритмы;
🔹 как оценивать их эффективность и практический потенциал.

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

Программа курса подготовлена сотрудниками группы «Квантовые информационные технологии» РКЦ, часть из которых также работает в Математическом институте им. В. А. Стеклова РАН.

Преподаватели : Евгений Киктенко, Максим Гавреев и Всеволод Яшин.

🗓 Лекции будут проходить по четвергам в период с 24 сентября по 24 декабря 2026 г. в 18:15

Участие бесплатное, но необходима регистрация на странице курса:
https://www.mathnet.ru/conf2803

Перешлите этот пост тем, кому интересны квантовые вычисления и современные алгоритмы!

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

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

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

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

А это картинка, опубликованная OpenAI: Визуализация одного из решений уравнений Навье–Стокса в окрестности точки, где формируется сингулярность.
Оранжевым цветом отмечено более быстрое угловое вращение, бирюзовым — более медленное. Как видим, скорость вращения возрастает при приближении к центральной оси - и, видимо, обращается там в бесконечность. Также говорится о растяжении (тоже бесконечном?) вдоль этой оси.

Начать придётся не с квантовой информатики, а с недавней сенсации - решена одна из семи "задач тысячелетия" о решениях уравнений Навье-Стокса:
Какие ваши доказательства. Действительно ли модель OpenAI решила Задачу тысячелетия?

Список из семи "задач тысячелетия" был составлен в 2000 году Математическим институтом Клэя в США. Сами задачи придуманы не ими, но они отобрали самые важные и обещали премию в миллион долларов за решение каждой.

Самая известная из них - гипотеза Римана из аж 19 века. Задача из списка, связанная с информатикой, - это открытый вопрос о равенстве или неравенстве классов сложности P и NP. Если по-простому, то это вопрос о существовании вычислительно эффективных алгоритмов решения сложных задач - таких как, например, разложение целого числа на простые сомножители, лежащие в основе современной криптографии.

Единственная до недавнего времени решенная задача - это так называемая гипотеза Пуанкаре, решенная петербургским математиком Григорием Перельманом в 2002-2003 годах. Была тогда знатная история, когда он отказался и от миллиона долларов, и от всех премий.

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

Там довольно запутанная история между учеными Тристаном Бакмастером и Левеном Альпёге и компанией OpenAI, разработчиком ChatGPT: какой слух прошел, кто что первым опубликовал, какие там подковёрные переговоры, конкуренция OpenAI и Anthropic (разработчик конкурирующей системы Claude) - тут ещё дело в том, что Альпёге работает в Anthropic.

Но что в итоге: Бакмастер и Альпёге опубликовали развитие сингулярностей для более простого уравнения Эйлера, но, вроде, проверяют своё доказательство и для собственно уравнений Навье-Стокса. В своей работе они активно использовали ИИ, но опирались и на недавние "человеческие" результаты Диего Кордобы и Луиса Мартинеса-Зороа. Также OpenAI то ли опубликовала, то ли только объявила об аналогичном результате именно для уравнений Навье-Стокса: в них действительно тоже развиваются сингулярности. Для этого они использвали новейшую, пока непубличную модель своего ChatGPT. Бакмастер и Альпёге обвинили компанию в том, что вот они общались с ИИ в процессе своих исследований, и эти данные могли утечь в "океан знаний" ChatGPT, так что OpenAI как бы "украли" их результат. В компании сказали, что такое маловероятно, но не исключено, но подчеркнули, что их метод совершенно другой.

Большинство изложений этой истории, в том числе вот этот в nplus1, не упоминают ещё и о третьей группе - ученые Adarsh Ganeshram, Valentin Duruisseaux и Anima Anandkumar из Калифорнийского технологического института, которые тоже решили проблему для уравнений Эйлера (может, в другом варианте, не буквально то же, что Бакмастер и Альпёге), но с минимальным использованием ИИ. Вот их статья: Euler.pdf

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

Такс, простите за долгий перерыв, возвращаюсь:) Сейчас в теоретической квантовой информатике, как и во всей математике, происходит огромный прогресс от использования ИИ. Буквально этим летом он резко вышел на такие мощности, что стал не просто продвинутым инструментом поиска, когда, в отличие от Яндекса и Google, необязательно знать ключевые слова, а можно по сути объяснить, что тебе нужно, и не просто средством ускорения решения несложных вспомогательных задач, где сам бы справился за несколько часов или дней, может, но он это сделал за секунды, а стал способен решать задачи, для которых у людей уже не хватает "мозгов". Посыпались решения открытых задач.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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