Этот документ нельзя скопировать и нельзя прочитать дважды. Можно ли заменить квантовое доказательство обычным текстом?
Математики искали ответ 20 лет. Оказалось — нельзя. И вот почему.
Квантовый компьютер может не только быстрее решать некоторые задачи. В отдельных случаях он требует доказательство, которое нельзя переписать в обычный документ. Исследователи показали, что для одной специальной вычислительной задачи правильность решения подтверждает только квантовое состояние. Текстовая инструкция, программа или набор чисел не заменяют такой сертификат.
В информатике доказательством называют не цепочку рассуждений из учебника математики, а короткое подтверждение правильного решения. Судоку дает простой пример. Найти заполнение сложной сетки трудно, но проверить готовую таблицу легко: компьютер проходит по строкам, столбцам и квадратам, затем убеждается, что цифры расставлены без ошибок. Многие вычислительные задачи устроены похожим образом. Поиск ответа требует больших усилий, проверка готового результата занимает гораздо меньше времени.
Квантовые задачи меняют привычную схему. Для части из них подтверждением служит не текст и не список параметров, а квантовое состояние. Так называют математическое описание системы частиц: электронов, фотонов или других объектов квантового мира. Проблема возникает из-за суперпозиции. Квантовая система может содержать сразу множество возможных конфигураций, а число этих вариантов растет чрезвычайно быстро. Даже у сравнительно небольшой системы полное описание может оказаться длиннее любого физически возможного документа.
Долгое время оставалась надежда, что квантовый сертификат получится заменить обычным. Возможно, вместо самого состояния достаточно записать хитрую инструкцию, которая позволит квантовому компьютеру создать нужный объект и проверить задачу. Для опровержения этой идеи мало найти пример с квантовым доказательством. Нужно показать, что никакой классический документ не справится, даже если проверку выполняет квантовая машина.
Новая работа строится вокруг задачи spectral forrelation problem. У термина нет устоявшегося русского перевода, поэтому корректнее оставить английское название и объяснить смысл. Задача сравнивает два разных способа измерить одно квантовое состояние. Удобная аналогия здесь такая: есть предмет и две тени от света под разными углами. По двум теням нужно понять, мог ли один предмет дать оба результата. В квантовой версии вместо предмета берется квантовое состояние, а вместо теней - результаты двух разных измерений.
Без дополнительных данных проблема трудна даже для квантового компьютера. Но если дать машине подходящее квантовое состояние, проверка становится простой. Компьютер измеряет состояние нужными способами и убеждается, что результаты согласуются с двумя заданными наборами данных. Само квантовое состояние работает как доказательство правильности.
Затем исследователи разобрали возможную замену. Представим, что вместо квантового состояния есть обычный текстовый документ. В нем записана процедура, по которой квантовый компьютер создает нужное состояние. После запуска процедуры машина получает объект, сравнивает результаты измерений с исходными данными и принимает доказательство. Такой документ считался бы классическим доказательством, потому что сам по себе он остается обычной записью, а не квантовым объектом.
Главное различие между двумя вариантами связано с повторным использованием. Текст можно читать и запускать сколько угодно раз. Документ не меняется после проверки. Квантовая запутанность устроена иначе: измерение нарушает состояние и меняет дальнейшие результаты. Один и тот же квантовый сертификат нельзя просто проверять бесконечно, не затрагивая его содержимое.
Именно повторяемость классического доказательства приводит к противоречию. Если бы текстовая процедура для spectral forrelation problem существовала, ее можно было бы запускать снова и снова, каждый раз получая свежую копию нужного квантового состояния. С помощью этих копий удалось бы решать дополнительную задачу: угадывать форму исходных результатов измерений по неполной информации. Отдельная часть доказательства показывает, что классический документ не может дать такую возможность. Значит, исходное предположение неверно: для этой задачи классического доказательства нет.
Формально результат разделяет два класса задач. QMA включает задачи, где доказательством может быть квантовое состояние. QCMA включает задачи, где доказательство остается классическим, хотя проверять его разрешено квантовому компьютеру. Авторы получили oracle separation, то есть разделение в модели с оракулом. В теории сложности оракулом называют условный внешний механизм, который отвечает на специальные запросы алгоритма. Такой результат не закрывает вопрос во всех возможных моделях, но дает сильное математическое свидетельство: квантовые доказательства не сводятся к классическим.
Позднее появилась еще одна работа с разделением QMA и QCMA на другой вычислительной задаче. Вместе эти результаты усиливают главный вывод: некоторые квантовые сертификаты нельзя заменить инструкцией, программой или компактным описанием на бумаге. Для теории вычислений это важная граница между тем, что можно проверить обычным текстом, и тем, что требует самого квантового состояния.