Физик строит новую теорию сложности из руин старой — обычные суперкомпьютеры окажутся бесполезными против квантовых задач

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

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

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

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

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

За последние 30 лет теория сложности научилась довольно уверенно описывать такие ситуации. Она позволяет формально отделять классы задач, где квантовый компьютер выигрывает, от тех, где особой пользы нет. Но, по мнению теоретика Генри Юэна из Колумбийского университета, этот метод всё равно устроен слишком узко. Ведь он предполагает, что вход и выход всегда классические: нули и единицы. А что, если сам вход — квантовый, и результат тоже должен быть квантовым?

Такие вводные данные нельзя просто переписать в виде обычной битовой строки. Квантовое состояние — не набор цифр в памяти, а физическое состояние системы. Его нельзя прочитать как файл и оставить всё как было. Если измерить квантовое состояние, вы получите один конкретный результат, а само измерение обычно меняет состояние. Плюс квантовые объекты могут быть запутаны: состояние одной части системы связано с другой частью так тесно, что их уже нельзя описать по отдельности, даже если они далеко друг от друга. Поэтому задача вида «взять квантовый вход и получить квантовый выход» по смыслу ближе к управлению физическим процессом, чем к обычной операции с числами.

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

Чтобы показать, что разница действительно принципиальная, Юэн приводит пример из криптографии: bit commitment (схема обязательства). Её часто объясняют через конверт. Человек заранее фиксирует выбранный бит или сообщение так, чтобы до раскрытия никто не узнал содержимое, а после фиксации он уже не мог подменить выбор. Такой приём пригодится, например, на аукционе, когда ставки должны оставаться тайными до вскрытия, или при тайном голосовании, где важны и секретность, и возможность проверки.

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

А теперь представим, что «конверт» устроен квантово. Тогда даже фантастически мощный классический компьютер не обязательно даст атакующему преимущество. Взлом превращается в задачу, где на руках не числа, а квантовое состояние. С ним нельзя обращаться как с файлом: попытка «посмотреть, что внутри» через измерение меняет сам объект. Поэтому просто быстро считать мало, нужно уметь выполнять квантовые преобразования. Юэн и делает отсюда вывод: огромная мощность в классических вычислениях не гарантирует таких же возможностей в задачах с квантовыми входами и выходами. Похоже, это разные типы ресурсов.

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

Юэн предлагает очень конкретную формулировку, которая сводит этот спор к одному вопросу: задача синтеза унитарного преобразования. Унитарное преобразование, это обратимая квантовая операция, базовый способ «переписать» квантовое состояние без измерений и потерь. Допустим, у нас есть идеальный классический оракул - воображаемое устройство, которое мгновенно решает любую задачу с обычным, классическим входом. Хватит ли такой поддержки, чтобы эффективно выполнить любое квантовое преобразование, какое мы захотим? Если ответ окажется отрицательным, это будет означать, что квантовые задачи не сводятся к классическим даже при помощи магии.

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

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

Когда можно управлять обеими частями сразу, нужное преобразование часто достижимо. Но Юэна интересует более жёсткий режим: трогать разрешено только одну часть, а вторую нельзя менять вообще. Тут и начинается интрига. Иногда цель недостижима, и тогда важнее понять другое: насколько близко можно подойти, действуя только с одной стороны.

Теорема Ульмана как раз про это. Она даёт точную оценку, какой максимум можно выжать из локальных действий, если у вас под контролем только половина запутанной системы.

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

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

Дальше разговор уходит от конкретных теорем к тому, как строится новая теория. Юэн подчёркивает: сначала приходится подбирать язык и формулировать правильные вопросы. Без этого нельзя даже нормально сравнить задачи и понять, какие ограничения действительно важны.